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

一、算法设计题

1． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

【答案】(1)递归算法如下:

递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值

(2)非递归算法如下:

递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值

S 是二叉排序树结点指针的栈，容量足够大

沿右分支向下

去左分支

算法结束

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

【答案】算法如下:

关键字

链指针

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

初始化

输入n(本例中n=9)

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

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

构造的哈希表如图所示:

图构造的哈希表

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

。

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

【答案】算法如下:

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

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

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

4． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

中序遍历左子树

5． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P的袓先结点

)

若后继是头结点，则转到根结点

根结点无双亲

准备到左子树中找

P