數(shù)據(jù)結(jié)構(gòu)馬睿、孫麗云習(xí)題答案

1、一、選擇題1、C 2 、 C 3 、二、判斷題X 4 X#”語句的執(zhí)行頻度（ n 為正整數(shù)）。1X 2 X 3 三、簡答題（略） 四、算法分析題：1）頻度：n ，時間復(fù)雜度：O（n）2）頻度：1 ，時間復(fù)雜度：O（1）3）頻度：n 2，時間復(fù)雜度：O（n2）4）頻度：n/2-1 ，時間復(fù)雜度： O（ n）5）頻度：1100寫出下列各程序段關(guān)于 n的時間復(fù)雜度。1）O( log 3n)1. 分析下列程序段中帶標號“22）O（n2）3）O（n2）6、7、8、9、一、選擇題1、A4. D 5. C 7. A二、填空題1. 、線性表2、3、前驅(qū)，后繼 p->next; s->data; t

2、4、5、q->next head->next = NULL6、p->next, s7、8、p->next != pO(1), O(n)一、選擇題1、C二、填空題10. D1. 、 n-12、3、O(n)135424、2xy+1x-/*5、a2, a 4, a 1, a 先進后出，加 滿，空， n 線性結(jié)構(gòu)2, 21， 減 110、4三、判斷題1. 、錯第2章 線性表第3 章 棧和隊列2、3、4、5、6、7、錯對錯對錯錯14可能的順序:四、解答題4、列車進入一個棧式結(jié)構(gòu)的車站，開岀車站有abcd; abdcadcb acdb, acbdbdca.bcda, bead ba

3、cd, badc cdba, cbda, cbad, dcba列車進入一個隊列式結(jié)構(gòu)的車站，開岀車站有6, 24staxychar第一個循環(huán)：隊列Q中的元素依次岀隊，1可能的順序：abcd5、7、8、9、岀隊后即進棧第二個循環(huán)：棧S中的元素依次岀棧，岀棧后即進入隊列第4章串一、選擇題1、A 2、D 3、C 4、C 5、D二、簡答題0。而空格串是由一個或多個空格組成的串,1、含零個字符的串稱為空串，用表示，串的長度為 串的長度為所含空格的個數(shù)。由串中任意連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地被稱為主串。假如一個串S= "a 0a1a2a n-1 ”(n > 0)，

4、其中：S為串名，用雙引號括起來的內(nèi)容為串的值，雙引 號本身不是串的值。2、當且僅當兩個串的長度相等并且各個對應(yīng)位置上的字符都相同時，兩個串才相等。3、19，7，good，e， 0， 3，” I am a good teacher "，” a goodyestea ”4、j0123456模式串a(chǎn)bcabaan extj-1000121三、算法題1、void Assig n( stri ng *s, stri ng t) Loc ( 3, 3) = Loc ( 0, 0 n =( 676 - 2 - 644) / 2 = 15)+ 3 * 15 + 3 = 644 + 45 + 3 =

5、692.2、( 1) 數(shù)組 B共有 1 + 2 + 3 +? + n= ( n+1 ) *n / 2 個元素。(2)只存下三角部分時，若i ? j，則數(shù)組元素 Aij 前面有i-1行(1?i-1，第0行第0列不算)，第1行有1個元素，第2行有2個元素，?，第i-1行有i-1個元素。在第i行中，第j號元素 排在第j個元素位置，因此，數(shù)組元素Aij 在數(shù)組B中的存放位置為：1 + 2 + ? +(i-1 )+ j =( i-1 ) *i / 2 + j若i < j ，數(shù)組元素 Aij 在數(shù)組B中沒有存放，可以找它的對稱元素Aji。在數(shù)組B的第(j-1 ) *j / 2 + i位置中找到。如果

6、第0行第0列也計入，數(shù)組 B從0號位置開始存放，則數(shù)組元素Aij 在數(shù)組B中的存放位置可以改為：當i ? j時，=i*(i+1 )/ 2 + j當i < j時，=j*(j+1 )/ 2 + i3、(1)Head(Tail(Tail(L1)(2)Head(Head(Tail(L2)(3)Head(Head(Tail(Tail(Head(4)Head(Head(Tail(Tail(L4)(5)Head(Tail(Head(L5)(6)Head(Head(Tail(Head(Tail(L3)(L6)4、由于線性表中的每個結(jié)點對應(yīng)稀疏矩陣的一個非零元素，其中包括下標、列下標和值，結(jié)點間的次序按矩

7、陣的行優(yōu)先順序排列，這個線性表用順序的方法存儲在連續(xù) 的存儲區(qū)，則對應(yīng)的三元組為其十字鏈表形式為：)3個字段，分別為該元素的行5、6、L=(a,(b，C),(d®n 0 I四、算法題1、從前向后找零元素【算void move(i nt A,i nt n)int i=0,j=n-1;int temp;while(ivj)while(Ai!=0) i+;while(Aj=0) j-;if(i<j)tem p=Ai;Ai=Aj;Aj=tem p;2、【算法分析】為保證算法的時間復(fù)雜度為 就能生成C數(shù)組，我們可采用設(shè)三個下標指針從后向前元素1 AJ0dA將Ai與Aj交換。的最大值)、B

8、數(shù)組的第一個元素(B數(shù)組的最大值)、 數(shù)組的最大值大者放C數(shù)組k所指單元；在上述比較中若否則j所指單元數(shù)送完后j后移，同時k前移，直到把【算法源代碼】O(m+n),即需要對數(shù)組 A和B的數(shù)據(jù)元素僅掃描一次 i,j,k初始時分別指向 A數(shù)組的最后一個元素(C數(shù)組將存放最大值的位置，然后比較 A數(shù)組i所指單元數(shù)大，則送完后iA與B數(shù)組的所有元素掃描完。A數(shù)組A與B前移，#defi ne m 3#defi ne n 4void Merge(i nt A,i nt B,i nt C)i nt i,j,k;i=m-1;j=0; k=m+n-1;while(i>=0)&&(j<

9、=n-1)if(Ai>Bj)Ck=Ai; i-;elseCk=Bj; j+; k-; Ck=Ai;i-;k-;Ck=Bj;j+;k-; while(i>=0)while(j<=n-1)3、【算法分析】 三元組表示中要求按行的順序存放，所有轉(zhuǎn)置過程不能直接將行下標和列下標轉(zhuǎn)換， 還必須使得列按順序存放。因此在A 中首先找出第一列中的所有元素，它們是轉(zhuǎn)置矩陣中第一行非元素，并把它們依次放在轉(zhuǎn)置矩陣三元組數(shù)組 B 中；然后依次找出第二列中的所有元素，把它們依 次放在數(shù)組B中；按照同樣的方法逐列進行，直到找岀第n列的所有元素，并把它們依次放在數(shù)組中?！舅惴ㄔ创a】*/void tra

