电大数据结构程序题.docxVIP

1．以下函数为直接选择排序算法，对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].keya[k].key) __(3)______; if(i!=k) {temp=a[i];___(4)_____;____(5)____;答案：（1）n-1 （2）n （3）k=j （4）a[i]=a[k] （5）a[k]=temp2．以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,……,n，完成程序中空格部分。NODE *create(n){NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE));head= （1） ; （2） ;pnext=NULL; /*建立头结点*/for(i=1; i=n; i++){ p= （3） ; pdata=i; pnext=NULL; qnext= （4） ; （5） ;}return(head);答案：（1）p （2）q=p （3）(NODE*)malloc(sizeof(NODE)) （4）p （5）q=p3 .设有一个头指针为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）q-next=head;（2）p=p-next;（3）q-next=p-next;4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Inorder (struct BTreeNode *BT){if(BT!=NULL){ （1） ;（2） ; （3） ;}}（1）Inorder(BT-left)（2）printf(“%c”,BT-data)（3） Inorder(BT-right)3．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Postorder (struct BTreeNode *BT){if(BT!=NULL){ （1） ; （2） ; （3） ;}}答案：（1）Postorder(BT-left)（2）Postorder(BT-right)（3） printf(“%c”,BT-data)1．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL）完成程序中的空格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(kp-key) ___(3)_____; else ___(4)_____; if(p==NULL) break; } return(___(5)_____); 答案：（1）NULL（2）k（3）p=p-left（4）p=p-right（5）p3 .设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句 (1).使该单向链表成为单向循环链表 (2)插入结点s,使它成为a结点的直接前驱 q=p; x=p-data; while （__(1)___ ）q=q-next; q-next=head;q=p; p=p-next;while(p-d