計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬

試卷1（共7套）

（共272題）

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬

試卷第1套

一、單選題（本題共34題，每題1.0分，共34分。）

1、下面是一個(gè)求最小生成樹的算法，其中G是連通無向圖，T是所求的生成樹。

T;=G;WhileT中存在回路dobegin在T中找一條權(quán)值最大的邊e；T：=T-[e]；

（T中去掉e邊）End.試問該算法是哪一種求最小生成樹的算法?（）

A、Prim（普里姆）算法

B、Kruskal（克魯斯卡爾算法）

C、羅巴赫算法

D、其他算法

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：由算法可以看出使用的是Knlskal算法。

2、鄰接表是圖的一種

A、順序存儲(chǔ)結(jié)構(gòu)

B、鏈接存儲(chǔ)結(jié)構(gòu)

C、索引存儲(chǔ)結(jié)構(gòu)

D、散列存儲(chǔ)結(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：圖的鄰接表存儲(chǔ)結(jié)構(gòu)是一種鏈接存儲(chǔ)結(jié)構(gòu)。

3、下面試圖對(duì)圖中路徑進(jìn)行定義，說法正確的是（）。

A、由頂點(diǎn)和相鄰頂點(diǎn)序列構(gòu)成的邊所形成的序列

B、由不同頂點(diǎn)所形成的序列

C、由不同邊所形成的序列

D、上述定義都不是

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：由圖的定義可知，B與c是錯(cuò)誤的。

4、無向圖中項(xiàng)點(diǎn)個(gè)數(shù)為n,那么邊數(shù)最多為（）。

A、n-1

B、n（n-l）/2

C>n（n+l）/2

D、n2

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：無向圖中有n個(gè)頂點(diǎn)，如果每兩個(gè)頂點(diǎn)之間均是相互連通的，那么此

時(shí)無向圖中的邊數(shù)最多，為凡（。一1）/2。

5、在一個(gè)具有n（n>0）個(gè)頂點(diǎn)的連通無向圖中，至少需要的邊數(shù)是（）。

A、n

n+1

C、n-1

D、n/2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在無向圖中，如果從一個(gè)頂點(diǎn)必到另一個(gè)頂點(diǎn)Vj（字j）有路徑，則稱頂

點(diǎn)Vi利Vj是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。所以

具有n個(gè)頂點(diǎn)的連通無向圖至少有n一1條邊。

6、以下敘述中正確的是（）。I.對(duì)有向圖G,如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)

先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖口.連通圖的廣度優(yōu)

先搜索中一般要采用隊(duì)列來暫存訪問過的頂點(diǎn)m.圖的深度優(yōu)先搜索中一般要采

用棧來暫存訪問過的頂點(diǎn)

A、I,n

B、口，in

c、I,m

D^I,n,in

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：I的敘述是錯(cuò)誤的，因?yàn)槿绻邢驁D構(gòu)成雙向有向環(huán)時(shí)，則從任一頂

點(diǎn)出發(fā)均能訪問到每個(gè)頂點(diǎn)，但該圖卻非完全圖。口、in的敘述顯然是正確的。

7、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（）。

A、第i行非8的元素之和

B、第i列非8的元素之和

C、第i行非8且非。的元素個(gè)數(shù)

D、第i列非8且非0的元素個(gè)數(shù)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：有向圖的鄰接矩陣中，0和8表示的幫不是有向邊，而入度是由鄰接

矩陣的列中元素計(jì)算出來的。

8、在一個(gè)無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（）倍。

A、1/2

B、1

C、2

D、4

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在無向圖中，一條邊計(jì)入兩個(gè)頂點(diǎn)的度數(shù)。

9、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）算法。

A、前序遍歷

B、中序遍歷

C、后序遍歷

D、按層遍歷

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：由圖的深度優(yōu)先遍歷算法和二叉樹的前序遍歷可知選Ao

10、任何一個(gè)無向連通圖（）最小生成樹。

A、只有一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：無向連通圖應(yīng)有一棵或多棵最小生成樹。

11、判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用的是

（）。

A、求關(guān)鍵路徑的方法

B、求最短路徑的迪杰斯特拉方法

C、深度優(yōu)先遍歷算法

D、廣度優(yōu)先遍歷算法

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析?：當(dāng)有向圖中無回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順

序（退出DFSTra—verse算法）即為逆向的拓?fù)湫蛄小?/p>

12、有n個(gè)頂點(diǎn)e條邊的無向圖，采用鄰接表存儲(chǔ)時(shí)，有（）個(gè)表頭結(jié)點(diǎn)，有（）個(gè)鏈

表結(jié)點(diǎn)。

A、n,2e

B、n,2e+1

C、n-1,2e

D、n-1,2e+l

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：根據(jù)鄰接表的結(jié)構(gòu)，無向圖對(duì)應(yīng)的鄰接表有n個(gè)表頭結(jié)點(diǎn)，有2e個(gè)

鏈表結(jié)點(diǎn)（每條邊對(duì)應(yīng)兩個(gè)鏈表結(jié)點(diǎn)）。

13、對(duì)于由n個(gè)頂點(diǎn)組成的有向完全圖來說，圖中共包含（）條邊，對(duì)于由n個(gè)頂點(diǎn)

組成的無向完全圖來說，圖中共包含（）條邊。

A、n,n（n—1）

B、n,n（n一1）/2

C、2n,n（n—1）

D、n（n一1）,n（n—1）/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：由完全圖的定義可知本題答案為Do

14、在一個(gè)（）圖中尋找拓?fù)湫蛄械倪^程稱為（）。

A、有向，拓?fù)渑判?/p>

B、無向，拓?fù)渑判?/p>

C、有向，最短路徑搜索

D、無向，最短路徑搜索

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：尋找拓?fù)湫蛄芯褪峭負(fù)渑判颍荒軐?duì)有向圖進(jìn)行拓?fù)渑判?

15、用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)力和胃之間是否有長度為m的路徑

相連，則只要檢查（）的第i行第j列的元素是否為零即可。

A^mA

B、A

C、Am

D、Am-1

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的鄰接矩陣存儲(chǔ).在圖的鄰接矩陣中，兩點(diǎn)之

間有邊，則值為1,否則為0。本題只要考慮Am=AxAx…x&m個(gè)A矩陣相乘后的

乘積矩陣）中（i,j）的元素值是否為。就行了。

16、當(dāng)各邊上的權(quán)值（）時(shí)，BFS算法可用來解決單源最短路徑問題。

A、均相等

B、均互不相等

C、不一定相等

D、不確定

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的BFS算法。BFS是從根結(jié)點(diǎn)開始，沿著樹

的寬度遍歷樹的結(jié)點(diǎn)，如果所有結(jié)點(diǎn)均被訪問，則算法中止。當(dāng)各邊上的權(quán)值相等

時(shí)，計(jì)算邊數(shù)即可，所以選A。

17、下面關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的敘述中正確的是（）。

A、用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)

B、用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)

C、用鄰接表存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)

D、用鄰接表存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：鄰接矩陣法的基本思想是對(duì)于有n個(gè)頂點(diǎn)的圖，用一維數(shù)組Vexs[n]

