的一种顶点序列。
(2)如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，给出可能得到的2种顶
点序列。
a
he c
f d b 图3
（3）一组记录的关键字序列为（85,62,46,44,51,52），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。
四、程序填空题
1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格
typedef struct { int key; ?? }NODE;
int Binary_Search(NODE a[],int n, int k) {
int low,mid,high; low=0; high=n-1;
while(___(1)_____) {
mid=(low+high)/2; if(a[mid].key==k)
return __(2)______; else if(___(3)_____) low=mid+1; else __(4)______; }
___(5)_____;
}
2.以下函数在头指针为head的单向链表中插入一个新结点，结点的数据域为x，要求该 结点在链表作为第i个结点。（提示： 程序中使工作指针q指向第i-1个结点）
第26页
struct node { int data;
struct node *next; };
typedef struct node NODE
int insert(NODE *head , int x , int i) {
NODE *q,*p;
int j; q=head; j=0;
while((q!=NULL)&&(j { ___(1)_____; j++;} if(q = =NULL) return(0); p=(NODE *) ___(2)_____; ___(3)_____=x; p->next= ___(4)_____; ___(5)_____; return(1); } 3..以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针 struct node { ElemType data; struct node *next; }; struct node *top ; void Push(ElemType x) { struct node *p; p=(struct node*)malloc(___(1)___); p->data=x; __ (2)____; ___(3)___; } 4．以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由 x返回，front、rear分别是链队列的队头、队尾指针 struct node { ElemType data; struct node *next; }; struct node *front，*rear; ElemType OutQueue( ) { 第27页 ElemType x; if(___(1)_____) { printf(\队列下溢错误！\\n\ exit(1); } else { struct node *p=front->next; x=p->data; front->next= ___(2)_____; if(p->next==NULL) rear=front; free(p); ___(3)_____; } } 练习三答案 一、单项选择题 1．C 2．A 3．A 4．D 5．A 6．D 7．B 812．C 13．C 14．B 15．C 16．B 17．C 1822．B 23．C 24．D 25．C 26．B 27．A 28 二、填空题 1. 6 2.图状结构 3. 逻辑 4.线性 5. 先出 6.(rear+1)%MaxSize==front为真 7.（b,a,c） 9. 18 10.O(n3) 11. 5 12.7 13 6 14.42 15. 二叉排序树 16.41 17. 10，12，11，13，14，16 18.20 19. 15 第28页 ．A 9．A 10．C 11．C 19．A 20．C 21．A 29．B 30．D ．A ．B 8.3 20.5 21. 15 22.该结点的直接前驱 23. 3 24.主关键字 三、综合应用题 1 （1）图4 51 6 14 3 81 9 5 15 61 82 10 14 7 2 5 8 8 33 73 93 图4 (2) 4次 (3) ( 1+2*2+3*4+4*4)/11=33/11=3 2． （1）图5 60 4 11 38 69 9 2 6 20 48 68 80 7 3 1 5 图5 (2) 3次 (3) 3次 (4) 1(20) 2 (38) 3 (48) 4(60) 5(68) 6(69) 7(80) 3. (1) acdbfeh (2) 152364 或 152634 或 156234 第29页 4. (1) 图6 39221712108 9 7 5 3 4 图6 (2) 3 0000 4 0001 5 001 10 01 8 10 9 11 5. (1) 图7 7 4 9 36 8 5 图7 (2) 4 (3) 3,4,,5,6,7,8,9 6. (1) acdbehf 第30页 (2) acedhbf aechdfb （3） 44，51，46，62，85，52 44 51 9 46 62 四、程序填空题 1. (1) low<=high (2) mid (3) a[mid].key < k (4) high=mid -1 (5) return -1 2. (1) q=q ?next (2) malloc(siseof(NODE)) (3) q?next (4) q?next (5) q?next=p 3. (1) sizeof(struct node) (2) p?next=top (3) top=p 4. (1) front= =rear (2) p->next (3) return x 85 52 图4 第31页