给出经过一次划分后结果。
(3) 一组记录的关键字序列为（ 60,47，80，57，39，41，46,30），利用归并排序的 方法,分别给出(1,1) 归并、(2,2) 归并、(4,4) 归并的结果序列。
四、程序填空题
1.设线性表为（1,3,7,5），以下程序用说明结构变量的方法建立单向链表，并输出 链表中各结点中的数据。 struct node {int data;
struct node *next; };
typedef struct node NODE; #define NULL 0
void main( )
{NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16;
d.data=4; /*d是尾结点*/ head= （1） ; a.next=&b; b.next=&c; c.next=&d;
（2） ; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do
{printf(“%d\\n”, （3） ); （4） ; }while(p!=NULL); }
画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。（5）
2.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。 struct node {int data;
struct node *next; };
typedef struct node NODE;
#define NULL 0 void main( )
{ NODE *head ,*p ;
p=head; /*p为工作指针*/ do
第6页
{printf(“%d\\n”, ___(1)_____); ___(2)_____ ; }while(___(3)_____); }
3．以下是先序遍历二叉树的递归算法程序，完成空格部分（树结构中左、 右指针域分 别为left和right，数据域data为字符型，BT指向根结点）。 void Inorder (struct BTreeNode *BT) {
if( （1） ){ （2） ; Inorder(BT->leftt);
Inorder(BT->right);} }
a b c d e 利用上述程序对右图进行遍历，结果是 （3） ; f 图5
4.以下函数为直接选择排序算法，对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
第7页
练习一答案
一、单项选择题 1．D 2．D 3．D 4．D 5．C 6．A 7．B 8．D 9．C 10．C 11．C 12． B 13． B 14．B 15． D 16．B 17．C 18．A 19．A 20．A 21．B 22．C 23． B 24．B 25．C 26．C 27．A 28．A 29．B 30． C 31．C 32．A 33．A 34．B 35．C
二、填空题 1．8 2．图状 3．图状 4．n-j 5．12
6．二叉排序树
7．front= =rear
8．1，2，4，8，3，5，9 9．n-j 10．4 11．12 12．3
13．二叉排序树 14．5
15．1，2，5，9，4，6，10 16．3 17. 4 18．9 19. 3 20. 12 21．顺序 22．32
23．有序 24．7
40 三、综合题
1． (1)
29 73
7 39 55 101
4 81
2 第8页 92 图6
(2)40,73,101,81,92。共5个元素比较
(3) 29/10
282．
(1) 11 69
1 15 30
2 24 56
图7
(2)28,69,30,56 (3)4次 3． (1) 33
18
9 9
5 4
2 3 图8
(2) 2：0000 3 0001 4 001 7 10 8 11 9 01
39 (3)
41 46
80 47 57 第9页 70 80 15 7 8 图9
4． (1)
50
51 56
90
57 67
图10
(2) 46,51,54,56,71,106
(3) (47 , 60 ) ( 57 , 80 ) ( 39 , 41 ) ( 30 , 46 )
(47, 57, 60, 80 ) ( 30,39,41,46 )
( 30,39,41,46,47,57,60,80)
四、程序填空题 1． （1）&a
（2）d->next=NULL （3）p->data （4）p=p->next （5）P指向NULL head 6 10 16 2．
（1）p->data （2）p=p->next （3）p!=NULL
3．
（1） if(BT!=NULL)
（2） printf(“%c”,BT->data); （3） a,b,d,e,f,c
4． （1）n-1 （2）n （3）k=j
（4）a[i]=a[k] (5) a[k]=temp
第10页
4 NULL