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

一、算法设计题

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． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。

【答案】算法如下:

//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前

//用类C 语言编写，数组下标从0开始

//交换A[i]与

A[j]

//算法Arrange 结束

3． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:

它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。

【答案】算法如下:

//输出由Hm 指向的十字链表中每一行的非零元素个数

//数组A 记各行非零元个数，i 记行号

//循环完各行列表头

//P是稀疏矩阵行内工作指针，num 记该行非零个

数

//完成行内非零元的查找

//指针后移

//存该行非零元个数

//移到下一行列表头

//输出各行非零元个数

第

}算法结束

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

【答案】算法如下:

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

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

行非零元个数为

}

//稀疏矩阵非零元个数

结束本题

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

【答案】算法如下:

在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为

长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相

。