ZH計(jì)0520九州0520

《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)

一、填空題：

1、空串的長(zhǎng)度是。，空格串的長(zhǎng)度是串中包含的容格的個(gè)數(shù)。

2、隊(duì)列是一種先進(jìn)先出表,在隊(duì)列中允許插入的一端稱(chēng)隊(duì)尾,允許刪除的另一端稱(chēng)隊(duì)頭。

3、兩串相等是指兩個(gè)字符串的長(zhǎng)度相等，且各對(duì)應(yīng)位置上的字符相等。

4、組成數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)。

5、線性結(jié)構(gòu)中元素之間存在一對(duì)一的關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多的關(guān)系,圖形

結(jié)構(gòu)中元素之間存在多對(duì)多的關(guān)系。

6、向棧中壓入元素的操作是：先移動(dòng)棧頂指針，后存入元素。

7、棧的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，其特點(diǎn)是后進(jìn)先出,先進(jìn)后出,棧中允許插入和刪除的一端

稱(chēng)棧頂。

8、在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn),另一個(gè)指向后繼結(jié)點(diǎn)。

9、數(shù)據(jù)結(jié)構(gòu)通常包括四種基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)、線性表

10、線性表(ai.a2…an)k,ai稱(chēng)表頭元素,an稱(chēng)表尾元素,線性表有兩種存儲(chǔ)結(jié)構(gòu)：順

序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

11、在一個(gè)順序存儲(chǔ)的線性表中，第1個(gè)元素的地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)

元素的地址是108。

12、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有L個(gè)前驅(qū)結(jié)點(diǎn)；最后

一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有L個(gè)后續(xù)結(jié)點(diǎn)。

二、選擇題

1、具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有A條邊才能確保是一個(gè)連通圖。

A、dB.cC.bD.e

2、在初始狀態(tài)為空的堆棧中依次插入元素f,e,d,c,a,b后，連續(xù)進(jìn)行了三次刪除操作，則此時(shí)的

棧頂元素是D

A、5B、6C、7D、8

3、后序遍歷的順序是D

A、根結(jié)點(diǎn)，左子樹(shù)，右子樹(shù)B、左子樹(shù)，根結(jié)點(diǎn)，右子樹(shù)

C、右子樹(shù)，根結(jié)點(diǎn)，左子樹(shù)D、左子樹(shù)，右子樹(shù)，根結(jié)點(diǎn)

4、設(shè)結(jié)點(diǎn)X有左孩子結(jié)點(diǎn)Y,右孩子結(jié)點(diǎn)Z,用三種基本遍歷方法得到的遍歷序列中X(B)

是Y的前驅(qū)，X(B)是Z的后繼,Y(A)是Z的前驅(qū)。

A、一定，B、不一定C、一定不

5、串是指B

A、少于一個(gè)字母的序列B、有限個(gè)字符的序列C、不少于一個(gè)字符的序列D、任意

個(gè)字母的序列

6、一個(gè)棧的輸入序列為1,2,3,4,則下列序列中不可能是棧的輸出序列的是C

A、2,3,4,1,5B、2,3,1,4,5C、5,4,1,2,3D、1,5,4,3,2

7、如果結(jié)點(diǎn)A有3個(gè)兄弟，且B是A的雙親，則B的度是A

A、4B、5C、1D、3

8、通常對(duì)數(shù)組進(jìn)行的兩種基本操作是C

A、插入和刪除B、索引和修改C、查找和修改D、刪除和修改

9、一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是B

A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1

10、計(jì)算機(jī)算法必須具備輸入、輸出和B等五個(gè)基本特性

A、可行性、可移植性、和可擴(kuò)充性B、可行性、確定性和可窮性C、確定性、可窮必和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

11、樹(shù)最適合用來(lái)表示C

A、有序數(shù)據(jù)元素B、無(wú)序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無(wú)聯(lián)系

的數(shù)據(jù)

12、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比

較，將其放入已排序的正確位置上的方法，稱(chēng)為：（8_

A、希爾排序B、起泡排序C、插入排序D、選擇排序

13、N個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（A）條邊

A、NB、N+lC、N-lD、N（N-1）

14、棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（A）

A、順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)B、散列方式和索引方式C、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D、線性存

儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)

15、深度為4的二叉樹(shù)至多有（D）個(gè)結(jié)點(diǎn)

A、8B、16C、7D、15

16、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（C）

A、以順序方式存儲(chǔ)B、以鏈接方式存儲(chǔ)C、以順序方式，且結(jié)點(diǎn)按關(guān)鍵字有序排序D、以鏈接

方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

17、線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（A）的存儲(chǔ)結(jié)構(gòu)、

A、隨機(jī)存取B、順序存取C、索引存取D、散列存取

18、串是一種特殊的線性表，其特殊性體現(xiàn)在（B）

A、可以順序存儲(chǔ)B、數(shù)據(jù)元素是一個(gè)字符C、可以鏈接存儲(chǔ)D、數(shù)據(jù)元素可以是多個(gè)字符

19、任何一個(gè)無(wú)向連通圖的最小生成樹(shù)有旦

A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在

20、在一棵非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊A

A、只有右子樹(shù)上的所有結(jié)點(diǎn)B、只有右子樹(shù)上的部分結(jié)點(diǎn)C、只有左子樹(shù)上的部分

結(jié)點(diǎn)D、只有左子樹(shù)上的所有結(jié)點(diǎn)、

三、試分別按先根遍歷，中根遍歷，后根遍歷法寫(xiě)出二叉樹(shù)的遍歷序列

ABDHIEJCFG

HDIBEJAFCG

HIDJEBFGCA

四、畫(huà)出含有三個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有形態(tài)。

五、給出圖中每個(gè)頂點(diǎn)的入度，出度和頂點(diǎn)的度

頂點(diǎn)入度出度度

①213

②224

③134

@303

⑤235

⑥123

六、用Dijkstra算法求圖中VI到其余各頂點(diǎn)的最短路徑

最短路徑長(zhǎng)度

VI——?V213

VI——?V38

VI—>V4（經(jīng)V3）13

VI—>V5（經(jīng)V3,V4）19

Vl^￥6（經(jīng)V3,V4,V5）21

VI—>V7（經(jīng)V2）20

七、已知無(wú)向圖，試給出：

1.從A出發(fā)的“深度優(yōu)先”遍歷序列

2.從A出發(fā)的“廣度優(yōu)先”遍歷序列

3.該圖是連通圖嗎？

答：①ABDCEGF②ABCDEFG③是

八、對(duì)照?qǐng)D未的樹(shù)回答下列問(wèn)題

1.樹(shù)中哪些是葉結(jié)點(diǎn)？哪個(gè)是根結(jié)點(diǎn)？

答：葉結(jié)點(diǎn)DMNFJKL；根結(jié)點(diǎn)：A

2.結(jié)點(diǎn)C的雙親結(jié)點(diǎn)是哪一個(gè)？A

3.結(jié)點(diǎn)C的孩子有哪些？FGH

4.哪些是G的兄弟？F、H

⑤C的深度是多少？3

⑥樹(shù)的深