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

一、算法设计题

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

【答案】算法如下:

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

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

//交换A[i]与

A[j]

//算法Arrange 结束

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

【答案】算法如下:

层次遍历二叉树，并统计度为1的结点的个数

统计度为1的结点的个数

是以二叉树结点指针为元素的队列

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

3． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

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

【答案】算法如下:

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

本算法的递归描述如下:

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

5． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

二、应用题

6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求P 1P 2......P j 为P 1P 2......P j 两头匹配的真子串？且为最大真子串？

【答案】失败函数(即next) 的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k(即next[j])个字符与第i 个相比，有

为了不因

模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j ﹣k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

7． 设目标为

(1)计算模式p 的nextval 函数值；

(2)不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】(1)P的nextval 函数值为0110132(P的next 函数值为0111232) 。 (2)利用KMP(改进的nextval) 算法，每趟匹配过程如下: 第一趟匹配:abcaabbabcabaacbacba abcab(i＝5，j ＝5)

，模式为