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

一、应用题

1． （1）判定起泡排序的结束条件是什么？

（2）请简单叙述希尔排序的基本思想。

（3）将下列序列调整成堆（堆顶为最小值）。

（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。

【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。

（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将

，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）

组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。

（3）13，24，33，65，70，56，48，92，80，112

（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最大值，均与兄弟比较，共4次选出亚军）。

2． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的

是否总有a ≤b ≤c? 为什么？

【答案】该结论不成立。例如，本题中对于任一

f 的左子树上。对于从a 到根结点路径上的所有

均有a

3． 设

中。

（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；

（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。

【答案】（1）构造的哈希函数为：哈希函数第 2 页，共 19 页 ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a

：要求用哈希（Hash ）方法将它们存入具有10个位置的表（关键字各字符编码之和）

（2）关键字在表中的位置如表所示：

表 关键字在表中的位置

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 页，共 19 页 和子网可以聚合为子网在AS2

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

5． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :

假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？

（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？

【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为

（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示： 和各自所在的主存块对应的Cache 行号分别是多少（Cache 行

第 4 页，共 19 页