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

一、综合题

1． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素A[i][j]在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？

【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为0(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置(下标) 放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序(或折半) 查找该元素，这时时间复杂度为0(logn)。

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

表

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

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

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

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

图

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

地址17CA ＝0001 0111 1100 1010B，故可知其逻辑页号为000101B ＝5.

(2)根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001 1111 1100 1010B＝1FCAH.

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

3． (1)对于有向无环图，叙述求拓扑有序序列的步骤；

(2)对于图1, 写出它的四个不同的拓扑有序序列。

图1

【答案】(1)对有向图，求拓扑序列步骤为:

1) 在有向图中选一个没有前驱(即入度为0) 的顶点并输出。

2) 在图中删除该顶点及所有以它为尾的弧。

3) 重复1) 和2) , 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

(2)拓扑有序序列如图2

图2拓扑有序序列

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

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

图各种排序算法稳定性归纳

5． 简述广义表属于线性结构的理由。

【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。