數(shù)據(jù)結(jié)構(gòu)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋哈爾濱商業(yè)大學(xué)第一章單元測(cè)試

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

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

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

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

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

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

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

A:事后統(tǒng)計(jì)的方法

B:事后分析估算的方法

C:事前分析估算的方法

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

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

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

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

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

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

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

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

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

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

B:存儲(chǔ)方式

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

D:數(shù)據(jù)項(xiàng)

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

算法的計(jì)算量的大小稱為計(jì)算的（）。

A:難度

B:效率

C:實(shí)現(xiàn)性

D:復(fù)雜性

答案:復(fù)雜性

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

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

B:都不是

C:問(wèn)題的規(guī)模

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

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

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

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第二章單元測(cè)試

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

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

B:插入運(yùn)算方便

C:存儲(chǔ)密度大

D:刪除運(yùn)算方便

答案:存儲(chǔ)密度大

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

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

B:線性表采用鏈接存儲(chǔ)，便于插入和刪除操作

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

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

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

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

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

B:字符

C:數(shù)據(jù)項(xiàng)

D:表元素

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

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

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

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

C:順序表

D:雙鏈表

答案:順序表

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

A:單鏈表

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

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

D:雙鏈表

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

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

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

B:單鏈表

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

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

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

若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A:單鏈表

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

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

D:雙鏈表

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

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

A:左、右孩子地址

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

C:下一元素地址

D:內(nèi)存地址

答案:下一元素地址

鏈表不具有的特點(diǎn)是（）。

A:所需空間與線性長(zhǎng)度成正比

B:不必事先估計(jì)存儲(chǔ)空間

C:可隨機(jī)訪問(wèn)任一元素

D:插入、刪除不需要移動(dòng)元素

答案:可隨機(jī)訪問(wèn)任一元素

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

A:線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)

B:線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)

C:線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

D:線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

答案:線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)

；線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

第三章單元測(cè)試

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

A:1

B:4

C:2

D:3

答案:3

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

A:bacde

B:ecbad

C:dbace

D:dbcae

答案:dbcae

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

A:1和4

B:4和1

C:2和3

D:3和2

答案:1和4

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

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

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

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

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

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

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

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

B:top-＞next=S

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

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

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

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

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

答案:錯(cuò)循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（）

A:錯(cuò)B:對(duì)

答案:對(duì)棧和隊(duì)列的存儲(chǔ)方式都可以采用順序方式存儲(chǔ)。（）

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

答案:對(duì)

第四章單元測(cè)試

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

A:20

B:21

C:19

D:18

答案:21

下列哪一個(gè)不是串的存儲(chǔ)方法（）。

A:定長(zhǎng)順序存儲(chǔ)

B:十字表存儲(chǔ)

C:堆分配存儲(chǔ)

D:塊鏈存儲(chǔ)

答案:十字表存儲(chǔ)

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

A:連接

B:串賦值

C:求串長(zhǎng)

D:求子串

答案:連接

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

A:37

B:8

C:9

D:36

答案:37

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

A:對(duì)B:錯(cuò)

答案:對(duì)兩個(gè)串相等就是兩個(gè)串含有相同字符。（）

A:對(duì)B:錯(cuò)

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

A:‘ijing’

B:‘ingNa’

C:‘jing&’

D:‘ing&N’

答案:‘jing&’

空串與空格串（）。

A:相同

B:不相同

C:無(wú)法確定

D:可能相同

答案:不相同

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

A:錯(cuò)B:對(duì)

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第五章單元測(cè)試

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

A:2004

B:2088

C:2320

D:2080

答案:2320

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

A:16

B:55

C:45

D:36

答案:45

對(duì)下述矩陣進(jìn)行壓縮存儲(chǔ)后，失去隨機(jī)存取功能是（）。

A:稀疏矩陣

B:三角矩陣

C:對(duì)稱矩陣

D:三對(duì)角矩陣

答案:稀疏矩陣

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

A:(b,c,d)

B:()

C:A

D:(a,b,c,d)

答案:()

一個(gè)5*5的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)（）個(gè)元素。

A:20

B:15

C:5

D:10

答案:15

設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)，以行序?yàn)橹餍虼鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。

A:13

B:33

C:18

D:40

答案:33

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

A:(d)

B:(g)

C:d

D:c

答案:d

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

A:2和2

B:1和1

C:2和3

D:1和3

答案:2和2

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

A:(b,c,d)

B:a,(b,c,d)

C:c,d

D:a

答案:(b,c,d)

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

A:三元組和十字鏈表

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

C:三元組和散列表

D:散列表和十字鏈表