存儲(chǔ)頂點(diǎn)信息，用二維數(shù)組A[n][n]存儲(chǔ)頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰

接矩陣。在鄰接矩陣中，以頂點(diǎn)在Vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元

素存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。

無?鄰接矩陣是對(duì)稱方陣；在具體存放鄰接矩陣時(shí)只需存放上（或下）三角矩陣的元素即可。

鄰

向

接?對(duì)于頂點(diǎn)%其度數(shù)是第i行的作。元案的個(gè)數(shù)

圖

矩?無向圖的邊數(shù)是上（或下）三角形矩陣中非。元索個(gè)數(shù)。_____

一

pr有?對(duì)于原點(diǎn)%第行的非元索的個(gè)數(shù)是其出度匕）。

的i00"

向

特

圖?第?列的非0元素的個(gè)數(shù)是其人度/。（巴）。

點(diǎn)

?鄰接矩陣中非。元素的個(gè)數(shù)就是圖的弧的數(shù)目。

鄰接表法的基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)

及其相關(guān)信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。第i個(gè)單鏈表表示依附于頂點(diǎn)Vi

的邊（對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧）.

?表頭向敬中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分成個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目。

?在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間。

鄰

接?在無向圖中，頂點(diǎn)匕的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)。

表

法?對(duì)有向圖可以建立正鄰接表或逆鄰接盤。

的?正鄰接融是以頂點(diǎn)V為出度（即為孤的起點(diǎn)）而建立的鄰接表。

特

點(diǎn)?逆鄰接我是以頂點(diǎn)匕為人度（即為弧的終點(diǎn)）而建立的鄰接表。

?在有向圖中，第i個(gè)鞋表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)匕的出（或入）度；求入（或出）度，須遍歷整個(gè)鄰接表。

?在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)。

18、在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)叫在頂點(diǎn)W之前，則下列情形不可能出現(xiàn)

的是（）。

A、G中有弧Vvi，vj>

B、G中有一條從必到可的路徑

C、G中沒有弧V%,vj>

D、G中有一條從vj到Vi的路徑

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析?：此題考查的知識(shí)點(diǎn)是圖的拓?fù)渑判颉８鶕?jù)拓?fù)渑判虻亩x，若頂點(diǎn)Vi

與頂點(diǎn)Vj有一條弧，則拓?fù)湫蛄兄许旤c(diǎn)力必在頂點(diǎn)Vj之前。若有一條從Vj到黨的

路徑，則頂點(diǎn)切不可能在頂點(diǎn)vj之前。所以應(yīng)選D。

19、以下關(guān)于圖的說法中正確的是（）。I.一個(gè)有向圖的鄰接表和逆鄰接表中內(nèi)結(jié)

點(diǎn)個(gè)數(shù)一定相等□.用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)

數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)in.無向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接

矩陣一定是不對(duì)稱的

A、I,n

B、nyin

c、i,m

D、僅有n

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：說法I是正確的，鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表

的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中的邊的個(gè)數(shù)。說法口是正確的，鄰接矩陣的空間復(fù)雜

度為on?),與邊的個(gè)數(shù)無關(guān)。說法in是錯(cuò)誤的，有向圖的鄰接矩陣不一定是不對(duì)

稱的，例如，有向完全圖的鄰接矩陣就是對(duì)稱的。

20、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是()。

A、關(guān)鍵活動(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ì)提前完成

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的關(guān)鍵路徑。在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具

有最大路徑長度(該路徑上的各個(gè)活動(dòng)所持續(xù)的時(shí)間之和)的路徑稱為關(guān)鍵路徑，并

且不只一條。關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。A、C、D的說法都正確。但任何

一個(gè)關(guān)鍵活動(dòng)提前完成，不一定會(huì)影響關(guān)鍵路徑，所以根據(jù)題意應(yīng)選B。

21、一個(gè)二部圖的鄰接矩陣A是一個(gè)()類型的矩陣。

A、nxn矩陣

B、分塊對(duì)稱矩陣

C、上三角矩陣

D,下三角矩陣

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是二部圖的定義與存儲(chǔ)。二部圖定義為：若能將無

向圖6=的頂點(diǎn)集V劃分成兩個(gè)子集VI和V2(V1CIV2=10),使得G中任何一條邊

的兩個(gè)端點(diǎn)一個(gè)屬于VI,另一個(gè)屬于V2,則稱G為二部圖。由于其特點(diǎn)，其存

儲(chǔ)矩陣必為分塊對(duì)稱的，所以選B。

22、求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為()。

A、0(n)

B、O(n+c)

C、0(n2)

D、0(n3)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：暫無解析

）是下圖所示的有向圖的拓?fù)湫蛄小?/p>

A、Cl,C2,C6,C7,C5,C4,C3

B、Cl,C2,C6,C3,C4,C5,C7

C、CI,C4,C2,C3,C5,C6,C7

D、C5,C7,C4,Cl,C2,C3,C6

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：考查拓?fù)渑判虻乃惴āＲ?開頭的拓?fù)渑判蜻^程，如下圖所示:

輸出5

66

輸出7輸出4

5開頭的拓?fù)渑判蜻^程，答案中的過程如下圖所示:

24、如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有（）棵生成樹。

A、n2

n

C、n—1

D、1

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：因?yàn)閚個(gè)頂點(diǎn)構(gòu)成的環(huán)共有n條邊，去掉其中任意一條便是一棵生成

樹，共有n種情況，所以可以有n棵不同的生成樹，

25、如下圖所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有（）個(gè)。

①aebfdc@acfdeb③aedfcb（4）aefdbc?aecfdb

A、5

B、4

C、3

D、2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：本題中，符合深度優(yōu)先遍歷順序的是I和5,其他三個(gè)序列均不符

合。

26、無向圖G有23條邊，度為4的頂點(diǎn)有5個(gè)，度為3的頂點(diǎn)有4個(gè)，其余都是

度為2的頂點(diǎn)，則圖G最多有（）個(gè)頂點(diǎn)。

A、11

B、12

C、15

D、16

標(biāo)準(zhǔn)答案：D

2孫噌=2e

知識(shí)點(diǎn)解析：由于在具有n個(gè)頂點(diǎn)e條邊的無向圖中，有片，故可求

得度為2的頂點(diǎn)數(shù)為7個(gè)，從而最多有16個(gè)頂點(diǎn)。

27、對(duì)AOE網(wǎng)絡(luò)中有關(guān)關(guān)鍵路徑的敘述中，正確的是（）。

A、從開始頂點(diǎn)到完成頂點(diǎn)的具有最大長度的路徑，關(guān)鍵路徑長度是完成整個(gè)工程

所需的最短時(shí)間

B、從開始頂點(diǎn)到完成頂點(diǎn)的具有最小長度的路徑，關(guān)鍵路徑長度是完成整個(gè)工程

所需的最短時(shí)間

C、從開始頂點(diǎn)到完成頂點(diǎn)的具有最大長度的路徑，關(guān)鍵路徑長度是完成整個(gè)工程

所需的最長時(shí)間

D、從開始頂點(diǎn)到完成頂點(diǎn)的具有最小長度的路徑，關(guān)鍵路徑長度是完成整個(gè)工程

