数据结构程序填空2

Typedef struct Bnode { int key ;

struct Bnode *left; struct Bnode * right ; }Bnode;

Bnode *BSearch(Bnode *bt,int k)

/*bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ {Bnode *P;

if( bt == (1) _____________) return (bt) ; p= bt ;

while(p->key!=(2)__________ ) {if( kkey)

(3)__________________;

else (4)___________________; if (p==NULL) break; }

Return((5)___________ ); }

2. 以下函数为链队列的出队操作(链队列带有头结点)，出队结点的数据域的值由x返回，front,rear分别是链队列的队头、队尾指针。 struct node

{ ElemType data; struct node * next; };

struct node * front, * rear; ElemType OutQueue() {

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. 以下冒泡法程序对存放在a[1],a[2].......,a [n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。 void bsort( NODE a[]，int n ) {NODE temp;

int i ,j, flag ;

for (j =1 ;(1)________________ ;j ++) ; {flag = 0;

for (i = 1; (2)____________________ ;i++)- if( a[i].key > a[i+1].key) {flag = 1; temp = a[i];

(3)_________________________ ; (4)__________________________ ; }

if( fla g= = 0)break; } }

程序 中 flag的功能是(5) ______________________________________________

2.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。 void Preorder(struct BTreeNode * BT) if(BT! =NULL){

(1)________________________; (2)________________________; (3)________________________; }

1.以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域从前向后依次为n,n-1,…， 1， 完成程序中空格部分。

NODE * create2(n) {NODE *head, *p， *q; int i ;

p= ( NODE *)malloc(sizeof(NODE)); p->next=NULL;

head = (1)___________________________; (2)_______________________________; for(i=1;i<=n;i++)

P= (3)____________________________; p->data=i; if(i==1)

p->next=NULL; else

p->next= (4)_______________________; q->next= (5)_________________________; }

return (head); }

2. 以下 程 序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。 void fostorder (struct BTreeNode *BT) { if (BT!=NULL){

(1)______________________________; (2)_______________________________; (3)_______________________________; } }