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

一、综合题

1． 解答问题。设有数据逻辑结构为:

(1)画出这个逻辑结构的图示。

(2)相对于关系R ，指出所有的开始结点和终端结点。

(3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。

(4)分别画出该逻辑结构的正向邻接表和逆向邻接表。

【答案】(1)如图1所示:

图1

(2)开始结点(入度为0) :

(3)拓扑序列:

规则:开始结点为K 1或K 2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。

(4)正向邻接表如图2所示，逆向邻接表如图3所示:

; 终端结点(出度为0) :

。

图2正向邻接表

图3逆邻接表

2． 假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如图所示(注:存储块头部size 域的值和申请分配的存储量均包括头部和尾部的存储空间)) 请画出:

(1)当系统回收一个起始地址为559大小为45的空闲块之后的链表状态；

(2)系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态

【答案】(1)系统回收一个起始地址为559，大小为45的空闲块后，因右恻起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示:

图1

(2)系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示:

图2

3． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时, 若有空座位, 则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下:

请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 实现上述过程中的互斥与同步。要求写出完整的过程, 说明信号量的含义并赋初值。

【答案】(1)互斥资源:取机号, 故设一个互斥信号量mutex 。

(2)同步问题:顾客需要获得空座位等待叫号, 当营业员空闲时, 将选取一位顾客为其服务。空座位的有、无影响等待顾客数量, 顾客的有、无决定两营业员是否能开始服务。另外, 顾客获得空座位后, 需要等待叫号和被服务, 顾客与营业员就服务何时开始有同步关系。设信号量teller , customer 和mutex 初值分别为0, 0和1, 设waiting 为整型量, 表示排队的储户数量, 其初始为0, 表示顾客初始时为0, 最大不超过10(10把座椅) , 各进程的具体实现如下所示:

座椅数, 也是最多排队的储户数

定义信号量

等待储户的柜员资源

排队等待服务的储户数量

对排队机操作的互斥量

在座椅上休息等待的储户数