所需的最長時(shí)間

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題考查關(guān)鍵路徑的定義。關(guān)鍵路徑：從起點(diǎn)到終點(diǎn)的最長路徑長

度（路徑上各活動(dòng)持續(xù)時(shí)間之和）。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。

28、以下關(guān)于圖的敘述中，正確的是（）。

A、強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有瓠

B、圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點(diǎn)數(shù)

C、無向圖的連通分量指無向圖中的極大連通子圖

D、假設(shè)有圖6=｛丫，｛E｝｝,頂點(diǎn)集VWV,EFE,則V，和｛E，｝構(gòu)成G的子圖

標(biāo)準(zhǔn)答窠：C

知識(shí)點(diǎn)解析：強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有路徑，但未必有弧，A

錯(cuò)誤。圖與樹的區(qū)別是邏輯上的，而不是邊數(shù)的區(qū)別，圖的邊數(shù)也可能小于樹的邊

數(shù)。若E，中的邊對(duì)應(yīng)的頂點(diǎn)不是V，中的元素時(shí)，則V，和｛E3無法構(gòu)成圖，D錯(cuò)

誤。

29、假設(shè)有n個(gè)頂點(diǎn)e條邊的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)v相關(guān)的所

有邊的時(shí)間復(fù)雜度為（）c

A、0（n）

B、O（e）

C、O(n+e)

D^O(ne)

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：刪除與某頂點(diǎn)v相關(guān)的所有邊的過程如下：先刪除下標(biāo)為v的頂點(diǎn)表

結(jié)點(diǎn)的單鏈表，出邊數(shù)最多為n—1,對(duì)應(yīng)時(shí)間復(fù)雜度為O(n),再掃描所有邊表結(jié)

點(diǎn)，刪除所有的入邊，對(duì)應(yīng)時(shí)間復(fù)雜度為0(e)。故總的時(shí)間復(fù)雜度為O(n+e)。

30、若G是一個(gè)具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G的結(jié)

點(diǎn)數(shù)至少是()。

A、11

B、10

C、9

D、8

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：n個(gè)頂點(diǎn)構(gòu)成的無向圖中，邊數(shù)9(n—l)/2,將e=36代入，有

n>9,現(xiàn)已知無向圖是非連通的，則n至少為10。

31、已知有向圖G=(V,A),其中V={a,b,c,d,e),A={,,,,,}<>對(duì)該圖

進(jìn)行拓?fù)渑判颍旅嫘蛄兄胁皇峭負(fù)渑判虻氖?).

A、a,d,c,b,e

B、d,a,b,c,e

C>a,b,d,c,e

D、a,b,c,d,e

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：選項(xiàng)D中，刪去a、b及其對(duì)應(yīng)的出邊后，c的入度不為0,因此有

邊，故不是拓?fù)湫蛄小＿x項(xiàng)A、B、C均為拓?fù)湫蛄小＝獯鸨绢愵}時(shí):建議讀者根

據(jù)邊集合畫出草圖。

32、用有向無環(huán)圖描述表達(dá)式(A+B)*((A+B)/A),至少需要頂點(diǎn)的數(shù)目為()。

A、5

B、6

C、8

D、9

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是有向無環(huán)圖的定義。有向無環(huán)圖是一個(gè)無環(huán)的有

向圖，可以用來表示公共子表達(dá)式，本題中出現(xiàn)的5個(gè)字符作為5個(gè)頂點(diǎn)，其中

A+B和A可共用，所以至少5個(gè)即可，選A。

33、鄰接多重表的存儲(chǔ)結(jié)構(gòu)和十字鏈表類似，也是由頂點(diǎn)表和邊表組成，每一條邊

用一個(gè)結(jié)點(diǎn)表示，其頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)和邊表結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：

頂點(diǎn)值域指針域

vertexfirstedge

⑻鄰接多重表頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)

標(biāo)記域頂點(diǎn)位置指針域頂點(diǎn)位置指針域邊上信息

markivexilinkjvexjiinkinfo

（b）鄰接多重表邊表結(jié)點(diǎn)結(jié)構(gòu)

關(guān)于圖中各個(gè)域的說明，不正確的是（）。

A、vertex存儲(chǔ)的是結(jié)點(diǎn)的數(shù)值域的內(nèi)容

B、fksledge域指示第一條依附于該頂點(diǎn)的邊

C、mark指向下一條依附于結(jié)點(diǎn)的邊

D、info為指向和邊相關(guān)的各種信息的指針域

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：頂點(diǎn)表由兩個(gè)域組成，veriex域存儲(chǔ)和該頂點(diǎn)相關(guān)的信息，firstedge

域指示第一條依附于該頂點(diǎn)的邊。邊表結(jié)點(diǎn)由六個(gè)域組成：mark為標(biāo)記域，用以

標(biāo)記該條邊是否被搜索過；ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置；ilink

指向下一條依附于頂點(diǎn)ivex的邊；jlink指向下一條依附于頂點(diǎn)jvex的邊：info為

指向和邊相關(guān)的各種信息的指針域。

34、以下關(guān)于十字鏈表的說法中，不正確的是（）。

A、十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B、行指針row為矩陣中的行位置，列指針col為矩陣中的列位置

C、數(shù)值val為矩陣中的值

D、right指針指向矩陣中的行位置，down指針指向矩陣中的列位置

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：righl指向右側(cè)的一個(gè)非零元素，down指向下側(cè)的一個(gè)非零元素。

二、綜合應(yīng)用題（本題共75題，每題7.0分，共75

分。）

35、證明：具有n個(gè)頂點(diǎn)和多于n—1條邊的無向連通圖G一定不是樹。

標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的定義。具有n個(gè)頂點(diǎn)n—1條邊的無向連通圖

是自由樹，即沒有確定艱結(jié)點(diǎn)的樹，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于。一1條，因

一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成

回路。形成回路的連通圖不再是樹（在圖論中樹定義為無回路的連通圖）。

知識(shí)點(diǎn)解析：暫無解析

36、證明：對(duì)有向圖的頂點(diǎn)適當(dāng)?shù)鼐幪?hào)，可使其鄰接矩陣為下三角形且主對(duì)角線為

全0的充要條件是該圖為無環(huán)圖。

標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是無環(huán)圖的定義。根據(jù)題意，該有向圖頂點(diǎn)編號(hào)的規(guī)

律是讓弧尾頂點(diǎn)的編號(hào)大于弧頭頂點(diǎn)的編號(hào)。由于不允許從某頂點(diǎn)發(fā)出并回到自身

頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角線元素均為0。先證明該命題的充分條件。由于弧

尾頂點(diǎn)的編號(hào)均大于弧頭頂點(diǎn)的編號(hào)，在鄰接矩陣中，非零元素自然是

落到下三角矩陣中；命題的必要條件是要使上三角為0,則不允許出現(xiàn)弧頭頂點(diǎn)編

號(hào)大于弧尾頂點(diǎn)編號(hào)的弧，否則，就必然存在環(huán)路。(對(duì)該類有向無環(huán)圖頂點(diǎn)編

號(hào)，應(yīng)按頂點(diǎn)出度順序編號(hào)。)

