2021年春期成人教育（專科）《數(shù)據(jù)結(jié)構(gòu)》期末復習指導

2021年春期成人教育（?？疲?/p>

《數(shù)據(jù)結(jié)構(gòu)》期末復習指導

2021年06月修訂

第一部分課程考核說明

1、考核目的

通過本次考試，了解學生對本課程基本內(nèi)容和重、難點的掌握程度，以及運用本課程的

基本知識、基本理論和基本方法來分析和解決數(shù)據(jù)結(jié)構(gòu)的算法研究問題的能力，同時還考察

不同數(shù)據(jù)結(jié)構(gòu)算法在實際中的應用，理解和運用相結(jié)合。

2、考核方式

本課程期末考試為開卷筆試，考試時間為90分鐘。

3、適用范圍、教材

本復習指導適用于重慶電大成人教育?？朴嬎銠C應用專業(yè)的必修課程《數(shù)據(jù)結(jié)構(gòu)》。

本課程考試命題依據(jù)的教材采用唐國民、王國鈞主編，清華大學出版社出版的《數(shù)據(jù)結(jié)

構(gòu)（C語言版）》（2013年4月第2版）。

4、命題依據(jù)

本課程的命題依據(jù)是《數(shù)據(jù)結(jié)構(gòu)》課程的教學大綱、教材、實施意見。

5、考試要求

考試主要是考核學生對基本理論和基本問題的理解和應用能力。在能力層次上，從了解、

掌握、重點掌握3個角度來要求。主要考核學生對不同數(shù)據(jù)結(jié)構(gòu)的基本理論、不同數(shù)據(jù)結(jié)構(gòu)

的算法理解和運用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力。

6、試題類型及結(jié)構(gòu)

考題類型及分數(shù)比重大致為：單項選擇題（20%）；填空題（20%）；判斷題（20%）；應

用題（20%）；編程題（20%）。

第二部分期末復習指導

第一章概述

一、重點名詞

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對象算法時間復雜度空間復雜度

二、重點掌握

1.數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語；

2.算法的概念、特點；

3.算法時間復雜度和空間復雜度的分析。

三、一般掌握

1.算法的表示方式。

第二章線性表

一、重點掌握

1.線性表的定義和特點；

2.線性表的操作；

3.線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。

二、一般掌握

I.線性表的應用?

第三章棧和隊列

一、重點掌握

1.棧的定義及運算；

2.棧的順序結(jié)構(gòu)與鏈式結(jié)構(gòu)；

3.隊列的定義及運算；

4.隊列的順序結(jié)構(gòu)與鏈式結(jié)構(gòu)；

二、一般掌握

1.棧和隊列的算法實現(xiàn)。

第四章串

一、重點掌握

1.串的定義及運算；

2.串的順序結(jié)構(gòu)與鏈式結(jié)構(gòu)；

二、一般掌握

1.串的模式匹配。

第五章多維數(shù)組和廣義表

一、重點掌握

1.多維數(shù)組的順序存儲；

2.特殊矩陣的順序存儲；

3.稀疏矩陣的存儲；

二、一般掌握

1.廣義表的表示。

第六章樹和二叉樹

一、重點掌握

1.樹和二叉樹的基本概念；

2.二叉樹的遍歷

3.線索二叉樹。

二、一般掌握

1.二叉樹和森林；

2.最優(yōu)二叉樹。

第七章圖

一、重點掌握

1.圖的基本概念和術(shù)語；

2.圖的存儲結(jié)構(gòu)；

3.圖的遍歷；

4.生成樹的概念；

5.最短路徑；

6.拓撲排序。

二、一般掌握

1.圖的應用。

第八章查找

一、重點掌握

1.查找的基本概念；

2.順序查找；

3.折半查找；

4.分塊查找。

二、一般掌握

1.樹表的查找

2.散列表的查找

第九章排序

一、重點掌握

1.排序的基本概念；

2.插入排序；

3.交換排序；

4.選擇排序。

二、一般掌握

1.歸并排序；

2.基數(shù)排序；

3.內(nèi)部排序算法比較；

4.外部排序。

第三部分綜合練習題

一、單項選擇題

1、下面關于線性表的敘述錯誤的是()。

