【文章內(nèi)容簡介】 相同的元素重復(fù)存儲。⑸ 下面（　　?。┎粚儆谔厥饩仃嚒 對角矩陣 B 三角矩陣 C 稀疏矩陣 D 對稱矩陣 【解答】C⑹ 若廣義表A滿足Head(A)=Tail(A)，則A為（ ）A ( ) B (( )) C (( ),( )) D(( ),( ),( ))【解答】B⑺ 下面的說法中，不正確的是（　　?。〢 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu)C 廣義表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。⑻ 下面的說法中，不正確的是（　　?。〢 對稱矩陣只須存放包括主對角線元素在內(nèi)的下（或上）三角的元素即可。B 對角矩陣只須存放非零元素即可。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3. 判斷題⑴ 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。【解答】錯。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。⑵ 使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑶ 稀疏矩陣壓縮存儲后，必會失去隨機存取功能?！窘獯稹繉ΑＲ驗閴嚎s存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表。【解答】對。⑸ 若一個廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e。如廣義表L=(( )，(a，b))的表頭為空表，但L不是空表。4．一個稀疏矩陣如圖44所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示?！窘獯稹繉?yīng)的三元組順序表如圖45所示，十字鏈表如圖46所示。5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求 運算的優(yōu)缺點?！窘獯稹吭O(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為Ｏ(mn)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度亦為Ｏ(mn)。如果采用三元組順序表進行壓縮存儲，假設(shè)矩陣中有t個非零元素，其空間復(fù)雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復(fù)雜度亦為Ｏ(t)。當(dāng)t mn時，采用三元組順序表存儲可獲得較好的時、空性能。6．設(shè)某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣” 。⑴ 請用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎金”項；⑵ 畫出該工資表ST的存儲結(jié)構(gòu)?！窘獯稹竣?ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST))))=獎金⑵ 工資表ST的頭尾表示法如圖47所示。7．若在矩陣A中存在一個元素ai,j（0≤i≤n1，0≤j≤m1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度。【解答】在矩陣中逐行尋找該行中的最小值，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復(fù)雜度為Ｏ(mn+n2)。 學(xué)習(xí)自測及答案 (沒看)1．二維數(shù)組M中每個元素的長度是3個字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲。若按行優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ），若按列優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ）。【解答】d+22，d+1412．一個nn的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮存儲，則其存儲容量為（　　 ）?！窘獯稹縩(n+1)/23．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲，則A[i][j]在數(shù)組S中的存儲位置是（ ）。【解答】i(i1)/2+j4．已知廣義表LS=(a, (b, c), (d, e, a))，運用Head函數(shù)和Tail函數(shù)取出LS中原子d的運算是（　　 ）?！窘獯稹縃ead(Head(Tail(Tail(LS))))5．廣義表(a, b, (c, (d)))的表尾是（ ）。A (d) B (c,(d)) C b,(c,(d)) D (b,(c,(d)))【解答】D6．設(shè)有三對角矩陣Ann（行、列下標(biāo)均從0開始），將其三條對角線上的元素逐行存于數(shù)組B[3n2]中，使得B[k]=aij求：⑴ 用i, j表示k的下標(biāo)變換公式；⑵ 用k表示i, j的下標(biāo)變換公式。【解答】⑴ 要求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲了多少個非零元素，這些非零元素的個數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個數(shù)是；k=2 + 3(i－1)+( j－i + 1)= 2i+ j。⑵ 因為k和i, j之間是一一對應(yīng)的關(guān)系，k+1是當(dāng)前非零元素的個數(shù)，整除即為其所在行號，取余表示當(dāng)前行中第幾個非零元素，加上前面零元素所在列數(shù)就是當(dāng)前列號，即：7．已知兩個nn的對稱矩陣按壓縮存儲方法存儲在已維數(shù)組A和B中，編寫算法計算對稱矩陣的乘積?！窘獯稹繉ΨQ矩陣采用壓縮存儲，乘積矩陣也采用壓縮存儲。注意矩陣元素的表示方法。第 5 章 樹和二叉樹課后習(xí)題講解1. 填空題⑴ 樹是n（n≥0）結(jié)點的有限集合，在一棵非空樹中，有（ ）個根結(jié)點，其余的結(jié)點分成m（m＞0）個（ ）的集合，每個集合都是根結(jié)點的子樹?！窘獯稹坑星覂H有一個，互不相交⑵ 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）。【解答】度，孩子，雙親⑶ 一棵二叉樹的第i（i≥1）層最多有（ ）個結(jié)點；一棵有n（n0）個結(jié)點的滿二叉樹共有（ ）個葉子結(jié)點和（ ）個非終端結(jié)點?！窘獯稹?i1，(n+1)/2，(n1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n1)/2。⑷ 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（ ），最小值是（ ）?！窘獯稹?h 1，2h1【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。⑸ 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）?！窘獯稹?k1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。⑹ 具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（ ）。【解答】50【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。⑺ 已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有（ ）個葉子結(jié)點。【解答】12【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、nn3分別為葉子結(jié)點、度為2的結(jié)點和度為3的結(jié)點的個數(shù)）。⑻ 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）?！窘獯稹緾DBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。⑼ 在具有n個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的。【解答】2n，n1，n+1⑽ 在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（ ），分支結(jié)點總數(shù)為（ ）?！窘獯稹縩，n1【分析】n1個分支結(jié)點是經(jīng)過n1次合并后得到的。2. 選擇題⑴ 如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（　?。?。A 1 B 2 C 3 D 4【解答】D⑵ 設(shè)二叉樹有n個結(jié)點，則其深度為（ ）。A n1 B n C +1 D 不能確定【解答】D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是 +1。⑶ 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A 空或只有一個結(jié)點 B 高度等于其結(jié)點數(shù)C 任一結(jié)點無左孩子 D 任一結(jié)點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑷ 線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（ 　?。 =NULL B =0 C =1 D =NULL【解答】C【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。⑸ 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）。A 2k2+1 B 2k1 C 2k 1 D 2k–1 1 E 2k+1 F 2k+1 1 G 2k 1+1 H 2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)是第k層上只有1個結(jié)點，最多的情況是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號。⑹ 一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（ 　）成立。A n=h+m B h+m=2n C m=h1 D n=2m1【解答】D【分析】滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則度為2的結(jié)點個數(shù)為m1。⑺ 任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（ ）。A 肯定不發(fā)生改變 B 肯定發(fā)生改變 C 不能確定 D 有時發(fā)生變化【解答】A【分析】三種遍歷次序均是先左子樹后右子樹。⑻ 如果T39。 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是T39。 中結(jié)點的（ ）序列，T中結(jié)點的后序序列就是 T39。 中結(jié)點的（　?。┬蛄?。A 前序 B 中序 C 后序 D 層序【解答】A，B⑼ 設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為nnnn4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（ ）個結(jié)點，根結(jié)點的左子樹上有（ ）個結(jié)點。A n11 B n1 C n1+n2+n3 D n2+n3+n4【解答】D，A【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點即為第一棵樹的根結(jié)點，根結(jié)點的左子樹是由第一棵樹中除了根結(jié)點以外其余結(jié)點組成的，根結(jié)點的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。⑽ 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。A 借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B 將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關(guān)問題C 將樹、森林轉(zhuǎn)換成二叉樹D 體現(xiàn)一種技巧，沒有什么實際意義【解答】B3. 判斷題⑴ 在線索二叉樹中，任一結(jié)點均有指向其前驅(qū)和后繼的線索?！窘獯稹垮e。某結(jié)點是否有前驅(qū)或后繼的線索，取決于該結(jié)點的標(biāo)志域是否為1。⑵ 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。【解答】對。由前序遍歷的操作定義可知。⑶ 二叉樹是度為2的樹?！窘獯稹垮e。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的?！窘獯稹繉?。因為根結(jié)點無兄弟結(jié)點。⑸ 用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結(jié)點。【解答】錯。二叉樹的順序存儲結(jié)構(gòu)是按層序存儲的，一般適合存儲完全二叉樹。4．證明：對任一滿二叉樹，其分枝數(shù)B＝2(n01) 。（其中，n0為終端結(jié)點數(shù)）【解答】因為在滿二叉樹中沒有度為1的結(jié)點，所以有：n=n0+n2 設(shè)B為樹中分枝數(shù)，則n=B+1所以B=n0 +n21再由二叉樹性質(zhì)：n0=n2+1代入上式有：B=n0+n011=2(n01)5．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹?！窘獯稹孔C明采用歸納法。設(shè)二叉樹的前序遍歷序列為a1a2a3… an，中序遍歷序列為b1b2b3… bn。當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(jié)點，所以，a1= b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n=k時，前序遍歷序列a1a2a3… ak和中序遍歷序列b1b2b3… bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3… akak+1和中序遍歷序列b1b2b3… bk bk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個訪問的一定是根結(jié)點，即二叉樹的根結(jié)點是a1，在中序遍歷序列中查找值為a1的結(jié)點，假設(shè)為bi，則a1=bi且b1b2… bi1是對根結(jié)點a1的左子樹進行中序遍歷的結(jié)果，前序遍歷序列a2a3… ai是對根結(jié)點a1的左子樹進行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3… ai和中序遍歷序列b1b2… bi1唯一確定了根結(jié)點的左子樹，同樣可證前序遍歷序列ai+1ai+2… ak+1和中序遍歷序列bi+1bi+2… bk+1唯一確定了根結(jié)點的右子樹。6．已知一棵度為m的樹中有：n1個度為1的結(jié)點