2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题
● 摘要
目录
2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题（一） ... 2 2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题（二） . 10 2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题（三） . 17 2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题（四） . 24 2018年云南大学软件学院842数据结构与程序设计之数据结构考研强化五套模拟题（五） . 31
一、填空题
1． 假定查找有序表
【答案】
表
平均查找次数为。
2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2
而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
3． 空格串是指_____，其长度等于_____。
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【解析】折半查找时每个的次数如表所示:
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
4． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
5． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
中
是连通图
，
，v ，
直到
，开始，重复执行下述操作:在所有u 属于
加入集合
，同时将并入
的边为止。
属于E 中找一条代价最小的边
6． 建立索引文件的目的是_____。
【答案】提高查找速度
二、判断题
7． 从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】 √
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
8． 设模式串的长度为m ，目标串的长度为n ，当n ≈m 且处理只匹配一次的模式时，朴素的匹配(即子串定位函数) 算法所花的时间代价可能会更为节省。（ ）
【答案】 √
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
9． 树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
10．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
11．静态链表就是一直不发生变化的链表。（ ）
【答案】 ×
【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。
12．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。
三、单项选择题
相关内容
相关标签