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

一、算法设计题

1． 假设串的存储结构如下所示，编写算法实现串的置换操作。

【答案】算法如下:

//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败

//检査参数及置换后的长度的合法性

//若S 串被替换的子串长度小于t 串长度，则S 串部分右移

//S串中被替换子串的长度小于t 串的长度

//将t 串复制到S 串的适当位置

//算法结束

//本算法是串的置换操作，将串S 中所有非空串t 相等且不重叠的子串用V 代替

//判断S 是否有和t 相等的子串

//串S 中包含和t 相等的子串

//creat操作是将串常量(此处为空串) 赋值给

temp

//求串t 和s 的长度

//用串v 替换t 形成部

分结果

//将串s 中串后的部分形成新的s 串

//求串s 的长度

//在新s 串中再找串t 的位置

//将串temp 和剩余的串s 连接后再赋值给s

}//if结束

//算法结束

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

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

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

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

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

哈希地址

1~26

设哈希表初始值为

null

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

(2)算法如下:

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

记査找不成功的总的次数

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

3． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。

【答案】算法如下:

//本算法将无符号十进制整数m 转换为十六进制整数

-

本算法的递归描述如下:

//本算法将无符号十进制整数m 转换为十六进制整数

4． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

5． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【答案】算法如下: