數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下哈爾濱商業(yè)大學

數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下哈爾濱商業(yè)大學哈爾濱商業(yè)大學

第一章測試

數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是（）。

A:邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的設(shè)計

B:數(shù)據(jù)結(jié)構(gòu)的設(shè)計與實現(xiàn)

C:數(shù)據(jù)結(jié)構(gòu)的評價與選擇

D:數(shù)據(jù)結(jié)構(gòu)的運算實現(xiàn)

答案:數(shù)據(jù)結(jié)構(gòu)的設(shè)計與實現(xiàn)

計算算法的時間復(fù)雜度是屬于一種（）。

A:事前分析估算的方法

B:事后統(tǒng)計的方法

C:事前統(tǒng)計的方法

D:事后分析估算的方法

答案:事前分析估算的方法

可以用（）定義一個完整的數(shù)據(jù)結(jié)構(gòu)。

A:數(shù)據(jù)元素

B:數(shù)據(jù)關(guān)系

C:抽象數(shù)據(jù)類型

D:數(shù)據(jù)對象

答案:抽象數(shù)據(jù)類型

數(shù)據(jù)的邏輯關(guān)系是指數(shù)據(jù)元素的（）。

A:存儲方式

B:關(guān)聯(lián)

C:數(shù)據(jù)項

D:結(jié)構(gòu)

答案:關(guān)聯(lián)

算法的計算量的大小稱為計算的（）。

A:難度

B:復(fù)雜性

C:效率

D:實現(xiàn)性

答案:復(fù)雜性

算法的時間復(fù)雜度取決于（）。

A:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)

B:都不是

C:待處理數(shù)據(jù)的初態(tài)

D:問題的規(guī)模

答案:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)

數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

A:錯B:對

答案:錯

數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。（）

A:對B:錯

答案:對

算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。（）

A:錯B:對

答案:錯

數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。（）

A:錯B:對

答案:錯

第二章測試

下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（）。

A:存儲密度大

B:插入運算方便

C:可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

D:刪除運算方便

答案:存儲密度大

下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）。

A:線性表采用順序存儲，必須占用一片連續(xù)的存儲單元

B:線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

C:線性表采用順序存儲，便于進行插入和刪除操作

D:線性表采用鏈接存儲，便于插入和刪除操作

答案:線性表采用順序存儲，便于進行插入和刪除操作

線性表是具有n個（）的有限序列（n＞0）。

A:表元素

B:字符

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

D:數(shù)據(jù)項

答案:數(shù)據(jù)元素

若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。

A:帶頭結(jié)點的雙循環(huán)鏈表

B:順序表

C:單循環(huán)鏈表

D:雙鏈表

答案:順序表

某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。

A:僅有頭指針的單循環(huán)鏈表

B:單鏈表

C:雙鏈表

D:僅有尾指針的單循環(huán)鏈表

答案:僅有尾指針的單循環(huán)鏈表

設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用()最節(jié)省時間。

A:帶頭結(jié)點的雙循環(huán)鏈表

B:帶尾指針的單循環(huán)鏈表

C:單鏈表

D:單循環(huán)鏈表

答案:帶頭結(jié)點的雙循環(huán)鏈表

若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用（）存儲方式最節(jié)省運算時間。

A:單循環(huán)鏈表

B:帶頭結(jié)點的雙循環(huán)鏈表

C:單鏈表

D:雙鏈表

答案:帶頭結(jié)點的雙循環(huán)鏈表

靜態(tài)鏈表中指針表示的是（）。

A:內(nèi)存地址

B:下一元素地址

C:數(shù)組下標

D:左、右孩子地址

答案:下一元素地址

鏈表不具有的特點是（）。

A:所需空間與線性長度成正比

B:可隨機訪問任一元素

C:插入、刪除不需要移動元素

D:不必事先估計存儲空間

答案:可隨機訪問任一元素

下面的敘述不正確的是（）。

A:線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)

B:線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比

C:線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān)

D:線性表在順序存儲時，查找第i個元素的時間同i的值成正比

答案:線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān)

