計(jì)算機(jī)專業(yè)基礎(chǔ)綜合

1、計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（圖）-試卷2（總分：54.00，做題時間：90分鐘）一、單項(xiàng)選擇題（總題數(shù)：18,分?jǐn)?shù)：36.00）單項(xiàng)選擇題1-40小題。下列每題給出的四個選項(xiàng)中，只有一個選項(xiàng)是最符合題目要求的。下面是一個求最小生成樹的算法，其中G是連通無向圖，T是所求的生成樹。T： =G： While T中存在 回路do begin在T中找一條權(quán)值最大的邊e； T： =T 一 e； （T中去掉e邊）EnD.試問該算法是哪一 種求最小生成樹的算法？（）Prim（普里姆）算法Kruskal（克魯斯卡爾算法）羅巴赫算法其他算法由算法可以看出使用的是Kruskal算法。鄰接表是圖的一種（）。順序存儲結(jié)構(gòu)鏈接存

2、儲結(jié)構(gòu) V索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)圖的鄰接表存儲結(jié)構(gòu)是一種鏈接存儲結(jié)構(gòu)。下面試圖對圖中路徑進(jìn)行定義，說法正確的是（）。由頂點(diǎn)和相鄰頂點(diǎn)序列構(gòu)成的邊所形成的序列 V由不同頂點(diǎn)所形成的序列由不同邊所形成的序列上述定義都不是由圖的定義可知，B與C是錯誤的。無向圖中頂點(diǎn)個數(shù)為n，那么邊數(shù)最多為（）。n 一 1n（n 一 1）/2 Vn（n+1） / 2 TOC o 1-5 h z n 2無向圖中有n個頂點(diǎn)，如果每兩個頂點(diǎn)之間均是相互連通的，那么此時無向圖中的邊數(shù)最多，為n（n1） /2。在一個具有n（n0）個頂點(diǎn)的連通無向圖中，至少需要的邊數(shù)是（）。nn+1n 一 1 Vn/2在無向圖中，如果從一個頂

3、點(diǎn)v j到另一個頂點(diǎn)v j （i#j）有路徑，則稱頂點(diǎn)v j和v j是連通的。如果 圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。所以具有n個頂點(diǎn)的連通無向圖至少有n一1條邊。以下敘述中正確的是（）。I .對有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能 訪問到每個頂點(diǎn)，則該圖一定是完全圖II.連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存訪問過的頂點(diǎn) III.圖的深度優(yōu)先搜索中一般要采用棧來暫存訪問過的頂點(diǎn)I，IIn，m vi，mi，ii，mI的敘述是錯誤的，因?yàn)槿绻邢驁D構(gòu)成雙向有向環(huán)時，則從任一頂點(diǎn)出發(fā)均能訪問到每個頂點(diǎn)，但該圖 卻非完全圖。11、111的敘述顯然是正確的。帶權(quán)有

4、向圖G用鄰接矩陣A存儲，則頂點(diǎn)i的入度等于A中（）。第i行非8的元素之和第i列非8的元素之和第i行非8且非0的元素個數(shù)第i列非8且非0的元素個數(shù) V有向圖的鄰接矩陣中，0和8表示的都不是有向邊，而入度是由鄰接矩陣的列中元素計(jì)算出來的。在一個無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（）倍。 TOC o 1-5 h z 1 / 212 V4在無向圖中，一條邊計(jì)入兩個頂點(diǎn)的度數(shù)。采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）算法。前序遍歷 V中序遍歷后序遍歷按層遍歷由圖的深度優(yōu)先遍歷算法和二叉樹的前序遍歷可知選A。任何一個無向連通圖（）最小生成樹。只有一棵有一棵或多棵 V一定有多棵可能不存在無向

