數(shù)據(jù)結構習題包括解析

數(shù)據(jù)結構習題包含答案及分析數(shù)據(jù)結構習題包含答案及分析數(shù)據(jù)結構習題包含答案及分析第1章緒論課后習題解說填空⑴〔〕是數(shù)據(jù)的根本單位，在計算機程序中往常作為一個整體進行考慮和辦理?！窘獯稹繑?shù)據(jù)元素⑵〔〕是數(shù)據(jù)的最小單位，〔〕是議論數(shù)據(jù)結構時波及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項，數(shù)據(jù)元素【剖析】數(shù)據(jù)結構指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關系。⑶從邏輯關系上講，數(shù)據(jù)結構主要分為〔〕、〔〕、〔〕和〔〕?！窘獯稹繒希€性結構，樹結構，圖結構⑷數(shù)據(jù)的儲存結構主要有〔〕和〔〕兩種根本方法，不論哪一種儲存結構，都要儲存雙方面的內(nèi)容：〔〕和〔〕?！窘獯稹看涡騼Υ娼Y構，鏈接儲存結構，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關系⑸算法擁有五個特征，分別是〔〕、〔〕、〔〕、〔〕、〔〕?！窘獯稹坑辛銈€或多個輸入，有一個或多個輸出，有窮性，確立性，可行性⑹算法的描繪方法往常有〔〕、〔〕、〔〕和〔〕四種，其中，〔〕被稱為算法語言?！窘獯稹孔匀徽Z言，程序設計語言，流程圖，偽代碼，偽代碼⑺在一般狀況下，一個算法的時間復雜度是〔〕的函數(shù)?！窘獯稹繂栴}規(guī)模⑻設待辦理問題的規(guī)模為n，假定一個算法的時間復雜度為一個常數(shù)，那么表示成數(shù)目級的形式為〔〕，假定為n*log25n，那么表示成數(shù)目級的形式為〔〕?！窘獯稹喀?1)，Ο(nlog2n)【剖析】用大O記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。選擇題⑴次序儲存結構中數(shù)據(jù)元素之間的邏輯關系是由〔〕表示的，鏈接儲存結構中的數(shù)據(jù)元素之間的邏輯關系是由〔〕表示的。A線性結構B非線性結構C儲存地點D指針【解答】C，D【剖析】次序儲存結構就是用一維數(shù)組儲存數(shù)據(jù)結構中的數(shù)據(jù)元素，其邏輯關系由儲存地點〔即元素在數(shù)組中的下標〕表示；鏈接儲存結構中一個數(shù)據(jù)元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中的指針表示。⑵假定有以下遺產(chǎn)繼承規(guī)那么：丈夫和老婆能夠互相繼承遺產(chǎn)；兒女能夠繼承父親或母親的遺產(chǎn)；兒女間不能互相繼承。那么表示該遺產(chǎn)繼承關系的最適合的數(shù)據(jù)結構應當是〔〕。A樹B圖C線性表D會合【解答】B【剖析】將丈夫、老婆和兒女分別作為數(shù)據(jù)元素，依據(jù)題意畫出邏輯結構圖。⑶算法指的是〔〕。對特定問題求解步驟的一種描繪，是指令的有限序列。計算機程序C解決問題的計算方法D數(shù)據(jù)辦理【解答】A【剖析】計算機程序是對算法的詳細實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)辦理是經(jīng)過算法達成的。所以，只有A是算法的正確立義。⑷下邊〔〕不是算法所一定具備的特征。A有窮性B切實性C高效性D可行性【解答】C【剖析】高效性是好算法應具備的特征。⑸算法剖析的目的是〔〕，算法剖析的兩個主要方面是〔〕。A找出數(shù)據(jù)結構的合理性

B研究算法中輸入和輸出的關系C剖析算法的效率以求改進

D剖析算法的易讀性和文檔性E空間性能和時間性能

