數(shù)據(jù)結(jié)構(gòu)與算法作業(yè).doc

數(shù)據(jù)結(jié)構(gòu)與算法作業(yè)說明：1、題號(hào)形式: 每題都以【sn，cha，sec】開頭，sn表明本題的題目序號(hào)，每道題都有唯一的序號(hào)；cha表示內(nèi)容所在的章；sec表示內(nèi)容所在的節(jié)。如 【17，2，1】表示序號(hào)17的題來自第2章第1節(jié)。2、題型： 1)填空題:1-802)分析計(jì)算作圖題：序號(hào)1-30題（選自數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏等編）3、內(nèi)容取舍：根據(jù)本學(xué)期上課課件中的內(nèi)容，未上課章節(jié)的練習(xí)可舍棄。4、必做題或選做題：第四章和第五章不考，所以可以選做。1) 填空題：序號(hào)1-80題【1，1，2】線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系?！?，1，2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構(gòu)宜采用 結(jié)構(gòu)?！?，1，2】數(shù)據(jù)結(jié)構(gòu)的三要素是 ， ， ?！?，1，2】數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個(gè)二元組B(K，R)來表示，其中K是 _，R是 _?！?，1，2】存儲(chǔ)結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機(jī)器中的位置是否一定連續(xù)分為 _， _?！?，1，4】度量算法效率可通過 _來進(jìn)行?！?，1，4】算法的五個(gè)重要特性是確定性、輸入和輸出?！?，1，4】設(shè)n為正整數(shù)，則下面程序段的時(shí)間復(fù)雜度是 _。i=1；k=0；while(in)k=k+10*i；i+；【9，1，4】設(shè)n 為正整數(shù)，下面程序段中前置以記號(hào)的語(yǔ)句的頻度是 。 for (i=0; in; i+) for (j=0; jn; j+) if (i+j=n-1) aij=0; 【10，1，4】設(shè)n 為正整數(shù)，試確定下列各程序段中前置以記號(hào)的語(yǔ)句的頻度: (1) i=1; k=0; while (i=n-1) i+; k+=10 * i; / 語(yǔ)句的頻度是_。 (2) k=0; for (i=1;i=n;i+) for (j=i; jnext=_ _;和p-next=_ _的操作?！?9，2，3】在一個(gè)單鏈表中的指針p所指結(jié)點(diǎn)之前插入一個(gè)由指針s所指結(jié)點(diǎn)，可執(zhí)行以下操作序列：s-next= _;p-next=s;t=p-data;p-data=_ _;s-data=t;【20，2，3】在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作： q= p-next; p-data= p-next-data; p-next= _ ; free(q);【21，2，3】在單鏈表中，刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是 _?！?2，2，3】帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的判空條件是_； 不帶頭結(jié)點(diǎn)的單循環(huán)鏈表的判空條件是_?！?3，2，3】刪除帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的第一個(gè)結(jié)點(diǎn)的操作是_；刪除不帶頭結(jié)點(diǎn)的單循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)的操作是_?！?4，2，3】已知L是帶表頭結(jié)點(diǎn)的非空單鏈表, 且P結(jié)點(diǎn)既然不首元結(jié)點(diǎn),也不是尾元結(jié)點(diǎn),試從下列提供的答案中選擇合適的語(yǔ)句序列。a. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是_。b. 刪除結(jié)點(diǎn)P的語(yǔ)句序列是_。c. 刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是_。(1) P = P-next;(2) P-next = P;(3) P-next = P-next -next;(4) P = P-next -next;(5) while (P != NULL) P = P-next;(6) while (Q-next != NULL)P = Q; Q = Q-next;(7) while (P-next != Q) P = P-next;(8) while (P-next-next != Q) P = P-next;(9) while (P-next-next != NULL) P = P-next;(10) Q = P;(11) Q = P-next;(12) P = L;(13) L = L-next;(14) free (Q);【25，3，1】棧操作的原則是 。【26，3，1】對(duì)一個(gè)棧，給定輸入的順序是A、B、C，則全部不可能的輸出序列有 ?！?7，3，1】數(shù)據(jù)A、B、C、D依次進(jìn)棧后，再?gòu)臈Ｖ腥∫粩?shù)據(jù)，則它是 。則本棧得到DCBA的輸出序列，其理由是 ?！?8，3，1】.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是?！?9，3，1】將遞歸算法改寫成等價(jià)的非遞歸算法，通常應(yīng)該設(shè)置 的數(shù)據(jù)結(jié)構(gòu)【30，3，2】下列程序把十進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)，請(qǐng)?zhí)顚懞线m的語(yǔ)句成分。（每空2分）void conversion10_16() InitStack(&s); scanf(“%d”,&N); while(N) _ _ ; N = N/16; while(!StackEmpty(s) _ ; if(e=9)printf(“%d”,e); else printf(“%c”,e-10+A); /* conversion */【31，3，4】若一個(gè)棧的輸入序列為1,2,3,n，輸出序列的第一個(gè)元素為n，則第i個(gè)輸出元素是 。【32，3，4】若用一個(gè)大小為6個(gè)元素的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別是 和 。【33，3，4】已知一個(gè)棧的輸入序列為1，2，3，n,輸出序列為a1,a2,a3,an，那么a2=n的輸出序列共有 種?！?4，3，4】堆棧和隊(duì)列都是線性表, 堆棧是_的線性表, 而隊(duì)列是_的線性表。【35，3，4】從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是?！?6，3，4】若用一個(gè)大小為6個(gè)元素的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別是 和 ?！?7，3，4】下面是關(guān)于循環(huán)隊(duì)列的操作，請(qǐng)?jiān)趧澗€空白處填寫合適語(yǔ)句成分。Status EnQueue(SqQueue &Q, QelemType e) if( ) retrun ERROR; Q.base(Q.rear+1) % MAXSIZE = e; Q.rear = ; return OK; / EnQueue 【38，4，1-選】空串是 ，其長(zhǎng)度為 ?！?9，4，1-選】設(shè)串s1=”teachers and “,s2=”students”,則StrLength(s2)= ；Concat(s1,s2)= ?！?0，4，1-選】設(shè)s = I AM A TEACHER，其長(zhǎng)度是?！?1，4，1-選】?jī)蓚€(gè)串相等的充分必要條件是。【42，4，2-選】串的兩種最基本的存儲(chǔ)方式是。【43，4，3-選】令有串u=”aabcaab”和v=”abcaabcaabcaaba”,(1) 求Index(v,u,5)的值：Index(v,u,5)= ; (2分)(2) 求出u作為模式串時(shí)在KMP算法中的nextj值。(2分)j1234567uaabcaabnextj【44，5，1-選】二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A00的存儲(chǔ)地址是200，則A610的地址是。【45，5，1-選】設(shè)每個(gè)元素需要8個(gè)字節(jié)，順序存儲(chǔ)100個(gè)元素,若首地址是2500，那么第50個(gè)元素的地址是_?！?6，5，2-選】已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是【47，5，2-選】C語(yǔ)言采用行優(yōu)先方式存放數(shù)組元素，數(shù)組下標(biāo)從0開始。設(shè)維數(shù)為（5,6,7）的數(shù)組A5x6x7的起始存儲(chǔ)地址為L(zhǎng)oc000=1000，每個(gè)數(shù)組元素占用4個(gè)字節(jié)。則元素A444所在的地址Loc444= _?！?8，5，2-選】按行優(yōu)先次序列出三維數(shù)組A232的所有12個(gè)元素在內(nèi)存中的存儲(chǔ)次序，它們依次是： A000 A A A A A A A A A A A121【49，5，3-選】對(duì)一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹餍?，且A00的地址為1）,則A85的地址是 。【50，5，3-選】對(duì)一個(gè)10階三對(duì)角矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹餍?，且A00的地址為1，每個(gè)元素占4個(gè)字節(jié)）,則A65的地址是 ?！?1，5，3-選】對(duì)一個(gè)對(duì)稱矩陣A（aij=aji,0=i,j=j）對(duì)應(yīng)S中的下標(biāo)是 ；一維數(shù)組S的大小M至少為 ?！?2，6，1】已知一棵樹邊的集合是,。那么根結(jié)點(diǎn)是 ，結(jié)點(diǎn)b的雙親是 ，結(jié)點(diǎn)a的子孫有 ，樹的深度是 ，樹的度是 ，結(jié)點(diǎn)g在樹的第 層?！?3，6，2】通常使用來表示二叉樹結(jié)構(gòu)。【54，6，2】從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是?！?5，6，2】在圖1至圖5中, _是樹，_是二叉樹，_是完全二叉樹，_是滿二叉樹。 圖1 圖2 圖3 圖4 圖5【56，6，3】在圖4中，結(jié)點(diǎn)H在這棵樹的前序、中序和后序遍歷次序中分別是_、第_和第_個(gè)結(jié)點(diǎn)?！?7，6，2】滿三叉樹的第i層的結(jié)點(diǎn)個(gè)數(shù)為 ，深度為h時(shí)該樹中共有 結(jié)點(diǎn)?！?8，6，2】在圖4中，A是_結(jié)點(diǎn)，D是_結(jié)點(diǎn)，B是E的_，B是G的_，D是E的_。這棵樹的度是_，深度是_?！?9，6，2】程序填空：下列算法是求以二叉鏈表存儲(chǔ)的二叉樹中的最小值，設(shè)數(shù)據(jù)域的類型為int。void minnode(BiTree T, int *min) if(T!=NULL) if( ) *min = T-data; minnode(T-lchild,min); ; 【60，6，2】已知一棵完全二叉樹有56個(gè)葉子結(jié)點(diǎn)，從上到下、從左到右對(duì)它的結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)為1號(hào)。則該完全二叉樹總共結(jié)點(diǎn)有_個(gè)；有_層；第91號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)是_號(hào)；第63號(hào)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)是_號(hào)。（每空2分）【61，6，2】下列表示的圖中，共有_個(gè)是樹；有_個(gè)是二叉樹；有_個(gè)是完全二叉樹。【62，6，3】下列二叉樹的中序遍歷序列是_;后序遍歷序列是_。 【63，6，3】一棵二叉樹的中序遍歷序列是DBNGOAEC,后序遍歷序列是DNOGBECA，則其先序遍歷的序列中的第一個(gè)元素是_ _，第五個(gè)元素是_ _，最后一個(gè)元素是_【64，6，3】下列二叉樹的先序遍歷序列的第5個(gè)結(jié)點(diǎn)是_；第8個(gè)結(jié)點(diǎn)是_；后序遍歷序列的第2個(gè)結(jié)點(diǎn)是_；第6個(gè)結(jié)點(diǎn)是_。(每空 2 分)【65，6，3】如果某二叉樹的后序遍歷序列是ABCDEFGHI，中序遍歷序列是ACBIDFEHG，則其先序遍歷序列的第一個(gè)字母是 ，最后一個(gè)字母是 。【66，6，3】程序填空：設(shè)算法DFS(Mgraph *G, int i)是無向圖G從i頂點(diǎn)開始的深度優(yōu)先遍歷算法。下列算法是判斷無向圖G是否是連通的。int isconnect(Mgraph *G) int i,k=0; for(i=0; ivexnum; i+) visitedi = 0; for(i=0; ivexnum; i+) if(!visitedi) ； DFS(G, i); if(k=1) ； else return 0;【67，7，2】圖有 和 等存儲(chǔ)結(jié)構(gòu)?！?8，7，2】設(shè)無權(quán)圖G的鄰接矩陣為A，若（vi,vj）屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于 ，22、設(shè)無向圖G的鄰接矩陣為A，若Aij等于0，則Aji等于 ?！?9，7，2】若一個(gè)圖用鄰接矩陣表示，則計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。【70，7，2】若一個(gè)圖用鄰接矩陣表示，則刪除從第i個(gè)頂點(diǎn)出發(fā)的所有邊的方法是 ?！?1，7，4】n個(gè)頂點(diǎn)的連通圖至少有 條邊。【72，7，4】設(shè)一個(gè)圖G=V,A,V=a,b,c,d,e,f,A=,。那么頂點(diǎn)e的入度是 ；出度是 ；通過頂點(diǎn)f的簡(jiǎn)單回路有 條；就連通性而言，該圖是 圖；它的強(qiáng)連通分量有 個(gè)；其生成樹可能的最大深度是?！?3，7，5】下面有向圖共有_個(gè)頂點(diǎn)；從v3到v2的最短簡(jiǎn)單路徑之一是_；v1的出度是_；包含所有頂點(diǎn)的簡(jiǎn)單路徑之一是_?！?4，9，2】n個(gè)結(jié)點(diǎn)的二叉排序樹的最大深度是 ，最小深度為 【75，9，3】設(shè)HASH表的大小為 n (n=7), HASH函數(shù)為 h(x)=x % n, 如果用線性探測(cè)法 F(i)=i解決沖突，請(qǐng)?jiān)谙旅鍴ASH表中依次插入關(guān)鍵字5, 18, 21, 14, 25, 4以后，關(guān)鍵字4、5和25所在地址的下標(biāo)分別是 、 和 ，插入上述6個(gè)元素的平均比較次數(shù)是 。下標(biāo)：0 1 2 3 4 5 6 【76，10，1】排序過程一般需經(jīng)過兩個(gè)基本操作，它們是 和 ?！?7，10，2】結(jié)點(diǎn)的關(guān)鍵字序列是（F,B,J,G,E,A,I,D,C,H），對(duì)它按字母的字典序進(jìn)行排列。如果采用Shell排序方法，那么步長(zhǎng)取5時(shí)，第一次掃描結(jié)果的前5個(gè)字母分別是 ?！?8，10，2】在對(duì)一組關(guān)鍵字是（54,38,96,45,15,72,60,23,83）的記錄進(jìn)行直接插入排序時(shí)，當(dāng)把第七個(gè)記錄（關(guān)鍵字是60）插入到有序表時(shí)，為尋找插入位置需比較 次?！?9，10，3】在利用快速排序方法對(duì)一組關(guān)鍵字是（54,38,96,45,15,72,60,23,83）的記錄進(jìn)行排序時(shí)，需要遞歸調(diào)用partition函數(shù)，遞歸的最大深度（設(shè)第一次調(diào)用深度為1）為 ，共需5次遞歸調(diào)用，其中第二次遞歸調(diào)用是對(duì)關(guān)鍵字是 的一組記錄進(jìn)行的?！?0，10，4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排序方法中，不穩(wěn)定的排序方法有 。2) 分析計(jì)算作圖題：序號(hào)1-30（選自數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏等編）【1， 1，4】（選自數(shù)據(jù)結(jié)構(gòu)題集1.8，選做題）設(shè)n為正整數(shù)，試確定下列各段程序中前置以記號(hào)的語(yǔ)句的頻度(語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù))。(1) i=1；k=0;while (i0) if(x100) x-=10; y-; else x+;【2， 1，4】（選自數(shù)據(jù)結(jié)構(gòu)題集1.9，選做題） 假設(shè)n為2的乘冪，并且n2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n函數(shù)形式表示） int Time (int n)count =0;x=2;while(x next S ；（2）P next P next next；（3）P next S next；（4）S next P next；（5）S next L；（6）S next NULL；（7）Q P；（8）while （P next ！ Q）P P next；（9）while （P next ！ NULL） P P next；（10）P Q；（11）P L；（12）L S；（13）L P；【4， 2，2】（選自數(shù)據(jù)結(jié)構(gòu)題集2.10，選做題）指出以下算法中的錯(cuò)誤和低效（即費(fèi)時(shí)）之處，并將它改寫為一個(gè)既正確又高效的算法。 Status DeleteK（SqList &a，int i，int k）/本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素 if（i 1 | k a.length）return INFEASIBLE；/ 參數(shù)不合法 else for（count 1；count i +1；j ）a.elemj1 a.elemj；a. length ； return OK； / DeleteK【5， 3，1】（選自數(shù)據(jù)結(jié)構(gòu)題集3.4，必做題） 簡(jiǎn)述以下算法的功能（棧的元素類型 SElemType為int）（1）Status algo1（Stack S） int i，n，A255； n 0； while （！StackEmpty（S） n +；Pop（S，An）； for（i 1；i n；i +）Push（S，Ai）； （2）Status algo2（Stack S，int e） Stack T；int d； InitStack（T）； while（！StackEmpty（S） Pop（S，d）； if（d！e）Push（T，d）； while（！StackEmpty（T） Pop（T，d）； Push（S，d）； 【6， 3，1】（選自數(shù)據(jù)結(jié)構(gòu)題集3.15，選做題）假設(shè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧，即在一堆數(shù)組的存儲(chǔ)空間中存在著兩個(gè)棧，它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。試編寫實(shí)現(xiàn)這個(gè)雙向棧tws的三個(gè)操作：初始化inistack（tws）、入棧push（tws，i，x）和出棧pop（tws，i）的算法，其中i為0或1，用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論按過程（正/誤狀態(tài)變量可設(shè)為變參）或函數(shù)設(shè)計(jì)這些操作算法各有什么優(yōu)缺點(diǎn)。【7， 3，4】（選自數(shù)據(jù)結(jié)構(gòu)題集3.13，必做題）簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）void algo3(Queue &Q)Stack S; int d; InitStack (S);while (!QueueEmpty (Q) DeQueue (Q, d); Push (S,d);while (!StackEmpty (S) Pop (S, d); EnQueue(Q, d);【8， 3，2】（選自數(shù)據(jù)結(jié)構(gòu)題集3.19，選做題）假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”和花括號(hào)“”和“”，且這三種括號(hào)可以按任意的次序嵌套使用（如：()）。編寫判別給定表達(dá)式所含括號(hào)是否正確配對(duì)出現(xiàn)的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。【9， 4，1】（選自數(shù)據(jù)結(jié)構(gòu)題集4.3，必做題）設(shè)s =I AM A STUDENT,t =GOOD,q =WORKER。求：StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1),Index(s, A), Index(s, t), Replace(s, STUDENT,q ),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)【10， 5，1】（選自數(shù)據(jù)結(jié)構(gòu)題集5.1，必做題）假設(shè)有兩維數(shù)組A6x8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)按字節(jié)編址。已知A的起始地址為1000，計(jì)算：(1) 數(shù)組A的存儲(chǔ)量；(2) 數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；(3) 按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；(4) 按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址；【11， 6，1】（選自數(shù)據(jù)結(jié)構(gòu)題集6.1，必做題）已知一棵樹邊的集合為，請(qǐng)畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)G的雙親？（4）哪些是結(jié)點(diǎn)G的祖先？（5）哪些是結(jié)點(diǎn)G的孩子？（6）哪些是結(jié)點(diǎn)E的子孫？（7）哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？（8）結(jié)點(diǎn)B和N的層次號(hào)分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)C為根的子樹的深度是多少？【12， 6，1】（選自數(shù)據(jù)結(jié)構(gòu)題集6.4，選做題）一棵深度為H的滿k叉樹有如下性質(zhì)第H層上的結(jié)點(diǎn)都是葉子節(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，問：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為p的父結(jié)點(diǎn)（若存在）的編號(hào)是多少？（3）編號(hào)為p的結(jié)點(diǎn)的第i個(gè)兒子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4）編號(hào)為p的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？【13， 6，2】（選自數(shù)據(jù)結(jié)構(gòu)題集6.5，選做題）已知一棵度為k的樹中有n1個(gè)度為1 的結(jié)點(diǎn)，n2個(gè)度為2 的結(jié)點(diǎn)，nk個(gè)度為k的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？【14， 6，3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.13，必做題）假設(shè)n和m為二叉樹中的兩結(jié)點(diǎn)，用“1”、“0”、“”（分別表示肯定、恰恰相反或者不一定）填寫下表：已知 問答:前序遍歷時(shí)n在m前？中序遍歷時(shí)n在m前？后序遍歷時(shí)n在m前？n在m左方n在m右方n是m祖先n是m子孫注：如果（1）離a和b最近的共同祖先p存在，且（2）a在p的左子樹中，b在p的右子樹中，則稱a在b的左方（即b在a的右方）【15， 6，3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.14，選做題）找出所有滿足下列條件的二叉樹：（a）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列相同；（b）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列相同；（c）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列相同；【16， 6，4】（選自數(shù)據(jù)結(jié)構(gòu)題集6.19，必做題）分別畫出和下列樹對(duì)應(yīng)的各二叉樹：【17， 6，3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.23，選做題）畫出和下列已知序列對(duì)應(yīng)的樹T樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG?！?8， 6，5】（選自數(shù)據(jù)結(jié)構(gòu)題集6.26，必做題）假設(shè)用于通信的電文僅有8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10.試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。【19， 6，2】（選自數(shù)據(jù)結(jié)構(gòu)題集6.29，必做題）假設(shè)一棵二叉樹的層序序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請(qǐng)畫出該樹?！?0， 7，2】（選自數(shù)據(jù)結(jié)構(gòu)題集7.1，必做題）已知如右圖所示的有向圖，請(qǐng)給出該圖的（1） 每個(gè)頂點(diǎn)的入/出度； （2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 強(qiáng)連通分量?！?1， 7，3】（選自數(shù)據(jù)結(jié)構(gòu)題集7.4，選做題）試對(duì)教科書7.1節(jié)中圖7.3（a）所示的無向圖(如下圖)，畫出其廣度優(yōu)先生成森林?！?2， 7，4】（選自數(shù)據(jù)結(jié)構(gòu)題集7.5，選做題）已知以二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090