电大数据结构程序题

1、1 .以下函数为直接选择排序算法，对a1,a2，an中的记录进行直接选择排序，完成程序中的空格typ edefstruct in tkey;NODE;voidselsort(NODEa,i ntn)in ti,j,k;NODEte mp;i+)for(i=1;i<=_(1)k=i;for(j=i+1;j<=_(2);j+)if(aj.keyvak.key);if(i!=k)temp=ai;(4);(5);答案：(1)n-1( 2)n (3)k=j( 4)ai=ak( 5)ak=temp2以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,

2、n，完成程序中空格部分。NODE*create( n)NODE*head,* p,*q;in ti;p=(NODE*)malloc(sizeof(NODE);head= (1) ; (2) ;p next=NULL;/*建立头结点 */for(i=1;i<=n ;i+)p = (3);p data=i;p n ext=NULL;q next= (4);(5);return(head);答案：(1) p (2) q=p (3) (NODE*)malloc(sizeof(NODE)(4) p (5) q=p设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的指针变量，

3、p指向链表中某结点a (- 链表中没有结点的数据域与结点a的数据域相同)，写出相关语句(1).使该单向链表成为单向循环链表删去a结点q=p;x=p->data;while (q->next!=NULL) q=q->next;q=p;p=p->n ext; while( p->data!=x) q=p;(1) q->next=head; (2) p=p->next; (3) q->next=p->next;4以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right数据域data为字符型，BT

4、指向根结点)。din order(structBTreeNode*BT)BT!=NULL)(1) ； (2) ;(3);(1) Inorder(BT->left)(2) printf( “ %C ,BT->data) (3) Inorder(BT->right)以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right据域data为字符型，BT指向根结点)。dP ostorder(structBTreeNode*BT)BT!=NULL)1 ; (2) ; (3) ;案:(1) Postorder(BT->left) (

5、2) Postorder(BT->right) (3) printf( “c ,BT->data)1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针P (查找成功P指向查到的树结点，不成功P指向为NULL完成程序中的空格typ edefstructB nodein tkey;structB no de*left; structB no de*right;Bno de;Bn ode*BSearch(B node*bt,i ntk)/*bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/Bno de* p;if(bt=

6、 _(1)return(bt);p=bt;while( p- >key!= _(2)if(k< p->key)(3);else(4);if(p=NULL)break;return( (5);答案：(1) NULL (2) k (3) p=p->left ( 4) p=p->right ( 5) p设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a,(设链 表中没有结点的数据域与结点a的数据域相同)，写出相关语句使该单向链表成为单向循环链表插入结点s,使它成为a结点的直接前驱;x=p->data;le (_(

7、1) q=q->next;n ext=head;p;p=p->n ext;hile( p->data!=x)=p; >n ext=p;案：1)q-> next!=NULL(2) p=p-> next;(3)q-> next=s;.设线性表为(6, 10, 16, 4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结 点中的数据。defin eNULL0oidmai n()NODEa,b,c,d,*head,* p;6;10;16;4;/*d是尾结点*/ead= (1);&b;&c;&d;2);/*以上结束建表过程*/

8、=head;/*p为工作指针，准备输出链表*/oprintf( %dn”(3);while( 5);答案：(1)&a (2)d?next=NULL (3)p->data (4)p=p->next (5)p!=NULL1以下程序是折半插入排序的算法=设待排序的记录序列存放在a1,an中，以a0作为辅助工作单 元，以下程序是要把ai插入到已经有序的序列a1,ai-1中。voidbi nsort(NODEa,i ntn)in tx,i,j,s,k,m;or (i=2； i<=_(1);i+a0=ai;x=ai.key;s=1;=i-1;while(s<=j) m=_2

9、)_ f(x<am.key)3)else_or(k=i-1;k>=j+1;k-)(5)=ak;aj+1=a0;1 答案：(1)n(2)(s+j)/2;(3)j=m-1;s=m+1;(5)ak+13以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针 struct nodeElemT yp edata;struct no de* next;struct no de*t op;void Pu sh(ElemT yp ex)struct no de* p;p=(struct no de*)malloc(1)p->data=x; ； ；答(1)sizeof(struc

10、t no de)( 2)p->n ext=t op (3)top=p2以下程序是快速排序的算法设待序的记录序列存放在astart, aend中，按记录的关键字进行快速排序，先进行一次划分，再分 别进行递归调用oidquicksort(NODEa,i ntstart,i ntend)nti，j;NODEmid;(start>=e nd)eturn;=start;=end;mid=ai;while(i<j)while(ivj&&aj.key> (ivj) ai=aj;_(1) while(ivj&&ai.key<=_(2);(i<j)一i=mid;uicksort(a,stat,i-1); uicksort_(5)答案：2.(1)i+;(2)i+;(3)aj=ai;(4)j-;(5)(a,i+1,end);4以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链 队列的队头、队尾指针struct nodeElemT yp edata;struct no de* next;struct no de*fr ont，*