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

1、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= _;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é)點且有 n個結(jié)點的單向鏈表的程序，結(jié)點中的數(shù)據(jù)域從前向后依次為1,2,3,n, 完成程序中空格部分。NODE *create( n)NODE *head , *p, *q;in

2、t i;p=(NODE*)malloc(sizeof(NODE);head= (1);(2);p next=NULL; /*建立頭結(jié)點 */for(i=1; idata;while (q-next!=NULL) q=q-next;_(1)q=p; p=p-n ext;while(p-data!=x) q=p;_(2)_(3)(1) q-next=head; (2) p=p-next; (3) q-next=p-next;4以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點)。void In ord

3、er (struct BTreeNode *BT) if(BT!=NULL)(1);J2; _J3;(1) Inorder(BT-left)(2) printf(“ C ,BT-data) (3) Inorder(BT-right)3以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點)。void Postorder (struct BTreeNode *BT) if(BT!=NULL)(1);丄2; _(3;答案：(1) Postorder(BT-left)( 2)Postorder(BT-ri

4、ght) ( 3) printf( “c” ,BT-data)1 以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的 結(jié)構(gòu)指針p (查找成功p指向查到的樹結(jié)點，不成功p指向為NULL完成程序中的空格typedef struct Bnode int key;structBnode *left;structBnode *right; Bno de;Bn ode *BSearch(B node *bt, i nt k)/* bt用于接收二叉排序樹的根結(jié)點的指針，k用以接收要查找的關(guān)鍵字*/ Bn ode *p;if(bt=_(1)return (bt);p=

5、bt; while(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) p3設(shè)有一個頭指針為head的不帶頭結(jié)點單向鏈表，p、q是指向鏈表中結(jié)點類型的指針變量，p指向鏈表中結(jié)點a, (設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a的數(shù)據(jù)域相同)，寫出相關(guān)語句(1) .使該單向鏈表成為單向循環(huán)鏈表(2) 插入結(jié)點s使它成為a結(jié)點的直接前驅(qū)q=p; x=p-data; while (_(1) q=q-next;q-n ext=head;q=p; p

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

7、;(4);while( (5);答案：(1)&a (2)d?next=NULL(3) p-data(4)p=p-next(5) p!=NULL1 .以下程序是折半插入排序的算法=設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助 工作單元，以下程序是要把a(bǔ)i插入到已經(jīng)有序的序列a1,-ai-1中。void binsort (NODE a ,int n) int x,i,j,s,k,m;for (i=2； i= _(1);i+ a0=ai;x= ai.key;s=1;j=i-1;while (s=j) m= _if( x=j+1;k-)一(5一=ak;aj+1=a0;1.答案：(1) n (2

8、) (s+j)/2;(3) j=m-1; s=m+1; ak+13. 以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針struct node ElemType data;struct node *n ext;struct node *top ;void Push(ElemType x)struct node *p;p=(struct no de*)malloc(丄1)_);p-data=x;(2;(3)_;答(1) sizeof (struct no de)(2) p-n ext=top (3) top=p2.以下程序是快速排序的算法設(shè)待序的記錄序列存放在astart, -ae nd中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用void quicksort ( NODE a , int start ,int end ) int i，j;NODE mid ;if (start=e nd )return;i=start;j=e nd;mid=ai;while (ij) while(ij