考研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的存储结果如下：
| 40 | 25 | 60 | -1 | 30 | -1 | 80 | -1 | -1 | 27 |
T1.SqBiTNode
T1.ElemNum=10
T2的存储结果如下：
| 40 | 50 | 60 | -1 | 30 | -1 | -1 | -1 | -1 | -1 | 35 |
T2.SqBiTNode
T2.ElemNum=11
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
42、（10分）现有n(n>100000)个数保存在一维数组M中，需要在找M中最小的10个数。请回答下列问题。
（1）设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思想（不要程序实现）。
（2）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
相关推荐：
| 课程名称 | 课程价格 | 课程链接 |
2026写作备考攻略 | 免费 | 点击试听 |
| 2010-2025数学16套真题讲解 | 免费 | 点击试听 |
| 考研【公共课】自学视频教程 | 98元 | 点击试听 |
| 408计算机】考研自学视频教程（真题+习题+考点） | 98元 | 点击查看 |
| 管理类联考数学基本功视频教程 | 398元 | 点击查看 |
扫码直达>>>考研课程咨询
| ||
