数据结构（本）期末综合练习（2013年12月）(5)

if(i

{ a[i]=a[j]; __(1)___;

}

while(i

{ __(3)___ __(4)___

} } a[i]=mid;

quicksort(a,stat, i-1); quicksort __(5)___ }

2．以下函数为直接选择排序算法，对a[1],a[2],?a[n]中的记录进行直接选择排序，完成程序中的空格

typedef struct { int key;

?? }NODE;

void selsort(NODE a[],int n) {

int i,j,k;

NODE temp;

for(i=1;i<= ___(1)_____;i++) { k=i; for(j=i+1;j<= ___(2)_____;j++) if(a[j].key

3．以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是

21

链

队列的队头、队尾指针

struct node

{ ElemType data;

struct node *next; };

struct node *front，*rear; void InQueue(ElemType x) { struct node *p;

p= (struct node*) ___(1)_____; p->data=x;

p->next=NULL;

___(2)_____;

rear= ___(3)_____; }

4 .设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同）, 写出相关语句

(1).使该单向链表成为单向循环链表 (2) 删去a结点 q=p; x=p->data;

while （q->next!=NULL）q=q->next; __(1)___

q=p; p=p->next; while(p->data!=x) { q=p; __(2)___ }

__(3)___

期末综合练习二答案

一、单项选择题 1．B2．C3．A 4．A5．C 6．A 7．A 8．C 9．A 10．D 11．C12．C13．D 14．C15．C 16．D 17．C 18．C 19．C 20．B 21．D22．A 23．A 24．B 25．A 26．C 27．B 28．B 29．A 30．C

二、填空题 1．逻辑

2．物理（存储）

22

3．元素间的比较 O(n) 4．乘法O(n3) 5．25 6．8

7．p->next=q；

8．直接前驱的左指针 9．p->next=p->next->next; 10．p->next= head;

11．p->next=top; top=p；

12．d=top->data;top=top->next; 13．front->next

14．front= =(rear+1)%MaxSize 15．7 16．34 17．5 18．15 19．15 20．1

21．512389746 22．215347896 23．不正确 24．主关键字

三、综合应用题 1．(1)

图7 (2)

3 0000 4 0001

23

39221712108 9 7 5 3 4 5 001 10 01 8 10 9 11

（3）n个，因为非叶结点数比叶结点数少一个,而权值个数=叶结点数

2. (1)

23

9

8645

44

3 1

图8

（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58

(3) 共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故 有 22-10=12个空指针域,

3. (1) 循环执行以下两步 选择一个度为0的顶点并输出 从网中删除此结点及所有出边

（2）因为选择一个度为0的顶点时不一定是唯一的

（3）由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱

(4) 152364 152634 156234 4 .

(1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2)

24

14 (3)

7 4 8 2 5 3 9 1 6 3.5 图9 5.

（1) 5 (2)

26232921242731 2225283032图10 (3) 3

(4) ASL=(1+2*2+3*4+5*4)/12=37/12

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构（本）期末综合练习（2013年12月）(5)在线全文阅读。