当前位置：问答库＞考研试题

一、填空题

1． 设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

2． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；（动态）链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

3． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

4． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

5． 应用prim 算法求解连通网络的最小生成树问题。

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号，终顶点号，权值）

（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在〈limits •h>中

//图的顶点数，应由用户定义

//用二维数组作为邻接矩阵表示

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通，出错处理

//修改候选边集合

【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图

，是N

上最小生成树边的集合。算法从属于

为止。

E T 开始，重复执行下述操作：在所有u

属于

加入集合

同时将

并入

v

直到

的边（u ，v ）属于E

中找一条代价最小的边

6． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

7． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

8． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

9． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

块的伙伴地址分别为：_____ 和

其伙伴块的起始地址计算公

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为一个元素时，此时堆的元素个数最少，元素个数为

10．二进制地址为011011110000，大小为和

【答案】011011110100；011011100000

011011110000是块的起始地址，【解析】大小分别为式如下：

当大小为4时，起始地址

为当大小为16时，起始地址为

：

11．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，

【答案】比较；移动

12．在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

二、选择题

13．下列四个序列中，哪一个是堆（ ）？

A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15