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

一、算法设计题

1． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

2． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。

(2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

3． 当一棵有n() 个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

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

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

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

所査结点的最近公共祖先的下标是，值是设元素类型为 整型

4． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

5． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下:

非递归删除以r 为根的二叉排序树

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

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

二、应用题

6． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

7． 设某计算机的逻辑地址空间和物理地址空间均为64KB ，按字节编址. 若某进程最多需要6页(Page)数据存储空间，页的大小为1KB ，操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame).在时刻260前的该进程访问情况如下表所示(访问位即使用位).

表

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题:

(1)该逻辑地址对应的页号是多少？

(2)若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程.

(3)若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程.(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）