數(shù)據(jù)結(jié)構(gòu)習(xí)題19324

1、習(xí)題4-11.有六個元素A、B、C、D、E、F依次進棧，允許任何時候出棧，能否得到下列每個序列。（1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD2. 有4個元素a,b,c,d依次進棧，任何時侯都可以出棧，請寫出所有可能出棧序列和所有不存在的序列。3.用一維數(shù)組a7順序存儲一個循環(huán)隊列，隊首和隊尾指針分別用front和rear表示，當(dāng)前隊列中已有五個元素：23，45，67，80，34，其中，23尾隊首元素，front的值為3，請畫出對應(yīng)的存儲狀態(tài)，當(dāng)連續(xù)做4次出隊運算后，再讓15，36，48元素依次進隊，請再次畫出對應(yīng)的存儲狀態(tài)。4. 假定用于順序存儲一個隊列的數(shù)組

2、的長度為N，隊首和隊尾指針分別為front和rear，寫出求此長度（即所含元素個數(shù)）的公式。習(xí)題4-2 算法分析，寫出該算法的功能。1 int AE(int a,int n) if(n=0) return 0; else return an-1+AE(a,n-1);2.int AF(int k,int s)/第一次使用AF(0,0)調(diào)用此算法if(s>=100) return k-1;else k+;s+=k*k;return AF(k,s); 3. void Fun1(Stack& s1,int n) srand(time(0); int i=0,j; while(i<n

3、) int x=rand()%100; int y=int(sqrt(x); for(j=2;j<=y;j+) if(x%j=0)break; if(j>y&&x>10)i+;Push(s1,x); 4. void Fun2(Queue& q1,Queue& q2,int n) int i,x;cout<<”從鍵盤輸入”<<n<<”個正整數(shù):”<<endl; for(int i=1;i<=n;i+)cin>>x;if(x%2) Enqueue(q1,x);else Enqueue

4、(q2,x); 習(xí)題4-3 算法設(shè)計1. 寫出采用遞歸方法求1n之間所有整數(shù)的平方和的算法。2. 采用遞歸方法把任一十進制正整數(shù)轉(zhuǎn)換為S進制（2S9）數(shù)輸出。3. 采用輾轉(zhuǎn)相除法和遞歸的方法求出兩個正整數(shù)的最大公約數(shù)。4. 采用遞歸方法求兩個正整數(shù)的最小公倍數(shù)。5. 裴波那契(Fibonacci)數(shù)列的定義為：它的第1項和第2項為0和1，以后各項為其前兩項之和。若裴波那契數(shù)列中的第n項用Fib(n)表示，則計算公式為： Fib(n)=試編寫計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復(fù)雜度和空間復(fù)雜度。習(xí)題5-1 運算題1.已知一棵度為m的樹中有n個度為1的結(jié)點，n個度為2的結(jié)點，

5、n個度為m的結(jié)點，問樹中有多少個葉子結(jié)點？2.畫出由三個結(jié)點a、b、c組成的所有不同結(jié)構(gòu)的二叉樹，則共有多少種不同的結(jié)構(gòu)？每一種結(jié)構(gòu)又對應(yīng)多少種不同的值的排列次序？3. 設(shè)一棵二叉樹廣義表表示為a(b(c),d(e,f),分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。4. 設(shè)一棵二叉樹的廣義表表示為a(b(,e),c(f(h,i),d)分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。5. 已知一棵二叉樹的先根和中根序列，求該二叉樹的后根序列。 先根序列：A,B,C,D,E,F,G,H,I,J 中根序列：C,B,A,E,F,D,I,H,J,G 后根序列：6. 已知一棵二叉樹中根和后根序列，

6、求出該二叉樹的高度和雙支、單支和葉子節(jié)點數(shù)。 中根序列：c,b,d,e,a,g,i,h,j,f后根序列：c,e,d,b,i,j,h,g,f,a習(xí)題5-21. 下面函數(shù)的功能是返回二叉樹BT中值為X的節(jié)點所在層號，請在劃有橫線的地方填寫合適的內(nèi)容。int Nodelevel(BTreeNode *BT,ElemType x)if(BT=NULL) return 0;else if(BT->data=X)return 1;else int c1=Nodelevel(BT->left,X);if(c1>=1)_;int c2=_;if_;/若樹中不存在X節(jié)點則返回0return 0

7、;2.指出下面函數(shù)的功能。BTreeNode* BTreeSwapX(BTreeNode* BT)if(BT=NULL) return NULL: else BTreeNode* pt = new BTreeNode; pt->data=BT->data; pt->right=BTreeSwapX(BT->left); pt-> left =BTreeSwapX(BT-> right); return pt; 3. 已知二叉樹中的節(jié)點類型StreeNode定義如下。struct StreeNode(datatype data;STreeNode *lchil

8、d,*rchild,*parent;);其中，data為節(jié)點值域，lchild和rchild分別為指向左、右孩子節(jié)點的指針域，parent為指向父親節(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中的參數(shù)ST指向一顆二叉樹，X保存一個節(jié)點的值。STreeNode* PN(STreeNode *ST,datatype& X)if(ST=NULL) return NULL;else StreeNode* mt;if(ST->dat=x) return ST->parent;else if(mt=PN(ST->lchild,X) return mt;else if(mt

9、=PN(ST->rchild,X) return mt;return NULL;4.指出下面函數(shù)的功能。void BTC(BTreeNode*BT)if(BT!=NULL) if(BT->left!=NULL && BT->right!=NULL)if(BT->left->data>BT->right->data) BTreeNode*t=BT->left;BT->left=BT->right;BT-right=t;BTC(BT->left);BTC(BT->right);5. 設(shè)BT指向一棵二叉樹，

10、該二叉樹的廣義表表示為a(b(a,d(f),c(e(,a(k),b),則依次使用BTC(BT,a,C)、BTC(BT,b,C)、BTC(BT,c,C)、BTC(BT,g,C)、調(diào)用下面算法時，假定每次調(diào)用時C的初值均為0，引用變量帶回值依次為_、_、_、_。void BTC(BTreeNode*BT,char x,int& k)if(BT!=NULL)if(BT->data=x) k+;BTC(BT->left,x,k);BTC(BT->right,x,k);6.下面函數(shù)功能void preserve(BTreeNode*BT,ElemType a,int n) st

11、atic int i=0;if(BT!=NULL) preserve(BT->left,a,n);ai+=BT->data;preserve(BT->right,a,n); 習(xí)題5-3 算法設(shè)計題1. 根據(jù)下面函數(shù)聲明編寫求一棵二叉樹BT中結(jié)點總數(shù)的算法，其值由函數(shù)返回。 int BTreeCount(BTreeNode*BT);2. 根據(jù)下面函數(shù)聲明編寫求一棵二叉樹中葉節(jié)點總數(shù)的算法，其值由函數(shù)返回。 int BTreeLeafCount(BTreeNode*BT);3. 寫出對二叉樹進行中序遍歷的非遞歸算法。習(xí)題6-1 運算題1. 已知一組元素為（46，25，78，62，

12、12，37，70，29），畫出按元素排列順序輸入生成一顆二叉搜索樹，再以廣義表形式給出該二叉搜索樹。2. 已知一顆二叉搜索樹的廣義表表示尾28（12（，16），49（34（30），72（63），若從中依次刪除72、12、49、28等4個節(jié)點，拭分別畫出每刪除一個節(jié)點后得到圖形表示的二叉搜索樹，并寫出對應(yīng)的廣義表表示。3從空堆開始依次向小根堆中插入集合38,64,52,15,73,40,48,55中的每個元素，試以順序表的形式給出每插入一個元素后堆的狀態(tài)。4. 已知一個堆為(12,15,40,38,26,52,48,64),若從堆中依次刪除4個元素，請給出每刪除一個元素后堆的狀態(tài)。5. 有七個帶

13、權(quán)結(jié)點，其權(quán)值分別為3、7、8、2、6、10、14，試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹，給出其廣義表表示，并計算出帶權(quán)路徑長度WPL。6. 在一份電文中共使用五種字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、9，試畫出對應(yīng)的編碼哈夫曼樹，求出每個字符的哈夫曼編碼，并求出傳送電文的總長度7. 一組關(guān)鍵字為（40，28，16，56，50，32，30，63），試依次插入節(jié)點生成一顆平衡二叉搜索樹，并標(biāo)明插入時所需平衡的類型。8.一組關(guān)鍵字為（36，75，83，54，12，67，60，40，92，72），試依次插入節(jié)點分別生成一顆二叉搜索樹和二叉平衡樹，并分別求查找每個元素的平均查找長

14、度。習(xí)題6-2 算法設(shè)計題1. 寫出對二叉樹進行中序遍歷的非遞歸算法。2. 編寫一個非遞歸算法求出二叉排序樹中的關(guān)鍵字最大的元素。習(xí)題7-1 運算題1. 對于圖7-30(a)和圖7-30(b)，求出：（1）每一個圖的二元組表示，對于帶權(quán)圖，可將邊的權(quán)寫在該邊的后面；（2）在圖7-30(a)中每個頂點的度，以及每個頂點的所有鄰接點和所有邊；（3）在圖7-30(b)中每個頂點的入度、出度和度，以及每個頂點的所有入邊的出邊；（4）在圖7-30(a)中從v到v的所有簡單路徑及相應(yīng)路徑長度；在圖7-30(b)中從v到v的所有簡單路徑及相應(yīng)帶權(quán)路徑長度。 0 8 1 1 3 4 0 2 7 2 9 2 1

15、 3 3 5 4 (a) (b) 圖 7-302 對于圖7-30(a)和圖7-30(b)，畫出：（1）每個圖的鄰接矩陣；（2）每個圖的鄰接表；（3）7-30(b)的逆鄰接表和十字鄰接表；（4）每個圖的邊集數(shù)組。3對于圖7-31(a)和圖7-31(b)，按下列條件試分別寫出從頂點v出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。（1）假定它們均采用鄰接矩陣表示；（2）假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。 0 0 1 2 1 6 5 4 7 9 3 4 5 8 6 7 8 2 (a) 3 (b) 圖 7-314. 已知一

16、個圖的二元組表示如下：V=0，1，2，3，4，5，6，7，8E=（0，3），（0，4），（1，2），（1，4），（2，4），（2，5），（3，6），（3，7），（4，7），（5，8），（6，7），（7，8）（1）畫出對應(yīng)的圖形。 （2）假定從定點0出發(fā)，給出鄰接矩陣表示的圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的頂點序列。 （3）假定從定點0出發(fā)，給出鄰接表表示的圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的頂點序列，假定每個頂點鄰接表中的節(jié)點都是按頂點序號從大到小的次序鏈接的。習(xí)題8-1 運算題。1. 對于圖8-32，做：（1）畫出最小生成樹并求出它的權(quán)；（2）從頂點v出發(fā)，按照普里姆算法并入最小生成樹中各邊的次序

17、寫出各條邊；（3）按照克魯斯卡算法并入最小生成樹中各邊的次序?qū)懗龈鳁l邊。 0 12 5 0 3 1 15 2 6 8 15 13 9 5 6 8 9 7 1 4 6 16 4 8 3 3 4 6 12 12 9 20 10 10 12 5 8 2 5 3 5 4 6 20 7 7 圖 8-32 圖 8-332. 對于圖8-33，利用狄克斯特拉算法求出從頂點v到其余各頂點的最短路徑，并畫出對應(yīng)的圖形表示。3. 已知一個圖的二元組表示為：V=0，1，2，3，4，5，6，7E=(0,1)8,(0,3)2,(0,5)10,(1,2)6,(1,4)20,(1,6)12,(2,4)10,(2,7)15,(

18、3,5)5,(3,6)7,(4,7)4,(5,6)6,(6,7)8(1) 按照克魯斯卡爾算法求最小生成樹，寫出依次得到的各條邊。(2) 按照狄克斯特拉斯算法求從頂點0到其余各頂點的最短路徑。4. 對于圖8-34，利用弗洛伊德算法求出每對頂點之間的最短路徑，即仿照圖8-8的運算過程，給出從鄰接矩陣出發(fā)每加入一個中間點后矩陣的狀態(tài)。5. 對于圖8-35，試給出一種拓撲序列，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點鄰接表中的邊結(jié)點都是按照結(jié)點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。 2 2 0 7 2 0 5 7 4 3 4 1 9 6 3 9 1 8 3 1 6 8 4 4 圖 8-34 圖 8-356. 一個AOV網(wǎng)的二元組表示為：V=0，1，2，3，4，5，6，7，8，9，10E=<0,2>,<0,4>,<1,2>,<1,5>,<2,4>,<3,5>,<4,6>,<4,7>,<5,