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

一、综合题

1． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。

【答案】n 个元素采用起泡排序法进行排序，通常需要进行n －1趟排序。第j 趟起泡排序要进行n －j 次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag 的使用。

用作控制标记

是起泡排序趟数，最多n －1趟

设标记，若本趟不发生交换，本趟起泡排序后，算法结束

发生了交换，还要进行下

趟

2． 只要找出一个具有n 个元素的集合的第

最适合? 给出实现的思想。

【答案】在具有n 个元素的集合中找第个最小元素，应使用快速排序方法。其基本思想如下:设n 元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若说，则在1至i －1间继续进行快速排序的划分；若i

小元素。

3． 在堆排序、快速排序和合并排序中:

(1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

【答案】(1)应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。

第 2 页，共 35 页 个最小元素，你所学过的排序方法中哪种个最

(2)应选取归并排序方法

(3)应选取快速排序方法

(4)应选取堆排序方法

4． 用一个数组S(设大小为MAX) 作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push(i，x) ，其中i 为0或1，用于表示栈号，x 为入栈值。

【答案】两栈共享一向量空间(一维数组) ，栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为﹣1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push(i，x) 如下:

＝共享栈可能达到的最大容量

//ds为容量有MAX 个类型为elemtype 的元素的一维数组，由两个栈共享其空间。I 的值为0或1

//x为类型为elemtype 的元素。本算法将x 压入栈中。如压栈成功，返回1; 否则，返回

//人栈成功

5． 假定采用带头结点的单链表保存单词, 当两个单词有相同的后缀时, 则可共享相同的后缀存储空间。例如, “loading ”和“being ”的存储映像如下图所示。

图 存储映像本意图

设str1和str2分别指向两个单词所在单链表的头结点, 链表结点结构为

所在结点的位置p) 。要求:

(1)给出算法的基本设计思想。

第 3 页，共 35 页 , 请设计一个时间上尽可能高效的算法, 找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i

(2)根据设计思想, 采用C 或或JA V A 语言描述算法, 关键之处给出注释。

(3)说明你所设计算法的时间复杂度。

【答案】(1)算法的基本设计思想:

①分别求出str1和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐:令指针p 、q 分别指向str1和str2的头结点, 若m>n, 则使p 指向链表中的第n+1个结点; 若m

③反复将指针p 和q 同步向后移动, 并判断它们是否指向同一结点。若p 和q 指向同一结点, 则该点即为所求的共同后缀的起始位置。

(2)用C 语言算法描述如下:

n 分别为两个链表的长度。 。其中m 、(3)参考答案的时间复杂度为:

6． 解答问题。设有数据逻辑结构为:

(1)画出这个逻辑结构的图示。 或

(2)相对于关系R ，指出所有的开始结点和终端结点。

(3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。

(4)分别画出该逻辑结构的正向邻接表和逆向邻接表。

【答案】(1)如图1所示:

图1

(2)开始结点(入度为0) :; 终端结点(出度为0) :

第 4 页，共 35 页 。