F正確性和簡潔性G可讀性和文檔性H數(shù)據(jù)復雜性和程序復雜性【解答】C，E判斷題⑴算法的時間復雜度都要經(jīng)過算法中的根本語句的履行次數(shù)來確立?！窘獯稹垮e。時間復雜度要經(jīng)過算法中根本語句履行次數(shù)的數(shù)目級來確立。⑵每種數(shù)據(jù)結構都具備三個根本操作：插入、刪除和查找。【解答】錯。如數(shù)組就沒有插入和刪除操作。本題注意是每種數(shù)據(jù)結構。⑶所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)之間的邏輯關系。【解答】錯。是數(shù)據(jù)之間的邏輯關系的整體。⑷邏輯結構與數(shù)據(jù)元素自己的內(nèi)容和形式?jīng)]關?！窘獯稹繉?。所以邏輯結構是數(shù)據(jù)組織的主要方面。⑸鑒于某種邏輯結構之上的根本操作，其實現(xiàn)是獨一的?！窘獯稹垮e。根本操作的實現(xiàn)是鑒于某種儲存結構設計的，因此不是獨一的。4.剖析以下各程序段，并用大O記號表示其履行時間?！窘獯稹竣鸥菊Z句是k=k+10*i，共履行了n-2次，所以T(n)=O(n)。⑵根本語句是k=k+10*i，共履行了n次，所以T(n)=O(n)。⑶剖析條件語句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T(n)=O(n)。⑷設循環(huán)體共履行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最后T(n)=y，即：(T(n)+1)2≤n，所以T(n)=O(n1/2)。⑸x++是根本語句，所以5．設有數(shù)據(jù)結構〔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)}。試畫出其邏輯結構圖并指出屬于何種結構?！窘獯稹科溥壿嫿Y構圖如圖1-3所示，它是一種圖結構。為整數(shù)定義一個抽象數(shù)據(jù)種類，包含整數(shù)的常有運算，每個運算對應一個根本操作，每個根本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)型定以下：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的生改Add前置條件：存在一個整數(shù)a入：一個整數(shù)b功能：將整數(shù)a與入的整數(shù)b相加出：相加后的果后置條件：整數(shù)a的生改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ù)b功能：將整數(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的不生改endADT求多式A(x)的算法可依據(jù)以下兩個公式之一來：⑴A(x)=anxn+an-1xn-1+?+a1x+a0A(x)=(?(anx+an-1)x+?+a1)x)+a0依據(jù)算法的復度剖析比兩種算法的劣?！窘獯稹康诙N算法的性能要好些。第一種算法需行大批的乘法運算，而第二種算法行了化，減少了不用要的乘法運算。8.算法〔要求：算法用代和C++描繪，并剖析最壞狀況下的復度〕⑴一個整型數(shù)A[n]一個排序算法?！窘獯稹肯逻吺桥判蛩惴ǖ拇枥L。下邊是排序算法的C++描繪。剖析算法，有兩層嵌套的for循環(huán)，所以，。⑵找出整型數(shù)組A[n]中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描繪以下：算法的C++描繪以下：剖析算法，只有一層循環(huán)，共履行n-2次，所以，T(n)=O(n)。學習自測及答案1．次序儲存結構的特色是〔〕，鏈接儲存結構的特色是〔〕。【解答】用元素在儲存器中的相對地點來表示數(shù)據(jù)元素之間的邏輯關系，用指示元素儲存地點的指針表示數(shù)據(jù)元素之間的邏輯關系。2.算法在發(fā)生非法操作時能夠作出辦理的特征稱為〔〕?！窘獯稹繌娊⌒猿Ｓ械乃惴〞r間復雜度用大Ｏ記號表示為：常數(shù)階( )、對數(shù)階( )、線性階( )、平方階( )和指數(shù)階( )?！窘獯稹浚?1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．將以下函數(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ù)據(jù)結構和抽象數(shù)據(jù)種類的觀點與程序設計語言中數(shù)據(jù)種類觀點的差別?！窘獯稹繑?shù)據(jù)結構是指互相之間存在必定關系的數(shù)據(jù)元素的會合。而抽象數(shù)據(jù)種類是指一個數(shù)據(jù)結構以及定義在該結構上的一組操作。程序設計語言中的數(shù)據(jù)種類是一個值的會合和定義在這個值集上一組操作的總稱。抽象數(shù)據(jù)種類能夠當作是對數(shù)據(jù)種類的一種抽象。對以下用二元組表示的數(shù)據(jù)結構,試分別畫出對應的邏輯結構圖，并指出屬于何種結構。⑴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)所示。求以下算法的時間復雜度。count=0;x=1;while(x{x*=2;count++;}returncount;【解答】Ｏ(log2n)第2章線性表課后習題解說填空⑴在次序表中，等概率狀況下，插入和刪除一個元素均勻需挪動〔〕個元素，詳細挪動元素的個數(shù)與〔〕和〔〕相關?！窘獯稹勘黹L的一半，表長，該元素在表中的地點⑵次序表中第一個元素的儲存地點是100，每個元素的長度為2，那么第5個元素的儲存地點是〔〕?！窘獯稹?08【剖析】第5個元素的儲存地點=第1個元素的儲存地點＋(5－1)×2=108⑶設單鏈表中指針p指向結點A，假定要刪除A的后繼結點〔假定A存在后繼結點〕，那么需改正指針的操作為〔〕?！窘獯稹縫->next=(p->next)->next⑷單鏈表中設置頭結點的作用是〔〕。【解答】為了運算方便【剖析】比如在插入和刪除操作時不用對表頭的狀況進行特別辦理。⑸非空的單循環(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所指結點后插入一個新結點的時間復雜度為〔〕；在給定值為x的結點后插入一個新結點的時間復雜度為〔〕。【解答】Ο(1)，Ο(n)【剖析】在p所指結點后插入一個新結點只需改正指針，所以時間復雜度為Ο(1)；而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時間復雜度為Ο(n)。⑻可由一個尾指針獨一確立的鏈表有〔〕、〔〕、〔〕?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2.選擇題⑴線性表的次序儲存結構是一種〔〕的儲存結構，線性表的鏈接儲存結構是一種〔〕的儲存結構。A隨機存取B次序存取C索引存取D散列存取【解答】A，B【剖析】拜見。⑵線性表采納鏈接儲存時，其地點〔〕。A一定是連續(xù)的B局部地點一定是連續(xù)的C必定是不連續(xù)的D連續(xù)與否均能夠【解答】D【剖析】線性表的鏈接儲存是用一組隨意的儲存單元儲存線性表的數(shù)據(jù)元素，這組儲存單元能夠連續(xù)，也能夠不連續(xù)，甚至能夠零落散布在內(nèi)存中隨意地點。⑶單循環(huán)鏈表的主要優(yōu)點是〔〕。不再需要頭指針了從表中任一結點出發(fā)都能掃描到整個鏈表；某個結點的地點后，能夠簡單找到它的直接前趨；在進行插入、刪除操作時，能更好地保證鏈表不停開?！窘獯稹緽⑷鏈表不擁有的特色是〔〕。A可隨機接見任一元素B插入、刪除不需要挪動元素C不用預先預計儲存空間D所需空間與線性表長度成正比【解答】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é)儉運算時間。

〕儲存方A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表【解答】B【剖析】在鏈表中的最后一個結點以后插入一個結點需要知道終端結點的地點，所以，單鏈表、單循環(huán)鏈表都不適合，刪除最后一個結點需要知道終端結點的前驅(qū)結點的地點，所以，帶尾指針的單循環(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ù)據(jù)的插入和刪除C節(jié)儉儲存空間D很快回收儲存空間【解答】B【剖析】在鏈表中一般只好進行次序查找，所以，雙鏈表其實不可以提升查找速度，因為雙鏈表中有兩個指針域，明顯不可以節(jié)儉儲存空間，對于動向儲存分派，回收儲存空間的速度是同樣的。因為雙鏈表擁有對稱性，所以，其插入和刪除操作更為方便。⑾在一個單鏈表中，q所指結點是p所指結點的直接前驅(qū)，假定在q和p之間插入s所指結點，那么履行〔〕操作。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的圖解。判斷題⑴線性表的邏輯次序和儲存次序老是一致的。【解答】錯。次序表的邏輯次序和儲存次序一致，鏈表的邏輯次序和儲存次序不必定一致。⑵線性表的次序儲存結構優(yōu)于鏈接儲存結構。【解答】錯。兩種儲存結構各有優(yōu)弊端。⑶設p，q是指針，假定p=q，那么*p=*q?！窘獯稹垮e。p=q只好表示p和q指向同一同始地點，而所指種類那么不必定同樣。⑷線性結構的根本特色是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼?！窘獯稹垮e。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。⑸在單鏈表中，要獲得某個元素，只需知道該元素所在結點的地點即可，所以單鏈表是隨機存取結構。【解答】錯。要找到該結點的地點，一定從頭指針開始查找，所以單鏈表是次序存取結構。4．請說明次序表和單鏈表各有何優(yōu)弊端，并剖析以下狀況下，采納何種儲存結構更好些。⑴假定線性表的總長度根本穩(wěn)固，且極少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。⑵假如n個線性表同時并存，并且在辦理過程中各表的長度會動向發(fā)生變化。⑶描繪一個城市的設計和規(guī)劃。【解答】次序表的優(yōu)點：①無需為表示表中元素之間的邏輯關系而增添額外的儲存空間；②能夠迅速地存取表中任一地點的元素〔即隨機存取〕。次序表的弊端：①插入和刪除操作需挪動大批元素；②表的容量難以確立；③造成儲存空間的“碎片〞。單鏈表的優(yōu)點：①不用預先知道線性表的長度；②插入和刪除元素時只需改正指針，不用挪動元素。單鏈表的弊端：①指針的結構性開支；②存取表中隨意元素不方便，只好進行次序存取。⑴應采納次序儲存結構。因為次序表是隨機存取結構，單鏈表是次序存取結構。操作，所以空間變化不大，且需要迅速存取，所以應采納次序儲存結構。

本題極少進行插入和刪除⑵應采納鏈接儲存結構。鏈表簡單實現(xiàn)表容量的擴大，合適表的長度動向發(fā)生變化。⑶應采納鏈接儲存結構。因為一個城市的設計和規(guī)劃波及活動好多，才能適應不停展開的需要。而次序表的插入、刪除的效率低，故不適合。

需要常常改正、擴大和刪除各樣信息，5．算法設計⑴設計一個時間復雜度為Ｏ(n)的算法，實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個地點?！窘獯稹克惴ㄋ枷胝埌菀娭鹘滩牡谝徽滤枷牖鸹?。下邊給出詳細算法。剖析算法，第一次調(diào)用Reverse函數(shù)的時間復雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復雜度為第三次調(diào)用Reverse函數(shù)的時間復雜度為O(n)，所以，總的時間復雜度為O(n)。

O(n-k)，⑵數(shù)組A[n]中的元素為整型，設計算法將其調(diào)整為左右兩局部，為偶數(shù)，并要求算法的時間復雜度為Ｏ(n)。

左側所有元素為奇數(shù)，右側所有元素【解答】從數(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.2.4算法

2-4和算法

2-6。⑸假定在長度大于1的循環(huán)鏈表中，即無頭結點也無頭指針，法刪除結點s的前趨結點。

s為指向鏈表中某個結點的指針，試編寫算【解答】利用單循環(huán)鏈表的特色，

經(jīng)過指針

s可找到其前驅(qū)結點

r以及

r的前驅(qū)結點

p，而后將結點

r刪除，如圖2-11所示，詳細算法以下：⑹一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其余字符。試編寫算法，結構三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符。【解答】在單鏈表A中挨次取元素，假定拿出的元素是字母，把它插入到字母鏈表B中，假定拿出的元素是數(shù)字，那么把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別寄存字母、數(shù)字和其余字符。詳細算法以下：⑺設單鏈表以非遞減有序擺列，設計算法實此刻單鏈表中刪去值同樣的剩余結點?！窘獯稹繌念^至尾掃描單鏈表，假定目前結點的元素值與后繼結點的元素值不相等，那么指針后移；否那么刪除該后繼結點。詳細算法以下：⑻判斷帶頭結點的雙循環(huán)鏈表能否對稱?！窘獯稹吭O工作指針p和q分別指向循環(huán)雙鏈表的開始結點和終端結點，假定結點p和結點q的數(shù)據(jù)域相等，那么工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點〔循環(huán)雙鏈表中結點個數(shù)為奇數(shù)〕，或結點q成為結點p的前驅(qū)〔循環(huán)雙鏈表中結點個數(shù)為偶數(shù)〕。如圖2-12所示。學習自測及答案1.一數(shù)A采納序存構，每個元素占用4個存元，第9個元素的地點144，第一個元素的地點是〔〕。A108B180C176D112【解答】D2．在度n的性表中找x的數(shù)據(jù)元素的復度：〔〕。AO(0)BO(1)CO(n)DO(n2)【解答】C3．在一個度n的序表的第i〔1≤i≤n+1〕個元素從前插入一個元素，需向后移〔〕個元素，除第i〔1≤i≤n〕個元素，需向前移〔〕個元素?！窘獯稹縩-i+1，n-i4．在表中，除了點以外，任一點的存地點由〔〕指示?！窘獯稹科淝包c的指域5．當性表采納序存構，其主要特色是〔〕?！窘獯稹繕嬛邢嗟狞c在存構中仍相6．在雙表中，每個點置了兩個指域，其中一個指向〔〕點，另一個指向〔〕點。【解答】前，后7．A是一個性表〔a1,a2,?〕,an，采納序存構，在等概率的前提下，均勻每插入一個元素需要移的元素個數(shù)多少假定元素插在ai與ai+1之〔1≤i≤n〕的概率，均勻每插入一個元素所要移的元素個數(shù)又是多少【解答】，。8．線性表寄存在整型數(shù)組

A[arrsize]的前

elenum

個單元中，且遞加有序。編寫算法，將元素

x插入到線性表的合適地點上，以保持線性表的有序性，并且剖析算法的時間復雜度?！窘獯稹勘绢}是在一個遞加有序表中插入元素x，根本思路是從有序表的尾部開始挨次取元素與x比較，假定大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否那么，找到插入地點，將x插入。詳細算法以下：9.單鏈表中各結點的元素值為整型且遞加有序，

設計算法刪除鏈表中所有大于

mink

且小于

maxk的所有元素，并開釋被刪結點的儲存空間?！窘獯稹恳驗槭窃谟行騿捂湵砩系牟僮鳎?，要充分利用其有序性。在單鏈表中查找第一個大于

mink的結點和第一個小于

maxk的結點，再將兩者間的所有結點刪除。10．循表L1，其遍的果是：x1,x2,x3,?-1,xn。將循表拆成兩個循表L1和L2，使得L1中含有原L1表中序號奇數(shù)的點且遍果：x1,x3,?；L2中含有原L1表中序號偶數(shù)的點且遍果：?,x4,x2?！窘獯稹克惴ㄒ韵拢旱?章特別線性表——棧、隊列和串課后習題解說1.填空⑴設有一個空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是〔〕，棧頂指針為〔〕?！窘獯稹?3，1003H⑵棧往常采納的兩種儲存結構是〔〕；其判斷?？盏臈l件分別是〔〕，判斷棧滿的條件分別是〔〕?！窘獯稹看涡騼Υ娼Y構和鏈接儲存結構〔或次序棧和鏈?！?，棧頂指針top=-1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間⑶〔〕可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結構。【解答】?！酒饰觥窟f歸函數(shù)的調(diào)用和返回正好切合后進先出性。⑷表達式a*(b+c)-d的后綴表達式是〔〕?！窘獯稹縜bc+*d-【剖析】將中綴表達式變成后綴表達式有一個技巧：將操作數(shù)挨次寫下來，再將算符插在它的兩個操作數(shù)的后邊。⑸棧和隊列是兩種特別的線性表，棧的操作特征是〔〕，隊列的操作特征是〔〕，棧和隊列的主要差別在于〔〕?！窘獯稹亢筮M先出，先進先出，對插入和刪除操作限制的地點不同⑹循環(huán)隊列的引入是為了戰(zhàn)勝〔〕?！窘獯稹考僖绯觫藬?shù)組Q[n]用來表示一個循環(huán)隊列，front為隊頭元素的前一個地點，rear為隊尾元素的地點，計算隊列中元素個數(shù)的公式為〔〕。【解答】〔rear-front+n〕%n【剖析】也能夠是〔rear-front〕%n，但rear-front的結果可能是負整數(shù)，而對一個負整數(shù)求模，其結果在不同的編譯器環(huán)境下可能會有所不同。⑻用循環(huán)鏈表表示的隊列長度為n，假定只設頭指針，那么出隊和入隊的時間復雜度分別是〔〕和〔〕?！窘獯稹浚?1)，Ｏ(n)【剖析】在指的循表中，出即是除開始點，只需改正相指；入即是在端點的后邊插入一個點，需要從指開始找端點的地點。⑼串是一種特別的性表，其特別性體在〔〕。【解答】數(shù)據(jù)元素的型是一個字符⑽兩個串相等的充分必需條件是〔〕。【解答】度同樣且地點的字符相等【剖析】比如"abc"≠"abc，""abc"≠"bca"。2.⑴假定一個的入序列是1，2，3，?，n，出序列的第一個元素是n，第i個出元素是〔〕。A不確立Bn-iCn-i-1Dn-i+1【解答】D【剖析】此，出序列必定是入序列的逆序。⑵S和列Q的初始狀空，元素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【剖析】此有一個技巧：在出序列中隨意元素后邊不可以出比元素小并且是升序〔指的是元素的序號〕的兩個元素。⑷一個判表達式中左右括號能否配的算法，采納〔〕數(shù)據(jù)構最正確A序表BC列D表【解答】B【剖析】每個右括號與它前面的最后一個沒有般配的左括號配對，所以擁有后進先出性。⑸在解決心算機主機與打印機之間速度不般配問題時往常設置一個打印緩沖區(qū)，結構。