知識(shí)點(diǎn)解析：暫無解析

37、關(guān)于圖(Graph)的一些問題：(I)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?最

少有多少條邊？(2)表示有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)

矩陣元素?是否為稀疏矩陣？

標(biāo)準(zhǔn)答案：(l)n(n-l),n(2)l(A不一定是稀疏矩陣提示：此題考查的知識(shí)點(diǎn)是圖

的相關(guān)術(shù)語。(1)在有向圖G中，如果對(duì)于每一對(duì)V“vj,屬于V,必不等于巧，

從％到vj和從vj到增都存在路徑，則稱G是強(qiáng)連通圖。最多邊是所有的頂點(diǎn)每對(duì)

之間都有邊，邊數(shù)為n(n—1)；最少只有一個(gè)方向有邊，為n。(2)元素個(gè)數(shù)為矩

陣的大小，即106,稀疏矩陣的定義是非零個(gè)數(shù)遠(yuǎn)小于該矩陣元素個(gè)數(shù)，且分布無

規(guī)律，不一定稀疏。

知識(shí)點(diǎn)解析：暫無解析

38、如何對(duì)有向圖中的頂點(diǎn)號(hào)重新安排可使得該圖的鄰接矩陣中所有的1都集中到

對(duì)角線以上？

標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖頂點(diǎn)度數(shù)。可以按各頂點(diǎn)的出度進(jìn)行排序。n個(gè)

頂點(diǎn)的有向圖，其頂點(diǎn)最大出度是n-l,最小出度為0。這樣排序后，出度最大

的頂點(diǎn)編號(hào)為1,出度最小的頂點(diǎn)編號(hào)為n之后，進(jìn)行調(diào)整，即若存在弧，而頂點(diǎn)

j的出度大于頂點(diǎn)i的出度，則將j的編號(hào)排在頂點(diǎn)i的編號(hào)之前。

知識(shí)點(diǎn)解析：暫無解析

39、假定圖G=(V,E)是有向圖，V={1,2,N},N>1,G以鄰接矩陣方式存

儲(chǔ)，G的鄰接矩陣為A,即A是一個(gè)二維數(shù)組。如果i到j(luò)有邊，則A[i,j]=l,否

則A[i,j]=0。請(qǐng)給出一個(gè)算法思想，該算法能判斷G是否是非循環(huán)圖(即G中是否

存在回路)，要求算法的時(shí)間復(fù)雜性為0(/)。

標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。采用深度優(yōu)先遍歷算法，在執(zhí)行

DFS(v)時(shí)，若在退出DFS(v)前碰到某頂點(diǎn)u,其鄰接點(diǎn)是己經(jīng)訪問的頂點(diǎn)v,則說

明v的子孫u有到v的回邊，即說明有環(huán)；否則，無環(huán)。

知識(shí)點(diǎn)解析：暫無解析

40、對(duì)一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一

的因素有哪些？

標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。遍歷不唯?的因素有：開始遍歷的頂點(diǎn)

不同；存儲(chǔ)結(jié)構(gòu)不同；在鄰接表情況下鄰接點(diǎn)的順序不同。

知識(shí)點(diǎn)解析：暫無解析

41、G=（V,E）是一個(gè)帶有權(quán)的連通圖，如圖所示。（1）什么是G的最小生成樹?

（2）G如圖所示，請(qǐng)找出G的所有最小生成樹。

標(biāo)準(zhǔn)答案：（1）無向連通圖的生成樹包含圖中全部n個(gè)頂點(diǎn)，以及足以使圖連通的

n—1條邊。而最小生成樹則是各邊權(quán)值之和最小的生成樹。（2）最小生成樹有兩

棵。下面給出頂點(diǎn)集合和邊集合，編以三元組(Vi，Vj,W)形式，其中W代表權(quán)

值。V(G)={1,2,3,4,5)E1(G)={(4,5,2),(2,5,4),(2,3,5),(1,2,

7)}；E2(G)={(4,5,2),(2,4,4),(2,3,5),(1,2,7)}

知識(shí)點(diǎn)解析：暫無解析

42、對(duì)于如下的加權(quán)有向圖,給出算法Dijkstra產(chǎn)生的最短路徑的支撐樹，設(shè)頂點(diǎn)

A為源點(diǎn)，并寫出生成過程。

標(biāo)準(zhǔn)答案：頂點(diǎn)A到頂點(diǎn)B、C、D、E的最短路徑依次是3、18、38、43,按

Dijkstra所選頂點(diǎn)過程是B、C、D、E。支撐樹的邊集合為具體分析如

下表所示。

Dijkstra輯法的執(zhí)行過程

飾環(huán)SWD(2]D[3]D[4]i)[51

初態(tài)|A|-320X45

1IA.BIB3183843

2JA.B.CIC3183843

31A.B.C.DID3183843

4IA.B.C.D.EIE3183843

知識(shí)點(diǎn)解析：暫無解析

43、(I)對(duì)于有向無環(huán)圖，敘述2對(duì)于以下的圖，寫出它

17

的4個(gè)不同的拓?fù)溆行蛐蛄小?/p>

標(biāo)準(zhǔn)答案：(1)對(duì)有向圖，求拓?fù)湫蛄胁襟E為：①在有向圖中選一個(gè)沒有前驅(qū)(即入

度為零)的頂點(diǎn)并輸出。②在圖中刪除該頂點(diǎn)及所有以它為尾的弧。③重復(fù)①和

②步，直至全部頂點(diǎn)輸出，這時(shí)拓?fù)渑判蛲瓿桑环駝t，圖中存在環(huán)，拓?fù)渑判蚴?/p>

敗。(2)從入度為O的頂點(diǎn)開始，當(dāng)有多個(gè)頂點(diǎn)可以輸出時(shí)，將其按序從上往下排

列，這樣不會(huì)丟掉?種拓?fù)湫蛄小捻旤c(diǎn)1開始的可能的拓?fù)湫蛄袨?2345678、

12354678、13456278、13546278。提示：此題考杳的知識(shí)點(diǎn)是拓?fù)渑判颉?/p>

知識(shí)點(diǎn)解析：暫無解析

44、試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj

的路徑(訪)。(注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。)

標(biāo)準(zhǔn)答案：算法1：intvisited[]=O：//全局變量，訪問數(shù)組初始化int

dfs(AdjListg,vi){//以鄰接表存儲(chǔ)的有向圖g,判斷vi到vj是否有通路,返回

10visited(vi]=l；//visited是訪問數(shù)組，設(shè)頂點(diǎn)的信息就是頂點(diǎn)編號(hào)

P=g[vi].firstare；//第一個(gè)鄰接點(diǎn)while(P!=nuH){j=p—>adjvex；

if(vj==j){flag=l；return(l)；}//vi和vj有通路if(visited[j]==O)dfs(g,j)；P=P

一〉next：)//whileif(!flag)return(O)；}算法2：輸出vi到vj的路徑,其思想是