5、連通圖應(yīng)有一棵或多棵最小生成樹。判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用的是（）。求關(guān)鍵路徑的方法求最短路徑的迪杰斯特拉方法深度優(yōu)先遍歷算法 V廣度優(yōu)先遍歷算法當(dāng)有向圖中無回路時，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時，出棧的順序（退出I）FSTraverse算法）即為逆 向的拓?fù)湫蛄?。有n個頂點(diǎn)e條邊的無向圖，采用鄰接表存儲時，有（）個表頭結(jié)點(diǎn)，有（）個鏈表結(jié)點(diǎn)。n. 2e Vn. 2e+1n 一 1. 2en 一 1. 2e+1根據(jù)鄰接表的結(jié)構(gòu)，無向圖對應(yīng)的鄰接表有n個表頭結(jié)點(diǎn)，有2e個鏈表結(jié)點(diǎn)（每條邊對應(yīng)兩個鏈表結(jié)點(diǎn)）。對于由n個頂點(diǎn)組成的有向完全圖來說，圖中共包含（）條邊

6、，對于由n個頂點(diǎn)組成的無向完全圖來說， 圖中共包含（）條邊。n，n（n 一 1）n，n（n 一 1）/22n， n（n 一 1）n（n 一 1）， n（n 一 1）/2 V由完全圖的定義可知本題答案為D。在一個（）圖中尋找拓?fù)湫蛄械倪^程稱為（）。有向，拓?fù)渑判?V無向，拓?fù)渑判蛴邢?，最短路徑搜索無向，最短路徑搜索尋找拓?fù)湫蛄芯褪峭負(fù)渑判?，只能對有向圖進(jìn)行拓?fù)渑判颉?TOC o 1-5 h z 用鄰接矩陣A表示圖，判定任意兩個頂點(diǎn)v和v j之間是否有長度為m的路徑相連，則只要檢查（） 的第i行第j列的元素是否為零即可。1 JmAAA m VAm-1 此題考查的知識點(diǎn)是圖的鄰接矩陣存儲。在圖的鄰接

7、矩陣中，兩點(diǎn)之間有邊，則值為1，否則為0。本題只 要考慮A m =AXAXXA（m個A矩陣相乘后的乘積矩陣）中（i，j）的元素值是否為0就行了。當(dāng)各邊上的權(quán)值（）時，BFS算法可用來解決單源最短路徑問題。均相等 V均互不相等不一定相等不確定此題考查的知識點(diǎn)是圖的BFS算法。BFS是從根結(jié)點(diǎn)開始，沿著樹的寬度遍歷樹的結(jié)點(diǎn)，如果所有結(jié)點(diǎn)均 被訪問，則算法中止。當(dāng)各邊上的權(quán)值相等時，計(jì)算邊數(shù)即可，所以選A。下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是（）。用鄰接矩陣存儲圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān) V用鄰接矩陣存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)用鄰接表存儲圖占用空間大小只與圖中

8、頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)用鄰接表存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān) 鄰接矩陣法的基本思想是對于有n個頂點(diǎn)的圖，用一維數(shù)組vexsn存儲頂點(diǎn)信息，用二維數(shù)組Ann存儲頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素Aij存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。鄰接表法的基本思想:對圖的每個頂點(diǎn)建立一個單鏈表，存儲該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個單鏈表設(shè)一個表頭結(jié)點(diǎn)。第i個單鏈表表示依附于頂點(diǎn)V 的邊（對有向圖是以頂點(diǎn)V 為頭或尾的?。６?、綜合應(yīng)用題（總題數(shù)：8,分?jǐn)?shù)：18.00）1綜合應(yīng)用題41-47小題。證明：具

9、有n個頂點(diǎn)和多于n 一 1條邊的無向連通圖G 一定不是樹。正確答案：（正確答案：此題考查的知識點(diǎn)是圖的定義。具有n個頂點(diǎn)n一1條邊的無向連通圖是自由樹， 即沒有確定根結(jié)點(diǎn)的樹，每個結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n一1條，因一條邊要連接兩個結(jié)點(diǎn)，則必因加 上這一條邊而使兩個結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹（在圖論中樹定義為無回 路的連通圖）。）證明：對有向圖的頂點(diǎn)適當(dāng)?shù)鼐幪?，可使其鄰接矩陣為下三角形且主對角線為全O的充要條件是該圖為 無環(huán)圖。正確答案：（正確答案：此題考查的知識點(diǎn)是無環(huán)圖的定義。根據(jù)題意，該有向圖頂點(diǎn)編號的規(guī)律是讓弧尾 頂點(diǎn)的編號大于弧頭頂點(diǎn)的編號。由于不允許從某

