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

1、1以下函數(shù)為直接選擇排序算法，對a1,a2,an 中的記錄進行直接選擇排序，完成程序中的空格typedefstructint 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<= _(2)_;j+)if(aj.key<ak.key) _(3)_;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é)點中

2、的數(shù)據(jù)域從前向后依次為 1,2,3, ,n ，完成程序中空格部分。NODE *create(n)NODE *head , *p, *q;int i;p=(NODE*)malloc(sizeof(NODE);head=（1）;（2）;pnext=NULL; /*建立頭結(jié)點*/for(i=1; i<=n; i+) p=（3）pdata=i;pnext=NULL;qnext=（4）（5）;return(head);答案：（1） p （2）q=p （3）(NODE*)malloc(sizeof(NODE)（4）p （5）q=p. 設(shè)有一個頭指針為head 的不帶頭結(jié)點單向鏈表 ,且 p、q 是指

3、向鏈表中結(jié)點類型的指針變量，向鏈表中某結(jié)點 a（設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a 的數(shù)據(jù)域相同） ,寫出相關(guān)語句(1).使該單向鏈表成為單向循環(huán)鏈表(2)刪去 a 結(jié)點p 指q=p; x=p->data;while（q->next!=NULL ）q=q->next;_(1)_q=p; p=p->next;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)中左

4、、右指針域分別為 left 和 right ，數(shù)據(jù)域 data 為字符型， BT指向根結(jié)點）。oid Inorder (struct BTreeNode *BT)if(BT!=NULL)（1）;（1）Inorder(BT->left)（2）（2）printf(;（3）“%c”,BT->data) （3）;Inorder(BT->right)以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中，左、右指針域分別為left 和 right ，數(shù)據(jù)域 data 為字符型， BT指向根結(jié)點）。oid Postorder (struct BTreeNode *BT)i

5、f(BT!=NULL)（1）;（2）;（3）;案：（1）Postorder(BT->left)（2）Postorder(BT->right)（3） printf(“%c”,BT->data)1以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指針 p（查找成功 p 指向查到的樹結(jié)點，不成功 p 指向為 NULL）完成程序中的空格typedef struct Bnodeint key;structstructBnode *left;Bnode *right; Bnode;Bnode*BSearch(Bnode *bt, int k)

6、/* bt用于接收二叉排序樹的根結(jié)點的指針，k用以接收要查找的關(guān)鍵字*/Bnode *p;if(bt=_(1)_ )return (bt);p=bt;while(p->key!=_(2)_ ) if(k<p->key)_(3)_ ;else_(4)_ ;return(_(5)_ );答案：（1）NULL（2）k（3）p=p->left.設(shè)有一個頭指針為head 的不帶頭結(jié)點單向鏈表，鏈表中結(jié)點 a,（設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點(1). 使該單向鏈表成為單向循環(huán)鏈表(2)插入結(jié)點 s, 使它成為 a 結(jié)點的直接前驅(qū)q=p; x=p->data;hile （_(1

7、)_）q=q->next;->next=head;=p; p=p->next;hile(p->data!=x)q=p;_(2)_（4）p=p->right（5）pp、q 是指向鏈表中結(jié)點類型的指針變量，a 的數(shù)據(jù)域相同） , 寫出相關(guān)語句p 指向->next=p;_(3)_案：(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 main( )NODE a,

8、b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾結(jié)點 */head=（1）;a.next=&b;b.next=&c;c.next=&d;（2）; /*以上結(jié)束建表過程*/p=head; /*pdoprintf(為工作指針，準(zhǔn)備輸出鏈表“%dn”,（3）);*/（4）;while(（5）);答案：（1）&a（2）d?next=NULL（3）p->data （4）p=p->next （5）p!=NULL1 .以下程序是折半插入排序的算法=設(shè)待排序的記錄序列存放在a1,an 中，以 a0

9、 作為輔助工作單元，以下程序是要把 ai 插入到已經(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=_(2)_if( x<am.key)_(3)_else_(4)_for ( k=i-1;k>=j+1;k- -)_(5)_=ak;aj+1=a0;1. 答案： (1) n (2) (s+j)/2; (3) j=m-1; (4) s=m+1; (5) ak+13以下函

10、數(shù)為鏈棧的進棧操作， x 是要進棧的結(jié)點的數(shù)據(jù)域， top 為棧頂指針 struct nodeElemType data;struct node *next;struct node *top ;void Push(ElemType x)struct node *p;p=(struct node*)malloc(_(1)_);p->data=x;_(2)_;_(3)_;答（ 1）sizeof (struct node)（2）p->next=top（3）top=p2以下程序是快速排序的算法設(shè)待序的記錄序列存放在astart,先進行一次劃分，再分別進行遞歸調(diào)用aend 中，按記錄的關(guān)鍵字

11、進行快速排序，void quicksort ( NODE a , int start ,int end )int i，j;NODE mid ;if (start>=end )return;i=start;j=end;mid=ai;while (i<j)while(i<j && aj.key>mid.key)j- -;if(i<j) ai=aj;_(1)_;while(i<j && ai.key<=mid.key)_(2)_;if(i<j) _(3)_(4)_ai=mid;quicksort (a,stat, i-1);quicksort _(5)_答案： 2.(1)i+;(2)i+;(3)aj=ai;(4)j-;(5)(a,i+1,end);4以下函數(shù)為鏈隊列的入隊操作，x 為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是 鏈隊列的隊頭、隊尾指針struct nodeElemType data;struct node *next;struct