計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(圖)歷年真題試卷匯編6

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（圖）歷年真題試卷匯編(分：60.00做題時(shí)間：分鐘)一、單項(xiàng)擇(總題數(shù)：6，數(shù)12.00)1.有n個(gè)點(diǎn)、e條邊的圖G采用鄰接存儲，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為)?！灸暇├砉ご?005一、2(1)A.O(n)B.O(n+e)

√C.O(nD.O(n

e))2.在下列網(wǎng)中()邊不帶權(quán)值的圖?！救A南理工大學(xué)2007】A.電圖B.AOVC.路網(wǎng)D.AOE

√3.關(guān)鍵路徑是AOE網(wǎng)()【中南大學(xué)一10(1分)A.始點(diǎn)到終點(diǎn)的最短路徑B.始點(diǎn)到終點(diǎn)的最長路徑√C.始點(diǎn)到終點(diǎn)的邊數(shù)最多的路徑D.始點(diǎn)到終點(diǎn)的邊數(shù)最少的路徑4.下面關(guān)于求關(guān)鍵徑的說法不正確的是)?！灸暇├砉W(xué)1998一12(2分)】A.關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B.個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同C.個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差√D.鍵活動(dòng)一定位于關(guān)鍵路徑上C的敘述有誤。一個(gè)事件的最遲開始時(shí)間，是該事件所有后繼事件點(diǎn))遲開始時(shí)間和相應(yīng)活動(dòng)持續(xù)時(shí)間差的最小值。例如，某事(為E)有3后繼事件頂點(diǎn))它3后繼事件有3條弧(活動(dòng))，求3個(gè)后繼事件和弧頭指向它的那個(gè)活動(dòng)的持續(xù)時(shí)間的差，取最小值就得到最遲開始時(shí)間。5.下列關(guān)AOE網(wǎng)的敘述中，不正確的是)。北方交通大學(xué)1999一7(3)【北京工業(yè)大學(xué)1999一、1(2)【哈爾濱工業(yè)大學(xué)2004二3(1分)A.鍵活動(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之所以錯(cuò)誤，是因?yàn)橹挥袦p少所有關(guān)鍵路徑上共有的關(guān)鍵活動(dòng)，才能縮短工期。若某活動(dòng)不為關(guān)鍵路徑共享，減少它，并沒影響其他關(guān)鍵路徑。6.下列有關(guān)圖的說錯(cuò)誤的是()【中南大學(xué)2003二、19(1分A.有向圖中，出度為的點(diǎn)稱為葉子B.鄰接矩陣表示圖，容易判斷任意兩個(gè)結(jié)點(diǎn)之間是否有邊相連，并求得各結(jié)點(diǎn)的度C.深度方向遍歷圖和先根次序遍歷樹類似，得到的結(jié)果是唯一的√D.有向圖G中從結(jié)點(diǎn)Vi到結(jié)點(diǎn)Vj有一條路徑，則在圖G結(jié)點(diǎn)的線性序列中結(jié)點(diǎn)V必在結(jié)點(diǎn)V之前的話，則稱為一個(gè)拓?fù)湫蛄袌D的深度優(yōu)先遍歷的確和樹的先根遍歷類似。但若只給邏輯圖形，沒有存儲結(jié)構(gòu)，則圖的深度優(yōu)先遍歷結(jié)果會(huì)不唯一。即使給了存儲結(jié)構(gòu)，例如只說用鄰接表存儲，但沒說鄰接點(diǎn)如何排列，是升序還是降序，還是隨意，無法確定誰是第一鄰接點(diǎn)，都會(huì)造成結(jié)果不唯一。二、填空(總題數(shù)：10，分?jǐn)?shù)：20.00)