該緩沖區(qū)應當是一個〔〕A棧

B隊列

C數(shù)組

D線性表【解答】

B【剖析】先進入打印緩沖區(qū)的文件先被打印，所以擁有先進先出性。⑹一個隊列的入隊次序是

1，2，3，4，那么隊列的輸出次序是〔

〕。A4321B1234C1432D3241【解答】

B【剖析】隊列的入隊次序和出隊次序老是一致的。⑺棧和隊列的主要差別在于〔

〕。A它們的邏輯結構不同樣B它們的儲存結構不同樣C所包含的運算不同樣D插入、刪除運算的限制不同樣【解答】D【剖析】棧和隊列的邏輯結構都是線性的，都有次序儲存和鏈接儲存，有可能包含的運算不同樣，但不是主要差別，任何數(shù)據(jù)結構在針對詳細問題時包含的運算都可能不同。⑻設數(shù)組S[n]作為兩個棧S1和S2的儲存空間，對任何一個棧只有當這兩個棧分派空間的最正確方案是〔〕。

S[n]全滿時才不可以進前進棧操作。為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求串長【解答】B判斷題⑴有n個元素挨次進棧，那么出棧序列有(n-1)/2種。【解答】錯。應當有種。⑵棧能夠作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結構?！窘獯稹繉ΑＶ恍璨僮髦愫筮M先出性，都能夠采納棧作為協(xié)助數(shù)據(jù)結構。⑶在棧滿的狀況下不可以做進棧操作，否那么將產(chǎn)生“上溢〞?！窘獯稹繉Α＂仍谘h(huán)隊列中，front指向隊頭元素的前一個地點，rear指向隊尾元素的地點，那么隊滿的條件是front=rear?！窘獯稹垮e。這是隊空的判斷條件，在循環(huán)隊列中要將隊空和隊滿的判斷條件差別開。⑸空串與空格串是同樣的?！窘獯稹垮e?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。設有一個棧，元素進棧的次序為A，B，C，D，E，可否獲取以下出棧序列，假定能，請寫出操作序列，假定不可以，請說明原由。C，E，A，B，DC，B，A，D，E【解答】⑴不可以，因為在C、E出棧的狀況下，A必定在棧中，并且在

