2017年中国民航大学航空自动化学院833算法与数据结构考研冲刺密押题
● 摘要
一、填空题
1． 在一棵m
阶的个数是_____。
【答案】
【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是最少
2． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
4． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
5． 应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
第 2 页，共 57 页
树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的
关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
〔始顶点号，终顶点号，权值）
（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在〈limits •h>中
//图的顶点数，应由用户定义
//用二维数组作为邻接矩阵表示
//生成树的边结点
//边的起点与终点
//边上的权值
//最小生成树定义
//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点
//初始化最小生成树
T
//依次求MST 的候选边
//遍历当前候选边集合
//选具有最小权值的候选边
//图不连通，出错处理
//修改候选边集合
【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图
，是N
上最小生成树边的集合。算法从属于
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
第 3 页，共 57 页
为止。
6． 设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15
【解析】当时，而
，时，
7． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。 8． 假定查找有序表中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
9． 设广义表
则
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
要使前者快于后者，n 至少为
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
10．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
第 4 页，共 57 页