2023年數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

ZH計0520九州0520

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

一、填空題：

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

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

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

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

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

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

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

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

稱棧頂。

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

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

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

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

11、在一個順序存儲的線性表中，第1個元素的地址是100,每個元素的長度為2,則第5個

元素的地址是108。

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

一個結(jié)點沒有后續(xù)結(jié)點,其余每個結(jié)點有且只有L個后續(xù)結(jié)點。

二、選擇題

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

A、dB.cC.bD.e

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

棧頂元素是D

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

3、后序遍歷的順序是D

A、根結(jié)點，左子樹，右子樹B、左子樹，根結(jié)點，右子樹

C、右子樹，根結(jié)點，左子樹D、左子樹，右子樹，根結(jié)點

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

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

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

5、串是指B

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

個字母的序列

6、一個棧的輸入序列為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é)點A有3個兄弟，且B是A的雙親，則B的度是A

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

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

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

9、一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是B

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

10、計算機算法必須具備輸入、輸出和B等五個基本特性

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

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

11、樹最適合用來表示C

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

的數(shù)據(jù)

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

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

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

13、N個頂點的強連通圖至少有（A）條邊

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

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

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

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

15、深度為4的二叉樹至多有（D）個結(jié)點

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

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

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

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

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

A、隨機存取B、順序存取C、索引存取D、散列存取

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

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

19、任何一個無向連通圖的最小生成樹有旦

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

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

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

結(jié)點D、只有左子樹上的所有結(jié)點、

三、試分別按先根遍歷，中根遍歷，后根遍歷法寫出二叉樹的遍歷序列

ABDHIEJCFG

HDIBEJAFCG

HIDJEBFGCA

四、畫出含有三個結(jié)點的二叉樹的所有形態(tài)。

五、給出圖中每個頂點的入度，出度和頂點的度

頂點入度出度度

①213

②224

③134

@303

⑤235

⑥123

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

最短路徑長度

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

七、已知無向圖，試給出：

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

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

3.該圖是連通圖嗎？

答：①ABDCEGF②ABCDEFG③是

八、對照圖未的樹回答下列問題

1.樹中哪些是葉結(jié)點？哪個是根結(jié)點？

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

2.結(jié)點C的雙親結(jié)點是哪一個？A

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

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

⑤C的深度是多少？3

⑥樹的深