數據結構考試內部題庫含答案解析（全考點）1.已知帶權連通無向圖G=（V,E），其中V={O4U5比%"1%/1強233fff Jf匚一11f f ，嗎2M%皿"啊】方啊4心4,"6）6,（"5,"7）7,（"6,"7）3}（注：頂點偶對括號外的數ViV7據表示邊上的權值），從源點,到頂點’的最短路徑上經過的頂點序列是（）。。5。7A? 111B./I//J?/，/，力。2。5。4。6。7IJ?=? / / ，，I解析B:20?C:21?D:22解析畫出題目所表示的圖如下，可得到關鍵路徑的長度為21.圖中所示的兩條路徑都是關鍵路徑。答案：C10.下面關于求關鍵路徑的說法中，不正確的是（）。A:求關鍵路徑是以拓撲排序為基礎的.?B:一個事件的最早發生時間與以該事件為始的弧的活動的最早開始時間相同?C:一個事件的最遲發生時間是以該事件為尾的弧的活動的最遲開始時間與該活動的持續時間的差?D:關鍵活動一定位于關鍵路徑上解析一個事件的最遲發生時間等于Min｛以該事件為尾的弧的活動的最遲開始時間，最遲結束時間與該活動的持續時間的差｝。答案：C1、對下圖進行拓撲排序，可得不同拓撲序列的個數是（）。?A:4?B:3.?C:2?D:1解析可以得到3種不同的拓撲序列，即abced,abecd和aebcdo答案：B2、下列關于最小生成樹的敘述中，正確的是（）。I、最小生成樹的代價唯一口、所有權值最小的邊一定會出現在所有的最小生成樹中m、使用Prim算法從不同頂點開始得到的最小生成樹一定相同IV、使用Prim算法和Kruskal算法得到的最小生成樹總不相同.?A:僅工? ?B:僅口.?c：僅工、m?.D:僅口、IV解析最小生成樹的樹形可能不唯一（因為可能存在權值相同的邊），但代價一定是唯一的，工正確。若權值最小的邊有多條并且構成環狀，則總有權值最小的邊將不出現在某棵最小生成樹中，口錯誤。設N各結點構成環,N-1條邊權值相等,另一條邊權值較小，則從不同的頂點開始Prim算法會得到N-1種不同的最小生成樹，ID錯誤。當最小生成樹唯一時（各邊的權值不同），Prim算法和Kruskal算法得到的最小生成樹相同，IV錯誤。答案：A3、對下圖所示的有向帶權圖，若采用Dijkstra算法求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b目標頂點是b,第二條最短路徑的標頂點是c,后續得到的其余各最短路徑的目標頂點依次是（）OA:d,e,fB:e,d,fC:f,d,eD:f,e,d解析從a到各頂點的最短路徑的求解過程如下：□后續目標頂點依次為f,d,e。答案：C4、下列AOE網表示一項包含8個活動的工程，通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中,加快其進度就可以縮短工程工期的是（）。在這里插入圖片描述?A:c和e?B:d和c?C:f和d?D:f和h解析找出AOE網的全部關鍵路徑為bdcg、bdeh和bfho根據定義，只有關鍵路徑上的活動時間同時減少時，才能縮短工期。選項A、B和D并不包括在所有的關鍵路徑中，只有C包含，因此只有加快f和d的進度才能縮短工期。答案：C5、對下圖所示的有向圖進行拓撲排序，得到的拓撲序列可能是（）。A:3,124,5,6B:3,124,6,5C:3,1,425,6D:3,1,4,2,6,5解析按照拓撲排序的算法，每次都選擇入度為0的結點從圖中刪除，此圖中一開始只有結點3的入度為0;刪除結點3后，只有結點1的入度為0刪除結點1后，只有結點4的入度為0；刪除結點4后，結點2和結點6的入度都為0,此時選擇刪除不同的結點，會得出不同的拓撲序列，分別處理完畢后可知可能的拓撲序列為3,1,426,5和3,1,4,62,5,選Do答案：D6、若對n個頂點、e條弧的有向圖采用鄰接表存儲，則拓撲排序算法的時間復雜度是（）。A:0(n)B:O(n+e)n2c：0()D:O(ne)解析采用鄰接表作為AOV網的存儲結構進行拓撲排序，需要對n個頂點做進棧、出棧、輸出各一次，在處理e條邊時，需要檢測這n個頂點的邊鏈表的e個邊結點,共需要的時間代價為O(n+e)o若采用鄰接矩陣作為AOV網的存儲結構進行拓撲排序，在處理e條邊時需對每個頂點檢測相應矩陣中的某一行，尋找與它相關聯的邊，以便對這些邊的入度減1,需要的時n2間代價為0()o答案：B7、使用Dijkstra算法求下圖中從頂點1到其余各頂點的最短路徑，將當前找到的從頂點1到頂點2,3,4,5的最短路徑長度保存在數組dist中，求出第二條最短路徑后，dist中的內容更新為()。A:26,3,14,6B:25,3,14,6C:21,3,14,6D:15,3,14,6解析在執行Dijkstra算法時，首先初始化dist口，若頂點1到頂點i(i=2,3,4,5)有邊，就初始化為邊的權值：若無邊，就初始化為8；初始化頂點集S只含頂點1.Dijkstra算法每次選擇一個到頂點1距離最近的頂點j加入頂點集S,并判斷由頂點1繞行頂點j后到任一頂點k是否距離更短，若距離更短(即dist[j]+arcs[j][k]<dist[k]),則將dist[x]更新為dist[j]+arcs[j][k];重復該過程，直至所有頂點都加入頂點集So數組dist的變化過程如下圖所示,可知將第二個頂點5加入頂點集S后，數組dist更新為21,3,14,6,故選C。答案：C8、評價算法的標準包括如下幾方面:正確性健壯性、高效率及低存儲量。?A:可靠性?B:可行性?C:可讀性?D:可能性解析算法設計的要求：.?正確性.可讀性.?健壯性?效率與低存儲量答案：C9、一個有n個結點的圖，最少有一個連通分量。?A:0?B:1?C:n-1?D:n解析最少是1個，這種情況下，它本身就是一個連通圖；最多是n個，這種情況下，它由n個分散的點組成的一個圖。答案：B10.對｛05,46,13,55,94,17,42｝進行基數排序,一趟排序的結果是A:05,46,13,55,94,17,42B:05,13,17,42,46,55,94C:42,13,94,05,55,46,17D:05,13,46,55,17,42,94解析按照基數排序：.?(1)先按個位數數字，一次放入對應的桶，取出的結果為：42,13,94,05,55,46,17? ?(2)再按十位數字，依次放入對應的桶，取出的結果為：05,13,17,42,46,55,94但題目中問的是一趟排序后的結果，所以選Co答案：C題干內容所述的圖G如上圖所示。A,B,C,D對應的路徑長度分別為18,13,15,24O應用Dijkstra算法求出最短路徑為B所示路徑。答案：B2.下面的（）方法可以判斷出一個有向圖是否有環（2.下面的（）方法可以判斷出一個有向圖是否有環（路）。工、深度優先遍歷口、拓撲排序印、求最短路徑IV、求關鍵路徑 ?A:工、口、IV??B:I、皿、IV??c：］、口、m.?D:全部可以解析使用深度優先遍歷，若從有向圖上的某個頂點u出發，在DFS（u）結束之前出現一條從頂點v到u的邊，由于v在生成樹上是u的子孫，則圖中必定存在包含u和v的環，因此深度優先遍歷可以檢測一個有向圖是否有環。拓撲排序時，當某頂點不為任何邊的頭時才能加入序列，存在環時環中的頂點一直是某條邊的頭，不能加入拓撲序列。也就是說，還存在無法找到下一個可以加入拓撲序列的頂點，則說明此圖存在回路。求最短路徑是允許圖有環的。關鍵路徑能否判斷一個圖有環，則存在一些爭議。關鍵路徑本身雖然不允許有環，但求關鍵路徑的算法本身無法判斷是否有環，判斷是否有環是求關鍵路徑的第一步——拓撲排序。答案：A3、若一個有向圖的頂點不能排在一個拓撲序列中，則可判定該有向圖（）。A:是一個有根的有向圖B:是一個強連通圖C:含有多個入度為0的頂點D:含有頂點數目大于1的強連通分量解析若不存在拓撲排序，則表示圖中必定存在回路，該回路構成一個強連通分量（頂點數目大于1的強連通分量中必然存在回路）。答案：D4、以下關于拓撲排序的說法中，錯誤的是（）。I、若某有向圖存在環路，則該有向圖一定不存在拓撲排序口、在拓撲排序算法中為暫存入度為零的頂點，可以使用棧，也可以使用隊列印、若有向圖的拓撲有序序列唯一，則圖中每個頂點的入度和出度最多為1?a：ism?b：n、di?c：n.?d：in解析i中，對于一個存在環路的有向圖，使用拓撲排序算法運行后，肯定會出現有環的子圖，在此環中無法再找到入度為o的結點，拓撲排序也就進行不下去。口中，注意，若兩個結點之間不存在祖先或子孫關系，則它們在拓撲序列中的關系是任意的（即前后關系任意），因此使用棧和隊列都可以，因為進棧或隊列的都是入度為0的結點，此時入度為0的所有結點是沒有關系的。in中，若拓撲有序序列唯一，則很自然地讓人聯想到一個線性的有向圖（錯誤），下圖的拓撲序列也是唯一的，但度卻不滿足條件。答案：D5、若一個有向圖的頂點不能排成一個拓撲序列，則判定該有向圖（）。A:含有多個出度為0的頂點B:是個強連通圖C:含有多個入度為0的頂點D:含有頂點數大于1的強連通分量解析一個有向圖中的頂點不能排成一個拓撲序列，表明其中存在一個頂點數目大于1中存在一個頂點數目大于1路，該回路構成一個強連通分量，從而答案選Do答案：D6、下圖所示有向圖的所有拓撲序列共有（）個。?A:4?B:6?C:5?D:7解析本圖的拓撲排序序列有ABCFDEGzABCDFEG,ABCDEFGzABDCFEG和ABDCEFGO答案：C7、若一個人有向圖具有有序的拓撲排序序列，則它的鄰接矩陣必定為（）。A:對稱B:稀疏c:三角D:一般解析對有向圖中的頂點適當地編號，使其鄰接矩陣為三角矩陣且主對角元素全為零的充分必要條件是，該有向圖可以進行拓撲排序。若一個有向圖的鄰接矩陣為三角矩陣（對角線上元素為0）,則圖中必不存在環，因此其拓撲序列必然存在。答案：C8、下列關于圖的說法中，正確的是（）。工、有向圖中頂點V的度等于其鄰接矩陣中第V行中1的個數n、無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣川、在圖g的最小生成樹Gi中，某條邊的權值可能會超過未選邊最小生成樹Gi中，某條邊的權值可能會超過未選邊的權值IV、若有向無環圖的拓撲序列唯一，則可以唯一確定該圖a：I、it和inb：m和ivc：md：IV解析有向圖鄰接矩陣的第V行中1的個數是頂點V的出度，而有向圖中頂點的度為入度與出度之和，工錯。無向圖的鄰接矩陣一定是對稱矩陣，但當有向圖中任意兩個頂點之間有邊相連，且是兩條方向相反的有向邊（無向圖也可視為有兩條方向相反的有向邊的特殊有向圖）時，有向圖的鄰接矩陣也是一個對稱矩陣，口錯。最小生成樹中的n-1條邊并不能保證是圖中權值最小的n-1條邊，因為權值最小的n-1條邊并不一定能使圖連通。在下圖中，左圖的最小生成樹如右圖所示，權值為3的邊并不在其最小生成樹中。有向無環圖的拓撲序