;線性表在順序存儲時，查找第i個元素的時間同i的值成正比

第三章測試

設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是b,d,c,f,e,a,g，則棧S的容量至少是()。

A:4

B:1

C:2

D:3

答案:3

某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a,b,c,d,e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是()。

A:dbcae

B:bacde

C:dbace

D:ecbad

答案:dbcae

若用一個大小為5的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和2，當從隊列中刪除2個元素，再加入1個元素后，rear和front的值分別為多少()。

A:1和4

B:4和1

C:2和3

D:3和2

答案:1和4

若用鏈表來表示隊列，則應(yīng)該選用（）。

A:帶尾指針的循環(huán)鏈表

B:帶尾指針的非循環(huán)鏈表

C:帶頭指針的非循環(huán)鏈表

D:帶頭指針的循環(huán)鏈表

答案:帶尾指針的循環(huán)鏈表

向一個棧頂指針為top的鏈棧中插入一個S所指結(jié)點時，則執(zhí)行()。

A:S-＞next=top;top=S；

B:S-＞next=top-＞next;top-＞next=S;

C:S-＞next=top;top=top-＞next；

D:top-＞next=S

答案:S-＞next=top;top=S；

消除遞歸不一定需要使用棧。（）

A:對B:錯

答案:對

若輸入序列為1,2,3,4,5,6，則出棧序列不可能是3,2,5,6,4,1。（）

A:對B:錯

答案:錯

循環(huán)隊列也存在空間溢出問題。（）

A:錯B:對

答案:對

棧和隊列的存儲方式都可以采用順序方式存儲。（）

A:對B:錯

答案:對

在鏈隊列中，即使不設(shè)置尾指針也能進行入隊操作。（）

A:錯B:對

答案:對

第四章測試

字符串S="Todayis30July2005"，其長度是()。

A:20

B:19

C:18

D:21

答案:21

下列哪一個不是串的存儲方法（）。

A:塊鏈存儲

B:十字表存儲

C:定長順序存儲

D:堆分配存儲

答案:十字表存儲

設(shè)有兩個串p和q，Concat(p,q)操作是（）。

A:連接

B:串賦值

C:求子串

D:求串長

答案:連接

若串str=“Software”，其子串的個數(shù)是（）。

A:36

B:9

C:37

D:8

答案:37

串是一種數(shù)據(jù)對象和操作都特殊的線性表。（）

A:對B:錯

答案:對

兩個串相等就是兩個串含有相同字符。（）

A:錯B:對

答案:錯

設(shè)SUBSTR（S,i,k）是求S中從第i個字符開始的連續(xù)k個字符組成的子串操作，則對于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=()。

A:‘ingNa’

B:‘jing&’

C:‘ijing’

D:‘ing&N’

答案:‘jing&’

空串與空格串（）。

A:不相同

B:無法確定

C:相同

D:可能相同

答案:不相同

“DT”是“DATA”的子串。（）

A:對B:錯

答案:錯

串中不能含有數(shù)字。（）

A:對B:錯

答案:錯

第五章測試

一個一維數(shù)組A的長度為500，起始（A[0]）地址為2000，每個元素占4個字節(jié)，則A[80]的地址是（）。

A:2004

B:2080

C:2320

D:2088

答案:2320

數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)為（）。

A:45

B:36

C:55

D:16

答案:45

對下述矩陣進行壓縮存儲后，失去隨機存取功能是（）。

A:三對角矩陣

B:三角矩陣

C:稀疏矩陣

D:對稱矩陣

答案:稀疏矩陣

廣義表L=((a,b,c,d))的表尾是（）。

A:(b,c,d)

B:A

C:(a,b,c,d)

D:()

答案:()

一個5*5的對稱矩陣采用壓縮存儲，需要存儲（）個元素。

A:5

B:20

C:10

D:15

答案:15

設(shè)有一個10階的對稱矩陣A，采用壓縮存儲，以行序為主序存儲，a11為第一個元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。

A:33

B:13

C:18

D:40

答案:33

廣義表A=(a,b,(c,d),(e,(f,g)))，則表達式Head(Tail(Head(Tail(Tail(A)))))的值為（）。