7.若一個(gè)具有n個(gè)頂點(diǎn)、條邊的無向圖是一個(gè)森林，則該森林中必有_________棵?！竟枮I工業(yè)大學(xué)2005一、分)】__________________________________________________________________________________________正確答案：(確答案：n一e)8.設(shè)無向G有n頂點(diǎn)和e條每個(gè)頂點(diǎn)的度為di(1in>則e=__________福州大學(xué)1998二、2(2)__________________________________________________________________________________________正確答案：(確答案：)9.在有n個(gè)頂點(diǎn)的有圖中，每個(gè)頂點(diǎn)的度最大可達(dá)__________。中南大學(xué)2002一、1(1分)__________________________________________________________________________________________正確答案：(確答案：2(n一1))10.具10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為_________。華中理工大學(xué)一7(1分)】__________________________________________________________________________________________正確答案：(確答案：45)11.在據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)樹形結(jié)構(gòu)和圖形結(jié)構(gòu)數(shù)據(jù)元素之間分別存在___________________和聯(lián)系?！灸暇├砉ご髮W(xué)2004】__________________________________________________________________________________________正確答案：(確答案：一對一、一對多、多對多12.G是個(gè)非連通無向圖，共28條邊，則該圖至少__________個(gè)頂點(diǎn)。西安電子科技大學(xué)2001軟件一、8(2)__________________________________________________________________________________________正確答案：(確答案：9計(jì)算方法：至少需要構(gòu)成無向完全圖8頂點(diǎn)和一個(gè)孤立頂點(diǎn)。13.n個(gè)點(diǎn)的連通圖至少有__________條。【中南大學(xué)二、4(2分__________________________________________________________________________________________正確答案：(確答案：n一1)14.有圖G的強(qiáng)連通分量是指_________?！颈本┛萍即?997一、7】__________________________________________________________________________________________正確答案：(確答案：有向圖的極大強(qiáng)連通子圖15.在n頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需__________弧【合肥工業(yè)大學(xué)2000三、分)】__________________________________________________________________________________________正確答案：(確答案：n。n條形成一個(gè)環(huán)。)16.n個(gè)點(diǎn)的無向連通圖的連通分量個(gè)數(shù)為__________個(gè)。【電子科技大2005二1(1分)__________________________________________________________________________________________正確答案：(確答案：1)三、判斷(總題數(shù)：14，分?jǐn)?shù)：28.00)17.圖G一棵最小代價(jià)生成樹的代價(jià)未必小于G其他任何一棵生成樹的代價(jià)南大2005三、4(2)A.確B.誤

√18.對任意一個(gè)圖，從它的某個(gè)頂點(diǎn)進(jìn)行一次先深或先廣搜索可以訪問到該圖的每個(gè)頂點(diǎn)。()【哈爾濱工業(yè)大學(xué)2002三、分)A.確B.誤

√19.需借助于一個(gè)隊(duì)列來實(shí)現(xiàn)法。()南京航空航天大學(xué)六8(1分A.確B.誤

√20.采鄰接表存儲的圖廣度優(yōu)先遍歷類似于二叉樹的先序遍歷北京交通大學(xué)2005三)

A.確B.誤

√21.若v0開始對有向圖g進(jìn)深度遍歷序列唯一，則可唯一確定該圖。)【北京郵電大學(xué)2006二6(1分)A.確B.誤

√對一個(gè)邏輯圖進(jìn)行深度／廣度優(yōu)先遍歷，其遍歷序列一般是不唯一的，因?yàn)闆]確定存儲結(jié)構(gòu)。即使給出存儲結(jié)構(gòu)，若沒說明鄰接點(diǎn)的排列規(guī)則，遍歷序列也不唯一。因?yàn)榈谝秽徑狱c(diǎn)的確定以及下一鄰接點(diǎn)的確定并沒說明。本題的錯(cuò)誤在于沒說明進(jìn)入dfs次數(shù)。例如，若vx沒路徑vx可能是孤立頂點(diǎn)，也可能有弧指向遍歷序列上某頂點(diǎn)，從開的深度遍歷序列都是相同的，但不能唯一確定該圖。22.對個(gè)無向圖進(jìn)行先深搜索時(shí)，得到的先深序列是唯一的。)【爾濱工業(yè)大學(xué)2005三8(1分)A.確B.誤

√23.若向圖不存在回路，即使不用訪問標(biāo)志位同一結(jié)點(diǎn)也不會(huì)被訪問兩次()【北京郵電大學(xué)2005二7(1)A.確B.誤

√24.采深度優(yōu)先搜索或拓?fù)渑判蛩惴梢耘袛喑鲆粋€(gè)有向圖中是否有環(huán)路)()中南大學(xué)2003一、9(1)A.確B.誤

√25.一圖的廣度優(yōu)先遍歷生成樹是唯一的。)【中國海大學(xué)2006二11(1分)A.確B.誤√26.在Floyd算法解各頂點(diǎn)間的最短路徑時(shí)表示兩點(diǎn)間路徑的path的子集(K=12，，，n)。()合肥工業(yè)大學(xué)二6(1分)】A.確B.誤√

[I,J]一定path

[I,J]27.如有向圖的拓?fù)渑判蛐蛄惺俏ㄒ坏模瑒t圖中必定只有一個(gè)頂點(diǎn)的入度0一個(gè)頂點(diǎn)的出度為0()【北方交通大學(xué)2003三4(2分)】A.確B.誤

√28.具n個(gè)頂點(diǎn)條的無向圖鄰接矩陣作為存儲結(jié)構(gòu)任意頂點(diǎn)的度數(shù)的時(shí)間復(fù)雜