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

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

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

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

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

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

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

A:事前分析估算的方法

B:事后分析估算的方法

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

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

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

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

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

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

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

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

A:存儲方式

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

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

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

答案:C算法的計算量的大小稱為計算的（）。

A:效率

B:復(fù)雜性

C:實現(xiàn)性

D:難度

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

A:問題的規(guī)模

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

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

D:都不是

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

A:對

B:錯

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

A:錯

B:對

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

A:錯

B:對

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

A:對

B:錯

答案:B第二章測試下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（）。

A:存儲密度大

B:刪除運算方便

C:插入運算方便

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

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

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

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

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

D:線性表采用順序存儲，便于進(jìn)行插入和刪除操作

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

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

B:表元素

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

D:字符

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

A:順序表

B:雙鏈表

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

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

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

A:雙鏈表

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

C:單鏈表

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

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

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

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

C:單鏈表

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

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

A:雙鏈表

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

C:單鏈表

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

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

A:下一元素地址

B:左、右孩子地址

C:內(nèi)存地址

D:數(shù)組下標(biāo)

答案:A鏈表不具有的特點是（）。

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

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

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

D:可隨機訪問任一元素

答案:D下面的敘述不正確的是（）。

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

B:線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比

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

D:線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)

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

A:1

B:3

C:4

D:2

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

A:bacde

B:dbcae

C:ecbad

D:dbace

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

A:2和3

B:1和4

C:3和2

D:4和1

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

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

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

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

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

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

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

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

C:top-＞next=S

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

答案:D消除遞歸不一定需要使用棧。（）

A:對

B:錯

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

A:對

B:錯

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

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

答案:B第四章測試字符串S=“Todayis30July2005”，其長度是()。

A:19

B:18

C:21

D:20

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

A:堆分配存儲

B:十字表存儲

C:定長順序存儲

D:塊鏈存儲

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

A:求串長

B:連接

C:串賦值

D:求子串

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

A:36

B:9

C:8

D:37

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

A:錯

B:對

答案:B兩個串相等就是兩個串含有相同字符。（）

A:對

B:錯

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

A:‘ijing’

B:‘ingNa’

C:‘jing&’

D:‘ing&N’

答案:C空串與空格串（）。

A:無法確定

B:可能相同

C:不相同

D:相同

答案:C“DT”是“DATA”的子串。（）

A:對

B:錯

答案:B串中不能含有數(shù)字。（）

A:對

B:錯

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

A:2080

B:2004

C:2320

D:2088

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

A:45

B:16

C:55

D:36

答案:A對下述矩陣進(jìn)行壓縮存儲后，失去隨機存取功能是（）。

A:對稱矩陣

B:三對角矩陣

C:三角矩陣

D:稀疏矩陣

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

A:A

B:()

C:(b,c,d)

D:(a,b,c,d)

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

A:10

B:15

C:20

D:5

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

A:18

B:13

C:33

D:40

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

A:c

B:(d)

C:d

D:(g)

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

A:2和2

B:1和1

C:1和3

D:2和3

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

A:a,(b,c,d)

B:(b,c,d)

C:a

D:c,d

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

A:三元組和散列表

B:三元組和十字鏈表

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

D:散列表和十字鏈表

答案:B第六章測試已知一棵完全二叉樹的第5層有7個結(jié)點，則其有（）個葉子結(jié)點。

A:13

B:11

C:10

D:12

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

A:3

B:6

C:5

D:4

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

A:abecdfg

B:abcdefg

C:cdbgfea

D:cbdaegf

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

A:不確定

B:0

C:2

D:1

答案:D下列存儲形式中，（）是樹的存儲形式。

A:孩子表示法

B:雙親表示法

C:廣義表表示法

D:孩子兄弟表示法

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

A:4,1,2,3

B:4,3,2,1

C:3,4,2,1

D:2,4,3,1

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

A:左孩子編號為14

B:雙親編號為3

C:雙親編號為4

D:左孩子編號為15

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

A:錯

B:對

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

A:對

B:錯

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

A:對

B:錯

答案:A第七章測試在一個無向圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的多少倍？（）

A:2

B:1

C:4

D:1/2

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

A:錯

B:對

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

A:錯

B:對

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

）

A:3->5->4->6

B:4->3->5->6

C:3->4->5->6

D:3->5->6->4

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

）

A:17

B:23

C:19

D:16

答案:B有下圖所示的有向圖，其拓?fù)渑判蛐蛄袨?？?/p>

）

A:ABCED

B:ADBCE

C:ABDCE

D:ABCDE

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

）

A:{（A，B），（B，D）}

B:{（B，D），（D，E）}

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

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

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

）。

A:1273645

B:1236745

C:1523467

D:1253467

答案:A以下哪項是下面有向圖的鄰接表？（

）

A:

B:

C:

D:

答案:B下面哪項是下圖無向圖的鄰接矩陣？（

）

A:

B:

C:

D:

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

A:n/2

B:n

C:(n-1)/2

D:(n+1)/2

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

A:7

B:6

C:5

D:4

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

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

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

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

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

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

A:散列函數(shù)

B:存儲效率

C:平均查找長度

D:裝填因子

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

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

B:對二叉排序樹進(jìn)行層序遍歷可得到有序序列

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

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

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

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

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

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

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

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

A:LL型

B:RL型

C:LR型

D:RR型

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

A:錯

B:對

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

A:錯

B:對

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

A:對

B:錯

答案:A第九章測試下列排序算法中，穩(wěn)定的是（）。

A:歸并排序，冒泡排序

B:堆排序，冒泡排序

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

D:快速排序，堆排序

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

A:散列存儲

B:索引存儲

C:鏈?zhǔn)酱鎯?/p>

D:順序存儲

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

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

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