(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間

(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間

(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)

(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

2、設哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中

總共有()個結(jié)點。

(A)2m-1(B)2m(C)2m+l(D)4m

3、設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊

頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)

為()。

(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M

4、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()

(A)隊列(B)棧(C)線性表(D)圖

5、設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為()。

(A)O(n)(B)O(nlog2n)(C)O(l)(D)0(n2)

6、下面程序的時間復雜為()

for(i=l,s=0；i<=n；i++){t=l；for(j=I；j<=i；j++)t=t*j；s=s+t；}

(A)0(n)(B)O(n2)(C)O(n3)(D)0(n4)

7、棧是一種()的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

8、設有4個結(jié)點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。

(A)3(B)4(C)5(D)6

9、一個線性表第1個元素的存儲地址是200,每個元素的長度為5,則第3個元素的地

址是()o

(A)210(B)220(C)200(D)215

10、對一個算法的評價，不包括如下()方面的內(nèi)容。

(A)健壯性和可讀性(B)并行性(C)正確性(D)時空復雜度

11、設有6個結(jié)點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。

(A)5(B)6(C)7(D)8

12、棧和隊列的共同特點是()。

(A)只允許在端點處插入和刪除元素

(B)都是先進后出

(C)都是先進先出

(D)沒有共同點

13、一個線性表第1個元素的存儲地址是100,每個元素的長度為2,則第5個元素的

地址是()。

(A)110(B)108(C)100(D)120

14、線性表采用鏈式存儲時，結(jié)點的存儲地址()。

(A)必須是不連續(xù)的

(B)連續(xù)與否均可

(C)必須是連續(xù)的

(D)和頭結(jié)點的存儲地址相連續(xù)

15、二叉樹的第k層的結(jié)點數(shù)最多為().

(A)2k-1(B)2K+1(C)2K-1(D)2k-1

16、遍歷順序表的時間復雜度為()。

(A)0(1)(B)O(n)(C)O(log2n)(D)O(n2)

17、設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別

18、設某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為NL度數(shù)為2的結(jié)點

數(shù)為N2,則下列等式成立的是()o

(A)NO=N1+1(B)N0=Nl+N2(C)N0=N2+l(D)N0=2Nl+l

19、數(shù)據(jù)的最小單位是()。

(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

20、()二叉排序樹可以得到一個從小到大的有序序列。

(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

21、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()

(A)隊列⑻棧(C)線性表(D)樹

22、一個線性表第1個元素的存儲地址是100,每個元素的長度為4,則第3個元素的

地址是()。

(A)110(B)120(C)100(D)108

23、設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有()個表頭結(jié)點。

(A)n-1(B)n(C)n+1(D)2n-l

24、設某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,R),D={01,02,03,04,05,06,07,

08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,

<03,08>,<03,09>},則數(shù)據(jù)結(jié)構(gòu)A是（）。

(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)

25、根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。

(A)4(B)5(C)6(D)7

26、深度為k的完全二叉樹中最少有()個結(jié)點。

(A)2k-1-1(B)2k-l(C)2k-1+1(D)2k-1

27、隊列是一種()的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

28、用鏈接方式存儲的隊列，在進行插入運算時().

(A)僅修改頭指針(B)頭、尾指針都要修改

(C)僅修改尾指針(D)頭、尾指針可能都要修改

29、樹最適合用來表示()o

(A)有序數(shù)據(jù)元素(B)無序數(shù)據(jù)元素

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

30、下面關于線性表的敘述正確的是()。

(A)線性表采用順序存儲不必占用一片連續(xù)的存儲空間

(B)線性表采用鏈式存儲必須占用一片連續(xù)的存儲空間

(0線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)

(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

二、填空題

1、數(shù)據(jù)的物理結(jié)構(gòu)主要包括存儲和________存儲兩種情況。

2、設哈夫曼樹中共有99個結(jié)點，則該樹中有個葉子結(jié)點；若采用二叉鏈表

作為存儲結(jié)構(gòu)，則該樹中有個空指針域。

3、圖分為和o

4、判斷順序?？盏臈l件是top=,棧滿的條件是top=o

5、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D是的有限集合，R是D上的

有限集合。

6、空串的長度是：空格串的長度是.。

7、結(jié)點數(shù)為20的二叉樹可能達到的最大層次數(shù)為。

8、折半查找要求結(jié)點是（填有序或無序）和填順序或鏈式）存儲。

9、設結(jié)點A有4個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點,則結(jié)點B的度數(shù)為

10、直接插入排序算法的時間復雜度體現(xiàn)在元素的和。分為最

好、最壞和隨機的情況。其中最好的情況指的是順序表中的記錄是;最壞的情況

指的是順序表中的記錄是。

11、設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則

e=。

12、假定一棵樹的廣義表表示為A（C,D（E,F）,H（G,I,J））,則樹中所含的結(jié)

點數(shù)為個，樹的深度為，樹的度為o

13、設輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到種不同的輸出序

列。

14、三個頂點可以構(gòu)成棵不同的樹。

15、二叉樹是指度為2的（填有序或無序）樹。一棵結(jié)點數(shù)為N的二叉樹,

其所有結(jié)點的度的總和是o

16、設哈夫曼樹中共有49個結(jié)點，則該哈夫曼樹中有個度數(shù)為1的結(jié)點，個

葉子結(jié)點。

17、設結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)為

18、順序表、棧和隊列都是結(jié)構(gòu)，可以在順序表的（填任何或首

或尾）位置插入和刪除元素；對于棧只能在________插入和刪除元素；對于隊列只能在

插入和刪除元素。

19、數(shù)據(jù)的運算最常用的有5種，它們分別是插入、、、查找、

20、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以（填一個或任

意多個）。

21、不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復雜度

均為。

22、設二叉樹中度數(shù)為0的結(jié)點數(shù)為50,度數(shù)為1的結(jié)點數(shù)為30,則該二叉樹中總共

有個結(jié)點數(shù)。

23、結(jié)點數(shù)為5的二叉樹可能達到的最大層次數(shù)為______，最低層次數(shù)為。

24、設前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后

序遍歷該二叉樹的序列為。

25、完全二叉樹中第3層上最少有個結(jié)點，最多有個結(jié)點。

26、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和。線性結(jié)

構(gòu)中元素之間存在一對一關系，樹形結(jié)構(gòu)中元素之間存在___________關系，圖形結(jié)構(gòu)中元

素之間存在__________關系。

27、棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除

運算的一端稱為。是被限定為只能在表的一端進行插入運算，

在表的另一端進行刪除運算的線性表。

28、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且只有

個前驅(qū)結(jié)點；葉子結(jié)點沒有結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可

以O

29、在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前

驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。

30、一個算法的效率可分為效率和效率。

三、判斷題

1、分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）

2、冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）

3、滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）

4、設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）

5、哈夫曼樹中有度數(shù)為1的結(jié)點。（）

6、設一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）

7、線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。（）

8、中序遍歷二叉排序樹可以得到一個有序的序列。（）

9、快速排序是排序算法中平均性能最好的一種排序。（）

10、不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）

11、當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（）

12、鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。（）

13、完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（）

14.哈夫曼樹中沒有度數(shù)為1的結(jié)點。（）

15、滿二叉樹一定是完全二叉樹，完全二叉樹也一定是滿二叉樹。（）

16、先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（）

17、由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（）

18、線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）

19、對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。（）

20、順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。（）

21、當向二叉排序樹中插入一個結(jié)點，則該結(jié)點不一定成為葉子結(jié)點。（）

22、滿二叉樹中的葉子結(jié)點只可能在最后一層中出現(xiàn)。（）

23、哈夫曼樹中只有度數(shù)為。和2的結(jié)點。（）

24、前序遍歷二叉排序樹可以得到一個有序的序列。（）

25、不論線性表采用順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，刪除值為X的結(jié)點的時間復雜

度均為0（1）。（）

26、線性表中的不是所有元素都有一個前驅(qū)元素和后繼元素。（）

27、鏈式存儲結(jié)構(gòu)比順序存儲結(jié)構(gòu)更適合插入和刪除操作。（）

28、設一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有左子樹。（）

29、入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。（）

30、若一個結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序

遍歷序列中的最后一個結(jié)點。（）

四、應用題

1.畫出表達式（A+B*C-D）/（E+（F-G））的二叉樹，并求其后綴表達式。

2、已知二叉樹遍歷的先序序列為ABDECF,中序序列為DBEAFC。

（1）畫出此二叉樹

（2）寫出此二叉樹的后序遍歷序列。

3、請將下圖所示的森林轉(zhuǎn)換為相應的二叉樹。

4、一個棧的輸入序列是12345,它能得到54132的序列嗎？請列出三個它能得到的輸

出序列。

5、有5個元素，其入棧次序為ABCDE,在各種可能的出棧次序中，以元素CD最先出

棧（即C第一個且D第二個出棧）的次序有幾個？分別列出。

五、編程題

1、請用C語言描述冒泡排序算法。

2、請用C語言描述折半查找。

第四部分《數(shù)據(jù)結(jié)構(gòu)》期末復習指導答案

一、單項選擇題

P5DACDC6~10BBAAB1T15AABBD16~20BBCAB2廣25DDBBB26~30BADCC

二、填空題

1、順序、鏈式

2、50、100

3、有向圖、無向圖

4、-1,maxsize-1

5、數(shù)據(jù)元素、關系

6、0,空格的數(shù)目

7、20

8、有序、順序存儲

9、5

10、比較、移動、已排好序、反序