B的下邊，不行能先于

B出棧。⑵可以，設Ｉ為進棧操作，Ｏ為入棧操作，那么其操作序列為IIIOOOIOIO。舉例說明次序隊列的“假溢出〞現(xiàn)象。【解答】假定有一個次序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，假如再有元素入隊，就會產(chǎn)生“上溢〞，此時的“上溢〞又稱為“假溢出〞，因為隊列其實不是真的溢出了，儲存隊列的數(shù)組中還有2個儲存單元安閑，其下標分別為0和1。在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)以后，棧頂元素和棧底元素分別是什么〔push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧?！场窘獯稹織ｍ斣貫?，棧底元素為1。其履行過程如圖3-7所示。7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)以后，隊頭元素和隊尾元素分別是什么〔EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊〕。【解答】隊頭元素為5，隊尾元素為9。其履行過程如圖3-8所示。8．空串和空格串有何差別串中的空格符有何意義空串在串辦理中有何作用【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分開一般的字符，便于人們辨別和閱讀，但計算串長時應包含這些空格符?？沾诖k理中可作為隨意串的子串。算法設計⑴假以不點的循表表示列，并且只一個指指向尾點，但不指。相的入和出的算法。【解答】出操作是在循表的部行，相當于除開始點，而入操作是在循表的尾部行，相當于在端點以后插入一個點。因為循表不點，需要理空表的特別狀況。入算法以下：出算法以下：⑵序S中有2n個元素，從究竟的元素挨次a2n，a2n-1，?，a1，要求通一個循列從頭擺列中元素，使得從究竟的元素挨次a2n，a2n-2，?，a2，a2n-1，a2n-3，?，a1，算法操作，要求空復度和復度均O(n)?！窘獯稹坎僮鞑剑孩賹⑺性爻霾⑷耄虎诎ご螌㈥犃性爻鲫?，假如是偶數(shù)結點，那么再入隊，假如是奇數(shù)結點，那么入棧；③將奇數(shù)結點出棧并入隊；④將偶數(shù)結點出隊并入棧；⑤將所有元素出棧并入隊；⑥將所有元素出隊并入棧即為所求。⑶用次序儲存結構儲存串S，編寫算法刪除S中第i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容能否存在，假定存在，那么將第i+j-1以后的字符前移j個地點。算法以下：⑷對于采納次序儲存結構的串S，編寫一個函數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有挪動的元素中沒有值為ch的元素，能減少挪動元素的次數(shù)，提升算法的效率。算法以下：⑸對串的模式般配KMP算法設計求模式滑動地點的next函數(shù)。【解答】拜見學習自測及答案1．在一個擁有針，當出棧時，

n個單元的次序棧中，假定以地點低端〔即下標為top的變化為〔〕。

0的單元〕作為棧底，以

top

作為棧頂指A不變

Btop=0;Ctop=top-1;Dtop=top+1;【解答】

C2．一個棧的入棧序列是a,b,c,d,e，那么棧的不行能的出棧序列是〔AedcbaBcdebaCdebcaDabcde

〕。【解答】

C3．從棧頂指針為top的鏈棧中刪除一個結點，用

x保留被刪除結點的值，那么履行〔

