數(shù)據結構(C版)王紅梅-版課后答案

第1章緒論課后習題講解1.填空⑴（）是數(shù)據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理?！窘獯稹繑?shù)據元素⑵（）是數(shù)據的最小單位，（）是討論數(shù)據結構時涉及的最小數(shù)據單位?！窘獯稹繑?shù)據項，數(shù)據元素【分析】數(shù)據結構指的是數(shù)據元素以及數(shù)據元素之間的關系。⑶從邏輯關系上講，數(shù)據結構主要分為（）、（）、（）和（）。【解答】集合，線性結構，樹結構，圖結構⑷數(shù)據的存儲結構主要有（）和（）兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：（）和（）。【解答】順序存儲結構，鏈接存儲結構，數(shù)據元素，數(shù)據元素之間的關系⑸算法具有五個特性，分別是（）、（）、（）、（）、（）。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設計語言，流程圖，偽代碼，偽代碼⑺在一般情況下，一個算法的時間復雜度是（）的函數(shù)。1/90【解答】問題規(guī)模⑻設待處理問題的規(guī)模為n，若一個算法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為n*log25n，則表示成數(shù)量級的形式為（）?！窘獯稹喀?1)，Ο(nlog2n)【分析】用大O記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2.選擇題⑴順序存儲結構中數(shù)據元素之間的邏輯關系是由（）表示的，鏈接存儲結構中的數(shù)據元素之間的邏輯關系是由（）表示的。A線性結構B非線性結構C存儲位置D指針【解答】C，D【分析】順序存儲結構就是用一維數(shù)組存儲數(shù)據結構中的數(shù)據元素，其邏輯關系由存儲位置（即元素在數(shù)組中的下標）表示；鏈接存儲結構中一個數(shù)據元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中的指針表示。⑵假設有如下遺產繼承規(guī)則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的最合適的數(shù)據結構應該是（）。A樹B圖C線性表D集合【解答】B2/90【分析】將丈夫、妻子和子女分別作為數(shù)據元素，根據題意畫出邏輯結構圖。⑶算法指的是（）。對特定問題求解步驟的一種描述，是指令的有限序列。計算機程序C解決問題的計算方法D數(shù)據處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據處理是通過算法完成的。所以，只有 A是算法的準確定義。⑷下面（）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應具備的特性。⑸算法分析的目的是（），算法分析的兩個主要方面是（）。A找出數(shù)據結構的合理性 B研究算法中輸入和輸出的關系C分析算法的效率以求改進 D分析算法的易讀性和文檔性E空間性能和時間性能 F正確性和簡明性G可讀性和文檔性 H數(shù)據復雜性和程序復雜性【解答】C，E3.判斷題⑴算法的時間復雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。3/90【解答】錯。時間復雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。⑵每種數(shù)據結構都具備三個基本操作：插入、刪除和查找?！窘獯稹垮e。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據結構。⑶所謂數(shù)據的邏輯結構指的是數(shù)據之間的邏輯關系?！窘獯稹垮e。是數(shù)據之間的邏輯關系的整體。⑷邏輯結構與數(shù)據元素本身的內容和形式無關。【解答】對。因此邏輯結構是數(shù)據組織的主要方面。⑸基于某種邏輯結構之上的基本操作，其實現(xiàn)是唯一的?！窘獯稹垮e?；静僮鞯膶崿F(xiàn)是基于某種存儲結構設計的，因而不是唯一的。4.分析以下各程序段，并用大O記號表示其執(zhí)行時間?！窘獯稹竣呕菊Z句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。⑵基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。⑶分析條件語句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T(n)=O(n)。⑷設循環(huán)體共執(zhí)行 T(n)次，每循環(huán)一次，循環(huán)變量 y加1，最終T(n)=y，即：(T(n)+1)2 ，≤n所以T(n)=O(n1/2)。⑸x++是基本語句，所以5．設有數(shù)據結構（D，R），其中D={1,2,3,4,5,6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結構圖并指出屬于何種結構。4/90【解答】其邏輯結構圖如圖 1-3所示，它是一種圖結構。6.為整數(shù)定義一個抽象數(shù)據類型，包含整數(shù)的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據類型定義如下：ADTintegerData整數(shù)a：可以是正整數(shù)(1,2,3,,)、負整數(shù)(-1,-2,-3,,)和零OperationConstructor前置條件：整數(shù) a不存在輸入：一個整數(shù) b功能：構造一個與輸入值相同的整數(shù)輸出：無后置條件：整數(shù) a具有輸入的值Set前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：修改整數(shù) a的值，使之與輸入的整數(shù)值相同輸出：無后置條件：整數(shù) a的值發(fā)生改變5/90Add前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：將整數(shù) a與輸入的整數(shù) b相加輸出：相加后的結果后置條件：整數(shù) a的值發(fā)生改變Sub前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：將整數(shù) a與輸入的整數(shù) b相減輸出：相減的結果后置條件：整數(shù) a的值發(fā)生改變Multi前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：將整數(shù) a與輸入的整數(shù) b相乘輸出：相乘的結果后置條件：整數(shù) a的值發(fā)生改變Div前置條件：存在一個整數(shù) a輸入：一個整數(shù) b6/90功能：將整數(shù) a與輸入的整數(shù) b相除輸出：若整數(shù) b為零，則拋出除零異常，否則輸出相除的結果后置條件：整數(shù) a的值發(fā)生改變Mod前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：求當前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù) b為零，則拋出除零異常，否則輸出取模的結果后置條件：整數(shù) a的值發(fā)生改變Equal前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：判斷整數(shù) a與輸入的整數(shù)b是否相等輸出：若相等返回 1，否則返回0后置條件：整數(shù) a的值不發(fā)生改變endADT7.求多項式A(x)的算法可根據下列兩個公式之一來設計：A(x)=anxn+an-1xn1+,+a1x+a0-A(x)=(,(anx+an-1)x+,+a1)x)+a0根據算法的時間復雜度分析比較這兩種算法的優(yōu)劣。7/90【解答】第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化，減少了不必要的乘法運算。8.算法設計（要求：算法用偽代碼和C++描述，并分析最壞情況下的時間復雜度）⑴對一個整型數(shù)組A[n]設計一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。下面是簡單選擇排序算法的 C++描述。分析算法，有兩層嵌套的 for循環(huán)，所以，。⑵找出整型數(shù)組A[n]中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描述如下：算法的C++描述如下：分析算法，只有一層循環(huán)，共執(zhí)行 n-2次，所以，T(n)=O(n)。學習自測及答案1．順序存儲結構的特點是（），鏈接存儲結構的特點是（）?！窘獯稹坑迷卦诖鎯ζ髦械南鄬ξ恢脕肀硎緮?shù)據元素之間的邏輯關系，用指示元素存儲地址的指針表示數(shù)據元素之間的邏輯關系。2.算法在發(fā)生非法操作時可以作出處理的特性稱為（）。【解答】健壯性3.常見的算法時間復雜度用大Ｏ記號表示為：常數(shù)階()、對數(shù)階()、線性階()、平方階()和指數(shù)階()?！窘獯稹浚?1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)8/904．將下列函數(shù)按它們在 n時的無窮大階數(shù)，從小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n【解答】log2n,n1/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!5．試描述數(shù)據結構和抽象數(shù)據類型的概念與程序設計語言中數(shù)據類型概念的區(qū)別?！窘獯稹繑?shù)據結構是指相互之間存在一定關系的數(shù)據元素的集合。而抽象數(shù)據類型是指一個數(shù)據結構以及定義在該結構上的一組操作。程序設計語言中的數(shù)據類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數(shù)據類型可以看成是對數(shù)據類型的一種抽象。6.對下列用二元組表示的數(shù)據結構,試分別畫出對應的邏輯結構圖，并指出屬于何種結構。A=(D，R)，其中D={a1,a2,a3,a4}，R={}B=(D，R)，其中D={a,b,c,d,e,f}，R={,,,,}C=(D，R)，其中D={a，b，c，d，e，f}，R={,,,,,}D=(D，R)，其中D={1,2,3,4,5,6}，R={(1,2)，(1,4)，(2,3)，(2,4)，(3,4)，(3,5)，(3,6)，(4,6)}【解答】⑴屬于集合，其邏輯結構圖如圖1-4(a)所示；⑵屬于線性結構，其邏輯結構圖如圖1-4(b)所示；⑶屬于樹結構，其邏輯結構圖如圖1-4(c)所示；⑷屬于圖結構，其邏輯結構圖如圖1-4(d)所示。7.求下列算法的時間復雜度。count=0;x=1;9/90while(x{x*=2;count++;}returncount;【解答】Ｏ(log2n)第2章線性表課后習題講解1.填空⑴在順序表中，等概率情況下，插入和刪除一個元素平均需移動（）個元素，具體移動元素的個數(shù)與（）和（）有關?！窘獯稹勘黹L的一半，表長，該元素在表中的位置⑵順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（）?！窘獯稹?08【分析】第5個元素的存儲地址=第1個元素的存儲地址＋(5－1)×2=108⑶設單鏈表中指針p指向結點A，若要刪除A的后繼結點（假設A存在后繼結點），則需修改指針的操作為（）。【解答】p->next=(p->next)->next⑷單鏈表中設置頭結點的作用是（）。10/90【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。⑸非空的單循環(huán)鏈表由頭指針head指示，則其尾結點（由指針p所指）滿足（）?！窘獯稹縫->next=head【分析】如圖 2-8所示。⑹在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結點s的操作序列是（）；刪除開始結點的操作序列為（）?！窘獯稹縮->next=rear->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;deleteq;【分析】操作示意圖如圖 2-9所示：⑺一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時間復雜度為（）；在給定值為的結點后插入一個新結點的時間復雜度為（）?！窘獯稹喀?1)，Ο(n)【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為Ο(1)；而在給定值為x的結點后插入一個新結點需要先查找值為 x的結點，所以時間復雜度為 Ο(n)。⑻可由一個尾指針唯一確定的鏈表有（）、（）、（）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2.選擇題11/90⑴線性表的順序存儲結構是一種（）的存儲結構，線性表的鏈接存儲結構是一種（）的存儲結構。A隨機存取B順序存取C索引存取D散列存取【解答】A，B【分析】參見 。⑵線性表采用鏈接存儲時，其地址（）。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內存中任意位置。⑶單循環(huán)鏈表的主要優(yōu)點是（）。不再需要頭指針了從表中任一結點出發(fā)都能掃描到整個鏈表；已知某個結點的位置后，能夠容易找到它的直接前趨；在進行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹緽⑷鏈表不具有的特點是（）。A可隨機訪問任一元素 B插入、刪除不需要移動元素C不必事先估計存儲空間 D所需空間與線性表長度成正比12/90【解答】A⑸若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨，則采用（）存儲方法最節(jié)省時間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i個元素，所以，應選擇隨機存取結構即順序表，同時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第 i個元素的前趨，但不能實現(xiàn)隨機存取。⑹若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（）存儲方法最節(jié)省時間。A單鏈表B帶頭指針的單循環(huán)鏈表 C雙鏈表D帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結點，其時間性能是O(1)，所以，答案是 D。⑺若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（）存儲方法最節(jié)省運算時間。13/90A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。⑻在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)【解答】B【分析】首先應順序查找新結點在單鏈表中的位置。⑼對于n個元素組成的線性表，建立一個有序單鏈表的時間復雜度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。⑽使用雙鏈表存儲線性表，其優(yōu)點是可以（）。A提高查找速度B更方便數(shù)據的插入和刪除C節(jié)約存儲空間D很快回收存儲空間【解答】B14/90【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。⑾在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之間插入s所指結點，則執(zhí)行（）操作。As->next=p->next;p->next=s;Bq->next=s;s->next=p;Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;【解答】B【分析】注意此題是在q和p之間插入新結點，所以，不用考慮修改指針的順序。⑿在循環(huán)雙鏈表的 p所指結點后插入 s所指結點的操作是（）。Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案 C和D的圖解。3.判斷題15/90⑴線性表的邏輯順序和存儲順序總是一致的。【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。⑵線性表的順序存儲結構優(yōu)于鏈接存儲結構?！窘獯稹垮e。兩種存儲結構各有優(yōu)缺點。⑶設p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。⑷線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼?！窘獯稹垮e。每個元素最多只有一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有后繼。⑸在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構?！窘獯稹垮e。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4．請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結構更好些。⑴若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。⑵如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。⑶描述一個城市的設計和規(guī)劃。16/90【解答】順序表的優(yōu)點：①無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；②可以快速地存取表中任一位置的元素（即隨機存?。?。順序表的缺點：①插入和刪除操作需移動大量元素；②表的容量難以確定；③造成存儲空間的“碎片”。單鏈表的優(yōu)點：①不必事先知道線性表的長度；②插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：①指針的結構性開銷；②存取表中任意元素不方便，只能進行順序存取。⑴應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。⑵應選用鏈接存儲結構。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。⑶應選用鏈接存儲結構。因為一個城市的設計和規(guī)劃涉及活動很多，需要經常修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5．算法設計⑴設計一個時間復雜度為Ｏ(n)的算法，實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹āＯ旅娼o出具體算法。分析算法，第一次調用Reverse函數(shù)的時間復雜度為O(k)，第二次調用Reverse函數(shù)的時間復雜度為O(n-k)，第三次調用Reverse函數(shù)的時間復雜度為O(n)，所以，總的時間復雜度為O(n)。17/90⑵已知數(shù)組A[n]中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復雜度為Ｏ (n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設置兩個變量i和j，初始時i=0，j=n-1，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i]與A[j]交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復雜度為Ｏ (n)。⑶試編寫在無頭結點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現(xiàn)進行比較。【解答】參見。⑷試分別以順序表和單鏈表作存儲結構，各寫一實現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷?，即是將對稱元素交換，設順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：單鏈表的逆置請參見 算法2-4和算法2-6。⑸假設在長度大于1的循環(huán)鏈表中，即無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點。【解答】利用單循環(huán)鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p，然后將結點r刪除，如圖2-11所示，具體算法如下：18/90⑹已知一單鏈表中的數(shù)據元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下：⑺設單鏈表以非遞減有序排列，設計算法實現(xiàn)在單鏈表中刪去值相同的多余結點?！窘獯稹繌念^到尾掃描單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。具體算法如下：⑻判斷帶頭結點的雙循環(huán)鏈表是否對稱?！窘獯稹吭O工作指針p和q分別指向循環(huán)雙鏈表的開始結點和終端結點，若結點p和結點q的數(shù)據域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點（循環(huán)雙鏈表中結點個數(shù)為奇數(shù)），或結點q成為結點p的前驅（循環(huán)雙鏈表中結點個數(shù)為偶數(shù)）。如圖2-12所示。學習自測及答案1.已知一維數(shù)組A采用順序存儲結構，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是（）。A108B180C176D11219/90【解答】D2．在長度為n的線性表中查找值為 x的數(shù)據元素的時間復雜度為：（）。AO(0)BO(1)CO(n)DO(n2)【解答】C3．在一個長度為n的順序表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動（）個元素，刪除第i（1≤i≤n）個元素時，需向前移動（）個元素?！窘獯稹縩-i+1，n-i4．在單鏈表中，除了頭結點以外，任一結點的存儲位置由（）指示?！窘獯稹科淝摆吔Y點的指針域5．當線性表采用順序存儲結構時，其主要特點是（）?！窘獯稹窟壿嫿Y構中相鄰的結點在存儲結構中仍相鄰6．在雙鏈表中，每個結點設置了兩個指針域，其中一個指向（）結點，另一個指向（）結點。【解答】前驅，后繼7．設A是一個線性表（a1,a2,,,an），采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間（1≤i≤n）的概率為，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【解答】，20/90。8．線性表存放在整型數(shù)組A[arrsize]的前elenum個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。具體算法如下：9.已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結點的存儲空間?！窘獯稹恳驗槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink的結點和第一個小于 maxk的結點，再將二者間的所有結點刪除。10．設單循環(huán)鏈表L1，對其遍歷的結果是：x1,x2,x3,,,xn-1,xn。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表L1和L2，使得L1中含有原L1表中序號為奇數(shù)的結點且遍歷結果為： x1,x3,,；L2中含有原L1表中序號為偶數(shù)的結點且遍歷結果為： ,,x4,x2?！窘獯稹克惴ㄈ缦拢旱?章特殊線性表——棧、隊列和串21/90課后習題講解1.填空⑴設有一個空棧，棧頂指針為 1000H，現(xiàn)有輸入序列為 1、2、3、4、5，經過push，push，pop，push，pop，push，push后，輸出序列是（），棧頂指針為（）?！窘獯稹?3，1003H⑵棧通常采用的兩種存儲結構是（）；其判定?？盏臈l件分別是（），判定棧滿的條件分別是（）?！窘獯稹宽樞虼鎯Y構和鏈接存儲結構（或順序棧和鏈棧），棧頂指針top=-1和top=NULL，棧頂指針top等于數(shù)組的長度和內存無可用空間⑶（）可作為實現(xiàn)遞歸函數(shù)調用的一種數(shù)據結構?！窘獯稹織！痉治觥窟f歸函數(shù)的調用和返回正好符合后進先出性。⑷表達式a*(b+c)-d的后綴表達式是（）。【解答】abc+*d-【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。⑸棧和隊列是兩種特殊的線性表，棧的操作特性是（），隊列的操作特性是（），棧和隊列的主要區(qū)別在于（）。22/90【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同⑹循環(huán)隊列的引入是為了克服（）?！窘獯稹考僖绯觫藬?shù)組Q[n]用來表示一個循環(huán)隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為（）?！窘獯稹浚╮ear-front+n）%n【分析】也可以是（rear-front）%n，但rear-front的結果可能是負整數(shù)，而對一個負整數(shù)求模，其結果在不同的編譯器環(huán)境下可能會有所不同。⑻用循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊的時間復雜度分別是（）和（）?！窘獯稹浚?1)，Ｏ(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始查找終端結點的地址。⑼串是一種特殊的線性表，其特殊性體現(xiàn)在（）?！窘獯稹繑?shù)據元素的類型是一個字符⑽兩個串相等的充分必要條件是（）?！窘獯稹块L度相同且對應位置的字符相等【分析】例如"abc"≠"abc，""abc"≠"bca"。2.選擇題23/90⑴若一個棧的輸入序列是1，2，3，,，n，輸出序列的第一個元素是n，則第i個輸出元素是（）。A不確定Bn-iCn-i-1Dn-i+1【解答】D【分析】此時，輸出序列一定是輸入序列的逆序。⑵設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應該是（）。A6B4C3D2【解答】C【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設，即出棧的順序也是e2、e4、e3、e6、e5、e1。⑶一個棧的入棧序列是 1，2，3，4，5，則棧的不可能的輸出序列是（）。A54321B45321C43512D12345【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。⑷設計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據結構最佳A順序表B棧C隊列D鏈表24/90【解答】B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。⑸在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個（）結構。A棧B隊列C數(shù)組D線性表【解答】B【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先出性。⑹一個隊列的入隊順序是 1，2，3，4，則隊列的輸出順序是（）。A4321B1234C1432D3241【解答】B【分析】隊列的入隊順序和出隊順序總是一致的。⑺棧和隊列的主要區(qū)別在于（）。A它們的邏輯結構不一樣 B它們的存儲結構不一樣C所包含的運算不一樣 D插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據結構在針對具體問題時包含的運算都可能不同。⑻設數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。25/90為這兩個棧分配空間的最佳方案是（）。AS1的棧底位置為0，S2的棧底位置為 n-1BS1的棧底位置為 0，S2的棧底位置為n/2CS1的棧底位置為0，S2的棧底位置為nDS1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意C++中的數(shù)組下標是從 0開始的。⑼設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（）。A連接B模式匹配C求子串D求串長【解答】B3.判斷題⑴有n個元素依次進棧，則出棧序列有 (n-1)/2種?！窘獯稹垮e。應該有種。⑵棧可以作為實現(xiàn)過程調用的一種數(shù)據結構?！窘獯稹繉?。只要操作滿足后進先出性，都可以采用棧作為輔助數(shù)據結構。⑶在棧滿的情況下不能做進棧操作，否則將產生 “上溢”?！窘獯稹繉?。⑷在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是26/90front=rear?！窘獯稹垮e。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。⑸空串與空格串是相同的?！窘獯稹垮e?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。4.設有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。C，E，A，B，DC，B，A，D，E【解答】⑴不能，因為在C、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧。⑵可以，設Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為 IIIOOOIOIO。5.舉例說明順序隊列的“假溢出”現(xiàn)象?！窘獯稹考僭O有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標分別為0和1。6.在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。）27/90【解答】棧頂元素為 6，棧底元素為 1。其執(zhí)行過程如圖 3-7所示。7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊）?！窘獯稹筷狀^元素為 5，隊尾元素為 9。其執(zhí)行過程如圖 3-8所示。8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?9.算法設計⑴假設以不帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環(huán)鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：出隊算法如下：28/90⑵設順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢?a2n，a2n-1，，a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，,，a2，a2n-1，a2n-3，,，a1，請設計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為 O(n)?！窘獯稹坎僮鞑襟E為：①將所有元素出棧并入隊；②依次將隊列元素出隊，如果是偶數(shù)結點，則再入隊，如果是奇數(shù)結點，則入棧；③將奇數(shù)結點出棧并入隊；④將偶數(shù)結點出隊并入棧；⑤將所有元素出棧并入隊；⑥將所有元素出隊并入棧即為所求。⑶用順序存儲結構存儲串S，編寫算法刪除S中第i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內容是否存在，若存在，則將第i+j-1之后的字符前移j個位置。算法如下：⑷對于采用順序存儲結構的串 S，編寫一個函數(shù)刪除其值等于 ch的所有字符。【解答】從后向前刪除值為 ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下：⑸對串的模式匹配KMP算法設計求模式滑動位置的next函數(shù)。【解答】參見29/90學習自測及答案1．在一個具有n個單元的順序棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（）。A不變Btop=0;Ctop=top-1;Dtop=top+1;【解答】C2．一個棧的入棧序列是 a,b,c,d,e，則棧的不可能的出棧序列是（）。AedcbaBcdebaCdebcaDabcde【解答】C3．從棧頂指針為top的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執(zhí)行（）。Ax=top;top=top->next;Bx=top->data;Ctop=top->next;x=top->data;Dx=top->data;top=top->next;【解答】D4．設元素1,2,3,P,A依次經過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設計語言的變量名?！窘獯稹縋A321,P3A21,P32A1,P321A,AP3215.設S="I_am_a_teacther"，其長度為（）?！窘獯稹?56．對于棧和隊列，無論它們采用順序存儲結構還是鏈接存儲結構，進行插入和刪除操作的時間復雜度都是30/90（）。【解答】Ｏ(1)7．如果進棧序列為 A、B、C、D，則可能的出棧序列是什么？答：共14種，分別是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA8．簡述隊列和棧這兩種數(shù)據結構的相同點和不同點?！窘獯稹肯嗤c：它們都是插入和刪除操作的位置受限制的線性表。不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。9.利用兩個棧S1和S2模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想?！窘獯稹坷脙蓚€棧S1和S2模擬一個隊列，當需要向隊列中插入一個元素時，用S1來存放已輸入的元素，即通過向棧S1執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將S1中元素全部送入到S2中，再從S2中刪除棧頂元素，最后再將S2中元素全部送入到S1中；判斷隊空的條件是：棧S1和S2同時為空。10.設計算法把一個十進制整數(shù)轉換為二至九進制之間的任一進制數(shù)輸出。【解答】算法基于原理：N=(Ndivd)×d+Nmod（div為整除運算，mod為求余運算）。11．假設一個算術表達式中可以包含三種括號：圓括號“（”和“）”，方括號“[和”“]以”及花括號“{和”“}，”且31/90這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)?！窘獯稹考僭O表達式已存入字符數(shù)組 A[n]中，具體算法如下：第4章廣義線性表——多維數(shù)組和廣義表課后習題講解1.填空⑴數(shù)組通常只有兩種運算：（）和（），這決定了數(shù)組通常采用（）結構來實現(xiàn)存儲。【解答】存取，修改，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。⑵二維數(shù)組A中行下標從10到20，列下標從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是 1000，則元素A[15][10]的存儲地址是（）?！窘獯稹?140【分析】數(shù)組 A中每行共有6個元素，元素A[15][10]的前面共存儲了(15-×6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是 1000+140=1140。⑶設有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素 A[8][5]的存儲地址為（）?！窘獯稹縟+4132/90【分析】元素 A[8][5]的前面共存儲了(1+2+,+8)+5=41個元素。⑷稀疏矩陣一般壓縮存儲方法有兩種，分別是（）和（）?！窘獯稹咳M順序表，十字鏈表⑸廣義表((a),(((b),c)),(d))的長度是（），深度是（），表頭是（），表尾是（）?！窘獯稹?，4，(a)，((((b),c)),(d))⑹已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（）?！窘獯稹縃ead(Head(Tail(LS)))2.選擇題⑴二維數(shù)組A的每個元素是由6個字符組成的串，行下標的范圍從0~8，列下標的范圍是從0~9，則存放A至少需要（）個字節(jié)，A的第8列和第5行共占（）個字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當A按列優(yōu)先方式存儲時的（）元素的起始地址一致。A90B180C240D540E108F114G54HA[8][5]IA[3][10]JA[5][8]KA[4][9]【解答】D，E，K【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+8×10+5=d+85，設元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j×9+i=d+85，33/90解此方程，得 i=4，j=9。⑵將數(shù)組稱為隨機存取結構是因為（）A數(shù)組元素是隨機的 B對數(shù)組任一元素的存取時間是相等的C隨時可以對數(shù)組進行訪問 D數(shù)組的存儲結構是不定【解答】B⑶下面的說法中，不正確的是（）A數(shù)組是一種線性結構 B數(shù)組是一種定長的線性結構除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。⑷對特殊矩陣采用壓縮存儲的目的主要是為了（）A表達變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素 D減少不必要的存儲空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復存儲。⑸下面（）不屬于特殊矩陣。A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣【解答】C34/90⑹若廣義表A滿足Head(A)=Tail(A)，則A為（）A()B(())C((),())D((),(),())【解答】B⑺下面的說法中，不正確的是（）A廣義表是一種多層次的結構 B廣義表是一種非線性結構C廣義表是一種共享結構 D廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關系講，廣義表屬于線性結構。⑻下面的說法中，不正確的是（）對稱矩陣只須存放包括主對角線元素在內的下（或上）三角的元素即可。對角矩陣只須存放非零元素即可。稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應的映象函數(shù)。3.判斷題35/90⑴數(shù)組是一種復雜的數(shù)據結構，數(shù)組元素之間的關系既不是線性的，也不是樹形的。【解答】錯。例如二維數(shù)組可以看成是數(shù)據元素為線性表的線性表。⑵使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑶稀疏矩陣壓縮存儲后，必會失去隨機存取功能。【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關系。⑷線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表?！窘獯稹繉?。⑸若一個廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e。如廣義表 L=(()，(a，b))的表頭為空表，但 L不是空表。4．一個稀疏矩陣如圖 4-4所示，寫出對應的三元組順序表和十字鏈表存儲表示?！窘獯稹繉娜M順序表如圖 4-5所示，十字鏈表如圖 4-6所示。5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結構完成求運算的優(yōu)缺點?！窘獯稹吭O稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復雜度為Ｏ(m×n)；因為要將所有的矩36/90陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復雜度亦為Ｏ(m×n)。如果采用三元組順序表進行壓縮存儲，假設矩陣中有t個非零元素，其空間復雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復雜度亦為Ｏ(t)。當t<<m×n時，采用三元組順序表存儲可獲得較好的時、空性能。6．設某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣”。⑴請用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎金”項；⑵畫出該工資表ST的存儲結構?！窘獯稹竣臩T=((基本工資，津貼，獎金 )，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST))))=獎金⑵工資表ST的頭尾表示法如圖 4-7所示。7．若在矩陣A中存在一個元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設以二維數(shù)組存儲矩陣A，試設計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復雜度?！窘獯稹吭诰仃囍兄鹦袑ふ以撔兄械淖钚≈?，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。37/90具體算法如下：分析算法，外層 for循環(huán)共執(zhí)行n次，內層第一個 for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復雜度為Ｏ(mn+n2)。8．已知兩個n×n的對稱矩陣按壓縮存儲方法存儲在已維數(shù)組A和B中，編寫算法計算對稱矩陣的乘積?！窘獯稹繉ΨQ矩陣采用壓縮存儲，乘積矩陣也采用壓縮存儲。注意矩陣元素的表示方法。第5章樹和二叉樹課后習題講解1.填空題⑴樹是n（n≥0）結點的有限集合，在一棵非空樹中，有（）個根結點，其余的結點分成m（m＞0）個（）的集合，每個集合都是根結點的子樹?！窘獯稹坑星覂H有一個，互不相交⑵樹中某結點的子樹的個數(shù)稱為該結點的（），子樹的根結點稱為該結點的（），該結點稱為其子樹根結點的（）?！窘獯稹慷?，孩子，雙親⑶一棵二叉樹的第i（i≥1）層最多有（）個結點；一棵有n（n>0）個結點的滿二叉樹共有（）個葉子結點和（）個非終端結點。【解答】2i-1，(n+1)/2，(n-1)/238/90【分析】設滿二叉樹中葉子結點的個數(shù)為n0，度為2的結點個數(shù)為n2，由于滿二叉樹中不存在度為1的結點，所以n=n0+n2；由二叉樹的性質n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。⑷設高度為h的二叉樹上只有度為0和度為2的結點，該二叉樹的結點數(shù)可能達到的最大值是（），最小值是（）?！窘獯稹?h-1，2h-1【分析】最小結點個數(shù)的情況是第1層有1個結點，其他層上都只有2個結點。⑸深度為k的二叉樹中，所含葉子的個數(shù)最多為（）?！窘獯稹?k-1【分析】在滿二叉樹中葉子結點的個數(shù)達到最多。⑹具有100個結點的完全二叉樹的葉子結點數(shù)為（）?！窘獯稹?0【分析】100個結點的完全二叉樹中最后一個結點的編號為100，其雙親即最后一個分支結點的編號為50，也就是說，從編號 51開始均為葉子。⑺已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為的結點。則該樹中有（）個葉子結點?！窘獯稹?239/90【分析】根據二叉樹性質3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結點、度為2的結點和度為3的結點的個數(shù)）。⑻某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（）?！窘獯稹緾DBGFEA【分析】根據前序遍歷序列和后序遍歷序列將該二叉樹構造出來。 ⑼在具有n個結點的二叉鏈表中，共有（）個指針域，其中（）個指針域用于指向其左右孩子，剩下的（）個指針域則是空的?！窘獯稹?n，n-1，n+110）在有n個葉子的哈夫曼樹中，葉子結點總數(shù)為（），分支結點總數(shù)為（）?！窘獯稹縩，n-1【分析】n-1個分支結點是經過 n-1次合并后得到的。2.選擇題⑴如果結點A有3個兄弟，B是A的雙親，則結點 B的度是（）。A1B2C3D4【解答】D⑵設二叉樹有n個結點，則其深度為（）。An-1BnC+1D不能確定【解答】D40/90【分析】此題并沒有指明是完全二叉樹，則其深度最多是 n，最少是+1。⑶二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A空或只有一個結點 B高度等于其結點數(shù)C任一結點無左孩子 D任一結點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑷線索二叉樹中某結點 R沒有左孩子的充要條件是（）。AR.lchild=NULLBR.ltag=0CR.ltag=1DR.rchild=NULL【解答】C【分析】線索二叉樹中某結點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標志是否為1。⑸深度為k的完全二叉樹至少有（）個結點，至多有（）個結點，具有個結點的完全二叉樹按層序從開始編號，則編號最小的葉子的序號是（）。A2k-2+1B2k-1C2k-1D2k–1-1E2k+1F2k+1-1G2k-1+1H2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結點數(shù)的情況應是第k層上只有1個結點，最多的情況是滿二叉樹，編號最小的葉子應該是在結點數(shù)最少的情況下，葉子結點的編號。⑹一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有（）成立。41/90An=h+mBh+m=2nCm=h-1Dn=2m-1【解答】D【分析】滿二叉樹中沒有度為1的結點，所以有m個葉子結點，則度為2的結點個數(shù)為m-1。⑺任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序（）。A肯定不發(fā)生改變 B肯定發(fā)生改變C不能確定D有時發(fā)生變化【解答】A【分析】三種遍歷次序均是先左子樹后右子樹。⑻如果T'是由有序樹T轉換而來的二叉樹，那么T中結點的前序序列就是T'中結點的（）序列，T中結點的后序序列就是 T'中結點的（）序列。A前序B中序C后序D層序【解答】A，B⑼設森林中有4棵樹，樹中結點的個數(shù)依次為n1、n2、n3、n4，則把森林轉換成二叉樹后，其根結點的右子樹上有（）個結點，根結點的左子樹上有（）個結點。An1-1Bn1Cn1+n2+n3Dn2+n3+n4【解答】D，A【分析】由森林轉換的二叉樹中，根結點即為第一棵樹的根結點，根結點的左子樹是由第一棵樹中除了根結點以外其余結點組成的，根結點的右子樹是由森林中除第一棵樹外其他樹轉換來的。（10）討論樹、森林和二叉樹的關系，目的是為了（）。42/90借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關問題C將樹、森林轉換成二叉樹體現(xiàn)一種技巧，沒有什么實際意義【解答】B3.判斷題⑴在線索二叉樹中，任一結點均有指向其前趨和后繼的線索?！窘獯稹垮e。某結點是否有前驅或后繼的線索，取決于該結點的標志域是否為1。⑵在二叉樹的前序遍歷序列中，任意一個結點均處在其子女的前面?！窘獯稹繉?。由前序遍歷的操作定義可知。⑶二叉樹是度為2的樹?！窘獯稹垮e。二叉樹和樹是兩種不同的樹結構，例如，左斜樹是一棵二叉樹，但它的度為1。⑷由樹轉換成二叉樹，其根結點的右子樹總是空的?！窘獯稹繉?。因為根結點無兄弟結點。⑸用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結點?！窘獯稹垮e。二叉樹的順序存儲結構是按層序存儲的，一般適合存儲完全二叉樹。4．證明：對任一滿二叉樹，其分枝數(shù)B＝2(n0-1)。（其中，n0為終端結點數(shù)）【解答】因為在滿二叉樹中沒有度為 1的結點，所以有：n=n0+n243/90設B為樹中分枝數(shù)，則n=B+1所以B=n0+n2-1再由二叉樹性質：n0=n2+1代入上式有：B=n0+n0-1-1=2(n0-1)5．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。【解答】證明采用歸納法。設二叉樹的前序遍歷序列為 a1a2a3,an，中序遍歷序列為 b1b2b3,bn。當n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結點，所以，a1=b1，可以唯一確定該二叉樹；假設當n<=k時，前序遍歷序列a1a2a3,ak和中序遍歷序列b1b2b3,bk可唯一確定該二叉樹，下面證明當n=k+1時，前序遍歷序列a1a2a3,akak+1和中序遍歷序列b1b2b3,bkbk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個訪問的一定是根結點，即二叉樹的根結點是a1，在中序遍歷序列中查找值為a144/90的結點，假設為bi，則a1=bi且b1b2,bi-1是對根結點a1的左子樹進行中序遍歷的結果，前序遍歷序列a2a3,ai是對根結點a1的左子樹進行前序遍歷的結果，由歸納假設，前序遍歷序列a2a3,ai和中序遍歷序列b1b2,bi-1唯一確定了根結點的左子樹，同樣可證前序遍歷序列ai+1ai+2,ak+1和中序遍歷序列bi+1bi+2,bk+1唯一確定了根結點的右子樹。6．已知一棵度為 m的樹中有：n1個度為1的結點，n2個度為2的結點，，nm個度為m的結點，問該樹中共有多少個葉子結點？【解答】設該樹的總結點數(shù)為n，則n=n0+n1+n2+,,+nm又：n=分枝數(shù)+1=0×n0+1×n1+2+,,+m×n×nm+1由上述兩式可得：n0=n2+2n3+,,+(m-1)nm+17．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構造該二叉樹?！窘獯稹慷鏄涞臉嬙爝^程如圖 5-12所示。8．對給定的一組權值 W＝5，2，9，11，8，3，7），試構造相應的哈夫曼樹，并計算它的帶權路徑長度?！窘獯稹繕嬙斓墓蚵鼧淙鐖D5-13所示。zzzz45/90樹的帶權路徑長度為：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1209．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用[0，1]進行前綴編碼，問該字符串的編碼至少有多少位?！窘獯稹恳愿髯址霈F(xiàn)的次數(shù)作為葉子結點的權值構造的哈夫曼編碼樹如圖5-14所示。其帶權路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×，3+7所以×，2=98該字符 z10．算法設計⑴設計算法求二叉樹的結點個數(shù)。【解答】本算法不是要打印每個結點的值，而是求出結點的個數(shù)。所以可將遍歷算法中的“訪問”操作改為“計數(shù)操作”，將結點的數(shù)目累加到一個全局變量中，每個結點累加一次即完成了結點個數(shù)的求解。具體算法如下：⑵設計算法按前序次序打印二叉樹中的葉子結點?！窘獯稹勘舅惴ǖ囊笈c前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結點的值，而是打印出其中的葉子結點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：⑶設計算法求二叉樹的深度。46/90【解答】當二叉樹為空時，深度為0；若二叉樹不為空，深度應是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調用本算法來完成。具體算法如下：⑷編寫算法，要求輸出二叉樹后序遍歷序列的逆序?！窘獯稹恳氲玫胶笮虻哪嫘颍灰凑蘸笮虮闅v相反的順序即可，即先訪問根結點，再遍歷根結點的右子樹，最后遍歷根結點的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：⑸以二叉鏈表為存儲結構，編寫算法求二叉樹中結點 x的雙親?！窘獯稹繉Χ骀湵磉M行遍歷，在遍歷的過程中查找結點x并記載其雙親。具體算法如下：⑹以二叉鏈表為存儲結構，在二叉樹中刪除以值x為根結點的子樹。【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結點x并記載其雙親，然后將結點x的雙親結點中指向結點x的指針置空。具體算法如下：⑺一棵具有n個結點的二叉樹采用順序存儲結構，編寫算法對該二叉樹進行前序遍歷?！窘獯稹堪凑疹}目要求，設置一個工作棧以完成對該樹的非遞歸算法，思路如下：①每訪問一個結點，將此結點壓棧，查看此結點是否有左子樹，若有，訪問左子樹，重復執(zhí)行該過程直到左子樹為空。②從棧彈出一個結點，如果此結點有右子樹，訪問右子樹執(zhí)行步驟 ①，否則重復執(zhí)行步驟②。具體算法如下：47/90⑻編寫算法交換二叉樹中所有結點的左右子樹?！窘獯稹繉Χ鏄溥M行后序遍歷，在遍歷過程中訪問某結點時交換該結點的左右子樹。具體算法如下：⑼以孩子兄弟表示法做存儲結構，求樹中結點 x的第i個孩子?！窘獯稹肯仍阪湵碇羞M行遍歷，在遍歷過程中查找值等于x的結點，然后由此結點的最左孩子域firstchild找到值為x結點的第一個孩子，再沿右兄弟域 rightsib找到值為x結點的第個孩子并返回指向這個孩子的指針。樹的孩子兄弟表示法中的結點結構定義如下：templatestructTNode{Tdata;TNode*firstchild,*rightsib;};具體算法如下：學習自測及答案1．前序遍歷和中序遍歷結果相同的二叉樹是（）。根結點無左孩子的二叉樹根結點無右孩子的二叉樹48/90所有結點只有左子樹的二叉樹所有結點只有右子樹的二叉樹【解答】D2．由權值為{3,8,6,2,5}的葉子結點生成一棵哈夫曼樹，其帶權路徑長度為（）。A24B48C53D72【解答】C3．用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數(shù)組A[1]~A[n]中，結點A[i]若有左子樹，則左子樹的根結點是（）。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]【解答】D4．對任何一棵二叉樹T，如果其終端結點的個數(shù)為n0，度為2的結點個數(shù)為n2，則（）。An0=n2-1Bn0=n2Cn0=n2+1D沒有規(guī)律【解答】C5．一棵滿二叉樹中共有n個結點，其中有m個葉子結點，深度為h，則（）。An=h+mBh+m=2nCm=h-1Dn=2h-1【解答】D6．對于完全二叉樹中的任一結點，若其右分支下的子孫的最大層次為 h，則其左分支下的子孫的最大層次為（）。49/90AhBh+1Ch或h+1D任意【解答】C7．假定一棵度為 3的樹中結點數(shù)為 50，則其最小高度應為。A3B4C5D6【解答】C8．在線索二叉樹中，一個結點是葉子結點的充要條件為（）。A左線索標志為0，右線索標志為1B左線索標志為1，右線索標志為0C左、右線索標志均為0D左、右線索標志均為1【解答】C9．對于一棵具有 n個結點的樹，其所有結點的度之和為（）?！窘獯稹縩-110．在順序存儲的二叉樹中，編號為i和j的兩個結點處在同一層的條件是（）?！窘獯稹?1．現(xiàn)有按前序遍歷二叉樹的結果ABC，問有哪幾種不同的二叉樹可以得到這一結果？【解答】共有 5種二叉樹可以得到這一結果，如圖 5-15所示。12．試找出分別滿足下列條件的所有二叉樹：⑴前序序列和中序序列相同。⑵中序序列和后序序列相同。⑶前序序列和后序序列相同。50/90【解答】⑴空二叉樹、只有一個根結點的二叉樹和右斜樹。⑵空二叉樹、只有一個根結點的二叉樹和左斜樹。⑶空二叉樹、只有一個根結點的二叉樹13．將下面圖5-16所示的樹轉換為二叉樹，圖5-17所示的二叉樹轉換為樹或森林?！窘獯稹繄D5-16所示樹轉換的二叉樹如圖5-18所示，圖5-17所示二叉樹轉換的森林如圖5-19所示。14．以孩子兄弟表示法作為存儲結構，編寫算法求樹的深度?！窘獯稹坎捎眠f歸算法實現(xiàn)。若樹為空樹，則其深度為0，否則其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。具體算法如下：15．設計算法，判斷一棵二叉樹是否為完全二叉樹?！窘獯稹扛鶕耆鏄涞亩x可知，對完全二叉樹按照從上到下、從左到右的次序（即層序）遍歷應該滿足：⑴若某結點沒有左孩子，則其一定沒有右孩子；⑵若某結點無右孩子，則其所有后繼結點一定無孩子。若有一結點不滿足其中任意一條，則該二叉樹就一定不是完全二叉樹。因此可采用按層次遍歷二叉樹的方法依次對每個結點進行判斷是否滿足上述兩個條件。為此，需設兩個標志變量BJ和CM，其中BJ表示已掃描過的結點是否均有左右孩子， CM存放局部判斷結果及最后的結果。具體算法如下：51/90第6章圖課后習題講解1.填空題⑴設無向圖G中頂點數(shù)為n，則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n(n-1)/2，0，n(n-1)【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數(shù)達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。⑵任何連通圖的連通分量只有一個，即是（）?！窘獯稹科渥陨恝菆D的存儲結構主要有兩種，分別是（）和（）。【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷已知無向圖G的頂點數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復雜度為（）?！窘獯稹浚?n+e)【分析】在無向圖的鄰接表中，頂點表有 n個結點，邊表有 2e個結點，共有n+2e個結點，其空間復雜度為Ｏ(n+2e)=Ｏ(n+e)。52/90⑸已知一個有向圖的鄰接矩陣表示，計算第 j個頂點的入度的方法是（）?！窘獯稹壳蟮?j列的所有元素之和⑹有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點i的（）。【解答】出度⑺圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據結構是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據結構是（）。【解答】前序，棧，層序，隊列⑻對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復雜度為（），利用Kruskal算法求最小生成樹的時間復雜度為（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用鄰接矩陣做存儲結構，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲結構，適合于求稀疏圖的最小生成樹。⑼如果一個有向圖不存在（），則該圖的全部頂點可以排列成一個拓撲序列?！窘獯稹炕芈罚?0）在一個有向圖中，若存在弧、、，則在其拓撲序列中，頂點vi,vj,vk的相對次序為（）。【解答】vi,vj,vk【分析】對由頂點 vi,vj,vk組成的圖進行拓撲排序。53/902.選擇題⑴在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A1/2B1C2D4【解答】C【分析】設無向圖中含有 n個頂點e條邊，則。⑵n個頂點的強連通圖至少有（）條邊，其形狀是（）。AnBn+1Cn-1Dn ×(n-1)E無回路F有回路G環(huán)狀H樹狀【解答】A，G⑶含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（）。A1Bn/2Cn-1Dn【解答】C【分析】若超過 n-1，則路徑中必存在重復的頂點。⑷對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（）。AnB(n-1)2Cn-1Dn2【解答】D⑸圖的生成樹（），n個頂點的生成樹有（）條邊。A唯一B不唯一C唯一性不能確定 DnEn+1Fn-1【解答】C，F(xiàn)54/90⑹設無向圖G=(V,E)和G'=(V',E')，如果G'是G的生成樹，則下面的說法中錯誤的是（）。AG'為G的子圖BG'為G的連通分量CG'為G的極小連通子圖且 V=V'DG'是G的一個無環(huán)子圖【解答】B【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回路。⑺G是一個非連通無向圖，共有 28條邊，則該圖至少有（）個頂點。A6B7C8D9【解答】D【分析】n個頂點的無向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。⑻最小生成樹指的是（）。A由連通網所得到的邊數(shù)最少的生成樹B由連通網所得到的頂點數(shù)相對較少的生成樹C連通網中所有生成樹中權值之和為最小的生成樹D連通網的極小連通子圖【解答】C⑼判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用（）。A求關鍵路徑的方法 B求最短路徑的方法C廣度優(yōu)先遍歷算法 D深度優(yōu)先遍歷算法【解答】D55/90【分析】當有向圖中無回路時，從某頂點出發(fā)進行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓撲序列。⑽下面關于工程計劃的 AOE網的敘述中，不正確的是（）關鍵活動不按期完成就會影響整個工程的完成時間任何一個關鍵活動提前完成，那么整個工程將會提前完成所有的關鍵活動都提前完成，那么整個工程將會提前完成某些關鍵活動若提前完成，那么整個工程將會提前完【解答】B【分析】AOE網中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關鍵路徑上的關鍵活動。3.判斷題⑴一個有向圖的鄰接表和逆鄰接表中的結點個數(shù)一定相等?！窘獯稹繉?。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結點個數(shù)都等于有向圖中邊的個數(shù)。⑵用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關，而與圖的邊數(shù)無關?！窘獯稹繉Α｀徑泳仃嚨目臻g復雜度為Ｏ (n2)，與邊的個數(shù)無關。⑶圖G的生成樹是該圖的一個極小連通子圖【解答】錯。必須包含全部頂點。⑷無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