leavequeue (QUEUE *Q, int *e) {
if( ) { return 0; }
*e = Q->data[Q->front];
Q-front = ; return 1;
}1．Q->front == Q->rear;(Q->front+1)0;
13. 已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分）
for (p=h;p->data<300;p=p->next) { p->next = p->next->next;
}
printf(“%d”,p->data);
3．300
14. 指出下面程序段的功能是什么？ (1) void demo1(SeqStack S) {int i，arr[64]，n=0;
while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i 【解答】程序段的功能是实现了栈中元素的逆置。 (2) void demo2(SeqStack S，int m)∥设栈中元素类型为int型 {int x;SeqStack T; StackInit(T); while(!StackEmpty(S)) if((x=Pop(S))!=m) Push(T，x); while(!(StackEmpty(T)) {x=Pop(T); Push(S，x);} } 【解答】程序段的功能是删除了栈中值为m的元素。 (3) void demo3(SeQueue Q，int m)∥设队列中元素类型为int型 {int x;SeqStack S; StackInit(S); while(!QueueEmpty(Q)){x=QueueOut(Q); Push(S，x);} while(!StackEmpty(S)){x=Pop(s); QueueIn(Q，x);} } 【解答】程序段的功能是实现了队列中元素的逆置。 15. 假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。 # include < iostream.h> 21 # include < stdlib.h > consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” Void main ( ) { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout < } 该算法的输出结果为： __________________________________________________________. 该算法的输入结果是：34 91 30 45 63 78 16. 设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次 L.Locate (x)操作时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 函数中有些语句缺失，请将它们补上。（每一个空2分，共10分） template< class Type> void DblList DblNode While (p ! = frist && ① )p = ->next; If (p ! =first){ //链表中存在x ② ； //该结点的访问频度加l DblNode P=current?prior; //寻找重新插入的 位置 While (p !=first && ③ ) 22 P=p ?prior ; Current ?next= ④ ; //插入在p之后 Current ?prior=p ; P ?next ?prior=current ; P ?next= ⑤ ; } else cout<<”Sorry.Not find! \\n”; //没找到 } 缺失的内容为： ① ② ③ ④ ⑤ ①p?data!=x ②p?freq++ ③current?freq>p?freq ④p?next ⑤current 17. 已给如下关于单链表的类型说明： TYPE list=^node ; node=RECORD data: integer; next: list; END; 以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q. PROCEDURE mergelink(VAR p,q:list): VAR h,r: list; BEGIN （1）______ h^.next:= NIL; r:=h; WHILE((p<>NIL) AND (q<>NIL)) DO IF (p^.data<=q^.data) THEN BEGIN （2）___； r:=p; p:=p^.next； END ELSE BEGIN （3）____； r:=q; q:=q^.next; END; IF (p=NIL) THEN r^.next:=q; （4）__； p:=h^.next; dispose(h); END;【厦门大学 2000 三.2 （8分）】 (1)new(h);∥生成头结点，以便于操作。 (2)r^.next:=p; (3) r^.next:=q; (4) IF q=NIL THEN r^.next:=p; 18. 已知双链表中结点的类型定义为： TYPE dpointer=^list; 23 list=RECORD data:integer; left,right:dpointer; END; 如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。 PROCEDURE insert(VAR head:dpointer;i,x:integer); VAR s,p:dpointer; j: integer; BEGIN new(s); s^.data:=x; IF(i=0)THEN BEGIN s^.right:=head; (1)___ head:=s END{如果i=0,则将s结点插入到表头后返回} ELSE BEGIN p:=head; (2)_______；{在双链表中查找第i个结点,由p所指向} WHILE ((p<>NIL) AND (j IF （p^.right=NIL） THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END ELSE writeln(‘can not find node!’) END END; 【厦门大学 2002 二 （12分）】 (1)head^.left:=s ∥head的前驱指针指向插入结点 (2)j:=1; (3)p:=p^.right ∥工作指针后移 (4)s^.left:=p (5)p^.right^.left:=s; ∥p后继的前驱是s (6)s^.left:=p; 19. 阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。 CONST maxlen=30 TYPE sqlisttp=RECORD elem:ARRAY[1..maxlen] OF integer; last:0..maxlen END; PROC exam21(VAR L:sqlisttp); j:=1; i:=2; WHILE (1)______ DO [ IF L.elem[i]<>L.elem[j] THEN [ (2)_______; (3)______]; i:=i+1 ] (4) ________; ENDP;【同济大学 2000 二.1 (10分)】 (1)i<=L.last ∥L.last 为元素个数 (2)j:=j+1 ∥有值不相等的元素 24 (3)L.elem[j]:=L.elem[i] ∥元素前移 (4)L.last:=j ∥元素个数 20. 对于给定的线性链表head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。 TYPE nodeptr =^ nodetype； nodetype = RECORD data : integer；link : nodeptr END; VAR 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分）与本题相似】 (1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;∥q指向最小值结点，s是工作指针 (3)s:=s^.link∥工作指针后移 (4)head:=head^.next;∥第一个结点值最小； (5)p^link:=q^.link;∥跨过被删结点（即删除一结点） 21. 循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n） TYPE link=^node; node=RECORD key:char; next:link END; PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN new(c);c^.next:=c; q:=a; p:=a^.next; WHILE p<>a DO 25 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第二章 线性表(5)在线全文阅读。
相关推荐：