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

一、应用题

1． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，

，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）

凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序

割成两部分：和和

且

将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：

初始序列：[28]，07，39，10，65，14，61，17，50，21

21移动：21，07，39，10，65，14，61，17，50，[]

39移动：21，07，[]，10，65，14，61，17，50，39

17移动：21，07，17，10，65，14，61，[]，50，39

65移动：21，07，17，10，[]，14，61，65，50，39

14移动：21，07，17，10，14，[28]，61，65，50，39

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

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

【答案】（1）队空：

（2）队满：

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

3． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。

（1）画出可利用空间表的初始状态。

（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

（3）画出在回收3个占用块之后可利用空间表的状态。

【答案】（1）因为可利用空间表的初始状态图如图1所示：

图1 可利用空间表的初始状态

（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，

故将

的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个

大小为

的块。又将其中大小为的一块挂到可利用空间表上，

另一块再分裂成两个大小为的

块。其中一块的块挂到可利用空间表上，

另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。

图2 每个用户得到的存储空间的起始地址

]

图3 可利用空间表的状态

（3）在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192，也在占用。回收大小为11的占用块时，其伙伴地址是48，可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示：

图4

4． 画出对算术表达式

表所示。

表 操作数栈和运算符找的变化过程 求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式