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

一、应用题

1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，

每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字

列。

（2）最低位优先

先对最低位关键字

位关键字

序列参加排序，

但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

2． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？

【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下的叶结点是其后继。

（2）对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则其前驱是其左子树上按中序遍历的最后一个结点。

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

【答案】n 个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j 趟起泡排序要进行次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排

第 2 页，共 40 页 序结束，下面语句段说明了标记flag 的使用。

4． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。

题图网络拓扑结构

（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。

（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？

R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）

进行传输？

【答案】

（1）在AS1中，子网中，子

网和子网单独连接到的接口可以聚合为子网但缺少子网

于是可以得到R2的路由表如下：

（2）该IP 分组的目的IP 地址194.17.20.200与路由表中194.17.20.0/23和194.17.20.128/25两个路由表项均匹配，根据最长匹配原则，R2将通过E0接口转发该1P 分组。

（3）R1与R2之间利用BGP4 （或BGP ）交换路由信息；BGP4的报文被封装到TCP 协议段中进行传输。2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解

5． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是

第 3 页，共 40 页 和子网可以聚合为子网在AS2

以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

6． 在树和树中查找关键字时，有什么不同？

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

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

第 4 页，共 40 页