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

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

2、 若不存在結(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ǔ)結(jié)構(gòu)如下：typedef struct LnodeElemType 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

3、=0;Lnode *p=L-next;while(p) len+; p=p-next; return len;4、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L的第k個(gè)結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)x。解：存儲(chǔ)結(jié)構(gòu)如下：typedef struct LnodeElemType 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 & inext; /找到第k個(gè)結(jié)點(diǎn)p;if(!p) re

4、turn; /若不存在第k個(gè)結(jié)點(diǎn)，則返回；q=new 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，然后插入。、試寫一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表中刪除所有的數(shù)據(jù)元素為x的結(jié)點(diǎn)。解：存儲(chǔ)結(jié)構(gòu)如下：typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法如下：void Delete_all_x(LinkList L, Elemtype x) Lnode *p, *q; p=L; while(p) if(p-ne

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

6、=p-next; return s; 假設(shè)不帶頭結(jié)點(diǎn)，且指向循環(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;注：以上兩種情形，只要給出其中一種情形的解即可。、假設(shè)二叉樹用二叉鏈表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。解：存儲(chǔ)結(jié)構(gòu)如下：typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;b

7、itnode, *bitree;算法如下：int nodes(bitree T) if(!T) return 0; else return (1+nodes(T-lchild)+nodes(T-rchild);、寫一個(gè)算法，建立二叉樹的二叉鏈表。解：存儲(chǔ)結(jié)構(gòu)如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void creat_bitree(bitree &T) /按擴(kuò)展的先序序列輸入結(jié)點(diǎn)，輸入表示空。ElemTy

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

9、EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)畫出該二叉樹，并寫出后序序列。解：該二叉樹如下：后序序列為：ACDBGJKIHFE。10、假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF，請(qǐng)畫出該二叉樹，并寫出其先序序列和后序序列。解：該二叉樹如下：先序序列為：ABDEGHJCFI；后序序列為：DGJHEBIFCA。11、編寫一個(gè)遞歸算法，將用二叉鏈表表示的二叉樹的所有結(jié)點(diǎn)的左、右子樹交換。解：存儲(chǔ)結(jié)構(gòu)如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode

10、 *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ǔ)結(jié)構(gòu)如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void preorder(bitree T) /先序遍歷，當(dāng)前結(jié)點(diǎn)入棧。#define MaxNum 20bitree stackMaxNum;int top=0; /指向棧