Var head: nodeptr PROCEdURE sort output delete(head: nodeptr) VAR p, g, r, s: nodeptr bEgIN While head> NIl Do begin p: = NIL q: =head: r: =q s: =q. link: WHILE S NIL DO BEGIN IF s, data g. data THEn BEGIN (1) 2) END END: (a. data: 5) IF DENIL THEN ELSE (5 writeln END;【复旦大学1996七(20分)1995一(12分)与本题相似】 28.下面函数的功能是在一个按访问频度不增有序的,带头结点的双向链环上检索关键值为 x的结点,对该结点访问频度计数,并维护该链环有序。若未找到,则插入该结点。所有结 点的频度域初值在建表时都为零。请将程序中四处空缺补写完整 TYPE link= node node=RECORd key: char: freq: integer: pre, next: link VAR: link FUNCTIoN loc(1: link;x: char): link var p, g: link BEGIN p:=1.next;(1) WhiLE p. key >x Do p: =p. next IF p=l tHen new(g): g. key: = x; q. freg: =0 ELSE{找到} [ p. freg: =p. freq+1: g: =p:(2) WhILE q. freq>p. pre. freq do p: = p. pre IF p<>q THen [(3) iF (4) then [q. next: =p, q. pre; p. pre; p. pre. next: =q: p. pre: =q return END;【北京工业大学1999五(12分】 29.循环链表a和b的结点值为字母,其中a表非递减有序,下面的程序欲构造一个递增有 序的循环链表c,其中结点的值为同时在a,b两链表中出现的字母,且c中字母不重复, 请补上程序中空缺的部分,并估计算法的时间复杂度。(设a,b的结点数分别为m,n) TYPE link= node node=ReCOrdVAR head : nodeptr； PROCEDURE sort_output_delete (head : nodeptr); VAR p,q,r,s: nodeptr; BEGIN WHILE head <> NIL DO BEGIN p:= NIL ；q:= head；r:= q ；s:=q^.link ； WHILE s <> NIL DO BEGIN IF s^.data < q^.data THEN BEGIN (1)__; (2)___ END ； r:= s ； (3)___ END； write(q^.data : 5) ； IF p=NIL THEN (4)___ ELSE (5)____ ； dispose (q) ； END； writeln END；【复旦大学 1996 七（20 分） 1995 一（12 分）与本题相似】 28．下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为 x 的结点，对该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结 点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。 TYPE link=^node node=RECORD key:char; freq:integer; pre,next:link; END; VAR l:link; FUNCTION loc(l:link;x:char):link; VAR p,q:link; BEGIN p:=l^.next; （1）_； WHILE p^.key<>x DO p:=p^.next; IF p=l THEN [ new(q); q^.key:=x; q^.freq:=0 ] ELSE {找到} [ p^.freq:=p^.freq+1; q:=p; （2）______； WHILE q^.freq>p^.pre^.freq DO p:=p^.pre; IF p<>q THEN [ （3）______ ] ]； IF （4）_ THEN [q^.next:=p, q^.pre;=p^.pre; p^.pre^.next:=q; p^.pre:=q] return(q); END;【北京工业大学 1999 五 (12 分)】 29．循环链表 a 和 b 的结点值为字母，其中 a 表非递减有序，下面的程序欲构造一个递增有 序的循环链表 c，其中结点的值为同时在 a，b 两链表中出现的字母，且 c 中字母不重复， 请补上程序中空缺的部分，并估计算法的时间复杂度。（设 a，b 的结点数分别为 m，n） TYPE link=^node; node=RECORD