2022年計算機考研408真題（41-42）

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

2022年考研408計算機統(tǒng)考考研真題

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

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

int SqBiTNode[MAX_SIZE];//保存二叉樹節(jié)點值的數(shù)值

int ElemNum;//實際占用的數(shù)組元素個數(shù)

}SqBiTree;

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

T1的存儲結果如下：

T1.SqBiTNode

T1.ElemNum=10

T2的存儲結果如下：

T2.SqBiTNode

T2.ElemNum=11

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

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

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

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

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

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