用一個(gè)棧存放遍歷的頂點(diǎn)，遇到頂點(diǎn)vj時(shí)輸出路徑。voiddfs(AdjListg,inti){/

/頂點(diǎn)vi和頂點(diǎn)vj間是否有路徑，如有,則輸出inllop=0,stack[]；//stack是

存放頂點(diǎn)編號(hào)的棧visiled[i]=l；//visited數(shù)組在進(jìn)入dfs前已初始化

stack[++top]=i；P=g[i].firstarc；//求第一個(gè)鄰接點(diǎn)while(P){if(p

—>adjvex==j){stack[++top]=j；printf("頂點(diǎn)vi和vj的路徑為：\n")；for(i=1；

i<=top；i++)printf(''%4d'',stack|i|)；exit(O)：)elseif(visited|p

_*>adjvex]==0){dfs(g,g一>adjvex)；top-----；P=p->next；}}}算法3：非遞歸

算法親解。intJudge(AdjListg,inti,j){//判斷n個(gè)頂點(diǎn)以鄰接表示的有向圖g

中，頂點(diǎn)vi各vj是否有路徑，//有則返回1,否則返回0。for(i=l；i<=n；

i++)visited[i]=Oi//訪問標(biāo)記數(shù)組初始化intstack。，top=0；stack[++top]=vi；

while(top>0){k=stack[top-----]；P=g[k].firstarc；while(P!=null&&visited[p

->adjvexl==l)p=p—>next；//查第k個(gè)鏈表中第一個(gè)未訪問的弧結(jié)點(diǎn)

if(P==null)top-----：else{i=p->adjvex；if(i==j)return(l)；//頂點(diǎn)vi和vj訶有

路徑else{visited[i]=l；stack[++top]=i；)})whilereturn(O)；}//頂點(diǎn)vi和vj間

無通路

知識(shí)點(diǎn)解析：暫無解析

45、假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在

一個(gè)簡單有向回路，若存在，則以頂點(diǎn)序列的方式輸出該回路(找到一條即可)。(注

意：圖中不存在頂點(diǎn)到自己的弧)

標(biāo)準(zhǔn)答案：用鄰接矩陣存儲(chǔ)時(shí)，可用以卜方法實(shí)現(xiàn)：voidPrint(intv,intstart)[/

/輸出從頂點(diǎn)start開始的回路for(i：1；iv=n：i++)

if(g[v][i]!=0&&visited[i]==1){//若存在邊(v,i),且頂點(diǎn)i的狀態(tài)為1printf("％

d.t,V)；iRi==start)printfV'\rT)：elsePrint(i,start)：break；}//if)//Print

