2022年計(jì)算機(jī)考研408真題（41-42）

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

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

二、綜合應(yīng)用題（第41~47小題，共70分）

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

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

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

}SqBiTree;

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

T1的存儲(chǔ)結(jié)果如下：

T1.SqBiTNode

T1.ElemNum=10

T2的存儲(chǔ)結(jié)果如下：

T2.SqBiTNode

T2.ElemNum=11

請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，判定一棵采用這種方式存儲(chǔ)的二叉樹是否為二叉搜索樹，若是，則返回true，否則，返回false。要求：

（1）給出算法的基本設(shè)計(jì)思想。

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

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

（1）設(shè)計(jì)一個(gè)完成上述查找任務(wù)的算法，要求平均情況下的比較次數(shù)盡可能少，簡(jiǎn)述其算法思想（不要程序?qū)崿F(xiàn)）。

（2）說明你所設(shè)計(jì)的算法平均情況下的時(shí)間復(fù)雜度和空間復(fù)雜度。