《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題(總13頁)

《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題 說明：本文檔中涉及到的算法并非本書的全部，有些可根據(jù)此處的情況自行看書和作業(yè)題，黑色為綜合練習(xí)上的題目，紅色為我另增加的題，這些空的選擇是根據(jù)我個(gè)人的經(jīng)驗(yàn)來決定的并不能完全代表中央電大的出卷老師，因此一定不能有肯定就考這些題目的想法。不能放棄其他內(nèi)容的復(fù)習(xí)，切記！?。? 一、線性表 1.設(shè)線性表為（6，10，16，4），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(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é)點(diǎn)*/ head= （1） ; a.next=&b; b.next=&c; c.next=&d; （2） ; /*以上結(jié)束建表過程*/ p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/ do {printf(“%d\n”, （3） ); （4） ; }while( （5） ); } 答案： （1）&a （2）dnext=NULL （3）p->data （4）p=p->next （5）p!=NULL 2. 以下函數(shù)在head為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第i個(gè)結(jié)點(diǎn)， struct node { int data; struct node *next; }; typedef struct 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）p 3.將新元素插入到線性表中的第i位，MAX是數(shù)組的個(gè)數(shù)，a[0]用以存放線性表長度，b存放待插入的元素值，i存放插入的位置，n存放線性表長度 { int a[MAX]; int i,j,b,n; scanf(“%d%d%d”,&b,&i,&n); for(j=1;j<=n;j++) scanf(“%d”,&a[j]); a[0]=n; for(j=n; （1） ;j- -) （2） ; （3） ; （4） ; for(j=1;j<=a[0];j++) printf(“%5d\n”,a[j]); } 答案： （1）j>=i （2）a[j+1]=a[j] （3）a[i]=b （4）a[0]=n+1 4.用頭插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法 NODE *create(n) { NODE *head,*p,*q; int i p=(NODE *)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ù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針 struct node { ElemType 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 二、 隊(duì)列 1. 以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針 struct node { ElemType data; struct node *next; }; struct node *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）p 2. 以下函數(shù)為鏈隊(duì)列的出隊(duì)操作（鏈隊(duì)列帶有頭結(jié)點(diǎn)），出隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域的值由x返回，front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針 struct node { ElemType data; struct node *next; }; struct node *front，*rear; ElemType OutQueue() { ElemType x; if(___(1)_____) { printf("隊(duì)列下溢錯誤！\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.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 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é)點(diǎn)）。 void Inorder (struct BTreeNode *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é)點(diǎn)）。 void Postorder (struct BTreeNode *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; } } 答案： （1）Postorder(BT->left) （2）Postorder(BT->right) （3）printf(“%c”,BT->data); 四、 圖 五、 排序 1．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進(jìn)行排序，完成程序中的空格部分，其中n是元素個(gè)數(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(a[i].key>a[i+1].key) {flag=1; temp=a[i]; （3） ; （4） ; } if(flag= =0)break; } } 程序中flag的功能是（5） 答案： （1）j<=n-1 （2）i<=n-j （3）a[i]=a[i+1] （4）a[i+1]=temp （5）當(dāng)某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán) 2. 以下函數(shù)為直接選擇排序算法，對a[1],a[2],…a[n]中的記錄進(jìn)行直接選擇排序，完成程序中的空格 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(a[j].key<a[k].key) __(3)______; if(i!=k) { temp=a[i]; ___(4)_____; ____(5)____; } } } 答案： （1）n-1 （2）n （3）k=j （4）a[i]=a[k] （5）a[k]=temp 3.直接插入排序算法 Void disort(NODE a[],int n) { int I,j; NODE temp; for(i=1;i<n;i++) { temp=a[i]; （1） ; while(j>=0&&temp.key<a[j].key) { （2） ; （3） ; } （4） ; } } 答案： （1）j=i-1 （2）a[j+1]=a[j] （3）j-- （4）a[j+1]=temp 4.快速排序 void quicksort(NODE a[],int start,int end) { int iI,j; NODE mid; if(start>=end) return; （1） ; （2） ; mid=a[i]; while( （3） ) { while(i<j)&&a[j].key>mid.key) （4） ;; if( （5） ;) { （6） ;; （7） ;; } while(i<j&&a[i].key<=mid.key) （8） ;; if(i<j) { （9） ;; （10） ;; } } a[i]=mid; （11） ;; ; } 答案： （1）i=start （2）j=end （3）i<j （4）j-- 也可能將此條語句寫出，要填寫其條件中的a[j].key>mid.key （5）i<j （6）a[i]=a[j] （7）i++ （8）i++ 也可能將此條語句寫出，要填寫其條件中的a[i].key<=mid.key （9）a[j]=a[i] （10）j-- （11）quicksort(a,start,i-1) （12）quicksort(a,i+1,end) 最后兩句要填的概率會很高，要注意快速排序的考點(diǎn)很多，一般只會有三到四個(gè)空。 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(a[j].key<a[k].key) （3） ; if( （4） ) { （5） ; （6） ; （7） ; } } } 答案： （1）k=i （2）i+1 （3）k=j （4）i!=k （5）temp=a[i] （6）a[i]=a[k] （7）a[k]=temp 前四句較為重要 6.堆排序中的篩選算法 void heapshift(NODE a[],int I,int n) { NODE temp;int j; temp=a[i]; （1） ; while(j<n) { if(j+1<n&&a[j].key>a[j+1].key) （2） ; if(temp.key>a[j].key) { （3） ; （4） ; （5） ; } else break; } （6） ; } 答案： （1）j=2*i （2）j++ （3）a[i]=a[j] （4）i=j （5）j=2*i （6）a[i]=temp 這是構(gòu)建的小根堆，若是大根堆，只要將if語句中的a[j].key>a[j+1].key改為<，再將第二個(gè)if語句中的>改為<即可 7.堆排序 void heapsort(NODE a[],int n) { int i NODE temp; for(i= （1） ;i>=1;i--) （2） ; for(i=n;i>1;i--) { temp=a[1]; （3） ; （4） ; （5） ; } } 答案： （1）n/2 （2）heapshift(a,i,n) （3）a[1]=a[i] （4）a[i]=temp （5）heapshift(a,1,i-1) 8.兩個(gè)有序序列的歸并 void merge(NODE a[],int s,int m,int n,NODE order[]) { int i=s,j=m+1,k=s; while(( （1） )&&( （2） )) if(a[i].key<=a[j].key) （3） ; else （4） ; if(i>m) while(j<=n) （5） ; Else While(i<=m) （6） ; } 答案： （1）i<=m （2）j<=n （3）order[k++]=a[i++] 可保留此句，將其條件語句去掉 （4）order[k++]=a[j++] 可保留此句，將其條件語句去掉 （5）Order[k++]=a[j++] 可保留此句，將其條件語句去掉 （6）order[k++]=a[i++] 可保留此句，將其條件語句去掉 第（3）（4）空與第（5）（6）空有較直接的關(guān)聯(lián)，因此一般情況下若要求填（3）（4）就不會要求填（5）（6），若（5）（6）位要填也是填其條件句 七、查找 1. 以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-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(a[mid].key==k) return __(2)______; else if(___(3)_____) low=mid+1; else __(4)______; } ___(5)_____; } 答案： （1）low<=high （2）mid （3）a[mid].key<k; （4）high=mid-1 （5）return -1; 此為折半查找的非遞歸算法 2. 1. 以下函數(shù)在a[0]到a[n-1]中，用折半查找的遞歸算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-1，完成程序中的空格 int Binary_Search(NODE a[],int low,int high,int k) { if(low<=high) { int mid= （1） ; if( （2） ) return mid; else if( （3） ) （4） ; else （5） ;; } else return -1; } 答案： （1）mid=(low+high)/2 （2）a[mid].key==k （3）a[mid].key<k （4）return(a[],low,mid-1,k) （5）return(a[],mid+1,high,k) 3. 以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格 typedef struct Bnode { int key; struct Bnode *left; struct Bnode *right; } Bnode; Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/ { Bnode *p; if(bt== ___(1)_____) return (bt); p=bt; while(p->key!= __(2)______) { if(k<p->key) ___(3)_____; else ___(4)_____; if(p==NULL) break; } Return(___(5)_____); } 答案： （1）NULL （2）k （3）p=p->left （4）p=p->right （5）p