voiddfs(intv){visited[v]=i；for(j=l；j<=n；j++)if(g[v][j]!=O)//存在邊(v,j)

if(visited[j]!=1){if(!visited[j])dfs(j)；)//ifclsc{cycle=l；Print。，j)：}

visited|v]=2：}voidfind_cycle(){//判斷是否有回路，有則輸出鄰妻矩陣。

visited數(shù)組為全局變量for(i=l；i<=n；i++)visited[i：=O；for(i=l；i<=n；

i++)if(!visited[i])dfs(i)：}

知識(shí)點(diǎn)解析：暫無解析

46、己有鄰接表表示的有向圖，請(qǐng)編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡單路

徑，若有則打印出該路徑上的頂點(diǎn)。

標(biāo)準(zhǔn)答案:voidAllpath(AdjListg,vertypeU,verlypev){//求有向圖g中頂點(diǎn)u

到頂點(diǎn)v的所有簡$.路徑，初始調(diào)用形莪inttop=0,S[]：S[++top]=u；

visited!U1=1；while(top>0||P){P=g|S[top|].firstarc；//君一個(gè)鄰接點(diǎn)while(P

f=null&&visited[p->adjvex]==1)P=p->next；//下一個(gè)訪問鄰接點(diǎn)表

if(P==null)top—：//退棧else{i=p—>adjvex;//取鄰接點(diǎn)(編號(hào))if(i==V){//

找到從u到v的一條簡單路徑，輸出for(k=l；k<=top；k++)printf("％3d”，s[k])：

printf(tt%3d\n'\v)：)//ifelse{visited[i]=l；s[4-+top]=i；)//else深度優(yōu)先遍

歷}//else)//while}

知識(shí)點(diǎn)解析：暫無解析

47、“破圈法”是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有

圈為止.造給出用“破圈法”求解給定的帶權(quán)連通無句圖的一棵最小代價(jià)生成樹的詳

細(xì)算法，并用程序?qū)崿F(xiàn)彌所給出的算法。(注意：圈就是回路)

標(biāo)準(zhǔn)答案：voidSpnTree(AdjListg){//用“破圈法”求解帶權(quán)連通無向圖的一棵最

小代價(jià)生成樹typedefstruct{inti,j,w：(node：//設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，

權(quán)是整數(shù)nodeedge[]；scanf("％d%d"，&e,&n)；//輸入邊數(shù)和項(xiàng)點(diǎn)數(shù)

for(i=l；i<=e；i++)//輸入e條邊：頂點(diǎn)，權(quán)值seanf("%d%d%d"，

&edge[i].i,&edge[i].j,&edge[i].W)：for(i=2；i<=e；i++){//按邊上的權(quán)

值大小，對(duì)邊進(jìn)行逆序排序edge[O]=edge[i]；j=i—1；while(edge|j].W=n){//

破圈，直到邊數(shù)e=n一1if(connect(k))//刪除第k條邊若仍連通f

edgefkl.W=0；eg-；)//測試下一條邊edge[k],權(quán)值置0表示該邊被刪除

k++；//下條邊}//while}connect。是測試圖是否連通的函數(shù)，可用DFS函數(shù)

或BFS函數(shù)實(shí)現(xiàn)，若是連通圖，一次進(jìn)入DFS函數(shù)或BFS函數(shù)就可遍歷完全部頂

點(diǎn)，否則，因?yàn)閯h除該邊而使原連通圖成為兩個(gè)連通分量時(shí)，該邊不應(yīng)刪除。“破

圈”結(jié)束后，可輸出edge中W不為0的n—I條邊。

知識(shí)點(diǎn)解析：暫無解析

48、設(shè)計(jì)一個(gè)算法求圖的中心點(diǎn)。設(shè)v是有向圖G的一個(gè)頂點(diǎn)，把v的偏心度定

義為：MAx(從co到v的最短距離{①屬J'V(G)}如果v是有向圖G中具有最小偏

心度的頂點(diǎn)，則稱頂點(diǎn)v是G的中心點(diǎn)。

標(biāo)準(zhǔn)答案：設(shè)C是有向圖G的鄰接矩陣，求最小偏心度的頂點(diǎn)的步驟如卜.：(1)利

用Floyd算法求出每對(duì)頂點(diǎn)之間的最短路徑矩陣A；(2)對(duì)矩陣A求出每列i的最

大值，得到頂點(diǎn)i的偏心度；(3)在這n個(gè)頂點(diǎn)的偏心度中，求出最小偏心度的頂

點(diǎn)k,即為圖G的中心點(diǎn)。對(duì)應(yīng)的算法如下：iniCenier(MGraph&G)}ini

A[MAXV][MAXV],B[MAXV]；inti,j,k,m；for(i=0；i

知識(shí)點(diǎn)解析：暫無解析

49、對(duì)于一個(gè)使用鄰接表存儲(chǔ)的有向圖G,可以利用深度優(yōu)先遍歷方法，對(duì)該圖中

結(jié)點(diǎn)進(jìn)行拓?fù)渑判颉Ｆ浠舅枷胧牵涸诒闅v過程中，每訪問一個(gè)頂點(diǎn)，就將其鄰接

到的頂點(diǎn)的入度減1,并對(duì)其未訪問的、入度為0的鄰接到的頂點(diǎn)進(jìn)行遞歸。(1)

給出完成上述功能的圖的鄰接表定義。(2)定義在算法中使用的全局輔助數(shù)組。(3)

寫出在遍歷圖的同時(shí)進(jìn)行拓?fù)渑判虻乃惴ā?/p>

標(biāo)準(zhǔn)答案：(1)鄰接表定義typcdcfstructArcNodc{intadjvex;struct

ArcNode*next；[ArcNode；typedefstructVNode{vertypedata；

ArcNode*firstarc：)VNode,AdjList[MAX]；(2)全局?jǐn)?shù)組定義intvisited口=0：

finished[尸0；flag=1；//flag測試拓?fù)渑判蚴欠癯晒rcNode*final=null：//

final是指向頂點(diǎn)鏈表的指針,初始化為0(3)算法voiddfs(AdjListg,vertypeV){/

/以頂點(diǎn)v開始深度優(yōu)先遍歷有向圖g,頂點(diǎn)信息就是頂點(diǎn)編號(hào)ArcNode"：//

指向邊結(jié)點(diǎn)的臨時(shí)變量printf("％d"，V)；visited[v|=l；P=g[v].firstarc；

while(P!=null){j=p—^>adjvex；if(visited[j]==l&&finished[j]==O)flag=O；//dfs結(jié)

束前出現(xiàn)回邊elseif(visited[j]==O){dfs(g,j)；finished[j]=l：|P=P->next：|//

whilet=(ArcNode*)malloc(sizeof(ArcNode))；//申請(qǐng)邊結(jié)點(diǎn)t—>adjvex=v：t

一,next=final；final=t；//將該頂點(diǎn)插入鏈表)//dfs結(jié)束int

dfs_Topsort(Adjlistg){//對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖進(jìn)行拓?fù)渑判颍負(fù)涑?/p>

功返回1,否則返回0i=l；whilc(flag&&i<=n)if(visitcd.[i]==0){dfs(g,i)；

finished[i]=l；)//ifreturn(flag)；)

知識(shí)點(diǎn)解析：暫無解析

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合(數(shù)據(jù)結(jié)構(gòu))模擬

試卷第2套

一、單選題(本題共22題，每題1.0分，共22分。)

1、在下面關(guān)于樹的相關(guān)概念的敘述中，正確的是()。

A、只有一個(gè)結(jié)點(diǎn)的二叉樹的度為1

B、二叉樹的度一定為2

C、二叉樹的左右子樹可任意交換

D、深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：只有一個(gè)結(jié)點(diǎn)的二叉樹的度為零。二叉樹的度可以為0、I、2：二叉

樹的左右子樹不能任意交換。

2、已知一算術(shù)表達(dá)式的中綴形式為A+B*C?D/E,后綴形式為ABC*+DE/—，

其前綴形式為()。

A、-A+B*C/DE

B、一A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：根據(jù)題目給出的中綴和后綴表達(dá)式可以得到其算術(shù)表達(dá)式為：

(A+B*C)—D/E,前綴表達(dá)式：-+A*BC/DE。

3、算術(shù)表達(dá)式a+b*(c+d/e)轉(zhuǎn)為后綴表達(dá)式后為()。

A、ab+cde/*

B、abcde/+*+

C、abcde/*++

D、abcde*/++

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：根據(jù)表達(dá)式a+b*(c+d/e)可知其后綴表達(dá)式為abcde/+*+。

4、某二叉樹的先序遍歷序列為IJKLMNO,中序遍歷序列為JLKINMO,則后序遍

歷序列是()。

A、JLKMNOI

B、LKNJOMI

C、LKJNOMI

D、LKNOJMI

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：由先序和中序遍歷序列確定一棵二叉樹，再給出這棵二叉樹的后序遍

由此圖可以確認(rèn)后序遍歷的序列為

5、設(shè)森林F對(duì)應(yīng)的二叉樹為B,它有m個(gè)結(jié)點(diǎn)，B的根為P,P的右子樹結(jié)點(diǎn)個(gè)

數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是()。

A、m-n

B、m-n-l

C、n+l

D、條件不足，無法確定

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：F對(duì)應(yīng)的二叉樹共有m個(gè)結(jié)點(diǎn)，右子樹上n個(gè)，左子樹上有(m-n

-1)個(gè)，第一株樹包括根和左子樹，共(m—n)個(gè)。

6、二叉樹若用順序方法存儲(chǔ)，則下列四種算法中運(yùn)算時(shí)間復(fù)雜度最小的是()。

A、先序遍歷二叉樹

B、判斷兩個(gè)指定位置的結(jié)點(diǎn)是否在同一層上

C、層次遍歷二叉樹

D、根據(jù)結(jié)點(diǎn)的值查找其存儲(chǔ)位置

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：選項(xiàng)A、C、D運(yùn)算的時(shí)間復(fù)雜度都是0(n),而選項(xiàng)B的運(yùn)算的時(shí)間

復(fù)雜度為0(1),因?yàn)閷?duì)于指定位置p和q的兩個(gè)結(jié)點(diǎn)，判斷是否在同一層上，只

需判斷兩者[Iog2p]=[log2q]是否成立。

7、設(shè)某二叉樹中只有度為0和度為2的結(jié)點(diǎn)，如果此二叉樹的高度為100,那么

此二叉樹中所包含的結(jié)點(diǎn)數(shù)最少為()。

A、188

B、200

C、199

D、201

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：除根結(jié)點(diǎn)層只有1個(gè)結(jié)點(diǎn)外，其他各層均有兩個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)總數(shù)

=2x(100—1)+1=199。

8、樹是結(jié)點(diǎn)的有限集合，一棵樹中有()根結(jié)點(diǎn)。

A、有。個(gè)或1個(gè)

B、有。個(gè)或多個(gè)

C、有且只有一個(gè)

D、有1個(gè)或1個(gè)以上

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：根據(jù)樹的基本定義可知，每個(gè)樹只能有且只有一個(gè)根結(jié)點(diǎn)。

9、下列二叉排序樹中，滿足平衡二叉樹定義的是()。

A、

B、

C、

D、

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：考查平衡二叉樹的定義。根據(jù)平衡二叉樹的定義有，任意結(jié)點(diǎn)的左右

子樹高度差的絕對(duì)值不超過lo而其余三個(gè)選項(xiàng)均可以找到不符合的結(jié)點(diǎn)。

10、把樹的根結(jié)點(diǎn)的層數(shù)定義為1,其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上

I。設(shè)T是一棵二又樹，Ki和Kj是T中子結(jié)點(diǎn)數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們

所在的層數(shù)分別為大代和入0,當(dāng)關(guān)系式％Ki—入Kjgl一定成立時(shí)，則稱T為一棵

()。

A、滿二義樹

B、二叉查找樹

C、平衡二義樹

D、完全二叉樹

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：此題干的敘述符合平衡二義樹的定義。

11、設(shè)森林F中有三棵對(duì)，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為Mi、M2和

M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是()。

A、Mi

B、M1+M2

C、M3

D、M2+M3

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，第一棵樹的根結(jié)點(diǎn)作為此二叉樹的根結(jié)

點(diǎn)，第一棵樹除根結(jié)點(diǎn)外其他結(jié)點(diǎn)時(shí)此二叉樹的左子樹。二叉樹的右子樹為第二棵

樹和第二棵樹構(gòu)成的，因此結(jié)點(diǎn)數(shù)為M2+M3。

12、若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)

個(gè)數(shù)是（）。

A、10

B、11

C、16

D、不確定

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)可知，度為。的結(jié)點(diǎn)個(gè)數(shù)比度為2結(jié)點(diǎn)個(gè)數(shù)多一

個(gè),即110=02+1o

13、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（）個(gè)度為2的結(jié)點(diǎn)。

A、8

B、9

C、10

D、11

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)no=n2+1,可知度為2的結(jié)點(diǎn)個(gè)數(shù)為9。

14、在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為

1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為O的結(jié)點(diǎn)數(shù)為（）個(gè)。

A、4

B、5

C、6

D、7

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：一棵度為3的樹，總結(jié)點(diǎn)數(shù)n=n（）+n]+n2+n3，而總分支總數(shù)為

noxO+n1x2+n2X1+nsx2,由于分支總數(shù)加1為結(jié)點(diǎn)總數(shù)，可得出n（）=6o

15、已知一棵二叉樹，共有n個(gè)結(jié)點(diǎn)，那么此二叉樹的高度為（）。

A、nlog2n

B、log2n

C>[log2n]+l

D、不確定

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：已知一棵二叉樹共有n個(gè)結(jié)點(diǎn)，但二叉樹的形式?jīng)]有給出，因此，二

