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，*