2018年西安理工大学计算机科学与工程学院863数据结构考研核心题库
● 摘要
一、填空题
1． 在基于关键字比较且时间为
【答案】归并；堆
2． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
_ 的排序中，若要求排序是稳定的，则可选用_____
排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
第 2 页，共 45 页
，
left 指向其前驱；，
right 指向其右孩子，，
，
right 指向其后继。
【答案】
4． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4；2
5． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
6． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
第 3 页，共 45 页
中
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
的边为止。
，
属于E 中找一条代价最小的边
加入集合
是连通图
，
，v ，
直到
开始，重复执行下述操作:在所有u 属于
，同时将并入
二、单项选择题
7． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 【答案】A
8． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储
D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
9． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.
A. 连续结构 B. 索引结构
C. 链式结构且磁盘块定长
第 4 页，共 45 页