〕。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挨次經(jīng)過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設計語言的變量名?！窘獯稹縋A321,P3A21,P32A1,P321A,AP3215.設S="I_am_a_teacther"，其長度為〔〕?！窘獯稹?5第4章廣義線性表——多維數(shù)組和廣義表課后習題解說填空⑴數(shù)組往常只有兩種運算：〔〕和〔〕，這決定了數(shù)組往常采納〔〕結構來實現(xiàn)儲存。【解答】存取，改正，次序儲存【剖析】數(shù)組是一個擁有固定格式和數(shù)目的數(shù)據(jù)會合，在數(shù)組上一般不可以做插入、刪除元素的操作。除了初始化和銷毀以外，在數(shù)組中往常只有存取和改正兩種操作。⑵二數(shù)A中行下從10到20，列下從5到10，按行先存，每個元素占4個存元，A[10][5]的存地點是1000，元素A[15][10]的存地點是〔〕?！窘獯稹?140【剖析】數(shù)A中每行共有6個元素，元素A[15][10]的前面共存了(15-10)×6+5個元素，每個元素占4個存元，所以，其存地點是1000+140=1140。⑶有一個10的稱矩A采納存，A[0][0]第一個元素，其存地點d，每個元素占1個存元，元素A[8][5]的存地點〔〕?！窘獯稹縟+41【剖析】元素A[8][5]的前面共存了(1+2+?+8)+5=41個元素。⑷稀少矩一般存方法有兩種，分是〔〕和〔〕?！窘獯稹咳虮恚直恝蓮V表((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起碼需要〔〕個字，A的第8列和第5行共占〔〕個字，假定A按行先方式存，元素A[8][5]的開端地點與當A按列先方式存的〔〕元素的開端地點一致。A90B180C240D540E108F114G54HA[8][5]IA[3][10]JA[5][8]KA[4][9]【解答】D，E，K【剖析】數(shù)A9行10列，共有90個元素，所以，寄存A起碼需要90×6=540個存元，第8列和第5行共有18個元素〔注意隊列有一個交錯元素〕，所以，共占108個字，元素A[8][5]按行先存的開端地點d+8×10+5=d+85，元素A[i][j]按列先存的開端地點與之同樣，d+j×9+i=d+85，解此方程，得i=4，j=9。⑵將數(shù)稱隨機存取構是因〔〕A數(shù)組元素是隨機的B對數(shù)組任一元素的存取時間是相等的C隨時能夠?qū)?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對稱矩陣【解答】C⑹假定廣義表A知足Head(A)=Tail(A)，那么A為〔〕A( )B(( ))C(( ),( ))D(( ),( ),( ))【解答】B⑺下邊的說法中，不正確的選項是〔〕A廣義表是一種多層次的結構B廣義表是一種非線性結構C廣義表是一種共享結構D廣義表是一種遞歸【解答】B【剖析】從各層元素各自擁有的線性關系講，廣義表屬于線性結構。⑻下邊的說法中，不正確的選項是〔〕對稱矩陣只須寄存包含主對角線元素在內(nèi)的下〔或上〕三角的元素即可。對角矩陣只須寄存非零元素即可。稀少矩陣中值為零的元素許多，所以能夠采納三元組表方法儲存。稀少矩陣中大批值為零的元素散布有規(guī)律，所以能夠采納三元組表方法儲存【解答】D【剖析】稀少矩陣中大批值為零的元素散布沒有規(guī)律，所以采納三元組表儲存。假如零元素的散布有規(guī)律，就沒有必需儲存非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應的映象函數(shù)。判斷題⑴數(shù)組是一種復雜的數(shù)據(jù)結構，數(shù)組元素之間的關系既不是線性的，也不是樹形的?！窘獯稹垮e。比如二維數(shù)組能夠當作是數(shù)據(jù)元素為線性表的線性表。⑵使用三元組表儲存稀少矩陣的元素，有時其實不可以節(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)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復雜度亦為Ｏ(m×n)。假如采納三元組次序表進行壓縮儲存，假定矩陣中有t個非零元素，其空間復雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組次序表掃描一遍，其時間復雜度亦為Ｏ(t)。當t<<m×n時，采納三元組次序表儲存可獲取較好的時、空性能。6．設某單位員工薪資表ST由“薪資〞、“扣除〞和“實發(fā)金額〞三項構成，其中薪資項包含“根本薪資〞、“津貼〞和“獎金〞，扣除項包含“水〞、“電〞和“煤氣〞。⑴請用廣義表形式表示所描繪的薪資表ST，并用表頭和表尾求表中的“獎金〞項；⑵畫出該薪資表ST的儲存結構。【解答】⑴ST=((根本薪資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST))))=獎金⑵薪資表ST的頭尾表示法如圖4-7所示。7．假定在矩陣A中存在一個元素ai,j〔0≤i≤n-1，0≤j≤m-1〕，該元素是第中最大值，那么稱此元素為該矩陣的一個馬鞍點。假定以二維數(shù)組儲存矩陣鞍點的算法，并剖析最壞狀況下的時間復雜度。

