數(shù)據(jù)結(jié)構(gòu)試題2022(B卷)答案

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦數(shù)據(jù)結(jié)構(gòu)試題2022(B卷)答案一、填空題（每空1分，共15分）

1.數(shù)據(jù)的規(guī)律結(jié)構(gòu)有四種基本形態(tài)，分離是集合、_線性結(jié)構(gòu)_、_樹型結(jié)構(gòu)_和

圖狀結(jié)構(gòu)_。

2.一個(gè)算法的效率可分為_時(shí)光_效率和_空間_效率。

3.在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有前趨_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且惟獨(dú)_一_個(gè)

前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有_后繼_結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有_多_個(gè)。

4.要從一個(gè)挨次表刪除一個(gè)元素時(shí)，被刪除元素之后的全部元素均需前移一個(gè)

位置，移動(dòng)過(guò)程是從_前_向_后_依次移動(dòng)每一個(gè)元素。

5.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過(guò)push,push,pop,push,pop,

push,push后，輸出序列是_2，3_。

6.已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head((tail(A))=_(d,e,f)_。

7.對(duì)于一個(gè)有10個(gè)結(jié)點(diǎn)的二叉樹，最小可能高度為_4_，最大可能高度為_10_。

二、挑選題（每題2分，共30分）

1.C

2.A

3.B

4.A

5.A

6.D

7.C

8.D

9.D10.C11.A12.B

13.B14.D15.D

三、推斷題（每題1分，共10分）

1.√

2.×

3.×

4.×

5.×

6.√

7.√

8.√

9.×10.×

四、簡(jiǎn)答題（共15分）

1．簡(jiǎn)述什么是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)？簡(jiǎn)述存儲(chǔ)結(jié)構(gòu)的兩種不同的存儲(chǔ)方式？（6分）答：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的規(guī)律結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式，又稱物理機(jī)構(gòu)。（2分）

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有挨次和鏈?zhǔn)絻煞N不同的方式。挨次存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是要借助數(shù)據(jù)元素在存儲(chǔ)器中的相應(yīng)位置來(lái)體現(xiàn)數(shù)據(jù)元素互相間的規(guī)律關(guān)系；（2分）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)則通過(guò)表示數(shù)據(jù)元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素之間的規(guī)律關(guān)系。（2分）

2．比較對(duì)普通線性表、棧和隊(duì)列三種結(jié)構(gòu)數(shù)據(jù)舉行操作的不同之處？（9分）答：普通線性表可在表的隨意位置舉行插入和刪除操作；（3分）

棧限定僅在表的一端舉行插入或刪除操作，棧的修改是按“后進(jìn)先出”的原則舉行的；（3分）

隊(duì)列限定只能在表的一端舉行插入，在表的另一端舉行刪除，是一種“先進(jìn)先出”的線性表。（3分）

五、分析題（共30分）

1．寫出下列樹的先序、中序、后序遍歷序列。（9分）

答：先序序列：A-B-D-G-H-C-E-F（3分）

中序序列：B-G-D-H-A-E-C-F（3分）

后序序列：G-H-D-B-E-F-C-A（3分）

2.已知一棵樹邊的集合為{，，，，，，，，，，}，請(qǐng)畫出這棵樹，并回答下列問(wèn)題：（12分）

（1）哪個(gè)是根結(jié)點(diǎn)？a(1分)

（2）哪些是葉子結(jié)點(diǎn)？ljkfid(1分)

（3）哪個(gè)是結(jié)點(diǎn)k的雙親？g(1分)

（4）哪些是結(jié)點(diǎn)f的祖先？ac(1分)

（5）哪些是結(jié)點(diǎn)g的孩子？jk(1分)

（6）哪些是結(jié)點(diǎn)h的兄弟？gf(1分)

（7）結(jié)點(diǎn)c的度是多少？3(1分)

（8）結(jié)點(diǎn)d的層次號(hào)是多少？3(1分)

（9）囫圇樹的深度是多少？4(1分)

（10）以結(jié)點(diǎn)b為根的子樹深度是多少？3(1分)

(2分)

3．畫出下圖的帶權(quán)鄰接矩陣，并求出從V0到V5的最短路徑(寫出該路徑所

經(jīng)過(guò)的頂點(diǎn)序列以及權(quán)值之和)。(9分)

∞

∞

∞

∞

∞

答：帶權(quán)鄰接矩陣如下：????????????????????∞∞∞∞

∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞

∞∞∞

∞∞6020

1050

51003010（3