复旦大学1995年数据结构与操作系统考研试题
复旦大学1995年数据结构与操作系统考研试题
在下面一至三题中程序的空框填入适当的语句或表达式，每空限填一句，每空3分。
一、 下面的程序完成按递增次序打印给定的线性链表head中各结点的操作。打印的方法是每次寻找链表中值最小的结点，打印该结点后，把它从链表中删除，重复此操作直到链表结束为止(12分)
TYPE nodeptr = ^nodetype
Nodetype = RECORD
Data : char
Link : nodeptr
END
VAR n : integer
Head : nodeptr
PROCEDURE print_link (head : nodeptr)
VAR p , q , r , s : nodeptr
BEGIN
WHILE head <> NIL DO
BEGIN
p := head ;
q := head ;
r := head ;
s := r^.link ;
WHILE s <> NIL DO
BEGIN
IF s^.data < q^.data
THEN BEGIN
(A)____________ ;
q := s
END ;
r := s ;
(B)______________
END
write ( q^.data ) ;
IF q = head
THEN (C) ______________
ELSE (D) ______________ ;
dispose (q )
END
END ;
二、 下面的程序是利用一个顺序存储的栈S(栈顶指针为top);来实现快速排序。这里假设不会溢出。(18分)
CONST maxn = 100 ;
TYPE atype = ARRAY [1 .. maxn] OF char
VAR a : atype ;
n , i : integer ;
PROCEDURE quick (VAR a : atype ;n : integer)
TYPE stack = RECORD
low : integer ;
hig : integer
END
VAR s : ARRAY [1 .. maxn] OF stack ;
top , lw , hg , i , j : integer ;
temp : char ;
BEGIN
IF n > 1 THEN
BEGIN
top := 1 ;
s[top].low := 1 ;
s[top].hig := n ;
WHILE top > 0 DO
BEGIN
lw := s[top].low ;
hg := s[top].hig ;
top := top – 1 ;
i := lw ;
j := hg ;
temp := a ;
WHILE i <> j DO
BEGIN
WHILE (i < j) AND (a[j]>temp) DO
(A)__________ ;
IF i < j THEN
BEGIN (B)__________;
i := i + 1
END;
WHILE (i
(C)_______________;
IF i < j THEN
BEGIN (D)____________;
j := j –1
END;
END;
a := temp ;
IF (E)_________
THEN BEGIN
top := top + 1;
s[top].low := i +1 ;
s[top].hig := hg
END;
IF (F)_________
THEN BEGIN
top := top + 1;
s[top].low := lw ;
s[top].hig := i –1
END
END
END
END ;
三、 假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n和边的个数m, 以及图的m条边。在下面的程序中，我们用readdata程序过程输入图的信息， 并建立该图的邻接表，利用topol程序过程获得图中顶点的一个拓扑序列。(18分)
PROGRAM topol_order(input , output) ;
CONST maxn = 20 ;
TYPE nodeptr = ^nltype ;
nltype = RECORD
num : integer ;
link : nodeptr
END ;
chtype = RECORD
count : integer ;
head : nodeptr
END ;
VAR ch : ARRAY [1 .. maxn] OF chtype ;
m , n , top : integer ;
PROCEDURE readdata ;
VAR i , j , u , v : integer ;
p : nodeptr ;
BEGIN
write (′input vertex number n= ′);
readln (n) ;
write (′input edge number m= ′) ;
readln(m) ;
FOR i := 1 TO n DO
BEGIN
ch.count := 0 ;
ch.head := NIL
END;
writeln(′input edges :′);
FOR j := 1 TO m DO
BEGIN
write( j :3 , ′: ′) ;
readln( u , v ) ;
new( p ) ;
ch[v].count := ch[v].count + 1 ;
p^.num := v ;
(A)____________ ;
(B)_____________ ;
END
END ;
PROCEDURE topol ;
VAR i , j , k : integer ;
t : nodeptr ;
BEGIN
top := 0 ;
FOR i := 1 TO n DO
IF ch.count = 0
THEN BEGIN
ch.count := top ;
top := i
END;
i := 0 ;
WHILE (C)________ DO
BEGIN
(D)_____________ ;
(E)_____________ ;
write( j : 5) ;
i := i + 1 ;
t := ch[j].head ;
WHILE t <> NIL DO
BEGIN
k := t^.num ;
ch[k].count := ch[k]count – 1 ;
IF ch[k].count = 0
THEN BEGIN
ch[k].count := top ;
top := k
END;
(F)____________ ;
END
END ;
writeln;
IF i < n
THEN writeln (′the network has a cycle!′)
END;
BEGIN
readdata ;
writeln (′output topol order : ′);
topol
END.
四、 假设我们所考虑的简单算术表达式是由四种运算符′+ 、′- ′、′* ′、 ′/ ′ 和′( ′、′) ′，以及用一个小写字母标识的变量所组成，并用符号′# ′作为算术表达式的结束标记。比如，(a+b)/( c - ( d + e ) ) * ( f / g )#就是一个带结束标记的算术表达式，我们可以用下面的二叉树表示这个表达式。如果我们把一个给定的带结束标记的算术表达式存放在一个字符数组e[maxn]中，那么我们可以利用表达式e建立一棵表示该表达式的二叉树t。 请编写一个由表达式e建立二叉树t的函数过程create_tree(e) , 并编写一个获得表达式e的后缀形式pos_e的程序过程postfix( t , pos_e )。 可用PASCAL或C语言编写，要有设计程序的详细思路，对程序段作适当注释，对重要的量说明其作用。 creata_tree(e) 占10分。postfix( t , pos_e ) 占5分(22分)
五、 现有三个进程in , outA , outB共享缓冲区buf ( 容量为1)，约定：仅当buf 空时，in才可以把读入的数据放入(put)buf中。仅当buf有数据且为奇数时，outA才可以从buf中取出(GET)数据使buf为空并打印，若buf中有数据且为偶数，则由outB从buf中取出(GET)数据使buf为空并打印。请给出用pv操作实现三个进程并发执行的程序。(10分)
六、 对于下面的进程状态转换图，请回答以下问题： (1) 是否存在不可能发生的转换?若存在，请给出其编号。 (2)对于可能发生的转换，请分别指出一个转换i 可能引起的另一个转换j ,并说明引起的原因。(3) 指出(2)中回答的转换j 是必然的吗?若可能不发生，请写出可能不发生的条件。(12分)
七、 选择一个最佳答案(8分)
a) 对于轮转调度
i. 若采用很小的时间片，便退化成LIFO 。
ii. 若采用很大的时间片，便退化成FCFS 。
iii. 若采用极小的时间片， 则可提高系统性能。
iv. 若采用中等大小的时间片，则成为STR 。
v. 以上论断都不正确 。
b) 一个段式系统，共有64个段，最大段长512字，则逻辑地址长度为：
(a)12 (b) 13 (c) 14 (d) 15 (e) 16
c) 较高的快化因子将导致
i. 会增加主页的需求。
ii. 会降低顺序处理的时间。
iii. 会增加随机处理的时间。
iv. 会提高磁盘空间的利用率。
v. 以上论断都正确。
d) 对于可动臂磁盘，影响访问时间大小(降序)的三要素是：
1. 查找，等待，cache
2. cache , 等待，查找
3. 传输，等待，查找
4. 查找，等待，传输
5. 排队，cache, 传输