10、頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對角線 元素均為0。先證明該命題的充分條件。由于弧尾頂點(diǎn)的編號均大于弧頭頂點(diǎn)的編號，在鄰接矩陣中，非 零元素（Aij=1 ）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點(diǎn) 編號大于弧尾頂點(diǎn)編號的弧，否則，就必然存在環(huán)路。（對該類有向無環(huán)圖頂點(diǎn)編號，應(yīng)按頂點(diǎn)出度順序編 號。）關(guān)于圖（Graph）的一些問題：（分?jǐn)?shù)：4.00）(1).有n個頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?最少有多少條邊?正確答案：(正確答案：n(n1), n)(2).表示有1000個頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否為稀疏矩陣?正確答

11、案：(正確答案：10 6，不一定是稀疏矩陣提示：此題考查的知識點(diǎn)是圖的相關(guān)術(shù)語。(1)在有向 圖G中，如果對于每一對v j，v j屬于V，v j不等于v j，從v j到v j和從v j到v j都存在路徑， 則稱G是強(qiáng)連通圖。最多邊是所有的頂點(diǎn)每對之間都有邊，邊數(shù)為n(n 一 1)；最少只有一個方向有邊，為 n。 (2)元素個數(shù)為矩陣的大小，即10 6，稀疏矩陣的定義是非零個數(shù)遠(yuǎn)小于該矩陣元素個數(shù)，且分布無 規(guī)律，不一定稀疏。)如何對有向圖中的頂點(diǎn)號重新安排可使得該圖的鄰接矩陣中所有的1都集中到對角線以上？ 正確答案：(正確答案：此題考查的知識點(diǎn)是圖頂點(diǎn)度數(shù)?？梢园锤黜旤c(diǎn)的出度進(jìn)行排序。n個頂點(diǎn)

12、的有向 圖，其頂點(diǎn)最大出度是n 一 1，最小出度為0。這樣排序后，出度最大的頂點(diǎn)編號為1，出度最小的頂點(diǎn)編 號為n之后，進(jìn)行調(diào)整，即若存在弧i，j，而頂點(diǎn)，的出度大于頂點(diǎn)i的出度，則將j的編號排在頂 點(diǎn)i的編號之前。)假定圖G=(V，E)是有向圖，V=1，2，N，NN1，G以鄰接矩陣方式存儲，G的鄰接矩陣為A，即A 是一個二維數(shù)組。如果i到j(luò)有邊，則Ai，j=l，否則Ai，j=0。請給出一個算法思想，該算法能判斷 G是否是非循環(huán)圖(即G中是否存在回路)，要求算法的時間復(fù)雜性為O(n 2 )。正確答案：(正確答案：此題考查的知識點(diǎn)是圖的遍歷。采用深度優(yōu)先遍歷算法，在執(zhí)行DFS(v)時，若在 退出DFS(v)前碰到某頂點(diǎn)v，其鄰接點(diǎn)是巳經(jīng)訪問的頂點(diǎn)v，則說明v的子孫u有到v的回邊，即說明有 環(huán)；否則，無環(huán)。)對一個圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些？正確答案：(正確答案：此題考查的知識點(diǎn)是圖的遍歷。遍歷不唯一的因素有：開始遍歷的頂點(diǎn)不同；存儲正確答案：(正確答案：無向連通圖的生成樹包含圖中全部n個頂點(diǎn)，以及足以使圖連通的n一1條邊。而 最小生成樹則是各邊權(quán)值之和最小的生成樹。)