《數(shù)據(jù)結(jié)構(gòu)》程序填空復習題

1、數(shù)據(jù)結(jié)構(gòu)程序填空復習題說明：本文檔中涉及到的算法并非本書的全部，有些可根據(jù)此處的情況自行看書和作業(yè)題，黑色為綜合練習上的題目，紅色為我另增加的題，這些空的選擇是根據(jù)我個人的經(jīng)驗來決定的并不能完全代表中央電大的出卷老師，因此一定不能有肯定就考這些題目的想法。不能放棄其他內(nèi)容的復習，切記！一、線性表1.設線性表為（6，10，16，4），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(shù)據(jù)。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾結(jié)點*

2、/head= （1） ;a.next=&b;b.next=&c;c.next=&d; （2） ; /*以上結(jié)束建表過程*/p=head; /*p為工作指針，準備輸出鏈表*/do printf(“%dn”, （3） ); （4） ; while( （5） );答案：（1）&a（2）d×next=NULL（3）p->data（4）p=p->next（5）p!=NULL2. 以下函數(shù)在head為頭指針的具有頭結(jié)點的單向鏈表中刪除第i個結(jié)點， struct node int data;struct node *next;typedef struct

3、 node NODE int delete(NODE *head,int i )NODE *p,*q; int j; q=head;j=0; while(q!=NULL)&&( _(1)_) _(2)_;j+; if(q=NULL) return(0); p= _(3)_; _(4)_=p->next; free(_(5)_); return(1);答案：（1）j<i-1（2）q=q->next（3）q->next（4）q->next（5）p3.將新元素插入到線性表中的第i位，MAX是數(shù)組的個數(shù)，a0用以存放線性表長度，b存放待插入的元素值，i存放

4、插入的位置，n存放線性表長度int aMAX;int i,j,b,n;scanf(“%d%d%d”,&b,&i,&n);for(j=1;j<=n;j+)scanf(“%d”,&aj);a0=n;for(j=n; （1） ;j- -) （2） ; （3） ; （4） ;for(j=1;j<=a0;j+)printf(“%5dn”,aj);答案：（1）j>=i（2）aj+1=aj（3）ai=b（4）a0=n+14.用頭插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的算法NODE *create(n)NODE *head,*p,*q;int ip=(NODE

5、 *)malloc(sizeof(NODE); （1） ; （2） ; （3） ;for(i=1;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);p->data=i;if(i=1) （4） ;else （5） ; （6） ;return(head);答案：（1）head=p（2）p->next=NULL（3）q=p（4）p->next=NULL（5）p->next=q->next（6）q->next=p一、 棧1. 以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針struct node ElemType

6、data;struct node *next;struct node *top ;void Push(ElemType x) struct node *p; p=(struct node*)malloc(_(1)_); p->data=x; _(2)_; 答案：（1）sizeof (struct node)（2）p->next=top（3）top=p二、 隊列1. 以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *

7、front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p->data=x; p->next=NULL; _(2)_; rear= _(3)_; 答案：（1）malloc(sizeof (struct node)（2）rear->next=p（3）p2. 以下函數(shù)為鏈隊列的出隊操作（鏈隊列帶有頭結(jié)點），出隊結(jié)點的數(shù)據(jù)域的值由x返回，front、rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struc

8、t node *front，*rear; ElemType OutQueue() ElemType x; if(_(1)_) printf("隊列下溢錯誤！n"); exit(1); else struct node *p=front->next; x=p->data; front->next= _(2)_; if(p->next=NULL) rear=front; free(p); _(3)_; 答案：（1）front= =rear（2）p->next（3）return(x)三、 樹1.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格

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

10、e *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 答案：（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）Postord

11、er(BT->right)（3）printf(“%c”,BT->data);四、 圖五、 排序1以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進行排序，完成程序中的空格部分，其中n是元素個數(shù)，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.key>ai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break; 程序中flag的功能是（5） 答案：（1）j&

12、lt;=n-1（2）i<=n-j（3）ai=ai+1（4）ai+1=temp（5）當某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán)2. 以下函數(shù)為直接選擇排序算法，對a1,a2,an中的記錄進行直接選擇排序，完成程序中的空格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<= _(2)_;j+) if(aj.key<ak.key) _(3)_; if(i!=k) temp=ai;_(4)_;_(5)

