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

一、应用题

1． 某计算机的主存地址空间大小为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 行

图

数组按行优先方式存放，首地址为320, 数组元素占4个字节。

Cache 行号

为

（3）数组a 的大小为逐行访问数

组a ，共需访问的次数为

A 的数据访问命中率为次，每个字块的第一个数未面中，因此未面中次数为Cache 总容量为次，程序数组a —行的大占用个主存块，按行优先存放，程序A 所在的主存块对应的所在的主存块对应的Cache 行号

为小为1KB 正好是Cache 容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache 单元，而程序B 逐列访问数组a 的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B 的数据访问命中率是0, 因此程序A 的执行过程更短。

2． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？

【答案】不一定相邻。哈希地址为的关键字，和为解决冲突形成的探测序列f 的同义词，都争夺哈希地址i 。

3． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，

，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）

凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序

割成两部分：和和

且

将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：

初始序列：[28]，07，39，10，65，14，61，17，50，21

21移动：21，07，39，10，65，14，61，17，50，[]

39移动：21，07，[]，10，65，14，61，17，50，39

17移动：21，07，17，10，65，14，61，[]，50，39

65移动：21，07，17，10，[]，14，61，65，50，39

14移动：21，07，17，10，14，[28]，61，65，50，39

4． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？

【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元

，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）

元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小且分布没有规律。用十字链表作存储结构自然失去了随机

最差情况下是因此也失去存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。

5． （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次选出亚军）。

6． 快速排序的最大递归深度是多少? 最小递归深度是多少？

【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为

最大递归深度n 。