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

一、算法设计题

1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

2． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

第 2 页，共 32 页

) 小元素。

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

4． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

5． 线性表中元素存放在向量A(1，... ，，1) 中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。

【答案】算法如下:

//一维数组A 中存放有n 个整型数，本算法递归的求出其中的最小数和最大数

//算法结束

第 3 页，共 32 页

和B 的

【答案】算法如下:

二、应用题

6． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

7．

设与记录

对应的关键字分别是。如果存在

和

成立，试证明经过一趟起泡后，一定有记录与进行交换。

【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在

，又因

之前且

，则

，故

，即说明和

是反序；设对于

和

之前全部记录:

(其

中包括) 中关键字最大为

，故经过起泡排序前i-2次比较后，

必定交换。

的关键字一定为

使得j

且

和Rf 为反序，由此可知

8． 在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPACE[N﹣1]分别是两个栈的栈底。

(1)对栈1、栈2，试分别写出(元素X) 入栈的主要语句和出栈的主要语句。 (2)对栈1、栈2，试分别写出栈满、栈空的条件。 【答案】(1)入栈主要语句

//设X 为入栈元素

.

出栈主要语句

//返回出栈元素

//返回出栈元素

(2)

栈满条件:top2﹣topl ＝l

栈空条件:topl ＝﹣l 并且top2＝N //topl＝﹣l 为左栈空，top2＝N 为右栈空

9． 证明任一结点个数为n 的二叉树的高度至少为0(

) 。

。解此不等式，并考虑

。

【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低髙度是h ，则n 应满足h 是整数，则有

，即任一结点个数为n 的二叉树的高度至少为

第 4 页，共 32 页