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

一、应用题

1． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。

【答案】各种排序算法稳定性的归纳如图所示：

图

2． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。

3． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。

【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

4． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥

，下表给定了这六 大城市之间的交通里程：

（M ）

（1）画出这六大城市的交通网络图；

（2）画出该图的邻接表表示法；

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。

【答案】（1）这六大城市的交通网络图如图1所示：

图1

（2）该图的邻接表表示法如图2所示：

图2

（3）最小生成树有6个顶点与条边：V （G ）={Pe，N ，Pa ，L , T，M}

E （G ）=（ {（L , Pa, 3）, （Pe , T, 21）, （M , N, 32）, （L , N, 55）, （L , Pe, 81）}

5． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

6． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。

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;

⑤18，10，12，25，29， 47，51，58;

⑥12，10，18，25，29，47，51，58;

⑦10，12，18，25，29， 47，51，58

8． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。

（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？

（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？

【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记

请