当前位置:问答库>考研试题

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 页