第二章 线性表(7)

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 ：： Locate ( Type & x) {

DblNode*p=first->next ;

While (p ! = frist && ① )p = ->next;

If (p ! =first){ //链表中存在x ② ； //该结点的访问频度加l

DblNode*current=p; //从链表中摘下这个结点 Current ?prior?next = current ?next; Current ?next?prior = current ?prior;

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 (jNIL THEN

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 , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程 …… 此处隐藏：2822字，全部文档内容请下载后查看。喜欢就下载吧 ……