10、nspose(TSMatrix A,TSMatrix *B)/*A是稀疏矩陣的三元組形式，B是存放A的轉(zhuǎn)置矩陣的三元組數(shù)組int i,j,k;B->mu=;B->nu=;B->tu=;if(B->tu>0)j=1;for(k=1;k<=;k+)for(i=1;i<=;i+)ifi.col=k)B->dataj.row=i.col;B->dataj.col=i.row; B->dataj.e=i.e; j+;4、算法分析】 在求廣義表深度的遞歸算法中，若結(jié)點為原子則深度為 返回頭指針與尾指針所指廣義表的深度最大值?！舅惴ㄔ创a】0 ，若

11、是空表深度為 1，否則int Glist_Getdeph(Glist L) int m,n;if(!L->tag) return 0; else if(!L) return 1; m=Glist_Getdeph(L->+1; n=Glist_Getdeph(L-> return m>n?n:n;一選擇題1、B 2 、A 3 、B 4 、A 5 、C 6 、C A 7 、 BB 9 、D 10、B11、 B 12 、B 13 、B 14 、 A 15 、C 16 、D 17 二填空題1 1 前驅(qū) 2 一個前驅(qū)結(jié)點 3 后繼418 、A 19 、 C 20 、D后繼n-1n

12、 o=n2 +11 2 2 101 A 2 D G F A C E 76. 2507. 18. 2n 0-19. 1 D 2 F10. 1 GEACBDF 2 111. 1 InOrderTraverse2.3.4.5.3 113 B E 4 A C 右85 B左9 210 4p ri ntf(T->data) 3InO rderTraverse (T->right)12.1C；n。n 1三.判斷題1.X 2.X 3.V4. X 5. X6.V 7.X 8.V9. X 10. V四.操作題1 .(1)GCABFED(T->left)2(5)2.所有結(jié)點均沒有左孩子的二叉樹。

13、所有結(jié)點均沒有右孩子的二叉樹 只有一個根結(jié)點的二叉樹證明：當n=1時，前序序列和中序序列均只有一個元素且相同， 叉樹。假設(shè)n<m-1時，結(jié)論成立，現(xiàn)證明當 n=m時也成立。設(shè)前序序列為：a1 , a2，am,中序序列為：b1,b2，bm。因為前序序列由前序遍歷得到，則a1為根結(jié)點元素；又中序序列由中序遍歷得到，則在中序序列中必能找到和a1相同的元素并設(shè)為bj(1 < j w m),由此可得 b 1，-, bj-1為左子樹的中序序列， bj+1 ,，bm為 右子樹的中序序列。(1) 若j=1即b1為根，此時二叉樹的左子樹為空， b 2 ,，bm即為右子樹的中序序列，右子樹的結(jié)點數(shù)為

14、右子樹，也唯一確定了二叉樹。(2) 若j=m即bm為根，此時二叉樹的右子樹為空， b 2，bm即為左子樹的中序序列，同(1), 二叉樹。(3) 2< j w m-1，則子序列 a2，aj和序列，這兩個序列唯一確定了左子樹；子序列a3.(1)4.即為根，由此唯一地確定了這顆二2，am即為右子樹的前序序列, m-1,由此，這兩個序列唯一確定了2，am即為左子樹的前序序列, 這兩個序列唯一確定了左子樹，也唯一確定了b1 ,，bj-1分別為左子樹的前序序列和中序 j+1 ,，am和 bj+1 ,，bm分別為右子樹的前序序列和中序序列，這兩個序列唯一確定了右子樹； 由此，證明了知道一棵二叉樹的前序

15、序列和中序序列，就能唯一地確定一棵二叉樹。5.GDN©MCGKDNHOM6.07.AB(b)AB(c)(d)54(e)WPL=1*5+3*5+5*4+9*3+16*2+20*1=119A:01B:0001C:001D:1E:00001F:000008.f波蘭式：-+a*b-cd/ef逆波蘭式:abcd-*+ef/-五.算法設(shè)計題=P；p=p->lchild;if(t op 匸-1) return stackt op .T; else return NULL;6.BiThrNode *P reOrder_Next(BiThrNode *p) n ");v=0;elsep

16、=(q->fron t)->n ext;(q->fron t)->n ext=p->n ext;if(p->n ext=NULL) q->rear=q->front; v=p->T;free( p);return v;void visite(LINKQUEUE *q, BiTree p)if(p!=NULL)prin tf("%c “,p->data); en li nkqueue( q,p);void Level_Traverse(BiTree T)/* LINKQUEUE Que,*Q;BiTree p;Q=&Q

17、ue;in itli nkqueue(Q);if(T匸NULL)按層次遍歷二叉樹*/p=dellinkqueue(Q); visite(Q,p->lchild); visite(Q,p->rchild);*/ visite(Q,T); while(!emptylinkqueue(Q) printf("The pointer which points at the last Node is %xn",p);/* 給出離根結(jié)點最遠的一個結(jié)點(即最后一個出隊的結(jié)點)的指針8int9/*Node(BiTree T) 求以孩子兄弟鏈表存儲的樹或森林 T 中的結(jié)點數(shù)，并通過

18、函數(shù)值返回 */int count; BiTree T1;if(T =NULL) return 0;else if(T->firstchild =NULL) return 1;else count=0; T1=T->firstchild; while(T1) count=cout+Node(T1);T1=T1->nextsibling?; return count?;/*bt 為空時，結(jié)點數(shù)為 0*/int/*High(BiTree T) 求以孩子兄弟鏈表存儲的樹或森林 T 的高度，并通過函數(shù)值返回 */int h1,h2;BiTree T1;if(T =NULL) retu

19、rn 0;else h1=High(T->firstchild)+1; h2=High(T->nextsibling); return h1>h2? h1:h2;/*bt 為空時，結(jié)點數(shù)為 0*/ 10char Pred,Midd; .Build_Sub(1,n,1,n); .分析: 本算法利用了這樣一個性質(zhì) ,即一棵子樹在前序和中序序列中所占的位置總是連續(xù)的 .因此,就 可以用起始下標和終止下標來確定一棵子樹 .Pre_Start,Pre_End,Mid_Start 和 Mid_End 分別指示子 樹在前序子序列里的起始下標 , 終止下標 , 和在中序子序列里的起始和終止下

20、標 .第 7章 圖一、選擇題1. B 2 . B 3 . B 和 C 4 . D和 E 5 . C 6. D 7 . A 8 . A 9 . D 10 . B二、填空題1. 1 n(n-1) 2 n(n-2)/2 32. 1 ABCDFE 2 ABCEFD3. 1 按深度4 極大5. 圖本身6. 主對角線2 按廣度n-17. 1 i 2 j8. 1 n-1 29. 20大于 n-1 3小于 n-12e 3 n10. 1 n+2e 211. 1 n+e 2 e 312. 無環(huán)三、判斷題1X 2 V四、（略）五、（略）3 .VX 6 . X 7.X 8.X181920一、選擇題1、 C 2 、 B

21、第8 章 查找、C 5 、C 6 、D 7 、B 8 、B 9 、 B 10 、D11、 C 12 、13 、 D14 、 D 15 、D 16 、C 17 、A 18 、B 19 、 D 20 、B二、判斷題1 【答案】 【分析】順序查找并沒有假設(shè)數(shù)有序或者無序，因此有序或無序?qū)ζ骄檎议L度沒有影響。 2錯誤3答案】錯誤 答案】正確 答案】錯誤4【分析】鏈表表示的有序表不能用折半查找法查找。5 【答案】錯誤6 【答案】錯誤【分析】最優(yōu)二叉樹是靜態(tài)樹表， AVL 是動態(tài)樹表，二者范圍不同。 78910答案】正確答案】正確答案】正確【答案】正確【答案】錯誤11【分析】除非被刪除的結(jié)點是葉子結(jié)點，

