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

一、算法设计题

1． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

2． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

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

【答案】算法如下:

//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结束

//算法结束

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

【答案】算法如下:

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

标。

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

根结点

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

5． 试编写一算法对二叉树按前序线索化。

【答案】算法如下:

设置前驱

对以线索链表为存储结构的二叉树BT 进行前序线索化

设置左线索

设置前驱的右线索

为建立右链做准备

前驱后移

左子树前序线索化

右子树前序线索化

结束

二、应用题

6． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。

【答案】删除P 后

删除D 后