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

一、算法设计题

1． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

2． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。

【答案】算法如下:

//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面

//设链表有头结点

//q指向待处理结点

//P记数据域值最大的结点

第 2 页，共 37 页

//将P 摘下

//插人P 结点

3． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是

i

判断U 是否是V 的后代

4． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

第 3 页，共 37 页

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代

5． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

二、应用题

6． 某计算机主存按字节编址, 逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。

(1)若使用一级页表的分存储管理方式, 逻辑地址结构为:

则页的大小是多少字节？页表最大占用多少字节？ (2)若使用二级页表的分存储管理方式, 逻辑地址结构为:

设逻辑地址为LA , 请分别给出其对应的页目录号和表索引达式。

(3)采用(1)中的分页存储管理方式, 一个代码段起始逻辑地址为00008000H , 其长度为8KB , 被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存

开始的

物理地址处连续存放, 如下图所示(地址大小自下向上递增) 。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。

【答案】(1)因为页内偏移量是12位所以页大小为4KB 页表项数为该一级页表最大为(2)页目录号可表示为:页表索引可表示为:

第 4 页，共 37 页

。

。 。