考研408計算機統考分兩部分，80分單項選擇題和70分大題，滿分150分。單項選擇題總共80分，每小題2分，40小題。單項選擇題，1-10題是數據結構部分；11-22題是計算機組成原理部分；23-32題是操作系統部分；33-40題是計算機網絡部分。綜合應用題70分，共7小題，41和42題是數據結構題，分值各為10分和15分；43和44題是計算機組成原理題，各占8分和13分；45和46題是操作系統題，各占7分和8分；47題是計算機網絡題，分值為9分。為了方便大家更好的來備考，小編為大家整理了“2022年408計算機考研真題”，希望可以幫助大家更好的復習408計算機考研內容。

2022年考研408計算機統考考研真題

二、綜合應用題（第41~47小題，共70分）

41、（13分）已知非空二叉樹T的結點值均為正整數，采用順序存儲方式保存，數據結構定義如下： typedef struct{//MAX_SIZE為已定義常量

int SqBiTNode[MAX_SIZE];//保存二叉樹節點值的數值

int ElemNum;//實際占用的數組元素個數

}SqBiTree;

T中不存在的結點在數組SqBiNode中用-1表示。例如，對于下圖所示的兩棵非空二叉樹T1和T2，

T1的存儲結果如下：

T1.SqBiTNode

T1.ElemNum=10

T2的存儲結果如下：

T2.SqBiTNode

T2.ElemNum=11

請設計一個盡可能高效的算法，判定一棵采用這種方式存儲的二叉樹是否為二叉搜索樹，若是，則返回true，否則，返回false。要求：

（1）給出算法的基本設計思想。

（2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

42、（10分）現有n(n>100000)個數保存在一維數組M中，需要在找M中最小的10個數。請回答下列問題。

（1）設計一個完成上述查找任務的算法，要求平均情況下的比較次數盡可能少，簡述其算法思想（不要程序實現）。

（2）說明你所設計的算法平均情況下的時間復雜度和空間復雜度。