數(shù)據(jù)結(jié)構(gòu)試題大題編程與參考答案

1、WORD格式數(shù)據(jù)構(gòu)造考試題參考答案1、設(shè)順序表L 中的數(shù)據(jù)元素遞增有序。試寫一算法，將數(shù)據(jù)元素x 插入到順序表L 的適當(dāng)位置，以保持該表的有序性。解：存儲(chǔ)構(gòu)造為：typedefstructSeqList DataType *data; int MaxLen;intlen;SeqList;算法如下：void insertLx(SeqList &L, DataType x) if(L.len=L.maxlen) return;int i=L.len-1;while(i>=0 && x<L.datai) L.datai+1=L.datai; i=i-1;L.dat

2、ai+1=x; L.len+;2、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L 的元素 x 前插入一個(gè)結(jié)點(diǎn)y。解：存儲(chǔ)構(gòu)造如下：typedefstructLnodeElemType data;struct Lnode *next;Lnode,*LinkList;算法如下：void insert_y_before_x(LinkListL, ElemType x, ElemType y) Lnode*q, *p=L;while(p->next && p->next->data!=x)p=p->next; / 找 x 的前驅(qū)結(jié)點(diǎn) p;if(!p->next) re

3、turn;/ 假設(shè)不存在結(jié)點(diǎn) x，那么返回；q=new Lnode;q->data=y; q->next=p->next; p->next=q;3、試寫一個(gè)算法，統(tǒng)計(jì)帶頭指針的單鏈表L 的元素個(gè)數(shù)。解：存儲(chǔ)構(gòu)造如下：typedefstructLnodeElemType data;struct Lnode *next;Lnode,*LinkList;算法如下：int length(LinkList L) int len=0; Lnode *p=L;while(p) len+;p=p->next; 專業(yè)資料整理WORD格式returnlen;注：如果單鏈表是帶頭結(jié)點(diǎn)的

4、，那么算法如下：int length(LinkList L) int len=0;Lnode *p=L->next;while(p) len+;p=p->next; returnlen;專業(yè)資料整理WORD格式4、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L 的第k 個(gè)結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)x。專業(yè)資料整理WORD格式解：存儲(chǔ)構(gòu)造如下：專業(yè)資料整理WORD格式typedefstructLnode專業(yè)資料整理WORD格式ElemType data;struct Lnode *next;專業(yè)資料整理WORD格式Lnode,*LinkList;專業(yè)資料整理WORD格式算法如下：voidinsert_a

5、fter_k( LinkList L,intk,ElemTypex) if(k<0) return;Lnode *q, *p=L;int i=0;while(p && i<k) i+;p=p->next; / 找到第 k 個(gè)結(jié)點(diǎn) p;if(!p) return;/ 假設(shè)不存在第k 個(gè)結(jié)點(diǎn)，那么返回；q=new Lnode;q->data=x;q->next=p->next;p->next=q;專業(yè)資料整理WORD格式注：如果是在L 的第 k 個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，那么找第k-1 個(gè)結(jié)點(diǎn)、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表中刪除所有的數(shù)據(jù)元

6、素為p，然后插入。x 的結(jié)點(diǎn)。專業(yè)資料整理WORD格式解：存儲(chǔ)構(gòu)造如下：專業(yè)資料整理WORD格式typedefstructLnodeElemType data;struct Lnode *next;Lnode,*LinkList;算法如下：voidDelete_all_x(LinkList L, Elemtype x) Lnode *p, *q;p=L;while(p) if(p->next && p->next->data=x)q=p->next;p->next=q->next;delete q; elsep=p->next;注意：要

7、刪除所有的值為x 的結(jié)點(diǎn)。專業(yè)資料整理WORD格式、假設(shè)一個(gè)單循環(huán)鏈表的數(shù)據(jù)域?yàn)檎停O(shè)計(jì)一個(gè)算法， 求該表中所有結(jié)點(diǎn)的數(shù)據(jù)之和。解：存儲(chǔ)構(gòu)造如下：typedefstructLnodeElemType data;struct Lnode *next;Lnode,*LinkList;假設(shè)帶頭結(jié)點(diǎn)，且指向頭結(jié)點(diǎn)，那么算法如下：專業(yè)資料整理WORD格式int sum_Of_Data(LinkListL)專業(yè)資料整理WORD格式 int s=0;Lnode *p=L->next;專業(yè)資料整理WORD格式while(p!=L) s+=p->data;p=p->next; 專業(yè)資料整理W

8、ORD格式return s; 假設(shè)不帶頭結(jié)點(diǎn)，且指向循環(huán)鏈表中任何一個(gè)結(jié)點(diǎn)，那么算法如下：int sum_of_data(LinkListL) int s=0;Lnode *p=L;if(L) s+=p->data; p=p->next; while(p!=L) s+=p->data; p=p->next; return s;注：以上兩種情形，只要給出其中一種情形的解即可。、假設(shè)二叉樹用二叉鏈表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。解：存儲(chǔ)構(gòu)造如下：typedef struct bitnodeElemTypedata;struct bitnode *lchild,*r

9、child;bitnode, *bitree;算法如下：int nodes(bitree T) if(!T) return 0;else return (1+nodes(T->lchild)+nodes(T->rchild);、寫一個(gè)算法，建立二叉樹的二叉鏈表。解：存儲(chǔ)構(gòu)造如下：typedef charElemType;typedef struct bitnodeElemTypedata;struct bitnode *lchild,*rchild;bitnode, *bitree;算法如下：void creat_bitree(bitree &T) / 按擴(kuò)展的先序序列輸入

10、結(jié)點(diǎn)，輸入表示空。專業(yè)資料整理WORD格式ElemType ch;cin>>ch;if(ch= #)T=0;else T=new bitnode;T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);或者寫成以下算法：bitreecreat_bitree(void) / 按擴(kuò)展的先序序列輸入結(jié)點(diǎn)，輸入表示空。bitreeT;ElemType ch;cin>>ch;if(ch= #)T=0;else T=new bitnode;T->data=ch;creat_bitree(T-&g

11、t;lchuild);creat_bitree(T->rchild);returnT;9、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ ，中序序列為ABCDEFGHIJK ，請(qǐng)畫出該二叉樹，并寫出后序序列。解：該二叉樹如下：專業(yè)資料整理WORD格式后序序列為： ACDBGJKIHFE 。10、假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ ，中序序列為DBGEHJACIF ，請(qǐng)畫出該二叉樹，并寫出其先序序列和后序序列。解：該二叉樹如下：先序序列為： ABDEGHJCFI ；后序序列為： DGJHEBIFCA 。11、編寫一個(gè)遞歸算法，將用二叉鏈表表示的二叉樹的所有結(jié)點(diǎn)的左、右子樹交換

12、。解：存儲(chǔ)構(gòu)造如下：typedef charElemType;typedef struct bitnodeElemTypedata;struct bitnode *lchild,*rchild;bitnode, *bitree;算法如下：void exchange(bitree &T)if(!T) return;bitree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);12、試寫出二叉鏈表表示的二叉樹的先序遍歷的非遞歸算法。解：存儲(chǔ)構(gòu)造如下：typedef charElemType;typedef struct bitnodeElemTypedata;struct bitnode *lchild,*rchild;bitnode, *bitree;專業(yè)資料整理WORD格式算法如下：void preorder(bitree T) / 先序遍歷，當(dāng)前結(jié)點(diǎn)入棧。專業(yè)資料整理WORD格式#defineMaxNum 20bitree stackMaxNum;int top=0;/ 指向棧頂?shù)南乱晃恢?。bitnode