i行元素中最小值且又是第j列元素A，試設計一個求該矩陣所有馬【解答】在矩陣中逐行找尋該行中的最小值，而后對其所在的列找尋最大值，假如該列上的最大值與該行上的最小值相等，那么說明該元素是鞍點，將它所內(nèi)行號和列號輸出。詳細算法以下：剖析算法，外層for循環(huán)共履行n次，內(nèi)層第一個for循環(huán)履行m次，第二個for循環(huán)最壞狀況下履行n次，所以，最壞狀況下的時間復雜度為Ｏ(mn+n2)。學習自測及答案1．二維數(shù)組M中每個元素的長度是3個字節(jié)，行下標從0到7，列下標從0到9，從首地點d開始儲存。假定按行優(yōu)先方式儲存，元素M[7][5]的開端地點為〔〕，假定按列優(yōu)先方式儲存，元素M[7][5]的開端地址為〔〕?！窘獯稹縟+22，d+1412．一個n×n的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮儲存，那么其儲存容量為〔〕?！窘獯稹縩(n+1)/23．設n行n列的下三角矩陣A〔隊列下標均從1開始〕已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，假定按行優(yōu)先儲存，那么A[i][j]在數(shù)組S中的儲存地點是〔〕?！窘獯稹縤×(i-1)/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))Cb,(c,(d))D(b,(c,(d)))【解答】D6．設有三對角矩陣An×n〔行、列下標均從0開始〕，將其三條對角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=aij求：⑴用i,j表示k的下標變換公式；⑵用k表示i,j的下標變換公式?！窘獯稹竣乓骾,j表示k的下標變換公式，就是要求在k從前已經(jīng)儲存了多少個非零元素，這些非零元素的個數(shù)就是k的值。元素aij求所在的行為i，列為j，那么在其前面的非零元素的個數(shù)是；k=2+3(i－1)+(ji+1)=2i+j。⑵因為k和i,j之間是一一對應的關系，k+1是目前非零元素的個數(shù)，整除即為其所內(nèi)行號，取余表示目前行中第幾個非零元素，加上前面零元素所在列數(shù)就是目前列號，即：7．兩個n×n的對稱矩陣按壓縮儲存方法儲存在已維數(shù)組A和B中，編寫算法計算對稱矩陣的乘積?！窘獯稹繉ΨQ矩陣采納壓縮儲存，乘積矩陣也采納壓縮儲存。注意矩陣元素的表示方法。第5章樹和二叉樹課后習題解說1.填空題⑴樹是n〔n≥0〕結點的有限會合，在一棵非空樹中，有〔〕個根結點，其余的結點分紅m〔m＞0〕個〔〕的會合，每個會合都是根結點的子樹?！窘獯稹坑星覂H有一個，互不訂交⑵樹中某結點的子樹的個數(shù)稱為該結點的〔〕，子樹的根結點稱為該結點的〔〕，該結點稱為其子樹根結點的〔〕?！窘獯稹慷?，孩子，雙親⑶一棵二叉樹的第i〔i≥1〕層最多有〔〕個結點；一棵有n〔n>0〕個結點的滿二叉樹共有〔〕個葉子結點和〔〕個非終端結點?！窘獯稹?i-1，(n+1)/2，(n-1)/2【剖析】設滿二叉樹中葉子結點的個數(shù)為n0，度為2的結點個數(shù)為n2，因為滿二叉樹中不存在度為1的結點，所以n=n0+n2；由二叉樹的性質(zhì)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ù)為〔〕。【解答】50【剖析】100個結點的完整二叉樹中最后一個結點的編號為100，其雙親即最后一個分支結點的編號為50，也就是說，從編號51開始均為葉子。⑺一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點。那么該樹中有〔〕個葉子結點?！窘獯稹?2【剖析】依據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1〔n0、n2、n3分別為葉子結點、度為2的結點和度為3的結點的個數(shù)〕。⑻某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，那么后來序遍歷序列是〔〕?！窘獯稹緾DBGFEA【剖析】依據(jù)前序遍歷序列和后序遍歷序列將該二叉樹結構出來。⑼在擁有n個結點的二叉鏈表中，共有〔〕個指針域，其中〔〕個指針域用于指向其左右孩子，剩下的〔〕個指針域那么是空的?！窘獯稹?n，n-1，n+1⑽在有n個葉子的哈夫曼樹中，葉子結點總數(shù)為〔〕，分支結點總數(shù)為〔〕。【解答】n，n-1【剖析】n-1個分支結點是經(jīng)過n-1次合并后獲取的。選擇題⑴假如結點A有3個兄弟，B是A的雙親，那么結點B的度是〔〕。A1B2C3D4【解答】D⑵設二叉樹有n個結點，那么其深度為〔〕。An-1BnC+1D不可以確立【解答】D【剖析】本題并無指明是完整二叉樹，那么其深度最多是n，最少是+1。⑶二叉樹的前序序列和后序序列正好相反，那么該二叉樹必定是〔〕的二叉樹。A空或只有一個結點B高度等于其結點數(shù)C任一結點無左孩子D任一結點無右孩子【解答】B【剖析】本題注意是序列正好相反，那么左斜樹和右斜樹均知足條件。⑷線索二叉樹中某結點R沒有左孩子的充要條件是〔〕。A=NULLB=0C=1D=NULL【解答】C【剖析】線索二叉樹中某結點能否有左孩子，不可以經(jīng)過左指針域能否為空來判斷，而要判斷左標記能否為1。⑸深度為k的完整二叉樹起碼有〔〕個結點，至多有〔〕個結點，擁有n個結點的完整二叉樹按層序從1開始編號，那么編號最小的葉子的序號是〔〕。A2k-2+1B2k-1C2k-1D2k–1-1E2k+1F2k+1-1G2k-1+1H2k【解答】B，C，A【剖析】深度為k的完整二叉樹最少結點數(shù)的狀況應是第k層上只有1個結點，最多的狀況是滿二叉樹，編號最小的葉子應當是在結點數(shù)最少的狀況下，葉子結點的編號。⑹一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，那么有〔〕成立。An=h+mBh+m=2nCm=h-1Dn=2m-1【解答】D【剖析】滿二叉樹中沒有度為1的結點，所以有m個葉子結點，那么度為2的結點個數(shù)為m-1。⑺任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序〔A必定不發(fā)生改變B必定發(fā)生改變C不可以確立D有時發(fā)生變化

