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

一、算法设计题

1． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

2． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

【答案】算法如下:

全局变量链表头指针

将

若bt 不空

中序遍历左子树

叶结点

第一个叶结点

生成头结点

头结点的左链空，右链指向第一个结点

第一个叶结点左链指向头结点，pre 指向当前叶结点

中序遍历右子树

最后一个叶结点的右链置空(链表结束标记)

第 2 页，共 36 页

树中的所有叶结点链成带头结点的双链表

当前叶结点链入双链表

结束；

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

【答案】算法如下:

4． 设要求按

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

5． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。

【答案】算法如下:

第 3 页，共 36 页

建立有向图的十字链表存储结构

假定权值为整型

建立顶点向量

当输入i 、j 、v 之一为0时，结

束算法运行

申请结点

弧结点中权值域

算法结束

二、应用题

6． 一个循环队列的数据结构描述如下:

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】(1)队空:

//设s 是sequeuetp 类型变量

(2)队满:

//数组下标为

这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front ＝rear 为队空；tag ＝l 情况下，若因插入导致front ＝rear 则为队满。

7． 某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描, 每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计) , 本轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次被分配之前不被清空。当发生缺页时, 如果该页曾被使用过且还在空闲页框链表中, 则重新放回进程的驻留集中; 否则, 从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销, 初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P 依次访问的<虚拟页号, 访问时刻>是:

。

第 4 页，共 36 页