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

一、算法设计题

1． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。

【答案】算法如下:

//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称

//i记下结点个数，s 是字符栈

//P是链表的工作指针，指向待处理的当前元素

//链表前一半元素入栈

//恢复最后的i 值

//若n 是奇数，后移过中心结点

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

2． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束

:

3． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

4． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

5． 设记录的关键字为。，树结点

的败者树，要求除

指向败者记录，

和1

为全胜以外，只

记录下标。写一算法产生对应上述用O(1)辅助空间。

【答案】算法如下:

选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树

是

指示新的胜者

到:_

小数

设置T 中" 败者" 的初值

依次从

出发调整败者

为完全二叉树T 的叶结点，本算法建立败者树

是与题中要求的关键字类型相同的机器最

的双亲结点

二、应用题

6． 将关键字序列(7，8，30，11，18，9，14) 散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组. 散列函数是:H(key)＝(key×3)M0D7，处理冲突采用线性探测再散列法，要求装填(载）因子为

.

(1)请画出所构造的散列表.

(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度. 【答案】(1)

要求装填因子为列函数值如下表:

采用线性探测法再散列法处理冲突，所构造的散列表为:

(2)查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示:

，数组的长度应该为

数组下标为0〜9. 各关键字的散