2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题
● 摘要
目录
2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题（一） ... 2 2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题（二） . 14 2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题（三） . 28 2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题（四） . 39 2018年辽宁石油化工大学计算机与通信工程学院951数据结构考研强化五套模拟题（五） . 47
第 1 页，共 57 页
一、填空题
1． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
2． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
3． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；(动态) 链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
4． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
第 2 页，共 57 页
中
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
的边为止。
5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
第 3 页，共 57 页
是连通图
，
，v ，
直到
，开始，重复执行下述操作:在所有u 属于
加入集合
，同时将并入
属于E 中找一条代价最小的边
，
left 指向其前驱；，
right 指向其右孩子，，
，
right 指向其后继。
【答案】
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
7． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
a 中存放待排序的关键字
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
8． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
第 4 页，共 57 页
相关内容
相关标签