22、否則刪除后再插入同一結(jié)點得到的二叉排序樹與原來的二叉排序樹不同。12【答案】錯誤13【答案】錯誤14【答案】錯誤15【答案】正確16【答案】正確17【答案】錯誤【分析】a越小，只能說發(fā)生沖突的可能性越小，但依然有可能發(fā)生沖突。答案】正確答案】正確答案】正確三、填空題1 .【分析】最優(yōu)二叉樹是對葉子結(jié)點帶權(quán)平均查找路徑長度最小的樹，最優(yōu)查找樹是對所有結(jié)點帶 權(quán)查找路徑長度最小的樹，構(gòu)造這兩種樹均需要知道關(guān)鍵字的查找概率?！窘獯稹咳~子結(jié)點數(shù)結(jié)點數(shù)需要n個關(guān)鍵字的查找概率表?log 2n+1,所以，最大比較次數(shù)為?log 2n+1。2. 【分析】折半查找法在查找成功與不成功時進行比較的關(guān)鍵字個數(shù)最多

23、不超過樹的深度，而具有 n個結(jié)點的判定樹的深度為【答案】？log 2n+13.【分析】平均檢索長度ASJs=(s+n/s)/2+1，所以當 S=jn 時，ASG 取得最小值 “+1。21每個結(jié)點兩個關(guān)鍵字,1 22X 1 + 2 X 3 + 2X 3 =26?！窘獯稹?6174.【分析】第4層是葉子結(jié)點,【答案】26四、簡答題1. 【解答】判定樹如下所示：596等概率查找時成功的平均查找4ASLsucc=110(1 X 1+2 X 2+3 X 4+4 X 3)=(2)(3)2 .【解(1)/1 2=找。序樹：10c=(1+2+DecI50 100答D鍵字的順序構(gòu)造的二叉8Jan根據(jù)構(gòu)造的二叉A

24、SLsu2*2+3*3+4*3+b中元素先進行排序字樹求查找成功時的平均查找長度：*1)/12=構(gòu)造二叉排序樹，則構(gòu)造的二叉排序樹是一棵單支樹,的情況下查找成功A這種情況3. 【解答】4. 插入軍答】勺查找長度貝(Sep)30'60 70 290插入20-插9入10(2080入640290插入110930201006020那么,可知道12018030 40刪除150705 .【解答】令Fk表示含有最少結(jié)點的深度為k的平衡二叉樹的結(jié)點數(shù)目。hashf1(1)=1hashf1(13)=2n = Fn-2 +Fn-l + 1.F1=1,F2=2,.F含有12個結(jié)點的平衡二叉樹的最大深度為5.

