(全)數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023版

數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析（全考點(diǎn)）1.已知帶權(quán)連通無(wú)向圖G=（V,E），其中V={O4U5比%"1%/1強(qiáng)233fff Jf匚一11f f ，嗎2M%皿"啊】方啊4心4,"6）6,（"5,"7）7,（"6,"7）3}（注：頂點(diǎn)偶對(duì)括號(hào)外的數(shù)ViV7據(jù)表示邊上的權(quán)值），從源點(diǎn),到頂點(diǎn)’的最短路徑上經(jīng)過(guò)的頂點(diǎn)序列是（）。。5。7A? 111B./I//J?/，/，力。2。5。4。6。7IJ?=? / / ，，I解析B:20?C:21?D:22解析畫(huà)出題目所表示的圖如下，可得到關(guān)鍵路徑的長(zhǎng)度為21.圖中所示的兩條路徑都是關(guān)鍵路徑。答案：C10.下面關(guān)于求關(guān)鍵路徑的說(shuō)法中，不正確的是（）。A:求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的.?B:一個(gè)事件的最早發(fā)生時(shí)間與以該事件為始的弧的活動(dòng)的最早開(kāi)始時(shí)間相同?C:一個(gè)事件的最遲發(fā)生時(shí)間是以該事件為尾的弧的活動(dòng)的最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差?D:關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上解析一個(gè)事件的最遲發(fā)生時(shí)間等于Min｛以該事件為尾的弧的活動(dòng)的最遲開(kāi)始時(shí)間，最遲結(jié)束時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差｝。答案：C1、對(duì)下圖進(jìn)行拓?fù)渑判?，可得不同拓?fù)湫蛄械膫€(gè)數(shù)是（）。?A:4?B:3.?C:2?D:1解析可以得到3種不同的拓?fù)湫蛄?，即abced,abecd和aebcdo答案：B2、下列關(guān)于最小生成樹(shù)的敘述中，正確的是（）。I、最小生成樹(shù)的代價(jià)唯一口、所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中m、使用Prim算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同IV、使用Prim算法和Kruskal算法得到的最小生成樹(shù)總不相同.?A:僅工? ?B:僅口.?c：僅工、m?.D:僅口、IV解析最小生成樹(shù)的樹(shù)形可能不唯一（因?yàn)榭赡艽嬖跈?quán)值相同的邊），但代價(jià)一定是唯一的，工正確。若權(quán)值最小的邊有多條并且構(gòu)成環(huán)狀，則總有權(quán)值最小的邊將不出現(xiàn)在某棵最小生成樹(shù)中，口錯(cuò)誤。設(shè)N各結(jié)點(diǎn)構(gòu)成環(huán),N-1條邊權(quán)值相等,另一條邊權(quán)值較小，則從不同的頂點(diǎn)開(kāi)始Prim算法會(huì)得到N-1種不同的最小生成樹(shù)，ID錯(cuò)誤。當(dāng)最小生成樹(shù)唯一時(shí)（各邊的權(quán)值不同），Prim算法和Kruskal算法得到的最小生成樹(shù)相同，IV錯(cuò)誤。答案：A3、對(duì)下圖所示的有向帶權(quán)圖，若采用Dijkstra算法求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b目標(biāo)頂點(diǎn)是b,第二條最短路徑的標(biāo)頂點(diǎn)是c,后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是（）OA:d,e,fB:e,d,fC:f,d,eD:f,e,d解析從a到各頂點(diǎn)的最短路徑的求解過(guò)程如下：□后續(xù)目標(biāo)頂點(diǎn)依次為f,d,e。答案：C4、下列AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程，通過(guò)同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中,加快其進(jìn)度就可以縮短工程工期的是（）。在這里插入圖片描述?A:c和e?B:d和c?C:f和d?D:f和h解析找出AOE網(wǎng)的全部關(guān)鍵路徑為bdcg、bdeh和bfho根據(jù)定義，只有關(guān)鍵路徑上的活動(dòng)時(shí)間同時(shí)減少時(shí)，才能縮短工期。選項(xiàng)A、B和D并不包括在所有的關(guān)鍵路徑中，只有C包含，因此只有加快f和d的進(jìn)度才能縮短工期。答案：C5、對(duì)下圖所示的有向圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁牵ǎ?。A:3,124,5,6B:3,124,6,5C:3,1,425,6D:3,1,4,2,6,5解析按照拓?fù)渑判虻乃惴?，每次都選擇入度為0的結(jié)點(diǎn)從圖中刪除，此圖中一開(kāi)始只有結(jié)點(diǎn)3的入度為0;刪除結(jié)點(diǎn)3后，只有結(jié)點(diǎn)1的入度為0刪除結(jié)點(diǎn)1后，只有結(jié)點(diǎn)4的入度為0；刪除結(jié)點(diǎn)4后，結(jié)點(diǎn)2和結(jié)點(diǎn)6的入度都為0,此時(shí)選擇刪除不同的結(jié)點(diǎn)，會(huì)得出不同的拓?fù)湫蛄?，分別處理完畢后可知可能的拓?fù)湫蛄袨?,1,426,5和3,1,4,62,5,選Do答案：D6、若對(duì)n個(gè)頂點(diǎn)、e條弧的有向圖采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（）。A:0(n)B:O(n+e)n2c：0()D:O(ne)解析采用鄰接表作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)進(jìn)行拓?fù)渑判?，需要?duì)n個(gè)頂點(diǎn)做進(jìn)棧、出棧、輸出各一次，在處理e條邊時(shí)，需要檢測(cè)這n個(gè)頂點(diǎn)的邊鏈表的e個(gè)邊結(jié)點(diǎn),共需要的時(shí)間代價(jià)為O(n+e)o若采用鄰接矩陣作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)進(jìn)行拓?fù)渑判颍谔幚韊條邊時(shí)需對(duì)每個(gè)頂點(diǎn)檢測(cè)相應(yīng)矩陣中的某一行，尋找與它相關(guān)聯(lián)的邊，以便對(duì)這些邊的入度減1,需要的時(shí)n2間代價(jià)為0()o答案：B7、使用Dijkstra算法求下圖中從頂點(diǎn)1到其余各頂點(diǎn)的最短路徑，將當(dāng)前找到的從頂點(diǎn)1到頂點(diǎn)2,3,4,5的最短路徑長(zhǎng)度保存在數(shù)組dist中，求出第二條最短路徑后，dist中的內(nèi)容更新為()。A:26,3,14,6B:25,3,14,6C:21,3,14,6D:15,3,14,6解析在執(zhí)行Dijkstra算法時(shí)，首先初始化dist口，若頂點(diǎn)1到頂點(diǎn)i(i=2,3,4,5)有邊，就初始化為邊的權(quán)值：若無(wú)邊，就初始化為8；初始化頂點(diǎn)集S只含頂點(diǎn)1.Dijkstra算法每次選擇一個(gè)到頂點(diǎn)1距離最近的頂點(diǎn)j加入頂點(diǎn)集S,并判斷由頂點(diǎn)1繞行頂點(diǎn)j后到任一頂點(diǎn)k是否距離更短，若距離更短(即dist[j]+arcs[j][k]<dist[k]),則將dist[x]更新為dist[j]+arcs[j][k];重復(fù)該過(guò)程，直至所有頂點(diǎn)都加入頂點(diǎn)集So數(shù)組dist的變化過(guò)程如下圖所示,可知將第二個(gè)頂點(diǎn)5加入頂點(diǎn)集S后，數(shù)組dist更新為21,3,14,6,故選C。答案：C8、評(píng)價(jià)算法的標(biāo)準(zhǔn)包括如下幾方面:正確性健壯性、高效率及低存儲(chǔ)量。?A:可靠性?B:可行性?C:可讀性?D:可能性解析算法設(shè)計(jì)的要求：.?正確性.可讀性.?健壯性?效率與低存儲(chǔ)量答案：C9、一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有一個(gè)連通分量。?A:0?B:1?C:n-1?D:n解析最少是1個(gè)，這種情況下，它本身就是一個(gè)連通圖；最多是n個(gè)，這種情況下，它由n個(gè)分散的點(diǎn)組成的一個(gè)圖。答案：B10.對(duì)｛05,46,13,55,94,17,42｝進(jìn)行基數(shù)排序,一趟排序的結(jié)果是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解析按照基數(shù)排序：.?(1)先按個(gè)位數(shù)數(shù)字，一次放入對(duì)應(yīng)的桶，取出的結(jié)果為：42,13,94,05,55,46,17? ?(2)再按十位數(shù)字，依次放入對(duì)應(yīng)的桶，取出的結(jié)果為：05,13,17,42,46,55,94但題目中問(wèn)的是一趟排序后的結(jié)果，所以選Co答案：C題干內(nèi)容所述的圖G如上圖所示。A,B,C,D對(duì)應(yīng)的路徑長(zhǎng)度分別為18,13,15,24O應(yīng)用Dijkstra算法求出最短路徑為B所示路徑。答案：B2.下面的（）方法可以判斷出一個(gè)有向圖是否有環(huán)（2.下面的（）方法可以判斷出一個(gè)有向圖是否有環(huán)（路）。工、深度優(yōu)先遍歷口、拓?fù)渑判蛴?、求最短路徑IV、求關(guān)鍵路徑 ?A:工、口、IV??B:I、皿、IV??c：］、口、m.?D:全部可以解析使用深度優(yōu)先遍歷，若從有向圖上的某個(gè)頂點(diǎn)u出發(fā)，在DFS（u）結(jié)束之前出現(xiàn)一條從頂點(diǎn)v到u的邊，由于v在生成樹(shù)上是u的子孫，則圖中必定存在包含u和v的環(huán)，因此深度優(yōu)先遍歷可以檢測(cè)一個(gè)有向圖是否有環(huán)。拓?fù)渑判驎r(shí)，當(dāng)某頂點(diǎn)不為任何邊的頭時(shí)才能加入序列，存在環(huán)時(shí)環(huán)中的頂點(diǎn)一直是某條邊的頭，不能加入拓?fù)湫蛄小Ｒ簿褪钦f(shuō)，還存在無(wú)法找到下一個(gè)可以加入拓?fù)湫蛄械捻旤c(diǎn)，則說(shuō)明此圖存在回路。求最短路徑是允許圖有環(huán)的。關(guān)鍵路徑能否判斷一個(gè)圖有環(huán)，則存在一些爭(zhēng)議。關(guān)鍵路徑本身雖然不允許有環(huán)，但求關(guān)鍵路徑的算法本身無(wú)法判斷是否有環(huán)，判斷是否有環(huán)是求關(guān)鍵路徑的第一步——拓?fù)渑判?。答案：A3、若一個(gè)有向圖的頂點(diǎn)不能排在一個(gè)拓?fù)湫蛄兄校瑒t可判定該有向圖（）。A:是一個(gè)有根的有向圖B:是一個(gè)強(qiáng)連通圖C:含有多個(gè)入度為0的頂點(diǎn)D:含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量解析若不存在拓?fù)渑判颍瑒t表示圖中必定存在回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量（頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量中必然存在回路）。答案：D4、以下關(guān)于拓?fù)渑判虻恼f(shuō)法中，錯(cuò)誤的是（）。I、若某有向圖存在環(huán)路，則該有向圖一定不存在拓?fù)渑判蚩?、在拓?fù)渑判蛩惴ㄖ袨闀捍嫒攵葹榱愕捻旤c(diǎn)，可以使用棧，也可以使用隊(duì)列印、若有向圖的拓?fù)溆行蛐蛄形ㄒ?，則圖中每個(gè)頂點(diǎn)的入度和出度最多為1?a：ism?b：n、di?c：n.?d：in解析i中，對(duì)于一個(gè)存在環(huán)路的有向圖，使用拓?fù)渑判蛩惴ㄟ\(yùn)行后，肯定會(huì)出現(xiàn)有環(huán)的子圖，在此環(huán)中無(wú)法再找到入度為o的結(jié)點(diǎn)，拓?fù)渑判蛞簿瓦M(jìn)行不下去?？谥校⒁?，若兩個(gè)結(jié)點(diǎn)之間不存在祖先或子孫關(guān)系，則它們?cè)谕負(fù)湫蛄兄械年P(guān)系是任意的（即前后關(guān)系任意），因此使用棧和隊(duì)列都可以，因?yàn)檫M(jìn)棧或隊(duì)列的都是入度為0的結(jié)點(diǎn)，此時(shí)入度為0的所有結(jié)點(diǎn)是沒(méi)有關(guān)系的。in中，若拓?fù)溆行蛐蛄形ㄒ唬瑒t很自然地讓人聯(lián)想到一個(gè)線性的有向圖（錯(cuò)誤），下圖的拓?fù)湫蛄幸彩俏ㄒ坏?，但度卻不滿足條件。答案：D5、若一個(gè)有向圖的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t判定該有向圖（）。A:含有多個(gè)出度為0的頂點(diǎn)B:是個(gè)強(qiáng)連通圖C:含有多個(gè)入度為0的頂點(diǎn)D:含有頂點(diǎn)數(shù)大于1的強(qiáng)連通分量解析一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，表明其中存在一個(gè)頂點(diǎn)數(shù)目大于1中存在一個(gè)頂點(diǎn)數(shù)目大于1路，該回路構(gòu)成一個(gè)強(qiáng)連通分量，從而答案選Do答案：D6、下圖所示有向圖的所有拓?fù)湫蛄泄灿校ǎ﹤€(gè)。?A:4?B:6?C:5?D:7解析本圖的拓?fù)渑判蛐蛄杏蠥BCFDEGzABCDFEG,ABCDEFGzABDCFEG和ABDCEFGO答案：C7、若一個(gè)人有向圖具有有序的拓?fù)渑判蛐蛄?，則它的鄰接矩陣必定為（）。A:對(duì)稱B:稀疏c:三角D:一般解析對(duì)有向圖中的頂點(diǎn)適當(dāng)?shù)鼐幪?hào)，使其鄰接矩陣為三角矩陣且主對(duì)角元素全為零的充分必要條件是，該有向圖可以進(jìn)行拓?fù)渑判?。若一個(gè)有向圖的鄰接矩陣為三角矩陣（對(duì)角線上元素為0）,則圖中必不存在環(huán)，因此其拓?fù)湫蛄斜厝淮嬖凇４鸢福篊8、下列關(guān)于圖的說(shuō)法中，正確的是（）。工、有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中1的個(gè)數(shù)n、無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，有向圖的鄰接矩陣一定是非對(duì)稱矩陣川、在圖g的最小生成樹(shù)Gi中，某條邊的權(quán)值可能會(huì)超過(guò)未選邊最小生成樹(shù)Gi中，某條邊的權(quán)值可能會(huì)超過(guò)未選邊的權(quán)值IV、若有向無(wú)環(huán)圖的拓?fù)湫蛄形ㄒ唬瑒t可以唯一確定該圖a：I、it和inb：m和ivc：md：IV解析有向圖鄰接矩陣的第V行中1的個(gè)數(shù)是頂點(diǎn)V的出度，而有向圖中頂點(diǎn)的度為入度與出度之和，工錯(cuò)。無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，但當(dāng)有向圖中任意兩個(gè)頂點(diǎn)之間有邊相連，且是兩條方向相反的有向邊（無(wú)向圖也可視為有兩條方向相反的有向邊的特殊有向圖）時(shí)，有向圖的鄰接矩陣也是一個(gè)對(duì)稱矩陣，口錯(cuò)。最小生成樹(shù)中的n-1條邊并不能保證是圖中權(quán)值最小的n-1條邊，因?yàn)闄?quán)值最小的n-1條邊并不一定能使圖連通。在下圖中，左圖的最小生成樹(shù)如右圖所示，權(quán)值為3的邊并不在其最小生成樹(shù)中。有向無(wú)環(huán)圖的拓?fù)湫?/p>