算法與數(shù)據(jù)結(jié)構(gòu)智慧樹(shù)知到答案章節(jié)測(cè)試2023年蘭州理工大學(xué)

第一章測(cè)試只要算法是正確的，就一定會(huì)得到問(wèn)題的解。（

）

A:對(duì)

B:錯(cuò)

答案:B算法既獨(dú)立于數(shù)據(jù)的存儲(chǔ)，又與數(shù)據(jù)的存儲(chǔ)有一定的聯(lián)系。（

）

A:錯(cuò)

B:對(duì)

答案:B算法是獨(dú)立于計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的。（

）

A:錯(cuò)

B:對(duì)

答案:B按照數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系進(jìn)行分類，數(shù)據(jù)結(jié)構(gòu)可以分為（

）。

A:鏈?zhǔn)浇Y(jié)構(gòu)

B:非線性結(jié)構(gòu)

C:存儲(chǔ)結(jié)構(gòu)

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

答案:BD將一個(gè)幻方的求解問(wèn)題交由計(jì)算機(jī)來(lái)進(jìn)行，就要關(guān)注哪兩個(gè)方面（

）。

A:選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)求解算法

B:設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)

C:使用程序語(yǔ)言編程

D:設(shè)計(jì)求解算法

答案:A一個(gè)算法可以使用什么樣的方式進(jìn)行描述（

）

A:類語(yǔ)言

B:計(jì)算機(jī)高級(jí)語(yǔ)言

C:自然語(yǔ)言

D:流程圖

答案:ABCD第二章測(cè)試下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)（

）

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

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

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

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

答案:A設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（

）。

A:O(n)

B:O(1)

C:O(log2n)

D:O(n2)

答案:A順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（

）

A:錯(cuò)

B:對(duì)

答案:A單循環(huán)鏈表H的尾結(jié)點(diǎn)p的特點(diǎn)是（

）。

A:p==H

B:p->next==

H->next

C:p->next==H

D:p==H

->next

答案:C在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?

A:n/2

B:(2n-1)/2

C:(n+1)/2

D:(n-1)/2

答案:A第三章測(cè)試?？梢詰?yīng)用在哪里（

）。

A:表達(dá)式求值

B:A，Ｂ，Ｃ

C:遞歸調(diào)用

D:子程序調(diào)用

答案:B設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用哪種數(shù)據(jù)結(jié)構(gòu)最佳（

）。

A:線性表的順序存儲(chǔ)結(jié)構(gòu)

B:棧

C:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D:隊(duì)列

答案:B循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（

）。

A:rear=(rear+1)

%

m

B:rear=(rear+1)%(m+1)

C:rear=(rear+1)

%

(m-1)

D:rear=rear+1

答案:B任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。（

）

A:錯(cuò)

B:對(duì)

答案:B通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程的調(diào)用。（

）

A:錯(cuò)

B:對(duì)

答案:A設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（

）。

A:對(duì)棧不作任何判別

B:判別棧元素的類型

C:必須判別棧是否為空

D:必須判別棧是否為滿

答案:C不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（

）

A:對(duì)

B:錯(cuò)

答案:A第四章測(cè)試設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8

，j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲(chǔ)首地址為（

）。

A:BA+222

B:BA+225

C:BA+141

D:BA+180

答案:D將一個(gè)A[1..100，1..100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A66

65（即該元素下標(biāo)i=66，j=65），在B數(shù)組中的位置K為（

）。

A:195

B:196

C:197

D:198

答案:A若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關(guān)系為(

)。

A:i(i-1)/2+j

B:j(j+1)/2+i

C:i(i+1)/2+j

D:j(j-1)/2+i

答案:D設(shè)A是n*n的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為(

)。

A:i(i-l)/2+j

B:j(j-l)/2+i-1

C:j(j-l)/2+i

D:i(i-l)/2+j-1

答案:C從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個(gè)元素均屬于n個(gè)向量。（

）

A:錯(cuò)

B:對(duì)

答案:B設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（

）。

A:O(n)

B:O(nlog2n)

C:O(1)

D:O(n2)

答案:C稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。（

）

A:錯(cuò)

B:對(duì)

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

）。

A:16

B:36

C:45

D:55

答案:C設(shè)二維數(shù)組A[1..

m，1..

n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..

m*n]中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標(biāo)為(

)。

A:jm+i-1

B:i（j-1）

C:（i-1）n+j-1

D:（i-1）n+j

答案:D數(shù)組A[0..5,0..6]的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是(

)。

A:1210

B:1175

C:1180

D:1205

答案:B第五章測(cè)試設(shè)樹(shù)T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1，則T中的葉子結(jié)點(diǎn)數(shù)為

（

）

A:6

B:8

C:7

D:5

答案:B按二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有幾種（

）

A:6

B:4

C:5

D:3

答案:C一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（

）。

A:500

B:254

C:都不對(duì)

D:505

E:250

答案:C一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（

）

A:11

B:10至1024之間

C:11至1025之間

D:10

答案:C深度為h的滿m叉樹(shù)的第k層的結(jié)點(diǎn)結(jié)點(diǎn)個(gè)數(shù)有多少，(1=<k=<h)

（

）。

A:mk+1

B:mk-1

C:mh+1

D:mh-1

答案:B將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度（

）

A:4

B:5

C:7

D:6

答案:D某二叉樹(shù)中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E

則前序序列是（

）

A:E,A,G,C,F,B,D

B:上面的都不對(duì)

C:E,A,C,B,D,G,F

D:E,G,F,A,C,D,B

答案:C下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（

）。

A:{11,10,001,101,0001}

B:{00,010,0110,1000}

C:{01,10,11,00}

D:{0,10,110,1111}

答案:A完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。（

）

A:對(duì)

B:錯(cuò)

答案:B第六章測(cè)試如果一個(gè)有向圖中，任意兩個(gè)頂點(diǎn)之間都有有向路徑相通，那么這個(gè)有向圖就是強(qiáng)連通的。（

）

A:錯(cuò)

B:對(duì)

答案:B當(dāng)圖是稠密圖時(shí)，即邊數(shù)|E|很接近頂點(diǎn)的平方|V|2。（

）

A:對(duì)

B:錯(cuò)

答案:A對(duì)圖的每一個(gè)頂點(diǎn)訪問(wèn)一次且只訪問(wèn)一次的過(guò)程稱為圖的遍歷。（

）

A:對(duì)

B:錯(cuò)

答案:A生成樹(shù)就是將n個(gè)頂點(diǎn)連接在一起，且無(wú)環(huán)的一棵樹(shù)。（

）

A:錯(cuò)

B:對(duì)

答案:B將n個(gè)頂點(diǎn)連在一起最多需要n-2條邊。（

）

A:錯(cuò)

B:對(duì)

答案:A在拓?fù)渑判蜻^(guò)程中，要利用一個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序，這個(gè)結(jié)構(gòu)是什么（

