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

一、算法设计题

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

【答案】算法如下：

和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作

成功返回1, 否则返回0表示失败

2． 设表达式以字符形式已存入数组E 中，

【答案】算法如下：

为表达式的结束符，试写出判断表达式中括号

是否配对的C 语言描述算法：EXYX （E ）（注：算法中可调用栈操作的基本算法）。

3． 从键盘上输入一串正整数，最后输入-1作为结束标志。如：

请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为那么

序遍历次序的前驱结点的地址。

那么

【答案】算法如下：

其中：

域为结点的数据场。

域中存在的是该结点的左儿子结点的地址。ltag=1，那么left 域中存放的是该结点的按中

那么right 域中存放的是该结点的右儿子结点的地址。

域中存放的是该结点的按中序遍历次序的后继结点地址。

4． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

【答案】算法如下：

期望值分析：在等概率情况下，则查找成功的平均查找长度为长度为

查找失败的平均查找

（失败位置除小于每一个，还存在大于最后一个）。若查找成功和不成功的概率

也相等，则查找成功时和关键字比较的个数的期望值约为

5． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下：

int Level（BiTree bt） //层次遍历二叉树，并统计度为1的结点的个数 {int num=C; //num统计度为1的结点的个数

if （bt ）{Queuelnit（Q ）; Queueln（Q , bt ）; //Q是以二叉树结点指针为元素德 队列 while （!QueueEmpty （Q ））

{p=Queueout（Q ）; printf （p->data）; //出队访问结点

//非空右子女入队

//返回度为1的结点的个数

6． 令G=（V , E）为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下 条件：若从顶点i 至顶点j 有一条弧，则应使i

【答案】算法如下：

//对以邻接表存储的DAG 图g 重新编号, 使若有

i< j