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

一、算法设计题

1． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

为栈，容量足够大

分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

初始化

取出栈顶数据

在中序序列中査等于

.

根结点的值

无左子树

将建立左子树的数据入栈

无右子树

的结点

右子树数据入

结束

:

b 中连续的相等元素构成的子序列称为平台。试设计算法，

2． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

3． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。

【答案】算法如下:

//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称

//i记下结点个数，s 是字符栈

//P是链表的工作指针，指向待处理的当前元素

//链表前一半元素入栈

//恢复最后的i 值

//若n 是奇数，后移过中心结点

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

4． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

在b 数组中起始下标为”，1，

k)

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

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

【答案】算法如下:

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

点

结束

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

n0

. 叶结点

输出并计数

结束

:

二、应用题

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 执行的指令数为:

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

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

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

, 故MIPS 数为20;