2022年计算机考研408真题（41-42）

考研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）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。