25、例如:6.7.C黑測再【解答】452王要8.哈H解答】使用線性探測列法來構(gòu)造哈希表【解答】IB6070記錄數(shù)0. 30L口鏈地址法Na乜0 30丿 Q_60 7O7地址數(shù)據(jù)012345678910331131234382722hashf1(12)=1hashf1(34)=3hashf1(38)=5hashf1(27)=5hashf1(22)=0hashf2(12) = (1+1)%11=2hashf3(12)= (1+2)%11=3hashf2(34)=(3+1)%11=4hashf1(33)=0hashf2(27)=(5+1)%11=6hashf2(22)=(0+1)%11=1hashf3(

26、22)=2hashf4(22)=3hashf5(22)=4 hashf6(22)=5 hashf7(22)=6 hashf8(22)=7裝填因子？= 8/11查找成功所需的平均查找次數(shù)：(1+1+3+2+1+1+2+8)/8=19/8使用鏈地址法來構(gòu)造哈希表如下圖所示：0查找9.解2(1*3+2*3+3*1)/8=3/234AprDecFeb平均5查找長度為678910111213141516MarMayJuneJulySepOctNov5Jan(2)AprAug ADec I A10Feb JanMar OctJuneA1 NovAJuly ASep 卜10 11 12 13 14 15 1

