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

一、应用题

1． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。

图1

【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：

图2 图3

2． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。

【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。

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

，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）

共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：

4． 已知图的邻接矩阵为：

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历序列； （2）以顶点V1为出发点的唯一的广度优先遍历序列； （3）该图唯一的拓扑有序序列。

1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8 （3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO

5． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由

变换为

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或

或JA V A 语言描述算法，关键之处给出注释。

原地逆置，

得到

（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n

个数据由然后再将数组R 中的前

，

（2）用C 语言算法描述如下：

要求：

个数和后P 个数分别原地逆置，

最终得到结果

（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别

为

为O

故算法的时间复杂度为

，算法的空间复杂度为0（1）。

6． 下面程序段的时间复杂度是什么？

【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。

7． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58; 第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序

建大堆：58，47，51，29，18，12，25，10; ①51，47，25，29，18，12，10，58; ②47，29，25，10，18，12，51，58; ③29，18，25，10，12，47，51，58; ④25，18，12，10，29，47，51，58;