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 页