）

A:隊(duì)列

B:棧

C:圖

D:樹(shù)

答案:A貪婪算法的特點(diǎn)。（

）

A:這種策略通常是不能保證找到所求解問(wèn)題的全局最優(yōu)解。

B:貪婪策略主張所做的選擇在當(dāng)時(shí)是最好的選擇。

C:可以得到局部最優(yōu)解。

D:在算法的每一步，必須做出若干可能的選擇中的一個(gè)。

答案:ABCD第七章測(cè)試計(jì)算機(jī)中的查找方法是與數(shù)據(jù)的組織方式有著密切的關(guān)系。（

）

A:錯(cuò)

B:對(duì)

答案:B二分查找的前提是線性表有序。（

）

A:對(duì)

B:錯(cuò)

答案:A對(duì)于長(zhǎng)度為n的有序表，二分查找算法的時(shí)間復(fù)雜度為O(log2n)（

）

A:錯(cuò)

B:對(duì)

答案:B拉鏈法中，同義詞結(jié)點(diǎn)通常鏈接成一個(gè)單鏈表，鏈表的頭指針被放置于散列表T[0..m-1]中。（

）

A:對(duì)

B:錯(cuò)

答案:A散列過(guò)程中，可以安全的避免沖突就必須滿足哪些條件（

）

A:表無(wú)限大

B:|U|≤m；

C:占滿整個(gè)空間

D:選擇合適的散列函數(shù)。

答案:BD常見(jiàn)的散列函數(shù)的有（

）

A:隨機(jī)數(shù)法

B:舍入乘法

C:平方取中法

D:除基取余法

答案:BCD第八章測(cè)試設(shè)有關(guān)鍵字初始序列(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，新序列(F，H，C，D，P，A，M，Q，R，S，Y，X}是采用(

)方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。

A:以第一元素為界值元素的快速排序

B:二路歸并排序

C:基數(shù)排序

D:直接插入排序

答案:A在待排序文件已基本有序的前提下，下述排序方法中效率最高的是(

)。

A:直接選擇排序

B:直接插入排序

C:歸并排序

D:快速排序

答案:D對(duì)整數(shù)序列(179，208，93，306，55，859，984，9，271，33)使用基數(shù)排序，一趟分配收集之后的結(jié)果是(

)。

A:（9，33，55，93，179，208，271，306，859，984)

B:（271，93，33，984，55，306，208，179，859，9)

C:(208，306，9，33，55，859，179，271，984，93)

D:(93，55，9，33，179，208，271，306，859，984)

答案:B一個(gè)排序算法的時(shí)間復(fù)雜度與(

)有關(guān)。

A:排序算法的穩(wěn)定性

B:所采用的存儲(chǔ)結(jié)構(gòu)

C:所需輔助存儲(chǔ)空間的大小

D:所需比較關(guān)鍵字的次數(shù)

答案:D將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)為(

)。

A:n

B:2n

C:2n-1

D:n-1

答案:A設(shè)有一個(gè)小頂堆，其元素個(gè)數(shù)為n，順序存儲(chǔ)在數(shù)組A[1…n]中，則其具有最大值的元素可能在(

)位置。

A:A[1…n/2]

B:A[(n+1)/2…n]

C:A[1…(n+1)/2]

D:A[1]

答案:B對(duì)一組數(shù)據(jù)(84，47，25，15，21)排序，數(shù)據(jù)的排序次序在排序的過(guò)程中的變化為：84

47

25

15

21，15

47

25

84

21，15

21

25

84

47，15

21

25

47

84，則采用的排序方法是(

)。

A:快速排序

B:插入排序

C:冒泡排序

D:簡(jiǎn)單選擇排序

答案:D若用冒泡排序方法對(duì)序列（10，14，26，29，41，52）從大到小排序，需進(jìn)行(

)次比較。

A:10