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

1、1 以下函數(shù)為直接選擇排序算法，對(duì)a1,a2，an中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedefstruct in tkey;NODE;voidselsort(NODEa,i ntn)in ti,j,k;NODEtemp;for(i=1;i=(1);i+) k=i;for(j=i+1;j=_(2);j+)if(aj.keyak.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，完成程序中空格部分

2、。NODE*create( 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) 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);上);(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))。dPostorder(structBTreeNode*BT)BT!=NULL)1 ;( 2);( 3);案：1)Postorder(BT-left)( 2) Postorder(BT-ri

4、ght)( 3)printf( “ %C ,BT-data)1.以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指 針p (查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL完成程序中的空格typedefstructB 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(

5、p-key!= _(2)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

6、ext=p;案：1)q- next!=NULL(2)p=p- next;(3)q- next=s;設(shè)線性表為(6, 10, 16, 4),以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié) 點(diǎn)中的數(shù)據(jù)。defin eNULL0 oidmai 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);JT;while( (5);答案：(1) &a (2) d?next=NULL (3) p-data (4) p=p

7、-next (5) p!=NULL1以下程序是折半插入排序的算法=設(shè)待排序的記錄序列存放在a1,n中，以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-)=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為棧頂指針st

8、ruct nodeElemTypedata;struct no de* next;struct no de*top;voidPush(ElemTypex)struct no de*p;p=(struct no de*)malloc(1);p-data=x; ； ；答(1)sizeof(struct no de)( 2) p-n ext=top ( 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(ij)w