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

一、填空题

1． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

2． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；;

while （*x==node ）; *x=t; } }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

4． 试利用下列栈和串的基本操作完成下述填空题。

initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作；

gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；

置串 判串 返回联接

empty （st ） 判串空函数

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）

注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）

取栈顶操作符

为空串；

是否相等的函数；

之后的串；

length （st ） 返回串st 的长度；

sub （S , i , 1） 返回S 中第i 个字符；

栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符

如ch 是运算符，则入操作符栈s 判栈8是否为空

若读出ch 是操作数且栈为空，则按出错处理

若ch 是操作数且栈非空，则形成部分中缀表达式

（11

）（12）

操作符取出后，出栈

将pre 的最后一个字符（操作数）加入到中缀式exp 的最后

5． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

6． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。

【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为

7． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

的次数最小。总次数为

8．

求REPLACE （S ，V , m ）=_____。

【答案】

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

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

10．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

已

知

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测