A:(g)

B:d

C:c

D:(d)

答案:d

設(shè)廣義表L=（a,（b,c,d）），則L的長度和深度分別為（）。

A:1和1

B:2和3

C:2和2

D:1和3

答案:2和2

廣義表B=（a,(b,c,d)），則它的表尾是(）。

A:a

B:(b,c,d)

C:a,(b,c,d)

D:c,d

答案:(b,c,d)

稀疏矩陣一般的壓縮存儲方法有（）兩種。

A:散列表和十字鏈表

B:三元組和十字鏈表

C:二維數(shù)組和三維數(shù)組

D:三元組和散列表

答案:三元組和十字鏈表

第六章測試

已知一棵完全二叉樹的第5層有7個結(jié)點，則其有（）個葉子結(jié)點。

A:11

B:12

C:10

D:13

答案:11

含有10個結(jié)點的二叉樹中，度為0的結(jié)點數(shù)為4，則度為2的結(jié)點數(shù)為（）。

A:4

B:3

C:6

D:5

答案:3

一棵二叉樹的廣義表表示為a(b(c,d),e(,f(g)))，則得到的層次遍歷序列為（）。

A:cbdaegf

B:abcdefg

C:cdbgfea

D:abecdfg

答案:abecdfg

已知完全二叉樹有80個結(jié)點，則該二叉樹有（）個度為1的結(jié)點。

A:0

B:1

C:不確定

D:2

答案:1

下列存儲形式中，（）是樹的存儲形式。

A:雙親表示法

B:孩子兄弟表示法

C:孩子表示法

D:廣義表表示法

答案:雙親表示法

;孩子兄弟表示法

;孩子表示法

一棵先序序列為1,2,3,4的二叉樹，其中序序列可能是（）。

A:3,4,2,1

B:2,4,3,1

C:4,3,2,1

D:4,1,2,3

答案:3,4,2,1

;2,4,3,1

;4,3,2,1

一棵有16個結(jié)點的完全二叉樹，對它按層編號，則對編號為7的結(jié)點X，它的（）。

A:左孩子編號為14

B:左孩子編號為15

C:雙親編號為4

D:雙親編號為3

答案:左孩子編號為14

;雙親編號為3

將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用隊列。（）

A:對B:錯

答案:錯

完全二叉樹上結(jié)點之間的父子關(guān)系可由它們編號之間的關(guān)系來表達。（）

A:對B:錯

答案:對

設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹的結(jié)點個數(shù)為n，則森林F中第一棵樹的結(jié)點個數(shù)是m-n。（）

A:錯B:對

答案:對

第七章測試

在一個無向圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的多少倍？（）

A:1/2

B:4

C:2

D:1

答案:2

在十字鏈表中，既容易找到以頂點i為尾的弧，也容易找到以i為頭的弧。（）

A:對B:錯

答案:對

鄰接多重表用兩個邊結(jié)點表示一條邊。（）

A:對B:錯

答案:錯

對于下圖所示的帶權(quán)有向圖，采用迪杰斯特拉（Dijkstra）算法求從頂點0到其余各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是1，第二條最短路徑的目標頂點是2，后續(xù)得到其余各最短路徑的目標頂點依次為？（

）

A:3->5->6->4B:3->4->5->6C:4->3->5->6D:3->5->4->6

答案:3->5->4->6

在下圖表示某工程的AOE網(wǎng)中，關(guān)鍵路徑長度是多少？（

）

A:17B:16C:19D:23

答案:23

有下圖所示的有向圖，其拓撲排序序列為？（

）

A:ABCEDB:ABCDEC:ABDCED:ADBCE

答案:ABCDE

用普里姆(Prim)算法求一個連通圖的帶權(quán)圖的最小生成樹，在算法執(zhí)行過程中，已選取的頂點集合U={A，B}，已選取的邊的集合TE={（A，B）}，要選取下一條權(quán)值最小的邊，應(yīng)當從下列哪組中選??？（

）

A:{（B，C），（E，F(xiàn)），（B，E）}B:{（A，C），（A，E），（B，D）}C:{（A，B），（B，D）}D:{（B，D），（D，E）}

答案:{（A，C），（A，E），（B，D）}

按照深度優(yōu)先搜索遍歷下圖，從頂點1出發(fā)，可得到頂點訪問序列為（

）。

A:1236745B:1253467

C:1523467D:1273645

答案:1273645

以下哪項是下面有向圖的鄰接表？（

）

A:B:C:D:

答案:

下面哪項是下圖無向圖的鄰接矩陣？（

）

A:B:C:D:

答案:

第八章測試

若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（）。

A:n/2

B:(n-1)/2

C:n

D:(n+1)/2

答案:(n+1)/2

已知一個長度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是（）。

A:7

B:5

C:6

D:4

答案:5

對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是（）。

A:12,25,71,68,33,24

B:21,89,77,29,36,38

C:95,22,91,24,94,71

D:92,20,91,34,88,35

答案:95,22,91,24,94,71

用線性探測再散列處理沖突時，可能出現(xiàn)聚集現(xiàn)象。下列選項中，會受聚集現(xiàn)象直接影響的是（）。

A:裝填因子

B:平均查找長度

C:散列函數(shù)

D:存儲效率

答案:平均查找長度

對于二叉排序樹，下面的說法錯誤的是（）。

A:對二叉排序樹進行層序遍歷可得到有序序列

B:二叉排序樹是動態(tài)樹表，查找不成功時插入新結(jié)點時，會引起樹的重新分裂和組合

C:在二叉排序樹中進行查找，關(guān)鍵字的比較次數(shù)不超過結(jié)點數(shù)的1/2

D:逐點插入構(gòu)造二叉排序樹時，若先后插入的關(guān)鍵字有序，二叉排序樹的深度最大

答案:對二叉排序樹進行層序遍歷可得到有序序列

;二叉排序樹是動態(tài)樹表，查找不成功時插入新結(jié)點時，會引起樹的重新分裂和組合

;在二叉排序樹中進行查找，關(guān)鍵字的比較次數(shù)不超過結(jié)點數(shù)的1/2

在構(gòu)造哈希表方面，下面的說法正確的是（）。

A:鏈地址法在處理沖突時會產(chǎn)生聚集

B:在哈希表中進行查找也需要關(guān)鍵字的比較

C:哈希函數(shù)選的好可減少沖突現(xiàn)象

D:哈希表的裝填因子越大，說明空間利用率越好，因此應(yīng)使裝填因子盡量大

答案:在哈希表中進行查找也需要關(guān)鍵字的比較

;哈希函數(shù)選的好可減少沖突現(xiàn)象

在平衡二叉樹中插入一個結(jié)點后造成了不平衡，需要進行平衡化旋轉(zhuǎn)，調(diào)整類型有（）。

A:RL型

B:LL型

C:LR型

D:RR型

答案:RL型

;LL型

;LR型

;RR型

有n個數(shù)存放在一維數(shù)組A[1..n]中，在進行順序查找時，這n個數(shù)的排列有序或無序其平均查找長度不同。（）

A:對B:錯

答案:錯

對一棵二叉排序樹按先序方法遍歷得出的結(jié)點序列是從小到大的序列。（）

A:對B:錯

答案:錯

AVL樹是一棵二叉樹，該樹上任一結(jié)點的平衡因子的絕對值不大于1。（）

A:錯B:對

答案:對

第九章測試

下列排序算法中，穩(wěn)定的是（）。

A:歸并排序，冒泡排序

B:快速排序，堆排序

C:堆排序，冒泡排序

D:直接選擇排序，歸并排序

答案:歸并排序，冒泡排序

為實現(xiàn)快速排序算法，待排序序列采用的存儲方式是（）。

A:索引存儲

B:散列存儲

C:鏈式存儲

D:順序存儲

答案:順序存儲

對給定的關(guān)鍵字序列110,119,007,911,114,120,122進行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是（）。

A:007,110,911,114,119,120,122

B:007,110,119,114,911,122,120

C:007,110,119,114,911,