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

1、精品文檔 數(shù)據(jù)結(jié)構(gòu)考試題參考答案 1、設(shè)順序表 L 中的數(shù)據(jù)元素遞增有序。試寫一算法，將數(shù)據(jù)元素 x 插入到順序表 L 的適當(dāng) 位置，以保持該表的有序性。 解：存儲結(jié)構(gòu)為： typedef struct SeqList DataType *data; int MaxLen; int len; SeqList; 算法如下： void insertLx(SeqList int i=L.len-1; while(i=0 / 找 x 的前驅(qū)結(jié)點(diǎn) p; if(!p- next) return; /若不存在結(jié)點(diǎn)x,則返回； q=new Lnode; q-data=y; q-next=p-next; p-n

2、ext=q; 3、試寫一個(gè)算法,統(tǒng)計(jì)帶頭指針的單鏈表L 的元素個(gè)數(shù)。 解：存儲結(jié)構(gòu)如下： typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 算法如下： int length(LinkList L) int len=0; Lnode *p=L; while(p) len+; p=p-next; return len; 注：如果單鏈表是帶頭結(jié)點(diǎn)的，則算法如下： int length(LinkList L) int len=0; Lnode *p=L-next; while(p) len+; p=p-n

3、ext; return len; 4、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L 的第 k 個(gè)結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)x。 解： 存儲結(jié)構(gòu)如下： typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 算法如下： void insert_after_k( LinkList L, int k, ElemType x) if(k0) return; Lnode *q, *p=L; int i=0; while(p / 找到第 k 個(gè)結(jié)點(diǎn) p; if(!p) return; / 若不存在第 k 個(gè)結(jié)點(diǎn)，則返回； q=new

4、 Lnode; q-data=x; q-next=p-next; p-next=q; 注：如果是在L的第k個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，則找第 k-1個(gè)結(jié)點(diǎn)p,然后插入。 5、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L中刪除所有的數(shù)據(jù)元素為x的結(jié)點(diǎn)。 解： 存儲結(jié)構(gòu)如下： typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 算法如下： void Delete_all_x(LinkList L, Elemtype x) Lnode *p, *q; p=L; while(p) if(p-next p-next=q-ne

5、xt; delete q; else p=p-next; 注意：要刪除所有的值為 x 的結(jié)點(diǎn)。 6、假設(shè)一個(gè)單循環(huán)鏈表L的數(shù)據(jù)域?yàn)檎?，設(shè)計(jì)一個(gè)算法，求該表中所有結(jié)點(diǎn)的數(shù)據(jù)之和。 解： 存儲結(jié)構(gòu)如下： typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 假設(shè)L帶頭結(jié)點(diǎn)，且L指向頭結(jié)點(diǎn)，則算法如下： int sum_Of_Data(LinkList L) int s=0; Lnode *p=L-next; while(p!=L) s+=p-data; p=p-next; return s; 假設(shè)L不帶

6、頭結(jié)點(diǎn)，且L指向循環(huán)鏈表中任何一個(gè)結(jié)點(diǎn)，則算法如下： int sum_of_data(LinkList L) 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; 注：以上兩種情形，只要給出其中一種情形的解即可。 7、假設(shè)二叉樹用二叉鏈表存儲，設(shè)計(jì)一個(gè)算法，求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。 解：存儲結(jié)構(gòu)如下： typedef struct bitnode ElemType data; struct bitnode *lchild, *rchild; bitnode, *bitre

7、e; 算法如下： int nodes(bitree T) if(!T) return 0; else return (1+nodes(T-lchild)+nodes(T-rchild); 8、寫一個(gè)算法，建立二叉樹的二叉鏈表。 解：存儲結(jié)構(gòu)如下： typedef char ElemType; typedef struct bitnode ElemType data; struct bitnode *lchild, *rchild; bitnode, *bitree; 算法如下： void creat_bitree(bitree cin ch; if(ch= #)T=0; else T=new

8、bit no de; T-data=ch; creat_bitree(T-lchuild); creat_bitree(T-rchild); 或者寫成以下算法： bitree creat_bitree(void) /按擴(kuò)展的先序序列輸入結(jié)點(diǎn)，輸入#表示空。 bitree T; ElemType ch; cin ch; if(ch= #)T=0; else T=new bit no de; T-data=ch; creat_bitree(T-lchuild); creat_bitree(T-rchild); return T; 9、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ中序序列為ABC

9、DEFGHIJK請畫出該二叉樹, 并寫出后序序列。 解：該二叉樹如下： ABCDEFGH，中序序列為DBGEHJAC，請畫出該二叉樹, 后序序列為：ACDBGJKIHFE 10、假設(shè)一棵二叉樹的層次序列為 并寫出其先序序列和后序序列。 解：該二叉樹如下： 先序序列為：ABDEGHJCFI 后序序列為：DGJHEBIFCA 11、編寫一個(gè)遞歸算法，將用二叉鏈表表示的二叉樹的所有結(jié)點(diǎn)的左、右子樹交換。 解：存儲結(jié)構(gòu)如下： typedef char ElemType; typedef struct bit node ElemType data; struct bit node *lchild, *r

10、child; bit no de, *bitree; 算法如下： void excha nge(bitree bitree temp; temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; excha nge(T-lchild); excha nge(T-rchild); 12、試寫出二叉鏈表表示的二叉樹的先序遍歷的非遞歸算法。 解：存儲結(jié)構(gòu)如下： typedef char ElemType; typedef struct bit node ElemType data; struct bit node *lchild, *rchild; bit no de, *bitree; 6歡迎下載 精品文檔 算法如下： void preorder(bitree T) / 先序遍歷，當(dāng)前結(jié)點(diǎn)入棧。 #define MaxNum 20 bitree stackMaxNum; int top=0; / 指向棧頂?shù)南乱晃恢谩?bitnode *p; p=T; while(p | top0) while(p) coutdata; stacktop+=p; p=