電大數(shù)據(jù)結(jié)構(gòu)程序題

1、_(1)a1,a2，an中的記錄進(jìn)行直接選擇排序，完成程序中的空格typ edefstruct in tkey;NODE;voidselsort(NODEa,i ntn)in ti,j,k;NODEte mp;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以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。NODE*create(

2、 n)NODE*head,* p,*q;in ti;p=(NODE*)malloc(sizeof(NODE);head=(1);(2);p next=NULL;/*建立頭結(jié)點(diǎn)*/for(i=1;idata;while(q-next!=NULL)q=q-next;q=p;p=p-n ext; while( p-data!=x) q=p;1.以下函數(shù)為直接選擇排序算法，對(duì);i+)(1)q-next=head;(2)p=p-next;(3)q-next=p-next;4以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right數(shù)據(jù)域data為字符型，

3、BT指向根結(jié)點(diǎn))。din order(structBTreeNode*BT)BT!=NULL)(1)；(2);(3);(1)Inorder(BT-left)(2)printf(“%C ,BT-data)(3)Inorder(BT-right)以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中，左、右指針域分別為left和right據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。dP ostorder(structBTreeNode*BT)BT!=NULL)1 ;(2);(3);案:(1)Postorder(BT-left)(2)Postorder(BT-right)(3)print

4、f(“c ,BT-data)1.以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針P(查找成功P指向查到的樹結(jié)點(diǎn)，不成功P指向?yàn)镹ULL完成程序中的空格typ edefstructB nodein tkey;structB no de*left; structB no de*right;Bno de;Bn ode*BSearch(B node*bt,i ntk)/*bt用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/Bno de* p;if(bt= _(1)_)return(bt);p=bt;while( p- key!= _(2

5、)_ )if(kkey)(3)_;else_(4)_ ;if(p=NULL)break;return( _(5)_;答案：(1)NULL(2)k(3)p=p-left(4)p=p-right(5)p設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中結(jié)點(diǎn)a,(設(shè)鏈 表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同)，寫出相關(guān)語句使該單向鏈表成為單向循環(huán)鏈表插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū);x=p-data;le (_(1)_)q=q-next;n ext=head;p;p=p-n ext;hile( p-data!=x)=p; n ext=p;案：1)q

6、- next!=NULL(2) p=p- next;(3)q- next=s;.設(shè)線性表為(6,10,16,4),以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié) 點(diǎn)中的數(shù)據(jù)。defin eNULL0oidmai n()NODEa,b,c,d,*head,* p;6;10;16;4;/*d是尾結(jié)點(diǎn)*/ead=(1);&b;&c;&d;2);/*以上結(jié)束建表過程*/=head;/*p為工作指針，準(zhǔn)備輸出鏈表*/oprintf( %dn”(3);while( 5);答案：(1)&a(2)d?next=NULL(3)p-data(4)p=p-next(5)p

7、!=NULL1以下程序是折半插入排序的算法=設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單 元，以下程序是要把a(bǔ)i插入到已經(jīng)有序的序列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)_ f(x=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以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針struct nodeElemT

8、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(struct no de)(2)p-n ext=t op(3)top=p2以下程序是快速排序的算法設(shè)待序的記錄序列存放在astart, aend中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分 別進(jìn)行遞歸調(diào)用oidquicksort(NODEa,i ntstart,i ntend)nti，j;NODEmid;(start=e nd)eturn;=start;=end;mid=ai;while(i (