數(shù)據(jù)結(jié)構(gòu)(C-版)王紅梅-版課后答案

第1章緒論課后習(xí)題講解1.填空6（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理?！窘獯稹繑?shù)據(jù)元素⑵（）是數(shù)據(jù)的最小單位，（）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項(xiàng)，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。（3）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（）、（）和（）?！窘獯稹考希€性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)⑷數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（）和（）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（）和（）,【解答】順序存儲(chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系⑸算法具有五個(gè)特性，分別是（）、（）、（）、（）、（）?！窘獯稹坑辛銈€(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性（6）算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語(yǔ)言?！窘獯稹孔匀徽Z(yǔ)言，程序設(shè)計(jì)語(yǔ)言，流程圖，偽代碼，偽代碼⑺在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（）的函數(shù)?！窘獯稹繂栴}規(guī)模（8）設(shè)待處理問題的規(guī)模為n,若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為（），若為n*log25n,則表示成數(shù)量級(jí)的形式為（）。【解答】0（1）,0（nlog2n）【分析】用大。記號(hào)表示算法的時(shí)間復(fù)雜度，需要將低次幕去掉，將最高次嘉的系數(shù)去掉。.選擇題⑴順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表不的。A線性結(jié)構(gòu)B非線性結(jié)構(gòu)C存儲(chǔ)位置D指針【解答】C,D【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲(chǔ)位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針表示。⑵假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)：子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。⑶算法指的是（）?A對(duì)特定問題求解步驟的一種描述，是指令的有限序列。B計(jì)算機(jī)程序C解決問題的計(jì)算方法D數(shù)據(jù)處理【解答】A【分析】計(jì)算機(jī)程序是對(duì)算法的具體實(shí)現(xiàn)；簡(jiǎn)單地說(shuō)，算法是解決問題的方法；數(shù)據(jù)處理是通過(guò)算法完成的。所以，只有A是算法的準(zhǔn)確定義。（4）下面（）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。⑸算法分析的目的是（）,算法分析的兩個(gè)主要方面是（）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易讀性和文檔性E空間性能和時(shí)間性能F正確性和簡(jiǎn)明性G可讀性和文檔性H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C,E.判斷題⑴算法的時(shí)間復(fù)雜度都要通過(guò)算法中的基本語(yǔ)句的執(zhí)行次數(shù)來(lái)確定?！窘獯稹垮e(cuò)。時(shí)間復(fù)雜度要通過(guò)算法中基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)確定。⑵每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。【解答】錯(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。⑶所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系?！窘獯稹垮e(cuò)。是數(shù)據(jù)之間的邏輯關(guān)系的整體。（4）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)?！窘獯稹繉?duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。⑸基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的。【解答】錯(cuò)?；静僮鞯膶?shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。.分析以下各程序段，并用大。記號(hào)表示其執(zhí)行時(shí)間。【解答】⑴基本語(yǔ)句是k=k+10*i,共執(zhí)行了n-2次,所以T(n)=O(n)。⑵基本語(yǔ)句是k=k+10*i,共執(zhí)行了n次，所以T(n)=O(n)。⑶分析條件語(yǔ)句，每循環(huán)一次，i+j整體加1,共循環(huán)n次，所以T(n)=O(n)。⑷設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1,最終T(n)=y,即：(T(n)+l)2〈n,所以T(n)=O(n1/2).⑸x++是基本語(yǔ)句，所以.設(shè)有數(shù)據(jù)結(jié)構(gòu)(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)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。.為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADTintegerData整數(shù)a：可以是正整數(shù)(1,2,3,-)、負(fù)整數(shù)(-1,-2,-3,…)和零OperationConstructor前置條件：整數(shù)a不存在輸入：一個(gè)整數(shù)b功能：構(gòu)造一個(gè)與輸入值相同的整數(shù)輸出：無(wú)后置條件：整數(shù)a具有輸入的值Set前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同輸出：無(wú)后置條件：整數(shù)a的值發(fā)生改變Add前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相加輸出：相加后的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Sub前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相減輸出：相減的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Multi前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相乘輸出：相乘的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Div前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相除輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Mod前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Equal前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：判斷整數(shù)a與輸入的整數(shù)b是否相等輸出：若相等返回1,否則返回0后置條件：整數(shù)a的值不發(fā)生改變endADT.求多項(xiàng)式A(x)的算法可根據(jù)下列兩個(gè)公式之一來(lái)設(shè)計(jì)：⑴A(x)=anxn+anTxnT+…+alx+aO⑵A(x)=(…(anx+anT)x+…+al)x)+aO根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運(yùn)算。.算法設(shè)計(jì)(要求：算法用偽代碼和C++描述，并分析最壞情況下的時(shí)間復(fù)雜度)⑴對(duì)一個(gè)整型數(shù)組A[n]設(shè)計(jì)一個(gè)排序算法?！窘獯稹肯旅媸呛?jiǎn)單選擇排序算法的偽代碼描述。下面是簡(jiǎn)單選擇排序算法的C++描述。分析算法，有兩層嵌套的for循環(huán)，所以，。⑵找出整型數(shù)組A[n]中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描述如下：算法的C++描述如下:分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=O(n)。學(xué)習(xí)自測(cè)及答案.順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是(),鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是()?！窘獯稹坑迷卦诖鎯?chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。.算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為().【解答】健壯性.常見的算法時(shí)間復(fù)雜度用大0記號(hào)表示為：常數(shù)階()、對(duì)■數(shù)階()、線性階()、平方階()和指數(shù)階()?！窘獯稹?(1),0(log2n),0(n),0(n2),0(2n).將下列函數(shù)按它們?cè)趎時(shí)的無(wú)窮大階數(shù)，從小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,log2n,nl/2+log2n,(3/2)n,n!,n2+log2n【解答】log2n,nl/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!.試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別?！窘獯稹繑?shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對(duì)數(shù)據(jù)類型的一種抽象。.對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試分別畫出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。⑴A=(D, R), 其中 D={al,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={ }(4)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)屬于集合，其邏輯結(jié)構(gòu)圖如圖「4(a)所示；(2)屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(b)所示；(3)屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖14(c)所示；(4)屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(d)所示。7.求下列算法的時(shí)間復(fù)雜度。count=0;x=l;while(x{x*=2;count++;}returncount;【解答】0(log2n)第2章線性表課后習(xí)題講解1.填空⑴在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（）和（）有關(guān)?！窘獯稹勘黹L(zhǎng)的一半，表長(zhǎng)，該元素在表中的位置⑵順序表中第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的存儲(chǔ)地址是（）o【解答】108【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址+（5-1）X2=108⑶設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（）?！窘獯稹縫->next=（p->next）->next（4）單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）o【解答】為了運(yùn)算方便（分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。⑸非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）.【解答】p->next=head【分析】如圖2-8所示。（6）在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（）；刪除開始結(jié)點(diǎn)的操作序列為（）.【解答】s->next=rear->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;deleteq;【分析】操作示意圖如圖2-9所示：⑺一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（【解答】0（1）,0（n）【分析】在P所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為0（1）;而在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為0（n）o（8）可由一個(gè)尾指針唯一確定的鏈表有（）、（）、（）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表.選擇題⑴線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。A隨機(jī)存取B順序存取C索引存取D散列存取【解答】A,B【分析】參見2.2.1。⑵線性表采用鏈接存儲(chǔ)時(shí)，其地址（）?A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。⑶單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）oA不再需要頭指針了B從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；C已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開?！窘獯稹緽（4）鏈表不具有的特點(diǎn)是（）.A可隨機(jī)訪問任一元素B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長(zhǎng)度成正比【解答】A⑸若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前趨也不方便，雙鏈表雖然能快速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。（6）若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。A單鏈表B帶頭指針的單循環(huán)鏈表C雙鏈表D帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是0(1),所以，答案是D。⑺若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn),則采用()存儲(chǔ)方法最節(jié)省運(yùn)算時(shí)間。A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。(8)在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是()。A0(1)B0(n)C0(n2)D0(nlog2n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。0)對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是().A0(1)B0(n)C0(n2)D0(nlog2n)【解答】C【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需0(n)。00)使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以()oA提高查找速度B更方便數(shù)據(jù)的插入和刪除C節(jié)約存儲(chǔ)空間D很快回收存儲(chǔ)空間【解答】B【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對(duì)稱性，所以，其插入和刪除操作更加方便。(11)在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和P之間插入s所指結(jié)點(diǎn)，則執(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之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。（12）在循環(huán)雙鏈表的P所指結(jié)點(diǎn)后插入S所指結(jié)點(diǎn)的操作是（）。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【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。.判斷題⑴線性表的邏輯順序和存儲(chǔ)順序總是一致的?！窘獯稹垮e(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。⑵線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)?！窘獯稹垮e(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。（3）設(shè)p,q是指針，若p=q,則*p=*q?！窘獯稹垮e(cuò)。P=q只能表示P和q指向同一起始地址，而所指類型則不一定相同。（4）線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼?！窘獯稹垮e(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼。⑸在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。.請(qǐng)說(shuō)明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。⑴若線性表的總長(zhǎng)度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。⑵如果n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。⑶描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點(diǎn)：①無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；②可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。順序表的缺點(diǎn)：①插入和刪除操作需移動(dòng)大量元素；②表的容量難以確定；③造成存儲(chǔ)空間的“碎片”。單鏈表的優(yōu)點(diǎn)：①不必事先知道線性表的長(zhǎng)度；②插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)：①指針的結(jié)構(gòu)性開銷；②存取表中任意元素不方便，只能進(jìn)行順序存取。⑴應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。⑵應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生變化。⑶應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)?個(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。.算法設(shè)計(jì)⑴設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為。(n)的算法，實(shí)現(xiàn)將數(shù)組A［n］中所有元素循環(huán)右移k個(gè)位置?！窘獯稹克惴ㄋ枷胝?qǐng)參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為0(k),第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n-k),第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為0(n),所以，總的時(shí)間復(fù)雜度為0(n)。⑵已知數(shù)組A［n］中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù),右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為0(n)o【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j,初始時(shí)i=0,j=n-l,若A［i］為偶數(shù)并且A［j］為奇數(shù)，則將A［i］與A［與交換。具體算法如下:分析算法，兩層循環(huán)將數(shù)組掃描?遍，所以，時(shí)間復(fù)雜度為0(n)。⑶試編寫在無(wú)頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?.2.3。(4)試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷?，即是將對(duì)稱元素交換，設(shè)順序表的長(zhǎng)度為length,則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。具體算法如下：?jiǎn)捂湵淼哪嬷谜?qǐng)參見2.2.4算法2-4和算法2-6?⑸假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)?！窘獯稹坷脝窝h(huán)鏈表的特點(diǎn)，通過(guò)指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p,然后將結(jié)點(diǎn)r刪除，如圖2T1所示，具體算法如下:(6)已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B,D,A中分別存放字母、數(shù)字和其他字符。具體算法如下：⑺設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼結(jié)點(diǎn)。具體算法如F：（8）判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱?！窘獯稹吭O(shè)工作指針P和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)P和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針P后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點(diǎn)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)），或結(jié)點(diǎn)q成為結(jié)點(diǎn)P的前驅(qū)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)）。如圖2T2所示。學(xué)習(xí)自測(cè)及答案.已知一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144,則第一個(gè)元素的地址是()。A108B180C176D112【解答】D.在長(zhǎng)度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：()oA0(0)B0(1)C0(n)D0(n2)【解答】C.在一個(gè)長(zhǎng)度為n的順序表的第i(IWiWn+l)個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)()個(gè)元素，刪除第i(IWiWn)個(gè)元素時(shí)，需向前移動(dòng)()個(gè)元素?！窘獯稹縩-i+1,n-i.在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由()指示?！窘獯稹科淝摆吔Y(jié)點(diǎn)的指針域.當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是()?【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰.在雙鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)?！窘獯稹壳膀?qū)，后繼.設(shè)A是一個(gè)線性表（al,a2,…，an）,采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（IWiWn）的概率為，則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？【解答】.線性表存放在整型數(shù)組A[arrsize]的前elenum個(gè)單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度?！窘獯稹勘绢}是在一個(gè)遞增有序表中插入元素x,基本思路是從有序表的尾部開始依次取元素與x比較，若大于x,此元素后移一位，再取它前面一個(gè)元素重復(fù)上述步驟；否則，找到插入位置，將x插入。具體算法如下：.已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間?！窘獯稹恳?yàn)槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個(gè)大于mink的結(jié)點(diǎn)和第一個(gè)小于maxk的結(jié)點(diǎn)，再將二者間的所有結(jié)點(diǎn)刪除。.設(shè)單循環(huán)鏈表L1,對(duì)其遍歷的結(jié)果是：xl,x2,x3,…，xn-1,xn.請(qǐng)將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表L1和L2,使得L1中含有原L1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：xl,x3,…；L2中含有原L1表中序號(hào)為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：…，x4,x2o【解答】算法如下：第3章特殊線性表——棧、隊(duì)列和串課后習(xí)題講解1.填空⑴設(shè)有一個(gè)空棧，棧頂指針為1000H,現(xiàn)有輸入序列為1、2、3、4、5,經(jīng)過(guò)push,push,pop,push,pop,push,push后，輸出序列是（）,棧頂指針為（）.【解答】23,1003H⑵棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（）；其判定?？盏臈l件分別是（），判定棧滿的條件分別是（）o【解答】順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top=-l和top=NULL,橫頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無(wú)可用空間⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。（4）表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）?！窘獯稹縜bc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來(lái)，再將算符插在它的兩個(gè)操作數(shù)的后面。⑸棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（）,隊(duì)列的操作特性是（）,棧和隊(duì)列的主要區(qū)別在于（）o【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同（6）循環(huán)隊(duì)列的引入是為了克服（）o【解答】假溢出⑺數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）?【解答】（rear-front+n）%n【分析】也可以是（rear-front）%n,但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。（8）用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n,若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（）和（）?！窘獯稹?（1）,0（n）【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是在終端結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開始杳找終端結(jié)點(diǎn)的地址。0）串是一種特殊的線性表，其特殊性體現(xiàn)在（）o【解答】數(shù)據(jù)元素的類型是一個(gè)字符00）兩個(gè)串相等的充分必要條件是（）0【解答】長(zhǎng)度相同且對(duì)應(yīng)位置的字符相等【分析】例如"abc"#"abc:"abc"W"bca"。2.選擇題⑴若一個(gè)棧的輸入序列是1,2,3,…，n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是（）.A不確定Bn-iCn-i-1Dn-i+1【解答】D【分析】此時(shí)，輸出序列一定是輸入序列的逆序。⑵設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5、e6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、el,則棧S的容量至少應(yīng)該是（）.A6B4C3D2【解答】C【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、el?⑶一個(gè)棧的入棧序列是1,2,3,4,5,則棧的不可能的輸出序列是（）.A54321B45321C43512D12345【解答】C【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(hào)）的兩個(gè)元素。（4）設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳A順序表B棧C隊(duì)列D鏈表【解答】B【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。⑸在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A棧B隊(duì)列C數(shù)組D線性表【解答】B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。（6）一個(gè)隊(duì)列的入隊(duì)順序是1,2,3,4,則隊(duì)列的輸出順序是（）.A4321B1234C1432D3241【解答】B［分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。⑺棧和隊(duì)列的主要區(qū)別在于（）。A它們的邏輯結(jié)構(gòu)不一樣B它們的存儲(chǔ)結(jié)構(gòu)不一樣C所包含的運(yùn)算不一樣D插入、刪除運(yùn)算的限定不一樣【解答】D【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。（8）設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（）。AS1的棧底位置為0,S2的棧底位置為n-1BS1的棧底位置為0,S2的棧底位置為n/2CS1的棧底位置為0,S2的棧底位置為nDS1的棧底位置為0,S2的棧底位置為1【解答】A【分析】?jī)蓷９蚕砜臻g首先兩個(gè)棧是相向增長(zhǎng)的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。⑼設(shè)有兩個(gè)串P和q，求q在P中首次出現(xiàn)的位置的運(yùn)算稱作（）.A連接B模式匹配C求子串D求串長(zhǎng)【解答】B.判斷題⑴有n個(gè)元素依次進(jìn)棧，則出棧序列有（n-1）/2種?！窘獯稹垮e(cuò)。應(yīng)該有種。⑵?？梢宰鳛閷?shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹繉?duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。⑶在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉?duì)。（4）在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear?！窘獯稹垮e(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。⑸空串與空格串是相同的?！窘獯稹垮e(cuò)?？沾拈L(zhǎng)度為零，而空格串的長(zhǎng)度不為0,其長(zhǎng)度是串中空格的個(gè)數(shù)。.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳,B,C,D,E,能否得到如下出棧序列，若能，請(qǐng)寫出操作序列，若不能，請(qǐng)說(shuō)明原因。⑴C,E,A,B,D⑵C,B,A,D,E【解答】⑴不能，因?yàn)樵贑、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧。(2)可以，設(shè)I為進(jìn)棧操作，0為入棧操作，則其操作序列為1110001010。.舉例說(shuō)明順序隊(duì)列的“假溢出”現(xiàn)象?！窘獯稹考僭O(shè)有一個(gè)順序隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4,隊(duì)頭指針front=L如果再有元素入隊(duì)，就會(huì)產(chǎn)生“上溢”，此時(shí)的“上溢”又稱為“假溢出”，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)存儲(chǔ)單元空閑，其下標(biāo)分別為0和1。.在操作序列push(l)、push(2),pop,push(5),push(7),pop,push(6)之后，棧頂元素和棧底元素分別是什么？(push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。)【解答】棧頂元素為6,棧底元素為1。其執(zhí)行過(guò)程如圖3-7所示。.在操作序列EnQueue(l)、EnQueue(3)>DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？(EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)頭元素出隊(duì))?！窘獯稹筷?duì)頭元素為5,隊(duì)尾元素為9。其執(zhí)行過(guò)程如圖3-8所示。.空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長(zhǎng)度為零。僅含空格的串稱為空格串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。串中的空格符可用來(lái)分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。.算法設(shè)計(jì)⑴假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)的算法。【解答】出隊(duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。入隊(duì)算法如下：出隊(duì)算法如卜.:⑵設(shè)順序棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n,a2nT,…，al,要求通過(guò)一個(gè)循環(huán)隊(duì)列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n,a2n-2,…，a2,a2n-l,a2n-3,…,al,請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為0(n)?！窘獯稹坎僮鞑襟E為：①將所有元素出棧并入隊(duì)；②依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧；③將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)；④將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧：⑤將所有元素出棧并入隊(duì)；⑥將所有元素出隊(duì)并入棧即為所求。⑶用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S,編寫算法刪除S中第i個(gè)字符開始的連續(xù)j個(gè)字符?！窘獯稹肯扰袛啻畇中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如下：（4）對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串S,編寫一個(gè)函數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動(dòng)的元素中沒有值為ch的元素，能減少移動(dòng)元素的次數(shù)，提高算法的效率。算法如下：⑸對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)?！窘獯稹繀⒁?.2.5學(xué)習(xí)自測(cè)及答案.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為（）?A不變Btop=0;Ctop=top-l;Dtop=top+l;【解答】C.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的出棧序列是（）oAedcbaBcdebaCdebcaDabcde【解答】c.從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（）oAx=top;top=top->next;Bx=top->data;Ctop=top->next;x=top->data;Dx=top->data;top=top->next;【解答】D.設(shè)元素1,2,3,P,A依次經(jīng)過(guò)一個(gè)棧，進(jìn)棧次序?yàn)?23PA,在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計(jì)語(yǔ)言的變量名?！窘獯稹縋A321,P3A21,P32A1,P321A,AP321.設(shè)S="I_am_a_teacther”,其長(zhǎng)度為（）?！窘獯稹?5.對(duì)于棧和隊(duì)列，無(wú)論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是（【解答】0（1）.如果進(jìn)棧序列為A、B、C、D,則可能的出棧序列是什么？答：共14種，分別是：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA.簡(jiǎn)述隊(duì)列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)?！窘獯稹肯嗤c(diǎn)：它們都是插入和刪除操作的位置受限制的線性表。不同點(diǎn)：棧是限定僅在表尾進(jìn)行插入和刪除的線性表，是后進(jìn)先出的線性表，而隊(duì)列是限定在表的一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表，是先進(jìn)先出的線性表。.利用兩個(gè)棧S1和S2模擬一個(gè)隊(duì)列，如何利用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入和刪除操作，請(qǐng)簡(jiǎn)述算法思想?！窘獯稹坷脙蓚€(gè)棧S1和S2模擬一個(gè)隊(duì)列，當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí)，用S1來(lái)存放已輸入的元素，即通過(guò)向棧S1執(zhí)行入棧操作來(lái)實(shí)現(xiàn)；當(dāng)需要從隊(duì)列中刪除元素時(shí)，則將S1中元素全部送入到S2中，再?gòu)腟2中刪除棧頂元素，最后再將S2中元素全部送入到S1中；判斷隊(duì)空的條件是：棧S1和S2同時(shí)為空。.設(shè)計(jì)算法把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)輸出?！窘獯稹克惴ɑ谠恚篘=(Ndivd)xd+Nmodd(div為整除運(yùn)算，mod為求余運(yùn)算)。.假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)：圓括號(hào)“（”和“）"，方括號(hào)和以及花括號(hào)“{"和且這三種括號(hào)可按任意的次序嵌套使用。編寫算法判斷給定表達(dá)式中所含括號(hào)是否配時(shí)出現(xiàn)?！窘獯稹考僭O(shè)表達(dá)式已存入字符數(shù)組A[n]中，具體算法如下：第4章廣義線性表——多維數(shù)組和廣義表課后習(xí)題講解.填空⑴數(shù)組通常只有兩種運(yùn)算：()和()，這決定了數(shù)組通常采用()結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)?！窘獯稹看嫒?，修改，順序存儲(chǔ)【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。⑵二維數(shù)組A中行下標(biāo)從10到20,列下標(biāo)從5到10,按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元,A[10][5]的存儲(chǔ)地址是1000，則元素A[15][10]的存儲(chǔ)地址是()o【解答】1140【分析】數(shù)組A中每行共有6個(gè)元素，元素A[15][10]的前面共存儲(chǔ)了(15T0)X6+5個(gè)元素,每個(gè)元素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。⑶設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第一個(gè)元素，其存儲(chǔ)地址為d,每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為()?【解答】d+41【分析】元素A[8][5]的前面共存儲(chǔ)了(1+2+…+8)+5=41個(gè)元素。(4)稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是()和()。【解答】三元組順序表，十字鏈表⑸廣義表((a),(((b),c)),(d))的長(zhǎng)度是(),深度是(),表頭是(),表尾是()?！窘獯稹?,4,(a),((((b),c)),(d))(6)已知廣義表LS=(a,(b,c,d),e),用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是()。[解答]Head(Head(Tai1(LS))).選擇題⑴二維數(shù)組A的每個(gè)元素是山6個(gè)字符組成的串，行下標(biāo)的范圍從0~8,列下標(biāo)的范圍是從0?9,則存放A至少需要()個(gè)字節(jié)，A的第8列和第5行共占()個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ),元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的()元素的起始地址一致。A90B180C240D540E108F114G54HA[8][5]IA[3][10]JA[5][8]KA[4][9]【解答】D,E,K【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90X6=540個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注意行列有一個(gè)交叉元素），所以，共占108個(gè)字節(jié)，元素A[8][5]按行優(yōu)先存儲(chǔ)的起始地址為d+8X10+5=d+85,設(shè)元素A[i][j]按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+jX9+i=d+85,解此方程，得i=4,j=9。⑵將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)?)A數(shù)組元素是隨機(jī)的B對(duì)數(shù)組任一元素的存取時(shí)間是相等的C隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問D數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定【解答】B⑶下面的說(shuō)法中，不正確的是()A數(shù)組是一種線性結(jié)構(gòu)B數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu)C除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。(4)對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了()A表達(dá)變得簡(jiǎn)單B對(duì)矩陣元素的存取變得簡(jiǎn)單C去掉矩陣中的多余元素D減少不必要的存儲(chǔ)空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重:復(fù)存儲(chǔ)。⑸下面()不屬于特殊矩陣。A時(shí)角矩陣B三角矩陣C稀疏矩陣D對(duì)稱矩陣【解答】C(6)若廣義表A滿足Head(A)=Tail(A),則人為()A()B(())C((),())D((),(),())【解答】B⑺下面的說(shuō)法中，不正確的是()A廣義表是一種多層次的結(jié)構(gòu)B廣義表是一種非線性結(jié)構(gòu)C廣義表是一種共享結(jié)構(gòu)D廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。(8)下面的說(shuō)法中，不正確的是()A對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下(或上)三角的元素即可。B對(duì)角矩陣只須存放非零元素即可。C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。D稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分布有規(guī)律，就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。.判斷題⑴數(shù)組是?種夏雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的?！窘獯稹垮e(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。⑵使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間?！窘獯稹繉?duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。⑶稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能?！窘獯稹繉?duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。(4)線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表?！窘獯稹繉?duì)。⑸若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e(cuò)。如廣義表L=((),(a,b))的表頭為空表，但L不是空表。.一個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示?！窘獯稹繉?duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。.已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求運(yùn)算的優(yōu)缺點(diǎn)?！窘獯稹吭O(shè)稀疏矩陣為m行n歹IJ,如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為O(mXn)；因?yàn)橐獙⑺械木仃囋乩奂悠饋?lái)，所以，需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為O(mXn)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為O(t),將所有的矩陣元素累加起來(lái)只需將三元組順序表掃描?遍，其時(shí)間復(fù)雜度亦為O(t)。當(dāng)t〈〈mXn時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。.設(shè)某單位職工工資表ST由“工資”、“扣除”和“實(shí)發(fā)金額”三項(xiàng)組成，其中工資項(xiàng)包括“基本工資”、“津貼”和“獎(jiǎng)金”，扣除項(xiàng)包括“水”、“電”和“煤氣”O(jiān)⑴請(qǐng)用廣義表形式表示所描述的工資表ST,并用表頭和表尾求表中的“獎(jiǎng)金”項(xiàng)；⑵畫出該工資表ST的存儲(chǔ)結(jié)構(gòu)?！窘獯稹?1)ST=((基本工資，津貼，獎(jiǎng)金)，(水，電，煤氣)，實(shí)發(fā)金額)Head(Tail(Tail(Head(ST))))=獎(jiǎng)金⑵工資表ST的頭尾表示法如圖4-7所示。.若在矩陣A中存在一個(gè)元素ai,j(OWiWn-l,OMjWmT),該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣A,試設(shè)計(jì)一個(gè)求該矩陣所有馬鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度?！窘獯稹吭诰仃囍兄鹦袑ふ以撔兄械淖钚≈?，然后對(duì)其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說(shuō)明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。具體算法如下:分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第■個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時(shí)間復(fù)雜度為0(mn+n2)。.已知兩個(gè)nXn的對(duì)稱矩陣按壓縮存儲(chǔ)方法存儲(chǔ)在已維數(shù)組A和B中，編寫算法計(jì)算對(duì)稱矩陣的乘枳?！窘獯稹繉?duì)稱矩陣采用壓縮存儲(chǔ)，乘積矩陣也采用壓縮存儲(chǔ)。注意矩陣元素的表示方法。第5章樹和二叉樹課后習(xí)題講解.填空題⑴樹是n（n20）結(jié)點(diǎn)的有限集合，在一棵非空樹中，有（）個(gè)根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分成m（m>0）個(gè)（）的集合，每個(gè)集合都是根結(jié)點(diǎn)的子樹?！窘獯稹坑星覂H有一個(gè)，互不相交⑵樹中某結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的（），子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的（）,該結(jié)點(diǎn)稱為其子樹根結(jié)點(diǎn)的（）.【解答】度，孩子，雙親⑶一棵二叉樹的第i（i》D層最多有（）個(gè)結(jié)點(diǎn)：一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（）個(gè)葉子結(jié)點(diǎn)和（）個(gè)非終端結(jié)點(diǎn)。【解答】2i-l,（n+l）/2,（n-l）/2【分析】設(shè)滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,由于滿二叉樹中不存在度為1的結(jié)點(diǎn),所以n=n0+n2；由二叉樹的性質(zhì)nO=n2+L得nO=（n+l）/2,n2=（n-l）/2.（4）設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（），最小值是（）。【解答】2h-1,2h-l【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。⑸深度為k的二叉樹中，所含葉子的個(gè)數(shù)最多為（）?【解答】2k-1【分析】在滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最多。（6）具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為（）。【解答】50【分析】100個(gè)結(jié)點(diǎn)的完全二叉樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100,其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為50,也就是說(shuō)，從編號(hào)51開始均為葉子。⑺已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹中有（）個(gè)葉子結(jié)點(diǎn)?！窘獯稹?2【分析】根據(jù)二叉樹性質(zhì)3的證明過(guò)程，有n0=n2+2n3+l（nO、n2、n3分別為葉子結(jié)點(diǎn)、度為2的結(jié)點(diǎn)和度為3的結(jié)點(diǎn)的個(gè)數(shù)）。（8）某二叉樹的前序遍歷序列是ABCDEFG,中序遍歷序列是CBDAFGE,則其后序遍歷序列是（）?！窘獯稹緾DBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來(lái)。⑼在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（）個(gè)指針域，其中（）個(gè)指針域用于指向其左右孩子，剩下的（）個(gè)指針域則是空的。【解答】2n,n-1,n+1（10）在有n個(gè)葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為（）,分支結(jié)點(diǎn)總數(shù)為（）?【解答】n,n-1【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過(guò)n-1次合并后得到的。.選擇題⑴如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（）。A1B2C3D4【解答】D⑵設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為（）。An-1BnC+1D不能確定【解答】D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n,最少是+1.⑶二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A空或只有一個(gè)結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無(wú)左孩子D任一結(jié)點(diǎn)無(wú)右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。（4）線索二叉樹中某結(jié)點(diǎn)R沒有左孩子的充要條件是（）oAR.lchild=NULLBR.ltag=0CR.ltag=lDR.rchild=NULL【解答】C【分析】線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過(guò)左指針域是否為空來(lái)判斷，而要判斷左標(biāo)志是否為lo⑸深度為k的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)，至多有（）個(gè)結(jié)點(diǎn)，具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層序從1開始編號(hào)，則編號(hào)最小的葉子的序號(hào)是（）。A2k-2+lB2k-1C2k-1D2k-1-1E2k+lF2k+l-1G2k-1+1H2k【解答】B,C,A【分析】深度為k的完全二叉樹最少結(jié)點(diǎn)數(shù)的情況應(yīng)是第k層上只有1個(gè)結(jié)點(diǎn)，最多的情況是滿二叉樹，編號(hào)最小的葉子應(yīng)該是在結(jié)點(diǎn)數(shù)最少的情況下，葉子結(jié)點(diǎn)的編號(hào)。（6）一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（）成立。An=h+mBh+m=2nCm=hTDn=2m-l【解答】D【分析】滿二叉樹中沒有度為1的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為m-1。⑺任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（）oA肯定不發(fā)生改變B肯定發(fā)生改變C不能確定D有時(shí)發(fā)生變化【解答】A【分析】三種遍歷次序均是先左子樹后右子樹。⑻如果T'是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹，那么T中結(jié)點(diǎn)的前序序列就是T'中結(jié)點(diǎn)的（）序列，T中結(jié)點(diǎn)的后序序列就是T'中結(jié)點(diǎn)的（）序列。A前序B中序C后序D層序【解答】A,B0）設(shè)森林中有4棵樹，樹中結(jié)點(diǎn)的個(gè)數(shù)依次為nl、n2、n3、n4,則把森林轉(zhuǎn)換成二叉樹后,其根結(jié)點(diǎn)的右子樹上有（）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹上有（）個(gè)結(jié)點(diǎn)。Anl-1BnlCnl+n2+n3Dn2+n3+n4【解答】D,A【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點(diǎn)即為第一棵樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹是由第一棵樹中除了根結(jié)點(diǎn)以外其余結(jié)點(diǎn)組成的，根結(jié)點(diǎn)的右子樹是由森林中除第?棵樹外其他樹轉(zhuǎn)換來(lái)的。（10）討論樹、森林和二叉樹的關(guān)系，目的是為了（）oA借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算B將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題C將樹、森林轉(zhuǎn)換成二叉樹D體現(xiàn)一種技巧，沒有什么實(shí)際意義【解答】B3.判斷題⑴在線索二叉樹中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索?！窘獯稹垮e(cuò)。某結(jié)點(diǎn)是否有前驅(qū)或后繼的線索，取決于該結(jié)點(diǎn)的標(biāo)志域是否為1。⑵在二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女的前面?！窘獯稹繉?duì)。由前序遍歷的操作定義可知。⑶二叉樹是度為2的樹。【解答】錯(cuò)。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。（4）山樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的?！窘獯稹繉?duì)。因?yàn)楦Y(jié)點(diǎn)無(wú)兄弟結(jié)點(diǎn)。⑸用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)?！窘獯稹垮e(cuò)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的，一般適合存儲(chǔ)完全二叉樹。.證明：對(duì)任一滿二叉樹，其分枝數(shù)B=2(nOT)。(其中，nO為終端結(jié)點(diǎn)數(shù))【解答】因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，所以有：n=nO+n2設(shè)B為樹中分枝數(shù)，則n-B+1所以B=nO+n2-l再由二叉樹性質(zhì)：n0=n2+l代入上式有：B=nO+nOTT=2(nO-1).證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。【解答】證明采用歸納法。設(shè)二叉樹的前序遍歷序列為ala2a3…an,中序遍歷序列為bib2b3…bn。當(dāng)n=l時(shí)，前序遍歷序列為al,中序遍歷序列為bl,二叉樹只有一個(gè)根結(jié)點(diǎn)，所以，al=bl,可以唯一確定該二叉樹；假設(shè)當(dāng)n〈=k時(shí),前序遍歷序列ala2a3…ak和中序遍歷序列bib2b3…bk可唯一確定該二叉樹，下面證明當(dāng)n=k+l時(shí)，前序遍歷序列ala2a3…akak+1和中序遍歷序列bib2b3…bkbk+1可唯確定一棵二叉樹。在前序遍歷序列中第一個(gè)訪問的一定是根結(jié)點(diǎn)，即二叉樹的根結(jié)點(diǎn)是al,在中序遍歷序列中查找值為al的結(jié)點(diǎn)，假設(shè)為bi,則al=bi且blb2…bi-1是對(duì)根結(jié)點(diǎn)al的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列a2a3…ai是對(duì)根結(jié)點(diǎn)al的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3…ai和中序遍歷序列blb2…biT唯一確定了根結(jié)點(diǎn)的左子樹，同樣可證前序遍歷序列ai+lai+2…ak+1和中序遍歷序列bi+lbi+2…bk+1唯一確定了根結(jié)點(diǎn)的右子樹。.已知一棵度為m的樹中有：nl個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？【解答】設(shè)該樹的總結(jié)點(diǎn)數(shù)為n,則n=nO+nl+n2+ +nm又：n=分枝數(shù)+1=0XnO+1Xnl+2Xn2+ +mXnm+l由上述兩式可得：n0=n2+2n3+ +(m-l)nm+l.已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA,試構(gòu)造該二叉樹。【解答】二叉樹的構(gòu)造過(guò)程如圖5-12所示。.對(duì)給定的一組權(quán)值W=(5,2,9,11,8,3,7),試構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算它的帶權(quán)路徑長(zhǎng)度?！窘獯稹繕?gòu)造的哈夫曼樹如圖5T3所示。ZZZZ樹的帶權(quán)路徑長(zhǎng)度為：WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2=120.已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對(duì)該字符串用［0,1］進(jìn)行前綴編碼，問該字符串的編碼至少有多少位?！窘獯稹恳愿髯址霈F(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長(zhǎng)度=2X5+1X5+3X4+5X3+9X2+4X3+4X3+7X2=98,所以，該字符z.算法設(shè)計(jì)⑴設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)?！窘獯稹勘舅惴ú皇且蛴∶總€(gè)結(jié)點(diǎn)的值，而是求出結(jié)點(diǎn)的個(gè)數(shù)。所以可將遍歷算法中的“訪問”操作改為“計(jì)數(shù)操作”,將結(jié)點(diǎn)的數(shù)目累加到一個(gè)全局變量中，每個(gè)結(jié)點(diǎn)累加一次即完成了結(jié)點(diǎn)個(gè)數(shù)的求解。具體算法如下：⑵設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)?！窘獯稹勘舅惴ǖ囊笈c前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個(gè)結(jié)點(diǎn)的值，而是打印出其中的葉子結(jié)點(diǎn)，即為有條件打印。為此,將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：⑶設(shè)計(jì)算法求二叉樹的深度?！窘獯稹慨?dāng)二叉樹為空時(shí)，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1,而其左右子樹深度的求解又可通過(guò)遞歸調(diào)用本算法來(lái)完成。具體算法如下：(4)編寫算法，要求輸出二叉樹后序遍歷序列的逆序?！窘獯稹恳氲玫胶笮虻哪嫘?，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點(diǎn)，再遍歷根結(jié)點(diǎn)的右子樹，最后遍歷根結(jié)點(diǎn)的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：⑸以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點(diǎn)x的雙親?！窘獯稹繉?duì)二叉鏈表進(jìn)行遍歷，在遍歷的過(guò)程中查找結(jié)點(diǎn)x并記載其雙親。具體算法如F：(6)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點(diǎn)的子樹?！窘獯稹繉?duì)二叉鏈表進(jìn)行遍歷，在遍歷的過(guò)程中查找結(jié)點(diǎn)x并記載其雙親，然后將結(jié)點(diǎn)x的雙親結(jié)點(diǎn)中指向結(jié)點(diǎn)X的指針置空。具體算法如下：⑺一棵具有n個(gè)結(jié)點(diǎn)的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，編寫算法對(duì)該二叉樹進(jìn)行前序遍歷?！窘獯稹堪凑疹}目要求，設(shè)置一個(gè)工作棧以完成對(duì)該樹的非遞歸算法，思路如下：①每訪問一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓棧，查看此結(jié)點(diǎn)是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過(guò)程直到左子樹為空。②從棧彈出一個(gè)結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。具體算法如下：(8)編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹?！窘獯稹繉?duì)二叉樹進(jìn)行后序遍歷，在遍歷過(guò)程中訪問某結(jié)點(diǎn)時(shí)交換該結(jié)點(diǎn)的左右子樹。具體算法如下：（9）以孩子兄弟表示法做存儲(chǔ)結(jié)構(gòu)，求樹中結(jié)點(diǎn)x的第i個(gè)孩子?！窘獯稹肯仍阪湵碇羞M(jìn)行遍歷，在遍歷過(guò)程中查找值等于x的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域firstchild找到值為x結(jié)點(diǎn)的第一個(gè)孩子,再沿右兄弟域rightsib找到值為x結(jié)點(diǎn)的第i個(gè)孩子并返回指向這個(gè)孩子的指針。樹的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如F：templatestructTNodeTdata;TNode*firstchild,*rightsib;};具體算法如下：學(xué)習(xí)自測(cè)及答案.前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。A根結(jié)點(diǎn)無(wú)左孩子的二叉樹B根結(jié)點(diǎn)無(wú)右孩子的二叉樹C所有結(jié)點(diǎn)只有左子樹的二叉樹D所有結(jié)點(diǎn)只有右子樹的二叉樹【解答】D.由權(quán)值為｛3,8,6,2,5｝的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，其帶權(quán)路徑長(zhǎng)度為（）。A24B48C53D72【解答】C.用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組A[l]?A[n]中，結(jié)點(diǎn)A[i]若有左子樹，則左子樹的根結(jié)點(diǎn)是（）□AA[2i-1]BA[2i+1]CA[i/2]DA[2i]【解答】D.對(duì)任何一棵二叉樹T,如果其終端結(jié)點(diǎn)的個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則（）。An0=n2-lBn0=n2Cn0=n2+lD沒有規(guī)律【解答】C.一棵滿二叉樹中共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，深度為h,則（）,An=h+mBh+m=2nCm=h-lDn=2h-l【解答】D.對(duì)于完全二叉樹中的任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為h,則其左分支下的子孫的最大層次為（）?AhBh+1Ch或h+1D任意【解答】C.假定一棵度為3的樹中結(jié)點(diǎn)數(shù)為50,則其最小高度應(yīng)為。A3B4C5D6【解答】C.在線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)的充要條件為（）?A左線索標(biāo)志為0,右線索標(biāo)志為1B左線索標(biāo)志為1,右線索標(biāo)志為0C左、右線索標(biāo)志均為0D左、右線索標(biāo)志均為1【解答】C.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，其所有結(jié)點(diǎn)的度之和為（）?！窘獯稹縩-1.在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是（）0【解答】.現(xiàn)有按前序遍歷二叉樹的結(jié)果ABC,問有哪幾種不同的二叉樹可以得到這一結(jié)果？【解答】共有5種二叉樹可以得到這一結(jié)果，如圖5T5所示。.試找出分別滿足下列條件的所有二叉樹：⑴前序序列和中序序列相同。⑵中序序列和后序序列相同。⑶前序序列和后序序列相同?！窘獯稹竣趴斩鏄?、只有一個(gè)根結(jié)點(diǎn)的二叉樹和右斜樹。⑵空二叉樹、只有一個(gè)根結(jié)點(diǎn)的二叉樹和左斜樹。⑶空二叉樹、只有一個(gè)根結(jié)點(diǎn)的二叉樹.將下面圖5-16所示的樹轉(zhuǎn)換為二叉樹，圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林?！窘獯稹繄D5-16所示樹轉(zhuǎn)換的二叉樹如圖5-18所示，圖5-17所示二叉樹轉(zhuǎn)換的森林如圖5-19所示。.以孩子兄弟表示法作為存儲(chǔ)結(jié)構(gòu)，編寫算法求樹的深度?！窘獯稹坎捎眠f歸算法實(shí)現(xiàn)。若樹為空樹，則其深度為0,否則其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。具體算法如下：.設(shè)計(jì)算法，判斷一棵二叉樹是否為完全二叉樹?！窘獯稹扛鶕?jù)完全二叉樹的定義可知，對(duì)完全二叉樹按照從上到下、從左到右的次序（即層序）遍歷應(yīng)該滿足：⑴若某結(jié)點(diǎn)沒有左孩子，則其一定沒有右孩子；⑵若某結(jié)點(diǎn)無(wú)右孩子，則其所有后繼結(jié)點(diǎn)一定無(wú)孩子。若有一結(jié)點(diǎn)不滿足其中任意一條，則該二叉樹就一定不是完全二叉樹。因此可采用按層次遍歷二叉樹的方法依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行判斷是否滿足上述兩個(gè)條件。為此，需設(shè)兩個(gè)標(biāo)志變量BJ和CM,其中BJ表示已掃描過(guò)的結(jié)點(diǎn)是否均有左右孩子，CM存放局部判斷結(jié)果及最后的結(jié)果。具體算法如下：第6章圖課后習(xí)題講解1.填空題⑴設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n,則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?,n（n-l）/2,0,n（n-l）【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集：邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。⑵任何連通圖的連通分量只有一個(gè)，即是（）.【解答】其自身⑶圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（）和（）?【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重:表、邊集數(shù)組等。（4）已知無(wú)向圖G的頂點(diǎn)數(shù)為n,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為（）?【解答】0（n+e）【分析】在無(wú)向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有n+2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為0（n+2e）=O（n+e）。⑸已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是（）.【解答】求第j列的所有元素之和（6）有向圖G用鄰接矩陣A[n][n]存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的（）.【解答】出度⑺圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）;圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）?【解答】前序，棧，層序，隊(duì)列（8）對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時(shí)間復(fù)雜度為（）,利用Kruskal算法求最小生成樹的時(shí)間復(fù)雜度為（）o【解答】o（n2）,O（elog2e）【分析】Prim算法采用鄰接矩陣做存儲(chǔ)結(jié)構(gòu)，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲(chǔ)結(jié)構(gòu)，適合于求稀疏圖的最小生成樹。⑼如果一個(gè)有向圖不存在（）,則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄??！窘獯稹炕芈罚?0）在一個(gè)有向圖中，若存在弧、、，則在其拓?fù)湫蛄兄?，頂點(diǎn)vi,vj,vk的相對(duì)次序?yàn)椋ǎ??！窘獯稹縱i,vj,vk【分析】對(duì)由頂點(diǎn)vi,vj,vk組成的圖進(jìn)行拓?fù)渑判颉?選擇題⑴在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A1/2B1C2D4【解答】C【分析】設(shè)無(wú)向圖中含有n個(gè)頂點(diǎn)e條邊，則。⑵n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）條邊，其形狀是（）。AnBn+1Cn-1DnX（n-1）E無(wú)回路F有回路G環(huán)狀H樹狀【解答】A,G⑶含n個(gè)頂點(diǎn)的連通圖中的任意?條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（）.A1Bn/2Cn-1Dn【解答】C【分析】若超過(guò)n-L則路徑中必存在重復(fù)的頂點(diǎn)。（4）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）.AnB（n-1）2Cn-1Dn2【解答】D⑸圖的生成樹（），n個(gè)頂點(diǎn)的生成樹有（）條邊。A唯一B不唯一C唯一性不能確定DnEn+1Fn-1【解答】C,F（6）設(shè)無(wú)向圖G=（V,E）和G'=（V',E'）,如果G'是G的生成樹，則下面的說(shuō)法中錯(cuò)誤的是（）oAG'為G的子圖BG'為G的連通分量CG'為G的極小連通子圖且V=V'DG'是G的一個(gè)無(wú)環(huán)子圖【解答】B【分析】連通分量是無(wú)向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊都加上，所以，連通分量中可能存在回路。⑺G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有()個(gè)頂點(diǎn)。A6B7C8D9【解答】D【分析】n個(gè)頂點(diǎn)的無(wú)向圖中，邊數(shù)eWn(nT)/2,將e=28代入，有n28,現(xiàn)已知無(wú)向圖非連通，則n=9。(8)最小生成樹指的是()。A由連通網(wǎng)所得到的邊數(shù)最少的生成樹B由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹C連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹D連通網(wǎng)的極小連通子圖【解答】C⑼判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用()。A求關(guān)鍵路徑的方法B求最短路徑的方法C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法【解答】D【分析】當(dāng)有向圖中無(wú)回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序(退出DFSTraverse算法)即為逆向的拓?fù)湫蛄小?10)下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是()A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成D某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完【解答】B【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個(gè)關(guān)鍵活動(dòng)提前完成，還不能提前整個(gè)工程，而必須同時(shí)提高在幾條關(guān)鍵路徑上的關(guān)鍵活動(dòng)。.判斷題⑴一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等?！窘獯稹繉?duì)。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。⑵用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)?！窘獯稹繉?duì)。鄰接矩陣的空間復(fù)雜度為O(n2),與邊的個(gè)數(shù)無(wú)關(guān)。⑶圖G的生成樹是該圖的一個(gè)極小連通子圖【解答】錯(cuò)。必須包含全部頂點(diǎn)。(4)無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的【解答】錯(cuò)。有向圖的鄰接矩陣不一定對(duì)稱，例如有向完全圖的鄰接矩陣就是對(duì)稱的。⑸對(duì)任意?個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點(diǎn)?！窘獯稹垮e(cuò)。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。(6)在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧?！窘獯稹垮e(cuò)。只能說(shuō)明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。⑺若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖??！窘獯稹繉?duì)。參見第11題的證明。(8)在AOE網(wǎng)中一定只有一條關(guān)犍路徑？【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長(zhǎng)度相同。.n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接表存儲(chǔ)，回答下列問題?⑴圖中有多少條邊？⑵任意兩個(gè)頂點(diǎn)i和j是否有邊相連？⑶任意一個(gè)頂點(diǎn)的度是多少？【解答】⑴邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。⑵第i個(gè)邊表中是否含有結(jié)點(diǎn)j?⑶該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。.n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣存儲(chǔ)，回答下列問題：⑴圖中有多少條邊？⑵任意兩個(gè)頂點(diǎn)i和j是否有邊相連？⑶任意一個(gè)頂點(diǎn)的度是多少？【解答】⑴鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。(2)當(dāng)鄰接矩陣A中(或A[j][i]=l)時(shí)，表示兩頂點(diǎn)之間有邊相連。⑶計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。.證明：生成樹中最長(zhǎng)路徑的起點(diǎn)和終點(diǎn)的度均為1?！窘獯稹坑梅醋C法證明。設(shè)vl,v2,…，vk是生成樹的一條最長(zhǎng)路徑，其中，vl為起點(diǎn)，vk為終點(diǎn)。若vk的度為2,取vk的另一個(gè)鄰接點(diǎn)v,由于生成樹中無(wú)回路，所以，v在最長(zhǎng)路徑上，顯然vl,v2,…，vk,v的路徑最長(zhǎng)，與假設(shè)矛盾。所以生成樹中最長(zhǎng)路徑的終點(diǎn)的度為1.同理可證起點(diǎn)vl的度不能大于1,只能為lo.已知一個(gè)連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)vl出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列?！窘獯稹苦徑泳仃嚤硎救缦拢荷疃葍?yōu)先遍歷序列為：vlv2v3v5v4v6廣度優(yōu)先遍歷序列為：vlv2v4v6v3v5鄰接表表示如下：.圖6-7所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別按Prim算法和Kruskal算法求最小生成樹?！窘獯稹堪碢rim算法求最小生成樹的過(guò)程如卜.:按Kruskal算法求最小生成樹的過(guò)程如下:.對(duì)于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)vl到其他各頂點(diǎn)的最短路徑?！窘獯稹繌脑袋c(diǎn)vl到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度TOC\o"1-5"\h\zvl v7 vl v7 7vl v5 vl v5 11vl v4 vl v7 v4 13vl v6 vl v7 v4 v6 16vl v2 vl v7 v2 22vl v3 vl v7 v4 v6 v325.如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)vl到其他各頂點(diǎn)的最短路徑?！窘獯稹繌脑袋c(diǎn)vl到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度TOC\o"1-5"\h\zvl v3 vl v3 15vl v5 vl v5 15vl v2 vl v