〕?！窘獯稹?/p>

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【剖析】由叢林變換的二叉樹中，根結點即為第一棵樹的根結點，根結點的左子樹是由第一棵樹中除了根結點以外其余結點構成的，根結點的右子樹是由叢林中除第一棵樹外其余樹變換來的。⑽議論樹、叢林和二叉樹的關系，目的是為了〔〕。借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算將樹、叢林按二叉樹的儲存方式進行儲存并利用二叉樹的算法解決樹的相關問題將樹、叢林變換成二叉樹表達一種技巧，沒有什么實質(zhì)意義【解答】B判斷題⑴在線索二叉樹中，任一結點均有指向其前趨和后繼的線索。【解答】錯。某結點能否有前驅(qū)或后繼的線索，取決于該結點的標記域能否為1。⑵在二叉樹的前序遍歷序列中，隨意一個結點均處在其兒女的前面?！窘獯稹繉?。由前序遍歷的操作定義可知。⑶二叉樹是度為2的樹?！窘獯稹垮e。二叉樹和樹是兩種不同的樹結構，比如，左斜樹是一棵二叉樹，但它的度為1。⑷由樹變換成二叉樹，其根結點的右子樹老是空的?！窘獯稹繉?。因為根結點無兄弟結點。⑸用一維數(shù)組儲存二叉樹時，老是從前序遍歷儲存結點?！窘獯稹垮e。二叉樹的次序儲存結構是按層序儲存的，一般合適儲存完整二叉樹。4．明：任一二叉，其分枝數(shù)B＝2(n0-1)?！财渲?，n0端點數(shù)〕【解答】因在二叉中沒有度1的點，所以有：n=n0+n2B中分枝數(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，在中序遍序列中找a1的點，假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×n2+??+m×nm+1由上述兩式可得：n0=n2+2n3+??+(m-1)nm+17．二叉的中序和后序序列分CBEDAFIGH和CEDBIFHGA，結構二叉?！窘獯稹慷娴慕Y構程如5-12所示。8．定的一W＝〔5，2，9，11，8，3，7〕，結構相的哈夫曼，并算它的路徑度?！窘獯稹拷Y構的哈夫曼如5-13所示。的路徑度：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，該字符串的編碼長度起碼為98位。10．算法設計⑴設計算法求二叉樹的結點個數(shù)?！窘獯稹勘舅惴ú皇且蛴∶總€結點的值，而是求出結點的個數(shù)。所以可將遍歷算法中的“接見〞操作改為“計數(shù)操作〞，將結點的數(shù)目累加到一個全局變量中，每個結點累加一次即達成了卻點個數(shù)的求解。詳細算法以下：⑵設計算法按前序次序打印二叉樹中的葉子結點?！窘獯稹勘舅惴ǖ囊笈c前序遍歷算法既有同樣之處，又有不同之處。同樣之處是打印次序均為前序，不同之處是此處不是打印每個結點的值，而是打印出其中的葉子結點，即為有條件打印。為此，將前序遍歷算法中的接見操作改為條件打印即可。算法以下：⑶設計算法求二叉樹的深度?！窘獯稹慨敹鏄錇榭諘r，深度為0；假定二叉樹不為空，深度應是其左右子樹深度的最大值加子樹深度的求解又可經(jīng)過遞歸調(diào)用本算法來達成。詳細算法以下：

1，而其左右⑷編寫算法，要求輸出二叉樹后序遍歷序列的逆序?！窘獯稹恳氆@取后序的逆序，只需依據(jù)后序遍歷相反的次序即可，即先接見根結點，再遍歷根結點的右子樹，最后遍歷根結點的左子樹。注意和前序遍歷的差別，詳細算法以下：⑸以二叉鏈表為儲存結構，編寫算法求二叉樹中結點

x的雙親?！窘獯稹繉Χ骀湵磉M行遍歷，在遍歷的過程中查找結點

x并記錄其雙親。詳細算法以下：⑹以二叉鏈表為儲存結構，在二叉樹中刪除以值

x為根結點的子樹?！窘獯稹繉Χ骀湵磉M行遍歷，在遍歷的過程中查找結點

x并記錄其雙親，而后將結點

x的雙親結點中指向結點x的指針置空。詳細算法以下：⑺一棵擁有n個結點的二叉樹采納次序儲存結構，編寫算法對該二叉樹進行前序遍歷。【解答】依據(jù)題目要求，設置一個工作棧以達成對該樹的非遞歸算法，思路以下：①每接見一個結點，將此結點壓棧，查察此結點能否有左子樹，假定有，接見左子樹，重復履行該過程直到左子樹為空。②從棧彈出一個結點，假如此結點有右子樹，接見右子樹履行步驟①，否那么重復履行步驟②。詳細算法以下：⑻編寫算法互換二叉樹中所有結點的左右子樹?！窘獯稹繉Χ鏄溥M行后序遍歷，在遍歷過程中接見某結點時互換該結點的左右子樹。詳細算法以下：⑼以孩子兄弟表示法做儲存結構，求樹中結點

x的第

i個孩子?！窘獯稹肯仍阪湵碇羞M行遍歷，在遍歷過程中查找值等于找到值為x結點的第一個孩子，再沿右兄弟域rightsib

x的結點，而后由此結點的最左孩子域firstchild找到值為x結點的第i個孩子并返回指向這個孩子的指針。樹的孩子兄弟表示法中的結點結構定義以下：templatestructTNode{Tdata;TNode*firstchild,*rightsib;};詳細算法以下：學習自測及答案1．前序遍歷和中序遍歷結果同樣的二叉樹是〔〕。A根結點無左孩子的二叉樹B根結點無右孩子的二叉樹C所有結點只有左子樹的二叉樹D所有結點只有右子樹的二叉樹【解答】D1．前序遍歷和中序遍歷結果同樣的二叉樹是〔〕。A根結點無左孩子的二叉樹B根結點無右孩子的二叉樹C所有結點只有左子樹的二叉樹D所有結點只有右子樹的二叉樹【解答】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，那么其左分支下的后代的最大層次為〔〕。AhBh+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．試找出分別知足以下條件的所有二叉樹：⑴前序序列和中序序列同樣。⑵中序序列和后序序列同樣。⑶前序序列和后序序列同樣?！窘獯稹竣趴斩鏄?、只有一個根結點的二叉樹和右斜樹。⑵空二叉樹、只有一個根結點的二叉樹和左斜樹。⑶空二叉樹、只有一個根結點的二叉樹13．將下邊圖5-16所示的樹變換為二叉樹，圖5-17所示的二叉樹變換為樹或叢林?！窘獯稹繄D5-16所示樹變換的二叉樹如圖5-18所示，圖5-17所示二叉樹變換的叢林如圖5-19所示。14．以孩子兄弟表示法作為儲存結構，編寫算法求樹的深度?！窘獯稹坎杉{遞歸算法實現(xiàn)。假定樹為空樹，那么其深度為0，否那么其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。詳細算法以下：15．設計算法，判斷一棵二叉樹能否為完整二叉樹?！窘獯稹恳罁?jù)完整二叉樹的定義可知，對完整二叉樹依據(jù)從上到下、從左到右的次序〔即層序〕遍歷應當知足：⑴假定某結點沒有左孩子，那么其必定沒有右孩子；⑵假定某結點無右孩子，那么其所有后繼結點必定無孩子。假定有一結點不知足其中隨意一條，那么該二叉樹就必定不是完整二叉樹。所以可采納按層次遍歷二叉樹的方法挨次對每個結點進行判斷能否知足上述兩個條件。為此，需設兩個標記變量BJ和CM，其中BJ表示已掃描過的結點能否均有左右孩子，CM寄存局部判斷結果及最后的結果。詳細算法以下：第6章圖課后習題解說填空題⑴設無向圖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)。⑸一個有向圖的毗鄰矩陣表示，計算第j個極點的入度的方法是〔〕?！窘獯稹壳蟮趈列的所有元素之和⑹有向圖G用毗鄰矩陣A[n][n]儲存，其第i行的所有元素之和等于極點i的〔〕?！窘獯稹砍龆娶藞D的深度優(yōu)先遍歷近似于樹的〔〕遍歷，它所用到的數(shù)據(jù)結構是〔〕；圖的廣度優(yōu)先遍歷近似于樹的〔〕遍歷，它所用到的數(shù)據(jù)結構是〔〕?！窘獯稹壳靶?，棧，層序，隊列⑻對于含有n個極點e條邊的連通圖，利用Prim算法求最小生成樹的時間復雜度為〔〕，利用Kruskal算法求最小生成樹的時間復雜度為〔〕?！窘獯稹浚?n2)，Ｏ(elog2e)【剖析】Prim算法采納毗鄰矩陣做儲存結構，合適于求濃密圖的最小生成樹；Kruskal算法采納邊集數(shù)組做儲存結構，合適于求稀少圖的最小生成樹。⑼假如一個有向圖不存在〔〕，那么該圖的所有極點能夠擺列成一個拓撲序列?！窘獯稹炕芈发卧谝粋€有向圖中，假定存在弧、、，那么在其拓撲序列中，極點vi,vj,vk的相對次序為〔〕?！窘獯稹縱i,vj,vk【剖析】對由極點vi,vj,vk構成的圖進行拓撲排序。選擇題⑴在一個無向圖中，所有極點的度數(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)⑹設無向圖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。⑻最小生成樹指的是〔〕。由連通網(wǎng)所獲取的邊數(shù)最少的生成樹由連通網(wǎng)所獲取的極點數(shù)相對較少的生成樹連通網(wǎng)中所有生成樹中權值之和為最小的生成樹連通網(wǎng)的極小連通子圖⑼判斷一個有向圖能否存在回路除了能夠利用拓撲排序方法外，還能夠用〔〕。A求重點路徑的方法B求最短路徑的方法C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法【解答】D【剖析】當有向圖中無回路時，從某極點出發(fā)進行深度優(yōu)先遍歷時，出棧的次序〔退出DFSTraverse算法〕即為逆向的拓撲序列。⑽下邊對于工程方案的AOE網(wǎng)的表達中，不正確的選項是〔〕br/>A重點活動不如期達成就會影響整個工程的達成時間任何一個重點活動提早達成，那么整個工程將會提早達成所有的重點活動都提早達成，那么整個工程將會提早達成某些重點活動假定提早達成，那么整個工程將會提早完【解答】B【剖析】AOE網(wǎng)中的重點路徑可能不只一條，假如某一個重點活動提早達成，還不可以提早整個工程，而一定同時提升在幾條重點路徑上的重點活動。判斷題⑴一個有向圖的毗鄰表和逆毗鄰表中的結點個數(shù)必定相等?！窘獯稹繉ΑＥ彵砗湍媾彵淼牟顒e僅在于出邊和入邊，邊表中的結點個數(shù)都等于有向圖中邊的個數(shù)。⑵用毗鄰矩陣儲存圖，所占用的儲存空間大小只與圖中極點個數(shù)相關，而與圖的邊數(shù)沒關?！窘獯稹繉ΑＥ従仃嚨目臻g復雜度為Ｏ(n2)，與邊的個數(shù)沒關。⑶圖G的生成樹是該圖的一個極小連通子圖【解答】錯。一定包含所有極點。⑷無向圖的毗鄰矩陣必定是對稱的，有向圖的毗鄰矩陣必定是不對稱的【解答】錯。有向圖的毗鄰矩陣不必定對稱，比若有向完整圖的毗鄰矩陣就是對稱的。⑸對隨意一個圖，從某極點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷，可接見圖的所有極點?！窘獯稹垮e。只有連通圖從某極點出發(fā)進行一次遍歷，可接見圖的所有極點。⑹在一個有向圖的拓撲序列中，假定極點a在極點b從前，那么圖中必有一條弧?！窘獯稹垮e。只好說明從極點a到極點b有一條路徑。⑺假定一個有向圖的毗鄰矩陣中對角線以下元素均為零，那么該圖的拓撲序列必然存在?！窘獯稹繉?。拜見第11題的證明。⑻在AOE網(wǎng)中必定只有一條重點路徑br/>【解答】錯。AOE網(wǎng)中可能有不只一條重點路徑，他們的路徑長度同樣。4．n個極點的無向圖，采納毗鄰表儲存，回復以下問題br/>⑴圖中有多少條邊⑵隨意兩個極點i和j能否有邊相連⑶隨意一個極點的度是多少br/>【解答】⑴邊表中的結點個數(shù)之和除以2。⑵第i個表中能否含有點j。⑶點所的表中所含點個數(shù)。5．n個點的無向，采納接矩存，回復以下：⑴中有多少條⑵隨意兩個點i和j能否有相⑶隨意一個點的度是多少【解答】⑴接矩中非零元素個數(shù)的和除以2。⑵當接矩A中A[i][j]=1〔或A[j][i]=1〕，表示兩點之有相。⑶算接矩上點的行上非零元素的個數(shù)。6．明：生成中最路徑的起點和點的度均１?！窘獯稹坑梅捶?。v1,v2,?,vk是生成的一條最路徑，其中，v1起點，接點v，因為生成中無回路，所以，v在最路徑上，然以生成中最路徑的點的度1。

