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

一、算法设计题

1． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

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

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定，査找不成功指到空指针为止

-

2． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。

要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？

(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。

【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:

图中顶点的最大个数

弧(边) 结点

是邻接点在顶点向量中的下标，num 是边的编号

指向下一邻接点的指针

与弧(或边) 相关的信息指针

顶点结点

顶点信息及指向第一邻接点

的指针

邻接表

修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。

用邻接表作为存储结构的深度优先遍历算法

第一邻接点

结束dfs （ ）

求顶点的度

若顶点度为0, 或顶点的度不是偶

数，无解

无解

3． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如:

若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。

要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。

【答案】算法如下:

//本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败

//字符栈，容量足够大

//设链表带头结点

//前一半字符入栈，链表指针后移

//若链表有奇数个结点，则跳过中间结点

//不是回文

4． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下:

将满二叉树的后序序列转为前序序列，

标。

根结点

是序列初始和最后结点的下