叉樹的高度不能確定。

16、已知一棵二叉樹，第m層上最多含有結(jié)點(diǎn)數(shù)為（）。

A、2m

B、2m-1-1

C、2md

D、2m-l

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，二叉樹的第m層上最多有2m"。

17、有關(guān)二叉樹下列說法正確的是（）。

A、二叉樹就是度為2的樹

B、一棵二叉樹的度可以小于2

C、二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2

D、二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題考查二義樹的概念。

18、一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（）。

A、CABDEFG

B、ABCDEFG

C、DACEFBG

D、BAECFDG

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：由題可得A為根結(jié)點(diǎn)，并且B為A的孩子結(jié)點(diǎn)。選項(xiàng)A,C應(yīng)為A

的左孩子，其前序序列應(yīng)為AC……o選項(xiàng)B,當(dāng)B為A的右孩子，C為B的右孩

子時(shí)，滿足題目要求。選項(xiàng)C,類似選項(xiàng)A,其前序序列應(yīng)為AD……o選項(xiàng)D,

B為A的左孩子，C為A的右子樹的根，E為C的左子樹，F(xiàn)DG為C的右子樹，

其前序序列應(yīng)為ABEC……o

19、已知一個(gè)二叉樹有1025個(gè)結(jié)點(diǎn)，那么由此推斷二叉樹的高h(yuǎn)為（）。

A、11

B、10

C、11?1025

D、10—1024

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：右完全二叉樹中1025>27即最少需要11層，最多需要有1025

層。

20、一棵完全二叉樹，共有n個(gè)結(jié)點(diǎn)，那么，其葉結(jié)點(diǎn)數(shù)共有（）個(gè)。

A、n/2

B、n

C、（n-l）/2

D、(n+l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：此問題可以利用二叉樹及完全二叉樹的性質(zhì)來求解。設(shè)i、j、k分別

為度為0、I、2的結(jié)點(diǎn)數(shù)目，則n=i+j+k。根據(jù)二叉樹的性質(zhì)有i=k+l,即k=i一

1,代入上式，得n=2i+j—1,即i=(n-j+l)/2。由于完全二又樹中最多只有一個(gè)度

為1的結(jié)點(diǎn)，同時(shí)考慮到i為整數(shù)，(1)當(dāng)j=0時(shí)，比時(shí)n=i+k=2k+l為奇數(shù)，則

i=(n+l)/2；(2)當(dāng)j=l時(shí),此時(shí)n=i+k+l=2k+2為偶數(shù)，則i=(n+l)/2向下取整。

所以選D。

21、()的遍歷仍需要棧的支持。

A、前序線索樹

B、中序線索樹

C、后序線索樹

D、中序線索樹和前序線索樹

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：由于后序遍歷先訪問子樹后訪問根結(jié)點(diǎn)，從本質(zhì)上要求運(yùn)行棧中存放

祖先的信息，即使對(duì)二叉樹進(jìn)行后序線索化，仍然不能脫離棧的支持對(duì)此二叉樹進(jìn)

行遍歷。

22、已知一棵二叉樹高度為h,在此二叉樹中只有度為0和度為2的結(jié)點(diǎn)，那么這

棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少為()。

A、2h

B、2h-I

C、2h+l

D、h+1

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：暫無解析

二、綜合應(yīng)用題(本題共7題，每題1.0分，共7分。)

23、已知一個(gè)二叉樹，用二叉鏈表形式存儲(chǔ)，給出此二叉樹建立過程算法(可不描

述結(jié)構(gòu)體)。

標(biāo)準(zhǔn)答案：二叉樹是遞歸定義的，以遞歸方式建立最簡單。二叉樹建立過程如下：

BiTreeCreat(){//建立二叉樹的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu)ElemTypex：BiTree

bt；scanf(',%d,\&x)；//本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0)bt=null；else

if(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt—>data=x：bt->lchild=Creat()；

bt>ichild-Creat():}elseerror("輸入錯(cuò)誤");ieturn(bt)；)//結(jié)束BiTree

知識(shí)點(diǎn)解析：暫無解析

24、判別給定的二叉樹是否是完全二叉樹，并給出設(shè)計(jì)的算法(可不描述結(jié)構(gòu)體)。

標(biāo)準(zhǔn)答案：判斷此二又樹是否為完全二叉樹的算法設(shè)計(jì)如下：im

JudgeComplete(BiTreebt){//判斷二叉樹是否是完全二叉樹，如是，返回1；否

則，返回0intOg=0；BiTreeP=bt,Q[]：//Q是隊(duì)列,元素是二叉樹結(jié)點(diǎn)指

針，容量足夠大if(P=null)return1：Queuelnit(Q)；Queueln(Q,P)；//初始化

隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while(!QueueEmpty(Q)){P=QueueOul(Q)：//出隊(duì)if(p

->lchild&&!tag)QueueIn(Q,P->lchild)；//左孩子入隊(duì)else{if(P

—>lehild)retum0：//前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空elsetag=l；//首次出

現(xiàn)結(jié)點(diǎn)為空if(p—>rchild&&!tag)Queueln(Q,P—>rchild)；//右孩子入隊(duì)else

if(p->rchild)return0；elsetag=1：))//whilereturn1；)//JudgcComplctc

