桂林電子科技成人教育電氣自動化技術(shù)課程：數(shù)據(jù)結(jié)構(gòu)(高起專)期末考試復(fù)習(xí)題及參考答案

桂林電子科技大學(xué)

桂林電子科技大學(xué)繼續(xù)教育學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021年春季學(xué)期考卷A

卷

批次專業(yè)：202001-電氣自動化技術(shù)課程：數(shù)據(jù)結(jié)構(gòu)(高起專)總時長：

120分鐘

1.(單選題)數(shù)據(jù)的最小單位是()。(本題2。分)

A.數(shù)據(jù)項

B.數(shù)據(jù)類型

C.數(shù)據(jù)元素

D.數(shù)據(jù)變量

答案:A

解析:無

2.(單選題)設(shè)連通圖G中的邊集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}廁從頂點a出發(fā)

可以得到一種深度優(yōu)先遍歷的頂點序列為()。(本題2.0分)

A.abedfc

B.acfebd

C.aebdfc

D.aedfcb

答案:B

解析:無

3.（單選題）設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head廁其判空條件是（）。體題

2.0分）

A.head==0

B.head->next==0

C.head->next==head

D.head!=0

答案:C

解析:無

4.（單選題）設(shè)計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。（本題

2.0分）

A.順序表

B.棧

C.隊列

D.鏈表

答案:B

解析:無

5.（單選題）某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是（）的二叉樹。（本題

2.0分）

A.空或只有一個結(jié)點

B.樹高度等于其結(jié)點數(shù)

C.樹中任一結(jié)點無左孩子

D.樹中任一結(jié)點無右孩子

答案:B

解析:無

6.(單選題)下面程序段的時間復(fù)雜度是()

for(i=0;i<m;i++)

forQ=0;j<n;j++)

a[i][j]=i*j；(本題2.0分)

A.O(m2)

B.O(n2)

C.O(m*n)

D.O(m+n)

答案:C

解析:無

7.(單選題)研究數(shù)據(jù)結(jié)構(gòu)就是研究()(本題2.0分)

A.數(shù)據(jù)的邏輯結(jié)構(gòu)

B.數(shù)據(jù)的存儲結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

D.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作

答案:D

解析:無

8.（單選題）已知某二叉樹的后序遍歷是dabec,中序遍歷序列是debac,它的前序遍歷是

（）（本題2.0分）

A.acbed

B.decab

C.deabc

D.cedba

答案:D

解析:無

9.（單選題）一組記錄的排序碼為（25,48,16,35,79,82,23,40,36,72）,其中含有5個長度為2

的有序表才安歸并排序的方法對該序進行一趟歸并后的結(jié)果為（）.（本題2.0分）

A.16,25,35,48,23,40,79,82,36,72

B.16,25,35,48,79,82,23,36,40,72

C.16,25,48,35,79,82,23,36,40,72

D.16,25,35,48,79,23,36,40,72,82

答案:A

解析:無