vk點。假定vk的度2，取vk的另一個v1,v2,?,vk的,v路徑最，與假矛盾。所同理可起點v1的度不可以大于1，只好1。7．一個通如6-6所示，出的接矩和接表存表示，假定從點v1出行遍，分出一個按深度先遍和廣度先遍的點序列?！窘獯稹拷泳乇硎疽韵拢荷疃葍?yōu)先遍歷序列為：

v1v2v3v5v4v6廣度優(yōu)先遍歷序列為：

v1v2v4v6v3v5毗鄰表表示以下：8．圖6-7所示是一個無向帶權圖，請分別按Prim算法和Kruskal算法求最小生成樹。【解答】按Prim算法求最小生成樹的過程以下：按Kruskal算法求最小生成樹的過程以下：9．對于圖6-8所示的帶權有向圖，求從源點v1到其余各極點的最短路徑?！窘獯稹繌脑袋cv1到其余各極點的最短路徑以下表所示。源點終點最短路徑最短路徑長度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v32510．如6-9所示的有向網(wǎng)，利用Dijkstra算法求從點v1到其余各點的最短路徑。【解答】從源點v1到其余各點的最短路徑以下表所示。源點點最短路徑最短路徑度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v44511．明：只需合適地擺列點的次序，就能使有向無的接矩中主角以下的元素所有0?！窘獯稹侩S意n個點的有向無都能夠獲取一個拓撲序列。拓撲序列v0v1v2?vn-1，我來明此的接矩A上三角矩。明采納反法。假此的接矩不是上三角矩，那么，存在下i和j〔i>j〕，使得A[i][j]不等于零，即中存在從vi到vj的一條有向。由拓撲序列的定可知，在隨意拓撲序列中，vi的地點必定在vj從前，而在上述拓撲序列v0v1v2?vn-1中，因為i>j，即vi的地點在vj以后，致矛盾。所以命正確。算法⑴算法，將一個無向的接矩接表?！窘獯稹肯仍O置一個空的毗鄰表，而后在毗鄰矩陣上查找值不為零的元素，找到后在毗鄰表的對應單鏈表中插入相應的邊表結點。毗鄰矩陣儲存結構定義以下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];6C在一個擁有n個極點的有向完整圖中包含有〔〕條邊：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】B6．n個極點的連通圖用毗鄰矩陣表示時，該矩陣起碼有〔〕個非零元素?！窘獯稹?(n-1)7．表示一個有100個極點，1000條邊的有向圖的毗鄰矩陣有〔〕個非零矩陣元素。【解答】10008．一個擁有n個極點k條邊的無向圖是一個叢林〔n>k〕，那么該叢林中必有〔〕棵樹。AkBnCn-kD1【解答】C9．用深度優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應的極點，那么輸出的極點序列是〔〕。A逆拓撲有序B拓撲有序C無序D深度優(yōu)先遍歷序列【解答】A重點路徑是AOE網(wǎng)中〔〕。A從源點到終點的最長路徑B從源點到終點的最長路徑C最長的回路D最短的回路【解答】A11.無向圖G的毗鄰表如圖6-10所示，分別寫出從極點1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應的生成樹。【解答】深度優(yōu)先遍歷序列為：1，2，3，4，5，6對應的生成樹為：廣度優(yōu)先遍歷序列為：1，2，4，3，5，6對應的生成樹為：12.已個AOV網(wǎng)如圖6-11所示，寫出所有拓撲序列。【解答】拓撲序列為：v0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。第7章查找技術課后習題解說填空題⑴次序查找技術合適于儲存結構為〔〕的線性表，而折半查找技術合用于儲存結構為〔〕的線性表，并且表中的元素一定是〔〕。【解答】次序儲存和鏈接儲存，次序儲存，按重點碼有序⑵設有一個已按各元素值排好序的線性表，長度為125，用折半查找與給定值相等的元素，假定查找成功，那么起碼需要比較〔〕次，至多需比較〔〕次。【解答】1，7【剖析】在折半查找判斷樹中，查找成功的狀況下，和根結點的比較次數(shù)最少，為1次，最多不超出判斷樹的深度。⑶對于數(shù)列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每個結點的查找概率相同，假定用次序儲存結構組織該數(shù)列，那么查找一個數(shù)的均勻比較次數(shù)為〔〕。假定按二叉排序樹組織該數(shù)列，那么查找一個數(shù)的均勻比較次數(shù)為〔〕?！窘獯稹?，59/15【剖析】依據(jù)數(shù)列將二叉排序樹畫出，將二叉排序樹中查找每個結點的比較次數(shù)之和除以數(shù)列中的元素個數(shù)，即為二叉排序樹的均勻查找長度。⑷長度為20