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

一、算法设计题

1． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

2． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)

【答案】算法如下:

待排序记录的个数

关键字由d 个分量组成

静态链域

记录的其他数据域

存放n 个记录

.

用队列表示桶，共m 个

进行基数排序，返回收集用的链头指针

将

进行d 趟排序

初始化桶

第 2 页，共 37 页

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

队列的头、尾指针

对

链成一个静态链表

将初始链表的终端结点指针置空，P 指向链表的第一个结点

按关键字的第j 个分量进行分配

k 为桶的序号

将将

链到桶头

链到桶尾

修改桶的尾指针

扫描下一个记录

找第一个非空的桶

为收集链表的头指针，t 为尾指针

连接非空桶

本趟收集完毕，将链表的终端结点指针置空

3． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在

中时，试写一个算法，求

出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是

，值是

设元素类型为

整型

4． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

第 3 页，共 37 页

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束

:

5． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

二、应用题

6． 假定某计算机的CPU 主频为80MHz , CPI 为4, 并且平均每条指令访存之间交换的块大小为168, Cache 的命中率为

次, 主存与Cache

, 存储器总线宽度为32位。请回答下列问题。

(1)该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下, 主存带宽至少达到多少才能满足CPU 的访存要求？

(2)假定在Cache 缺失的情况下访问主存时, 存在式, 磁盘少是多少？

(3)CPU和DMA 控制器同时要求使用存储器总线时, 哪个优先级更高? 为什么？

(4)为了提高性能, 主存采用4体交叉存储模式, 工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns , 则该主存能提供的最大带宽是多少？

【答案】(1)平均每秒CPU 执行的指令数为:平均每秒Cache 缺失的次数为:为

:

。

在不考虑DMA 传输的情况下, 主存带宽至少达到(2)平均每秒钟“缺页”异常次数为:

第 4 页，共 37 页

的缺页率, 则CPU 平均每秒产生多少接口平均每秒发出的DMA 请求次数至

次缺页异常? 若页面大小为4KB , 每次缺页都需要访问磁盘, 访问磁盘时DMA 传送采用周期挪用方

接口的数据缓冲寄存器为32位, 则磁盘

, 故MIPS 数为20;

当Cache 缺失时, CPU 访问主存, 主存与Cache 之间以块为单位传送数据, 此时, 主存带宽

才能满足CPU 的访存要求。 次;