【文章內(nèi)容簡介】 四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素A[i,j]的長度均為32個二進位,行下標從1到9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：① 存放該數(shù)組所需多少單元？② 存放數(shù)組第4列所有元素至少需多少單元？③ 數(shù)組按行存放時，元素A[7,4]的起始地址是多少？④ 數(shù)組按列存放時，元素A[4,7]的起始地址是多少？答案：每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H（H（T（H（T（H（T（L）））））））第5章 樹和二叉樹1．選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A．唯一的 Ｂ．有多種C．有多種，但根結(jié)點都沒有左孩子 Ｄ．有多種，但根結(jié)點都沒有右孩子答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A．2 B．3 C．4 D．5 答案：D解釋：五種情況如下： （3）一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）。A．250 B． 500 C．254 D．501 答案：D解釋：設(shè)度為0結(jié)點（葉子結(jié)點）個數(shù)為A，度為1的結(jié)點個數(shù)為B，度為2的結(jié)點個數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因為C為整數(shù)，所以B=0，C=500，A=501，即有501個葉子結(jié)點。（4）一個具有1025個結(jié)點的二叉樹的高h為（ ）。A．11 B．10 C．11至1025之間 D．10至1024之間答案：C解釋：若每層僅有一個結(jié)點，則樹高h為1025；且其最小樹高為235。log21025+1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=k=h) A．mk1 B．mk1 C．mh1 D．mh1答案：A解釋：深度為h的滿m叉樹共有mh1個結(jié)點，第k層有mk1個結(jié)點。（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A．指向最左孩子 B．指向最右孩子 C．空 D．非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點，因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空。（7）對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號。A．先序 B. 中序 C. 后序 D. 從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹，即后序遍歷二叉樹。（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（ ）遍歷方法最合適。A．前序 B．中序 C．后序 D．按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲形式中，（ ）不是樹的存儲形式？A．雙親表示法 B．孩子鏈表表示法 C．孩子兄弟表示法 D．順序存儲表示法答案：D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進行存儲。（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。A．所有的結(jié)點均無左孩子 B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點 D．是任意一棵二叉樹答案：C解釋：因為先序遍歷結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當沒有左子樹時，就是“中右”和“右中”；當沒有右子樹時，就是“中左”和“左中”。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可，所以A、B不能選，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點，故選C。（11）設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（ ）個葉子結(jié)點。A．99 B．100 C．101 D．102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點，只有度為0（葉子結(jié)點）和度為2的結(jié)點。設(shè)葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點數(shù)n= n0+n2=2*n01，得到n0=100。（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（ ）。A．X的雙親 B．X的右子樹中最左的結(jié)點 C．X的左子樹中最右結(jié)點 D．X的左子樹中最右葉結(jié)點答案：C（13）引入二叉線索樹的目的是（ ）。A．加快查找結(jié)點的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（ ）個。A．n?1 B．n C．n + 1 D．n + 2答案：C（15）n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點C．樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D．樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值答案：A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點、兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點、任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值。2．應(yīng)用題（1）試找出滿足下列條件的二叉樹① 先序序列與后序序列相同 ②中序序列與后序序列相同③ 先序序列與中序序列相同 ④中序序列與層次遍歷序列相同答案：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有① 或為空樹，或為只有根結(jié)點的二叉樹② 或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹．③ 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹．④ 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C①畫出這棵二叉樹。②畫出這棵二叉樹的后序線索樹。③將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。答案： ABFD③CEHG ① ② （3） 假設(shè)用于通信的電文僅由8個字母組成，，，。① 試為這8個字母設(shè)計赫夫曼編碼。② 試設(shè)計另一種由二進制表示的等長編碼方案。③ 對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6], (7,10)】, ……19, 21, 32（100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 方案比較：字母編號對應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108111字母編號對應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101方案1的WPL＝2(++)+4(++)+5(+)=++=方案2的WPL＝3(+++++++)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為18，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000初態(tài):終態(tài)：weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112第6章 圖1．選擇題（1）在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：C（2）在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：B解釋：有向圖所有頂點入度之和等于所有頂點出度之和。（3）具有n個頂點的有向圖最多有（ ）條邊。 A．n B．n(n1) C．n(n+1) D．n2 答案：B解釋：有向圖的邊有方向之分，即為從n個頂點中選取2個頂點有序排列，結(jié)果為n(n1)。（4）n個頂點的連通圖用鄰接距陣表示時，該距陣至少有（ ）個非零元素。A．n B．2(n1) C．n/2 D．n2 答案：B（5）G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。A．7 B．8 C．9 D．10 答案：C解釋：8個頂點的無向圖最多有8*7/2=28條邊，再添加一個點即構(gòu)成非連通無向圖，故至少有9個頂點。（6）若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（ ）圖。A．非連通 B．連通 C．強連通 D．有向答案：B解釋：即從該無向圖任意一個頂點出發(fā)有到各個頂點的路徑，所以該無向圖是連通圖。（7）下面（　）算法適合構(gòu)造一個稠密圖G的最小生成樹。A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法答案：A解釋：Prim算法適合構(gòu)造一個稠密圖G的最小生成樹，Kruskal算法適合構(gòu)造一個稀疏圖G的最小生成樹。（8）用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常借助（ ）來實現(xiàn)算法。A．棧 B. 隊列 C. 樹 D．圖 答案：B解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法，深度優(yōu)先遍歷通常借助棧來實現(xiàn)算法。（9）用鄰接表表示圖進行深度優(yōu)先遍歷時，通常借助（ ）來實現(xiàn)算法。A．棧 B. 隊列 C. 樹