【正文】 ?br /【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長度相同。4．n個(gè)頂點(diǎn)的無向圖，采用鄰接表存儲(chǔ)，回答下列問題?br /⑴ 圖中有多少條邊？⑵ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？⑶ 任意一個(gè)頂點(diǎn)的度是多少?br /【解答】⑴ 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。⑵ 第i個(gè)邊表中是否含有結(jié)點(diǎn)j。⑶ 該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。5．n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣存儲(chǔ)，回答下列問題：⑴ 圖中有多少條邊？⑵ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？⑶ 任意一個(gè)頂點(diǎn)的度是多少？【解答】⑴ 鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。⑵ 當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時(shí)，表示兩頂點(diǎn)之間有邊相連。⑶ 計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。6．證明：生成樹中最長路徑的起點(diǎn)和終點(diǎn)的度均為１?！窘獯稹坑梅醋C法證明。設(shè)v1, v2, …, vk是生成樹的一條最長路徑，其中，v1為起點(diǎn)，vk為終點(diǎn)。若vk的度為2，取vk的另一個(gè)鄰接點(diǎn)v，由于生成樹中無回路，所以，v在最長路徑上，顯然v1, v2, …, vk , v的路徑最長，與假設(shè)矛盾。所以生成樹中最長路徑的終點(diǎn)的度為1。同理可證起點(diǎn)v1的度不能大于1，只能為1。7．已知一個(gè)連通圖如圖66所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)v1出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列?！窘獯稹苦徑泳仃嚤硎救缦拢荷疃葍?yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5鄰接表表示如下：8．圖67所示是一個(gè)無向帶權(quán)圖，請分別按Prim算法和Kruskal算法求最小生成樹。【解答】按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：9．對(duì)于圖68所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑?！窘獯稹繌脑袋c(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長度v1 v7 v1 v7 7v1 v5 v1 v5 11v1 v4 v1 v7 v4 13v1 v6 v1 v7 v4 v6 16v1 v2 v1 v7 v2 22v1 v3 v1 v7 v4 v6 v3 2510．如圖69所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑。【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長度v1 v3 v1 v3 15v1 v5 v1 v5 15v1 v2 v1 v3 v2 25v1 v6 v1 v3 v2 v6 40v1 v4 v1 v3 v2 v4 4511．證明：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無環(huán)圖的鄰接矩陣中主對(duì)角線以下的元素全部為0。【解答】任意n個(gè)結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個(gè)拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2…vn1，我們來證明此時(shí)的鄰接矩陣A為上三角矩陣。證明采用反證法。假設(shè)此時(shí)的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（ij），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄?，vi的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn1中，由于ij，即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。12. 算法設(shè)計(jì)⑴ 設(shè)計(jì)算法，將一個(gè)無向圖的鄰接矩陣轉(zhuǎn)換為鄰接表?！窘獯稹肯仍O(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10。template struct AdjMatrix{ T vertex[MaxSize]。 //存放圖中頂點(diǎn)的數(shù)組int arc[MaxSize][MaxSize]。 //存放圖中邊的數(shù)組int vertexNum, arcNum。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。鄰接表存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10。struct ArcNode //定義邊表結(jié)點(diǎn){int adjvex。 //鄰接點(diǎn)域ArcNode *next。}。template struct VertexNode //定義頂點(diǎn)表結(jié)點(diǎn){T vertex。ArcNode *firstedge。}。struct AdjList{VertexNode adjlist[MaxSize]。int vertexNum, arcNum。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。具體算法如下：⑵ 設(shè)計(jì)算法，將一個(gè)無向圖的鄰接表轉(zhuǎn)換成鄰接矩陣?！窘獯稹吭卩徑颖砩享樞虻厝∶總€(gè)邊表中的結(jié)點(diǎn)，將鄰接矩陣中對(duì)應(yīng)單元的值置為1。鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)定義與上題相同。具體算法如下：⑶ 設(shè)計(jì)算法，計(jì)算圖中出度為零的頂點(diǎn)個(gè)數(shù)。【解答】在有向圖的鄰接矩陣中，一行對(duì)應(yīng)一個(gè)頂點(diǎn)，每行的非零元素的個(gè)數(shù)等于對(duì)應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，則對(duì)應(yīng)頂點(diǎn)的出度為零。據(jù)此，從第一行開始，查找每行的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下：⑷ 以鄰接表作存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)按深度優(yōu)先遍歷圖的非遞歸算法?！窘獯稹?。⑸ 已知一個(gè)有向圖的鄰接表，編寫算法建立其逆鄰接表?！窘獯稹吭谟邢驁D中，若鄰接表中頂點(diǎn)vi有鄰接點(diǎn)vj，在逆鄰接表中vj一定有鄰接點(diǎn)vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點(diǎn)firstedge域置空，然后逐行將表頭結(jié)點(diǎn)的鄰接點(diǎn)進(jìn)行轉(zhuǎn)化。⑹ 分別基于深度優(yōu)先搜索和廣度優(yōu)先搜索編寫算法，判斷以鄰接表存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（i≠j）。【解答】⑴ 基于深度優(yōu)先遍歷：⑵ 基于廣度優(yōu)先遍歷：學(xué)習(xí)自測及答案 1．某無向圖的鄰接矩陣A=，可以看出，該圖共有（ ）個(gè)頂點(diǎn)。A 3 B 6 C 9 D 以上答案均不正確【解答】A2．無向圖的鄰接矩陣是一個(gè)（ ），有向圖的鄰接矩陣是一個(gè)（ ）A 上三角矩陣 B 下三角矩陣 C 對(duì)稱矩陣 D 無規(guī)律【解答】C，D3．下列命題正確的是（ ）。A 一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B 一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C 一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D 一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一【解答】B4．十字鏈表適合存儲(chǔ)（ ），鄰接多重表適合存儲(chǔ)（ ）?！窘獯稹坑邢驁D，無向圖5. 在一個(gè)具有n 個(gè)頂點(diǎn)的有向完全圖中包含有（ ）條邊：A n(n1)/2 B n(n1) C n(n+1)/2 D n2【解答】B6．n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有（ ）個(gè)非零元素?！窘獯稹?(n1)7．表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有（ ）個(gè)非零矩陣元素?！窘獯稹?0008．一個(gè)具有n個(gè)頂點(diǎn)k條邊的無向圖是一個(gè)森林（nk），則該森林中必有（ ）棵樹。　A k 　 B n 　 C n k 　 D 1【解答】C9．用深度優(yōu)先遍歷方法遍歷一個(gè)有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（ ）?！ 逆拓?fù)溆行?B 拓?fù)溆行?C 無序 　 D 深度優(yōu)先遍歷序列【解答】A10. 關(guān)鍵路徑是AOE網(wǎng)中（ ）。A 從源點(diǎn)到終點(diǎn)的最長路徑 B從源點(diǎn)到終點(diǎn)的最長路徑C 最長的回路 　 D 最短的回路【解答】A11. 已知無向圖G的鄰接表如圖610所示，分別寫出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應(yīng)的生成樹。【解答】深度優(yōu)先遍歷序列為：1，2，3，4，5，6對(duì)應(yīng)的生成樹為：廣度優(yōu)先遍歷序列為：1，2，4，3，5，6對(duì)應(yīng)的生成樹為：12. 已知已個(gè)AOV網(wǎng)如圖611所示，寫出所有拓?fù)湫蛄?。【解答】拓?fù)湫蛄袨椋簐0 v1 v5 v2 v3 v6 v v0 v1 v5 v2 v6 v3 v v0 v1 v5 v6 v2 v3 v4。第 7 章 查找技術(shù)課后習(xí)題講解1. 填空題⑴ 順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表，而折半查找技術(shù)適用于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表，并且表中的元素必須是（ ）?！窘獯稹宽樞虼鎯?chǔ)和鏈接存儲(chǔ)，順序存儲(chǔ)，按關(guān)鍵碼有序⑵ 設(shè)有一個(gè)已按各元素值排好序的線性表，長度為125，用折半查找與給定值相等的元素，若查找成功，則至少需要比較（ ）次，至多需比較（ ）次?！窘獯稹?，7【分析】在折半查找判定樹中，查找成功的情況下，和根結(jié)點(diǎn)的比較次數(shù)最少，為1次，最多不超過判定樹的深度。⑶ 對(duì)于數(shù)列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每個(gè)結(jié)點(diǎn)的查找概率相同，若用順序存儲(chǔ)結(jié)構(gòu)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（ ）。若按二叉排序樹組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（ ）。【解答】8，59/15【分析】根據(jù)數(shù)列將二叉排序樹畫出，將二叉排序樹中查找每個(gè)結(jié)點(diǎn)的比較次數(shù)之和除以數(shù)列中的元素個(gè)數(shù)，即為二叉排序樹的平均查找長度。⑷ 長度為20的有序表采用折半查找，共有（ ）個(gè)元素的查找長度為3?！窘獯稹?【分析】在折半查找判定樹中，第3層共有4個(gè)結(jié)點(diǎn)。⑸ 假定一個(gè)數(shù)列{25，43，62，31，48，56}，采用的散列函數(shù)為H(k)=k mod 7，則元素48的同義詞是（ ）?！窘獯稹?2【分析】H(48)= H(62)=6⑹ 在散列技術(shù)中，處理沖突的兩種主要方法是（　 　）和（　　 ）?！窘獯稹块_放定址法，拉鏈法⑺ 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的查找方法是（ ）?！窘獯稹可⒘胁檎摇痉治觥可⒘斜淼钠骄檎议L度是裝填因子的函數(shù)，而不是記錄個(gè)數(shù)n的函數(shù)。⑻ 與其他方法相比，散列查找法的特點(diǎn)是（ ）。【解答】通過關(guān)鍵碼計(jì)算記錄的存儲(chǔ)地址，并進(jìn)行一定的比較2. 選擇題⑴ 靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 　　　　 　 B 施加在其上的操作不同C 所包含的數(shù)據(jù)元素的類型不一樣 　 D 存儲(chǔ)實(shí)現(xiàn)不一樣【解答】B【分析】靜態(tài)查找不涉及插入和刪除操作，而動(dòng)態(tài)查找涉及插入和刪除操作。⑵ 有一個(gè)按元素值排好序的順序表（長度大于2），分別用順序查找和折半查找與給定值相等的元素，比較次數(shù)分別是s和b，在查找成功的情況下，s和b的關(guān)系是（ ）；在查找不成功的情況下，s和b的關(guān)系是（ ）。A s=b B sb C s 【解答】D，D【分析】此題沒有指明是平均性能。例如，在有序表中查找最大元素，則順序查找比折半查找快，而平均性能折半查找要優(yōu)于順序查找，查找不成功的情況也類似。⑶ 長度為 12的有序表采用順序存儲(chǔ)結(jié)構(gòu)，采用折半查找技術(shù)，在等概率情況下，查找成功時(shí)的平均查找長度是（ ），查找失敗時(shí)的平均查找長度是（ ）。A 37/12 B 62/13 C 3 9/12 D 49/13【解答】A，B【分析】畫出長度為12的折半查找判定樹，判定樹中有12個(gè)內(nèi)結(jié)點(diǎn)和13個(gè)外結(jié)點(diǎn)。⑷ 用n個(gè)鍵值構(gòu)造一棵二叉排序樹，其最低高度為（ ）。A n/2 B n C log2n D log2n+1【解答】D【分析】二叉排序樹的最低高度與完全二叉樹的高度相同。⑸ 二叉排序樹中，最小值結(jié)點(diǎn)的（ ）。A 左指針一定為空 B 右指針一定為空C 左、右指針均為空 D 左、右指針均不為空【解答】A【分析】在二叉排序樹中，值最小的結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問的結(jié)點(diǎn)，即二叉樹的最左下結(jié)點(diǎn)。⑹ 散列技術(shù)中的沖突指的是（ ）。A 兩個(gè)元素具有相同的序號(hào) B 兩個(gè)元素的鍵值不同，而其他屬性相同C 數(shù)據(jù)元素過多 D 不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址【解答】D⑺ 設(shè)散列表表長m=14，散列函數(shù)H(k)=k mod 11。表中已有13684四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素49的存儲(chǔ)地址是（ ）。A 8 B 3 C 5 D 9 【解答】A【分析】元素13684分別存儲(chǔ)在7單元，而元素49的散列地址為5，發(fā)生沖突，向后探測3個(gè)單元，其存儲(chǔ)地址為8。⑻ 在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測多個(gè)位置，在查找成功的情況下，所探測的這些位置的鍵值（ ）。A 一定都是同義詞 B 一定都不是同義詞 C不一定都是同義詞 D 都相同【解答】C【分析】采用線性探測法處理沖突會(huì)產(chǎn)生堆積，即非同義詞爭奪同一個(gè)后繼地址。3. 判斷題⑴ 二叉排序樹的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值?！窘獯稹垮e(cuò)。分析二叉排序樹的定義，是左子樹上的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，右子樹上的所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。例如圖77所示二叉樹滿足任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序樹。⑵ 二叉排序樹的查找和折半查找的時(shí)間性能相同。【解答】錯(cuò)。二叉排序樹的查找性能在最好情況和折半查找相同。⑶ 若二叉排序樹中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)。【解答】錯(cuò)。在二叉排序樹中，最小元素所在結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問的結(jié)點(diǎn)，即是二叉樹的最左下結(jié)點(diǎn)，但可能有右子樹。最大元素所在結(jié)點(diǎn)一定是中序遍歷序列中最后一個(gè)被訪問的結(jié)點(diǎn)，即是二叉樹的最右下結(jié)點(diǎn)，但可能有左子樹。如圖78所示，5是最小元素，25是最大元素，但5和25都不是葉子結(jié)點(diǎn)。⑷ 散列技術(shù)的查找效率主要取決于散列函數(shù)和處理沖突的方法?！窘獯稹垮e(cuò)。更重要的取決于