13、_;答案：（1）n-1（2）n（3）k=j（4）ai=ak（5）ak=temp3.直接插入排序算法Void disort(NODE a,int n)int I,j;NODE temp;for(i=1;i<n;i+)temp=ai; （1） ;while(j>=0&&temp.key<aj.key) （2） ; （3） ; （4） ;答案：（1）j=i-1（2）aj+1=aj（3）j-（4）aj+1=temp4.快速排序void quicksort(NODE a,int start,int end)int iI,j;NODE mid;if(start>=e

14、nd)return; （1） ; （2） ;mid=ai;while( （3） )while(i<j)&&aj.key>mid.key) （4） ;if( （5） ;) （6） ; （7） ;while(i<j&&ai.key<=mid.key) （8） ;if(i<j) （9） ; （10） ;ai=mid; （11） ;答案：（1）i=start（2）j=end（3）i<j（4）j-也可能將此條語句寫出，要填寫其條件中的aj.key>mid.key（5）i<j（6）ai=aj（7）i+（8）i+也可能將此條語句

15、寫出，要填寫其條件中的ai.key<=mid.key（9）aj=ai（10）j-（11）quicksort(a,start,i-1)（12）quicksort(a,i+1,end)最后兩句要填的概率會很高，要注意快速排序的考點很多，一般只會有三到四個空。5.直接選擇排序void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i<=n-1;i+) （1） ;for(j= （2） ;j<=n;j+)if(aj.key<ak.key) （3） ;if( （4） ) （5） ; （6） ; （7） ;答案：（1）k=i（2）i

16、+1（3）k=j（4）i!=k（5）temp=ai（6）ai=ak（7）ak=temp前四句較為重要6.堆排序中的篩選算法void heapshift(NODE a,int I,int n)NODE temp;int j;temp=ai; （1） ;while(j<n)if(j+1<n&&aj.key>aj+1.key) （2） ;if(temp.key>aj.key) （3） ; （4） ; （5） ;elsebreak; （6） ;答案：（1）j=2*i（2）j+（3）ai=aj（4）i=j（5）j=2*i（6）ai=temp這是構(gòu)建的小根堆，若是大

17、根堆，只要將if語句中的aj.key>aj+1.key改為<，再將第二個if語句中的>改為<即可7.堆排序void heapsort(NODE a,int n)int iNODE temp;for(i= （1） ;i>=1;i-) （2） ;for(i=n;i>1;i-)temp=a1; （3） ; （4） ; （5） ;答案：（1）n/2（2）heapshift(a,i,n)（3）a1=ai（4）ai=temp（5）heapshift(a,1,i-1)8.兩個有序序列的歸并void merge(NODE a,int s,int m,int n,NODE o

18、rder)int i=s,j=m+1,k=s;while( （1） )&&( （2） )if(ai.key<=aj.key) （3） ;else （4） ;if(i>m)while(j<=n) （5） ;ElseWhile(i<=m) （6） ;答案：（1）i<=m（2）j<=n（3）orderk+=ai+可保留此句，將其條件語句去掉（4）orderk+=aj+可保留此句，將其條件語句去掉（5）Orderk+=aj+可保留此句，將其條件語句去掉（6）orderk+=ai+可保留此句，將其條件語句去掉第（3）（4）空與第（5）（6）空有較直接的

19、關(guān)聯(lián)，因此一般情況下若要求填（3）（4）就不會要求填（5）（6），若（5）（6）位要填也是填其條件句七、查找1. 以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 答案：（1）low<=high（2）mid（3）amid.key<k;（4）high=mid-1（5）return -1;此為折半查找的非遞歸算法2. 1. 以下函數(shù)在a0到an-1中，用折半查找的遞歸算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格int Binary_