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

一、应用题

1． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素

在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？

【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，

时间复杂度为若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中

顺序（或折半）查找该元素，这时时间复杂度为

2． 假设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中，子网和子网第 2 页，共 34 页 可以聚合为子网在AS2

中，子

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

于是可以得到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年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解

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

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

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

列。

（2）最低位优先

先对最低位关键字

位关键字

序列参加排序，

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

4． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：

（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。

（2）当n=7时，给出一个最好情况的初始排序的实例。

（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。

（4）当n=7时，给出一个最坏情况的初始排序的实例。

【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为

以此类推，

总共进行

需2次，共10次即可。

（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。

第 3 页，共 34 页 的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各

（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

n=7时，最坏情况下的比较次数为21次。

（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。

5． 三维数组

的存储首地址。

【答案】数组占的存储字节

数

6． 设LS 是一个线性表，的存储地

址的每个元素的长度为4个字节，试问该数组要占多少个字节所以当的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素若采用顺序存储结构，则在等概率的前提下，插

与

之间的概率

为入一个元素需要平均移动的元素个数是多少? 若元素插

在

【答案】需要分两种情况讨论：

，插入位置0..n ，则平均移动个数为（1）等概率（后插）

（2）若不等概率，则平均移动的元素个数为

则插入一个元素需要平均移动的元素个数又是多少？

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

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

第 4 页，共 34 页