2017年大连海洋大学634数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为
外部归
并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
（2）因为归并的趟数
其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都
可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。
2． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。
【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。
3． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
4． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
5． 假定某计算机的CPU 主频为80MHz , CPI为4, 并且平均每条指令访存1.5次，主存与Cache 之间交换的块大小为168, Cache的命中率为
存储器总线宽度为32位。请回答下列问题。
（1）该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU 的访存要求？
（2）假定在Cache 缺失的情况下访问主存时，存在期挪用方式，磁盘
接口的数据缓冲寄存器为32位，则磁盘
的缺页率，则CPU 平均每秒产
接口平均每秒发出的DMA
生多少次缺页异常? 若页面大小为4KB ，每次缺页都需要访问磁盘，访问磁盘时DMA 传送采用周请求次数至少是多少？
（3）CPU 和DMA 控制器同时要求使用存储器总线时，哪个优先级更高? 为什么？
（4）为了提高性能，主存采用4体交叉存储模式，工作时每每个体的存储周期为50ns ，则该主存能提供的最大带宽是多少？
【答案】
（1）平均每秒CPU 执行的指令数为：平均每秒Cache 缺失的次数为：为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：故平均每秒磁盘DMA 请求的次数至少为：请求得不到及时响应，
传输数据可能会丢失。
个存储周期启动一个体。若
故MIPS 数为20; =300000;
才能满
当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽
在不考虑DMA 传输的情况下，主存带宽至少达到
因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，
CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）
（4）4体交叉存储模式能提供的最大带宽为：
6． 有A 、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方B 的信箱最多放N 提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件，个邮件。初始时 A 的信箱中有x 个邮件邮件数减1. 。
A 、B 两人操作过程：
从A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱；
当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。
B 中有y 个辩论者每取出一个邮件，
请添加必要的信号量和P 、V （或wait signed ）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。
【答案】首先定义两个互斥信号量：mutexA 和mutexB , 初始时为1，分别用来实现对A 的邮箱和B 的邮箱的互斥使用；然后针对A 的邮箱再定义两个信号量emptyA 和fullA ，
初值分别为
和X ，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB 和fullB , 初值为
和y 。
通信代码：
从A 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入A 的信箱；
初始代码：
相关内容
相关标签