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

一、算法设计题

1． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

2． 假设K1，... ，Kn 是n 个关键词，试解答：

(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。

(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。

图

该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下:

在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针

f

以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树

不再插入相同值结点

.

申请结点空间

根结点

左子女

右子女

结束算法 (2)算法如下:

以嵌套括号表示结构打印二叉排序树

打印根结点值

左子女和右子女中至少有一个不空

输出左栝号

输出左子树的嵌套括号表示

若右子树不空，输出逗号

输出右子树的嵌套括号表示

输出右括号

3． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下:

关键字

链指针

用链地址法解决冲突，构造哈希表，哈希函数用

初始化

输入n(本例中n=9)

个关键字按题意x 互不相同

4等插入结点链入同义词表

构造的哈希表如图所示:

图构造的哈希表

查找成功时的平均查找长度

。