知識(shí)點(diǎn)解析：暫無解析

25、以孩子一兄弟表示法存儲(chǔ)的森林的葉子結(jié)點(diǎn)數(shù)(要求描述結(jié)構(gòu))。

標(biāo)準(zhǔn)答案：當(dāng)森林(樹)以孩子兄弟表示法存儲(chǔ)時(shí)\若結(jié)點(diǎn)沒有孩子(fch=null),則它

必是葉子，總的葉子結(jié)點(diǎn)個(gè)數(shù)是孩子子樹(fch)上的葉子數(shù)和兄弟(nsib)子樹上葉結(jié)

點(diǎn)個(gè)數(shù)之和。typedefstructnode{elemTypedata；//數(shù)據(jù)域structnode*fch,

*nsib；//孩子與兄弟域}*Tree；intLcaves(Trcct){//計(jì)算以孩子一兄弟表示

法存儲(chǔ)的森林的葉子數(shù)if⑴if(t一,fch=：null)//若結(jié)點(diǎn)無孩子，則該結(jié)點(diǎn)必是

葉子return(1+Leaves(t->nsib))；//返回葉子結(jié)點(diǎn)和其兄弟子樹中的葉子結(jié)點(diǎn)數(shù)

elsercturn(Lcaves(t->fch)+Lcaves(t->nsib))；//孩了?子樹和兄弟子樹中口I子數(shù)之

和}

知識(shí)點(diǎn)解析：暫無解析

26、已知一棵二叉樹的前序序列為：A,B,D,G,J,E,H,C,F,I,K,L；

中序序列為：D,J,G,B,E,H,A,C,K,I,L,F。(1)寫出該二又樹的后序

序列。(2)畫出該二叉樹。(3)求該二叉樹的高度以及該二叉樹中度為2、1、0的結(jié)

點(diǎn)個(gè)數(shù)。

標(biāo)準(zhǔn)答案：此題只需從前序序列、中序序列得到唯一確定的二叉樹即可。(1)J,

G,D.H,E,R,K,L,I,F.C.A?(2)二叉樹的形式如下圖所示：

(3)高度是5,度為0的結(jié)點(diǎn)個(gè)數(shù)為4,度為1的結(jié)

點(diǎn)個(gè)數(shù)為5,度為2的結(jié)點(diǎn)個(gè)數(shù)為3。

知識(shí)點(diǎn)解析：暫無解析

27、有n個(gè)結(jié)點(diǎn)的二叉樹，已知葉結(jié)點(diǎn)個(gè)數(shù)為no。（1）寫出求度為1的結(jié)點(diǎn)的個(gè)數(shù)

的山的計(jì)算公式。（2）若此樹是深度為k的完全二叉樹，寫出n為最小的公式。

（3）若二叉樹中僅有度為0和度為2的結(jié)點(diǎn)，寫出求該二叉樹結(jié)點(diǎn)個(gè)數(shù)n的公式。

標(biāo)準(zhǔn)答案：（1）設(shè)度為2的結(jié)點(diǎn)個(gè)數(shù)為止,?n=n0+ni+n2o由二叉樹的性質(zhì)

no=n2+Ln=2no+nj—1,所以度為1的結(jié)點(diǎn)的個(gè)數(shù)〃=n+l—2no;（2）當(dāng)樹是深度

為k的完全二叉樹時(shí)，n的最小值min（n）=2k/。（3）當(dāng)二叉樹中只有度為0和度為2

的結(jié)點(diǎn)時(shí)，n=2n（）—1（其中n為樹中的總結(jié)點(diǎn)數(shù)，頊為度為0的結(jié)點(diǎn)數(shù)目）。

知識(shí)點(diǎn)解析：暫無解析

28、已知一棵樹的結(jié)點(diǎn)表示如下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，畫出對(duì)應(yīng)的二叉

二叉樹的轉(zhuǎn)換規(guī)則如下：（I）樹的根結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)；（2）每個(gè)結(jié)點(diǎn)的第一個(gè)

子結(jié)點(diǎn)（最左的子樹）作為該結(jié)點(diǎn)的左孩子：（3）每個(gè)結(jié)點(diǎn)的右孩子為在樹中與該結(jié)

點(diǎn)的左孩子鄰近的兄弟，所有具有兄弟關(guān)系的結(jié)點(diǎn)用指針鏈接起來。轉(zhuǎn)換成二叉

29、在一棵表示有序集S的二叉搜索樹(binarysearchtree)中，任意一條從根到葉結(jié)

點(diǎn)的路徑將S分為3部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合Si；在該路徑

上的結(jié)點(diǎn)中的元素組成的集合S2;在該路徑右邊結(jié)點(diǎn)中的元素組成的集合S3。

S=S]US2US3o若對(duì)于任意的a6Si，beS2?cESs>是否總有aSbWc?為什么?

標(biāo)準(zhǔn)答案：不是。如下圖所示的二叉搜索樹:

取從4到12的路徑，則S尸{1,2,3,7),S2={4,8,10,12},S3為空集，取Si

中的元素7和S2中的元素4,令a=7,b=4,有a>b。則上述命題不成立。

知識(shí)點(diǎn)解析：暫無解析

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合(數(shù)據(jù)結(jié)構(gòu))模擬

試卷第3套

一、單選題(本題共24題，每題1.0分，共24分。)

1、若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查

找法查找一個(gè)記錄，其平均查找長度ASL為().

A、(n—1)/2

B、n/2

C、(n+l)/2

D、n

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是順序查找長度ASL的計(jì)算。假設(shè)表長度為n,

那么查找第i個(gè)數(shù)據(jù)元素需進(jìn)行n—i+l次比較，即G=n—i+l。又假設(shè)查找每個(gè)數(shù)

據(jù)元素的概率相等，即Pi=l/n,則順序查找算法的平均查找長度為：

ASL=VP,Ct=—YC,=~Y(n-i+I)=--(n1)

父「田nG2所以應(yīng)選C。

順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表，平均比較次數(shù)為((1)),二

分法查找只適用于查找順序存儲(chǔ)的有序表，平均比較次數(shù)為((2))。在此假定N為

線性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。

2、(1)

A、N+1

B、21og2N

C、logzN

D、N/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：暫無解析

3、(2)

A、N+1

B、210g2N

C、log2N

D、N/2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是各類查找算法的比較次數(shù)計(jì)算。順序查找法用所

給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗，其ASL=(n+l)/

2,即查找成功時(shí)的平均比較次數(shù)約為表長的一半。二分法查找過程可用一個(gè)稱為

判定樹的二義樹描述，由于判定樹的葉子結(jié)點(diǎn)所在層次之差最多為1,故n個(gè)結(jié)點(diǎn)

的判定樹的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相等，均為[log2n]+l。這樣，折半

查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過Uog2n]+1,所以，(1)應(yīng)選擇D,(2)應(yīng)選

Co

4、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為()。

A、鏈接方式存儲(chǔ)，元素?zé)o序

B、