答案:三元組和十字鏈表

第六章單元測(cè)試

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

A:10

B:11

C:12

D:13

答案:11

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

A:4

B:6

C:3

D:5

答案:3

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

A:cdbgfea

B:cbdaegf

C:abecdfg

D:abcdefg

答案:abecdfg

已知完全二叉樹(shù)有80個(gè)結(jié)點(diǎn)，則該二叉樹(shù)有（）個(gè)度為1的結(jié)點(diǎn)。

A:1

B:0

C:2

D:不確定

答案:1

下列存儲(chǔ)形式中，（）是樹(shù)的存儲(chǔ)形式。

A:廣義表表示法

B:雙親表示法

C:孩子表示法

D:孩子兄弟表示法

答案:雙親表示法

；孩子表示法

；孩子兄弟表示法

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

A:3,4,2,1

B:2,4,3,1

C:4,1,2,3

D:4,3,2,1

答案:3,4,2,1

；2,4,3,1

；4,3,2,1

一棵有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)它按層編號(hào)，則對(duì)編號(hào)為7的結(jié)點(diǎn)X，它的（）。

A:左孩子編號(hào)為14

B:左孩子編號(hào)為15

C:雙親編號(hào)為3

D:雙親編號(hào)為4

答案:左孩子編號(hào)為14

；雙親編號(hào)為3

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

A:錯(cuò)B:對(duì)

答案:錯(cuò)完全二叉樹(shù)上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來(lái)表達(dá)。（）

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

答案:對(duì)

第七章單元測(cè)試

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

A:1/2

B:2

C:1

D:4

答案:2

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

A:對(duì)B:錯(cuò)

答案:對(duì)鄰接多重表用兩個(gè)邊結(jié)點(diǎn)表示一條邊。（）

A:錯(cuò)B:對(duì)

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

）

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

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

）

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

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

）

A:ADBCEB:ABDCEC:ABCDED:ABCED

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

）

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

答案:{（A，C），（A，E），（B，D）}按照深度優(yōu)先搜索遍歷下圖，從頂點(diǎn)1出發(fā)，可得到頂點(diǎn)訪問(wèn)序列為（

）。

A:1523467B:1273645C:1253467

D:1236745

答案:1273645以下哪項(xiàng)是下面有向圖的鄰接表？（

）

A:B:C:D:

答案:下面哪項(xiàng)是下圖無(wú)向圖的鄰接矩陣？（

）

A:B:C:D:

答案:

第八章單元測(cè)試

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

A:n

B:(n-1)/2

C:n/2

D:(n+1)/2

答案:(n+1)/2

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

A:4

B:5

C:6

D:7

答案:5

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

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

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

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

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

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

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

A:裝填因子

B:散列函數(shù)

C:存儲(chǔ)效率

D:平均查找長(zhǎng)度

答案:平均查找長(zhǎng)度

對(duì)于二叉排序樹(shù)，下面的說(shuō)法錯(cuò)誤的是（）。

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

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

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

D:二叉排序樹(shù)是動(dòng)態(tài)樹(shù)表，查找不成功時(shí)插入新結(jié)點(diǎn)時(shí)，會(huì)引起樹(shù)的重新分裂和組合

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

；對(duì)二叉排序樹(shù)進(jìn)行層序遍歷可得到有序序列

；二叉排序樹(shù)是動(dòng)態(tài)樹(shù)表，查找不成功時(shí)插入新結(jié)點(diǎn)時(shí)，會(huì)引起樹(shù)的重新分裂和組合

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

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

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

C:哈希函數(shù)選的好可減少?zèng)_突現(xiàn)象

D:鏈地址法在處理沖突時(shí)會(huì)產(chǎn)生聚集

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

；哈希函數(shù)選的好可減少?zèng)_突現(xiàn)象

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

A:LL型

B:LR型

C:RR型

D:RL型

答案:LL型

；LR型

；RR型

；RL型

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)對(duì)一棵二叉排序樹(shù)按先序方法遍歷得出的結(jié)點(diǎn)序列是從小到大的序列。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)AVL樹(shù)是一棵二叉樹(shù)，該樹(shù)上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于1。（）

A:錯(cuò)B:對(duì)

答案:對(duì)

第九章單元測(cè)試

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

A:快速排序，堆排序

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

C:歸并排序，冒泡排序

D:堆排序，冒泡排序

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

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

A:索引存儲(chǔ)

B:鏈?zhǔn)酱鎯?chǔ)

C:順序存儲(chǔ)

D:散列存儲(chǔ)

答案:順序存儲(chǔ)

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

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

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

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