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

一、应用题

1． 三维数组

的存储首地址。

【答案】数组占的存储字节

数

2． 如果只要找出一个具有n 个元素的集合的第种最适合? 给出实现的思想。

【答案】在具有n 个元素的集合中找第

个最小元素，应使用快速排序方法。其基本

思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若

则在1至i-1间继续进行快速排序的划分；若

则在i+1至n 间继续进

个最小元

行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第素。

3． 已知图的邻接矩阵为：

的存储地

址

的每个元素的长度为4个字节，试问该数组要占多少个字节

的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素

个最小元素，你所学过的排序方法中哪

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历序列； （2）以顶点V1为出发点的唯一的广度优先遍历序列； （3）该图唯一的拓扑有序序列。

1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8 （3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO

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

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？

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

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

图

【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B, 按字节编址，并且页的大小为IK=210, 故逻辑地址和物理地址的地址格式均为：

地址17CA=0001011111001010B，故可知其逻辑页号为000101B=5。

（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH。

（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0, 则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9, 并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0, 故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1, 所以对应的物理地址为0000101111001010B=0BCAH。

5． 调用下列C 函数f （n ），回答下列问题：

（1）试指出f （n ）值的大小，并写出，f （n ）值的推导过程；

（2）假定n=5，试指出，f （5）值的大小和执行，f （5）时的输出结果。 C 函数：

【答案】（1）第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为（n ＋，第三层循环体受第一层循环和第二层循环的控制，其执行次数如（n －1）＋（n －2）＋... ＋1）表所示。

表 执行次数

执行次数为

（2）在n=5对，f （5）=55，执行过程中，输出结果为：

6． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。

【答案】各种排序算法稳定性的归纳如图所示：

图