27、6平均查找長度為：3/2五、算法設(shè)計題1.【分析】算法思想：先遍歷右子樹后遍歷左子樹?！窘獯稹克惴ㄈ缦拢篒n order(BiSTree bt, dataty pe X) if (bt) Inorder(bt->rchild，X);if(bt->data >=X) printf( “ %c ， bt->data);Inorder(bt->lchild，X);2.【分析】在合并過程中，并不釋放或新建任何結(jié)點，而是采取修改指針的方式來完成合并，這樣, 就必須按照后序序列把一棵樹中元素逐個連接到另一棵樹上，否則將會導(dǎo)致樹的結(jié)構(gòu)的混亂。解答】算法如下：void BiTMe

28、rge(BiSTree *T, BiSTree *S) if(S->lchild) BiTMerge (T if(S->rchild) BiTMerge (T Insert_Node(T , S);void Insert (BiSTree *T if(S->data>T->data) if (!T->rchild) T->rchild=S; else Insert (T->rchild else if(S->data<T->data) if (!T->lchild) T->lchild=S; else Insert

29、(T->lchildS->lchild=NULL;S->rchild=NULL;/* 把二叉排序樹合并到 T 中*/, S->lchild);, S->rchild)/* 合并子樹 */，BiSTNode *S)，S);，S);/*把樹結(jié)點S插入到T的合適位置*/* 插入的新結(jié)點必須和原來的左右子樹斷絕關(guān)系/* 否則會導(dǎo)致樹結(jié)構(gòu)的混亂 */*/3【分析】算法思想；以 x 為分界點遍歷原二叉樹并構(gòu)造兩棵新的二叉排序樹。 【解答】算法如下 :void BiTSplit(BiSTree *T, BiSTree *A, BiSTree *B/*把二叉排序樹T分裂為兩棵二叉

30、排序樹A和B,其中, int x)A的元素全部小于等于x，B 的元素全部大于 x*/ if (T->lchild) BiTSplit(T->lchildif (T->rchild) BiTSplit(T->rchildif (T->data<=x) Insert(Aelse Insert(B , T);void Insert (BiSTree *T,BiSTNode *S)/*把樹結(jié)點S插入到T的合適位置上*/,A,A,B,B,x);x);/* 分裂左右子樹*/,T);/* 將元素結(jié)點插入到T 的合適位置上 */*考慮到剛開始分裂時樹A和樹B為空的情況*/

31、if(!T) T=S;else if(S->data>T->rchild)if (!T->rchild) T->rchild=S;else Insert (T->else if(S->data<T->data) if(T->lchild) T->lchild=S; else Insert (T->S->lchild=NULL;S->rchild=NULL;4【提示】對于每次查找的思想是相同的,只是查找區(qū)間發(fā)生了變化,因此寫為遞歸算法時要將查 找區(qū)間的上下限作為參數(shù),遞歸調(diào)用時查找區(qū)間的上下限是變化的。int B

32、inSearch(datatype R , int low, int hig, keytype K) int mid;if (low<hig) return(0);else mid=(low+hig)/2;if(K=Rmid.key) return(mid);else if (K> Rmid.key) return(Binsearch(R, mid+1,hig,K); else return( Binsrch (R,low,mid-1,K) );5【提示】先在有序表 R 中利用折半查找法查找關(guān)鍵字值小于或等于x 的結(jié)點， mid 指向關(guān)鍵字正好等于x的結(jié)點或low指向關(guān)鍵字正好大于

33、 x的結(jié)點，然后采用移動法插入 x結(jié)點即可。void BinInsert (datatype R, KeyType x) int low=1,hig=n,mid,inplace,i,find=0;while (low<=hig && !find) mid=(low+hig)/2;if < Rmid.key) hig=mid-1;else if > Rmid.key) low=mid+1;else i=mid;find=1;if (find) inspace=mid;else inspace=low;for (i=n;i>=inspace;i-) Ri+1

34、=Ri; Rinspace=x;6【提示】調(diào)整中序遞歸遍歷算法，先遍歷右子樹，然后輸出根結(jié)點的值，再遍歷左子樹。void PrintNode (BiSTree T) if (T)PrintNode(T->rchild); printf( T->data) ;PrintNode(T->lchild);7【提示】解決本題的關(guān)鍵是遞歸函數(shù)的參數(shù)設(shè)置，采用逐漸縮小查找區(qū)間的方法來實現(xiàn)。void fun(BiSTree T int x, int *a, int *b) if (T) if (x<T-> *b =T-> ;/*當x小于根結(jié)點時，修改 b,在左子樹上繼續(xù)查

35、找*/fun(T->lchild, x,a,b); else if (x>T->/*當x大于根結(jié)點時，修改a,在右子樹上繼續(xù)查找*/ *a = T-> ;fun(T->rchild,x,a,b);else if (T->lchild) p=T->lchildwhile (p->rchild) p=p->rchild; *a=p->/* 當 x 等于根結(jié)點時， a 是其左子樹的最右下結(jié)點，/* 是其右子樹的最左下結(jié)點 */b*/if (T->rchild) p=T->rchild;while (p->lchild )

36、p=p->lchild;*b=p->8【提示】判斷一棵二叉樹是否是二叉排序樹，可以采用遞歸算法。對于樹中所有結(jié)點，檢查其左 子樹上所有結(jié)點的關(guān)鍵字是否都小于它的關(guān)鍵字，檢查其右子樹上所有結(jié)點的關(guān)鍵字是否都大于它 的關(guān)鍵字。int BinSortTree(BiSTree T)判別由二叉鏈表存儲的二叉樹是否為二叉排序樹，是則返回/*1，否則返回 0*/int l,r;if (!T ) return 1;else if (T->lchild=NULL && T->rchild=NULL ) return 1;/* 空樹是二叉排序樹 */* 只有一個根結(jié)點是二叉

37、排序樹 */else l = BinSortTree( T->lchild);r = BinSortTree( T->rchild);if (T->lchild && T->rchild )if (T->key>T->lchild->key && T->key<T->rchild->key && l && r) return 1;else ruturn 0;else if (T->lchild=NULL )return ( T->key < T->rchild->key && r) else return( T->key > T->lchild->key && l)/ * 只有一個根結(jié)點是二叉排序樹 */* 只有一個根結(jié)點是二叉排序樹*/9【提示】輸入關(guān)鍵字后，應(yīng)先確定其哈希地址，再將其插入到相應(yīng)的單鏈表中去。typedef struct HNode