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

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

√C.O(nD.O(n

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

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

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

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

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

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

A.確B.誤

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

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

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

√24.采深度優(yōu)先搜索或拓撲排序算法可以判斷出一個有向圖中是否有環(huán)路)()中南大學2003一、9(1)A.確B.誤

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

[I,J]一定path

[I,J]27.如有向圖的拓撲排序序列是唯一的，則圖中必定只有一個頂點的入度0一個頂點的出度為0()【北方交通大學2003三4(2分)】A.確B.誤

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