10.（單選題）設(shè)一組權(quán)值集合0={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑

長度之和為（）。（本題2.0分）

A.20

B.30

C.40

D.45

答案:D

解析:無

11.(單選題)程序段s=i=0;do{i=i+l;s=s+i;}while(i<=n);的時間復(fù)雜度為()。(本題2.0

分)

A.O(n)

B.O(nlog2n)

C.O(n2)

D.O(n3/2)

答案:A

解析:無

12.(單選題)設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點最多有()。(本題2.0分)

A.20

B.256

C.512

D.1024

答案:C

解析:無

13.（單選題）（）二叉排序樹可以得到一個從小到大的有序序列。（本題2.0分）

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

答案:B

解析:無

14.（單選題）執(zhí)行一趟快速排序能夠得到的序列是（）。（本題2.0分）

A.[41,12,34,45,27]55[72,63]

B.[45,34,12,41]55[72,63,27]

C.[63,12,34,45,27]55[41,72]

D.[12,27,45,41]55[34,63,72]

答案:A

解析:無

15.（單選題）順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）.（本題

2.0分）

A.O（n）

B.O（n2）

C.O(nl/2)

D.O（log2n）

答案:A

解析:無

16.（單選題）設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。（本題2.0分）

A.n

B.n-1

C.2n

D.2n-l

答案:B

解析:無

17.（單選題）用鏈接方式存儲的隊列，在進行插入運算時（）。（本題2.0分）

A.僅修改頭指針

B.頭、尾指針都要修改

C.僅修改尾指針

D.頭、尾指針可能都要修改

答案:D

解析:無

18.（單選題）若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外,還有指向左孩子和右孩子的

兩個指針。在這種存儲結(jié)構(gòu)中,n個結(jié)點的二叉樹共有__個指針域，其中有__個指針域是存

放了地址，有__個指針是空指針。（）（本題2.0分）

A.2n,n-l,n+l

B.2n,n+l,n-l

C.n,n+l,n-l

D.n,n-l,n+l

答案:A

解析:無

19.（單選題）設(shè)W為一個二維數(shù)組,其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7,列下

標(biāo)j從。到3，則二維數(shù)組W的數(shù)據(jù)元素共占用（）個字節(jié)。（本題2.0分）

A.255

B.64

C.21

D.128

答案:D

解析:無

20.（單選題）廣義表A=⑵心屬他屬切測它的深度為____，它的長度為一。（）（本題2.0

分）

A.3,3

B.3,2

C.2,3

D.1,3

答案:A

解析:無

21.（多選題）順序表的缺點是（）。（本題2.0分）

A.不能快速存取標(biāo)重任一位置元素

B.插入和刪除操作需要移動大量元素

C.表的容量難以確定

D.造成存儲空間的"碎片"

答案:BCD

解析:無

22.（多選題）一種抽象數(shù)據(jù)類型包括以下部分（）。（本題2.0分）

A.數(shù)據(jù)定義

B.數(shù)據(jù)存儲

C.操作聲名

D.數(shù)據(jù)描述

答案:CD

解析:無

23.侈選題）可由一個尾指針唯一確定的鏈表有（）。體題2.0分）

A.循環(huán)鏈表

B.循環(huán)雙鏈表

C.單鏈表

D.雙鏈表

答案:ABD

解析:無

24.侈選題）在圖的鄰接表中，每個結(jié)點被稱為邊結(jié)點，通常它包含（）。體題2.0分）

A.值域

B.鄰接點域

C.權(quán)域

D.鏈域

答案:BCD

解析:無

25.（多選題）鏈表具有的特點是（）（本題2.0分）

A.可隨機訪問任一元素

B.插入、刪除不需要移動元素

C.不必事先估計存儲空間

D.所需空間與線性表長度成正比

答案:BCD

解析:無

26.（多選題）f棧的輸入序列為A,B,C,D,E下面哪序列可能是這個棧的輸出序

列?（）（本題2.0分）

A.E,D,C,B,A

B.D,E,C,B,A

C.D,C,E,A,B

D.A,B,C,D,E

答案:ABD

解析:無

27.（多選題）算法的描述方法通常有（）。（本題2.0分）

A.自然語言

B.程序設(shè)計語言

C.流程圖

D.偽代碼

答案:ABCD

解析:無

28.（多選題）在單鏈表上難以實現(xiàn)的排序方法有（）。（本題2,0分）

A.快速排序

B.冒泡排序

C.堆排序

D.希爾排序

答案:ACD

解析:無

29.（多選題）下面（）屬于特殊矩陣。（本題2。分）

A.對角矩陣

B.三角矩陣

C.稀疏矩陣

D.對稱矩陣

答案:ABD

解析:無

30.（多選題）計算機中的算法指的是解決某一問題的有限運算序列，它必須具備輸入、輸出、

確定性和（）等特性。（本題2.0分）

A.可執(zhí)行性

B.有窮性

C.無限性

D.可讀性

答案:AB

解析:無

31.（判斷題）算法分析的兩個主要方面是空間復(fù)雜度和時間復(fù)雜度。（）（本題2.0分）

A.正確

B.錯誤

答案:A

解析:無

32.（判斷題）有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。（）（本題2.0分）

A.正確

B.錯誤

答案:B

解析:無

33.（判斷題）對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。（）體題2.0分）

A.正確

B.錯誤

答案:A

解析:無

34.（判斷題）如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等很U稱這兩個關(guān)鍵字為同義詞。

（）（本題2.0分）

A.正確

B.錯誤

答案:A

解析:無

35.（判斷題）二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（）（本題2.0分）

A.正確

B.錯誤

答案:B

解析:無

36.（判斷題）向二叉排序樹中插入T結(jié)點需要I：戚的次數(shù)可能大于該二叉樹的高度。

（）體題2.0分）

A.正確

B.錯誤

答案:B

解析:無

37.（判斷題）對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）（本題2.0分）

A.正確

B.錯誤

答案:A

解析:無

38.（判斷題）當(dāng)待排序的記錄數(shù)較大,存儲空間允許且要求排序是穩(wěn)定時，宜采用歸并排序。

（）（本題2.0分）

A.正確

B.錯誤

答案:A

解析:無

39.（判斷題）AOV網(wǎng)是一種有向無回路的圖。（）（本題2.0分）

A.正確

B.錯誤

答案:A

解析:無

40.（判斷題）將數(shù)組稱為隨機存取結(jié)構(gòu)式因為隨時可以對數(shù)組進行訪問。（）（本題2.0分）

A.正確

B.錯誤

答案:B

解析:無

41.（填空題）數(shù)據(jù)的物理結(jié)構(gòu)主要包括—和一兩種情況。（本題4.0分）

答案:（1）順序存儲結(jié)構(gòu);（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)；

得分點:未設(shè)置

解析:無

42.（填空題）設(shè)一組初始記錄關(guān)鍵字為（72,73,71,23,94,16,5）,則以記錄關(guān)鍵字72

為基準(zhǔn)的一趟快速排序結(jié)果為（本題2.0分）

答案:⑴（5,16,71,23,72,94,73）;

得分點:未設(shè)置

解析:無

43.（填空題）設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年?/p>

尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作為：

體題4.0分）

答案：(1)rear->next=s;;

得分點:未設(shè)置

解析：rear=s;

44.（填空題）設(shè)連通圖G中的邊集￡={（9）,似怎）,（趾）,（13￡）,66,（€1,。,（b）},則從頂點2出發(fā)

可以得到一種深度優(yōu)先遍歷的頂點序列為（本題2.0分）

答案