數(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 &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.datai+1

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

3、n; / 若不存在結(jié)點x，則返回；q=new Lnode;q->data=y; q->next=p->next; p->next=q;3、試寫一個算法，統(tǒng)計帶頭指針的單鏈表L的元素個數(shù)。解：存儲結(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é)點的，則算法如下：int le

4、ngth(LinkList L) int len=0;Lnode *p=L->next;while(p) len+; p=p->next; return len;4、試寫一個算法，在帶頭結(jié)點的單鏈表L的第k個結(jié)點后插入一個結(jié)點x。解：存儲結(jié)構(gòu)如下：typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法如下：void insert_after_k( LinkList L, int k, ElemType x) if(k<0) return; Lnode *q, *p=L;int i=0;

5、while(p && i<k) i+; p=p->next; /找到第k個結(jié)點p;if(!p) return; /若不存在第k個結(jié)點，則返回；q=new Lnode; q->data=x; q->next=p->next; p->next=q;注：如果是在L的第k個結(jié)點前插入一個結(jié)點，則找第k-1個結(jié)點p，然后插入。、試寫一個算法，在帶頭結(jié)點的單鏈表中刪除所有的數(shù)據(jù)元素為x的結(jié)點。解：存儲結(jié)構(gòu)如下：typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法

6、如下：void Delete_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; else p=p->next;注意：要刪除所有的值為x的結(jié)點。、假設(shè)一個單循環(huán)鏈表的數(shù)據(jù)域為整型，設(shè)計一個算法，求該表中所有結(jié)點的數(shù)據(jù)之和。解：存儲結(jié)構(gòu)如下：typedef struct LnodeElemType data; struct Lnode *ne

7、xt;Lnode, *LinkList;假設(shè)帶頭結(jié)點，且指向頭結(jié)點，則算法如下：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è)不帶頭結(jié)點，且指向循環(huán)鏈表中任何一個結(jié)點，則算法如下：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

8、; return s;注：以上兩種情形，只要給出其中一種情形的解即可。、假設(shè)二叉樹用二叉鏈表存儲，設(shè)計一個算法，求二叉樹的結(jié)點個數(shù)。解：存儲結(jié)構(gòu)如下：typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：int nodes(bitree T) if(!T) return 0; else return (1+nodes(T->lchild)+nodes(T->rchild);、寫一個算法，建立二叉樹的二叉鏈表。解：存儲結(jié)構(gòu)如下：typedef char El

9、emType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void creat_bitree(bitree &T) /按擴展的先序序列輸入結(jié)點，輸入表示空。ElemType ch; cin>>ch;if(ch=#) T=0;else T=new bitnode; T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);或者寫成以下算法：bitree crea

10、t_bitree(void) /按擴展的先序序列輸入結(jié)點，輸入表示空。bitree T;ElemType ch; cin>>ch;if(ch=#) T=0;else T=new bitnode; T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);return T;9、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹，并寫出后序序列。解：該二叉樹如下：后序序列為：ACDBGJKIHFE。10、假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列

11、為DBGEHJACIF，請畫出該二叉樹，并寫出其先序序列和后序序列。解：該二叉樹如下：先序序列為：ABDEGHJCFI；后序序列為：DGJHEBIFCA。11、編寫一個遞歸算法，將用二叉鏈表表示的二叉樹的所有結(jié)點的左、右子樹交換。解：存儲結(jié)構(gòu)如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void exchange(bitree &T)if(!T) return; bitree temp;temp=T-&

12、gt;lchild;T->lchild=T->rchild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);12、試寫出二叉鏈表表示的二叉樹的先序遍歷的非遞歸算法。解：存儲結(jié)構(gòu)如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void preorder(bitree T) /先序遍歷，當(dāng)前結(jié)點入棧。#define MaxNum 20bitree stackMaxNum;int top=0; /指向棧頂?shù)南乱晃恢?。bitnode *p;p=T;while(p | top>0