2023年數(shù)據(jù)結構復習題

ZH計0520九州0520

《數(shù)據(jù)結構》復習

一、填空題：

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

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

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

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

5、線性結構中元素之間存在一對一的關系,樹形結構中元素之間存在一對多的關系,圖形

結構中元素之間存在多對多的關系。

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

7、棧的邏輯結構是線性結構，其特點是后進先出,先進后出,棧中允許插入和刪除的一端

稱棧頂。

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

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

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

序存儲結構和鏈式存儲結構。

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

元素的地址是108。

12、在線性結構中，第一個結點沒有前驅結點,其余每個結點有且只有L個前驅結點；最后

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

二、選擇題

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

A、dB.cC.bD.e

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

棧頂元素是D

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

3、后序遍歷的順序是D

A、根結點，左子樹，右子樹B、左子樹，根結點，右子樹

C、右子樹，根結點，左子樹D、左子樹，右子樹，根結點

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

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

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、如果結點A有3個兄弟，且B是A的雙親，則B的度是A

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

8、通常對數(shù)組進行的兩種基本操作是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、元素之間具有分支層次關系的數(shù)據(jù)D、元素之間無聯(lián)系

的數(shù)據(jù)

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

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

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

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

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

14、棧通常采用的兩種存儲結構是（A）

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

儲結構和非線性存儲結構

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

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

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

A、以順序方式存儲B、以鏈接方式存儲C、以順序方式，且結點按關鍵字有序排序D、以鏈接

方式存儲，且結點按關鍵字有序排序

17、線性表的順序存儲結構是一種（A）的存儲結構、

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

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

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

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

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

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

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

結點D、只有左子樹上的所有結點、

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

ABDHIEJCFG

HDIBEJAFCG

HIDJEBFGCA

四、畫出含有三個結點的二叉樹的所有形態(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.樹中哪些是葉結點？哪個是根結點？

答：葉結點DMNFJKL；根結點：A

2.結點C的雙親結點是哪一個？A

3.結點C的孩子有哪些？FGH

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

⑤C的深度是多少？3

⑥樹的深