2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题
● 摘要
目录
2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题（一）.... 2 2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题（二）.... 9 2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题（三）.. 16 2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题（四）.. 23 2017年军事医学科学院军事兽医研究所836计算机应用之数据结构考研冲刺密押题（五）.. 29
第 1 页，共 35 页
一、填空题
1． 实现字符串拷贝的函数strcpy 为：
【答案】
2． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
第 2 页，共 35 页
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部
分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
3． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9
4．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
5． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
6． 应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
〔始顶点号，终顶点号，权值）
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
第 3 页，共 35 页
（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
上最小生成树边的集合。算法从属于
为止。
7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，
将
第 4 页，共 35 页
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
在B
代入得93。