数据结构考研分类复习真题 第二章 线性表[18]

．对于给定的线性链表head 下面的程序过程实现了按结点值非降次序输出链表中的所有结点在每次输出一个结点时就把刚输出的结点从链表中删去请在划线处填上适当的内容使之成为一个完整的程序过程每个空框只填一个语句

TYPE nodeptr =^ nodetype

nodetype = RECORD

data : integerlink : nodeptr

END;

VAR head : nodeptr

PROCEDURE sort_output_delete (head : nodeptr);

VAR pqrs: nodeptr;

BEGIN WHILE head <> NIL DO

BEGIN p:= NIL q:= headr:= q s:=q^link

WHILE s <> NIL DO

BEGIN IF s^data < q^data THEN BEGIN () ; () END

r:= s ()

END

write(q^data : )

IF p=NIL THEN () ELSE ()

dispose (q)

END

writeln

END【复旦大学 七（分） 一（分）与本题相似】

．下面函数的功能是在一个按访问频度不增有序的带头结点的双向链环上检索关键值为x的结点对该结点访问频度计数并维护该链环有序若未找到则插入该结点所有结点的频度域初值在建表时都为零请将程序中四处空缺补写完整

TYPE

link=^node

node=RECORD

key:char; freq:integer; prenext:link;

END;

VAR l:link;

FUNCTION loc(l:link;x:char):link;

VAR pq:link;

BEGIN

p:=l^next; （）

WHILE p^key<>x DO p:=p^next;

IF p=l THEN [ new(q); q^key:=x; q^freq:= ]

ELSE {找到}

[ p^freq:=p^freq+; q:=p; （）

WHILE q^freq>p^pre^freq DO p:=p^pre;

IF p<>q THEN [ （） ]

]

IF （） THEN [q^next:=p q^pre;=p^pre; p^pre^next:=q; p^pre:=q]

return(q);

END;【北京工业大学 五 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []