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

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

第一章測(cè)試

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

）

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

答案:錯(cuò)

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

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）。

A:線性結(jié)構(gòu)B:非線性結(jié)構(gòu)C:鏈?zhǔn)浇Y(jié)構(gòu)D:存儲(chǔ)結(jié)構(gòu)

答案:線性結(jié)構(gòu);非線性結(jié)構(gòu)

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

）。

A:選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)求解算法B:設(shè)計(jì)求解算法C:設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)D:使用程序語(yǔ)言編程

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

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

）

A:流程圖B:類(lèi)語(yǔ)言C:自然語(yǔ)言D:計(jì)算機(jī)高級(jí)語(yǔ)言

答案:流程圖;類(lèi)語(yǔ)言;自然語(yǔ)言;計(jì)算機(jī)高級(jí)語(yǔ)言

第二章測(cè)試

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

）

A:線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B:線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。C:線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。D:線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

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

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

）。

A:O(n)B:O(1)C:O(n2)D:O(log2n)

答案:O(n)

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

）

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

答案:錯(cuò)

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

）。

A:p->next==

H->next

B:p==H

->next

C:p==H

D:p->next==H

答案:p->next==H

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

A:(n-1)/2

B:(n+1)/2C:(2n-1)/2D:n/2

答案:n/2

第三章測(cè)試

?？梢詰?yīng)用在哪里（

）。

A:A，Ｂ，ＣB:子程序調(diào)用

C:表達(dá)式求值

D:遞歸調(diào)用

答案:A，Ｂ，Ｃ

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

）。

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

B:棧C:隊(duì)列

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

答案:棧

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

）。

A:rear=(rear+1)

%

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

C:rear=(rear+1)%(m+1)D:rear=(rear+1)

%

m

答案:rear=(rear+1)%(m+1)

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

）

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

答案:對(duì)

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

）

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

答案:錯(cuò)

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

）。

A:必須判別棧是否為滿B:對(duì)棧不作任何判別C:必須判別棧是否為空D:判別棧元素的類(lèi)型

答案:必須判別棧是否為空

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

）

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

答案:對(duì)

第四章測(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+141

B:BA+225C:BA+222

D:BA+180

答案:BA+180

將一個(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:196C:198

D:197

答案:195

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

)。

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

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

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

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

答案:j*(j-1)/2+i

設(shè)A是n*n的對(duì)稱(chēng)矩陣，將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:i(i-l)/2+j-1C:j(j-l)/2+i-1

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

答案:j(j-l)/2+i

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

）

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

答案:對(duì)

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

）。

A:O(n)B:O(1)C:O(nlog2n)D:O(n2)

答案:O(1)

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

）

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

答案:對(duì)

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

）。

A:55

B:45C:16D:36

答案:45

設(shè)二維數(shù)組A[1..

m，1..

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

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

)。

A:（i-1）*n+j

B:i*（j-1）

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

D:j*m+i-1

答案:（i-1）*n+j

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

)。

A:1205

B:1180

C:1175

D:1210

答案:1175

第五章測(cè)試

設(shè)樹(shù)T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1，則T中的葉子結(jié)點(diǎn)數(shù)為

（

）

A:8B:5

C:7

D:6

答案:8

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

）

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

答案:5

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

）。

A:500

B:505

C:都不對(duì)D:250

E:254

答案:都不對(duì)

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

）

A:11至1025之間

B:11

C:10

D:10至1024之間

答案:11至1025之間

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

（

）。

A:mk+1

B:mh+1C:mk-1

D:mh-1

答案:mk-1

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

）

A:6

B:7C:5

D:4

答案:6

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

則前序序列是（

）

A:上面的都不對(duì)B:E,G,F,A,C,D,B

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

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

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

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

）。

A:{01,10,11,00}

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

C:{00,010,0110,1000}D:{0,10,110,1111}

答案:{11,10,001,101,0001}

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

）

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

答案:錯(cuò)

第六章測(cè)試

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

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）

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

答案:錯(cuò)

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

）

A:棧B:樹(shù)C:圖D:隊(duì)列

答案:隊(duì)列

貪婪算法的特點(diǎn)。（

）

A:在算法的每一步，必須做出若干可能的選擇中的一個(gè)。B:這種策略通常是不能保證找到所求解問(wèn)題的全局最優(yōu)解。C:可以得到局部最優(yōu)解。D:貪婪策略主張所做的選擇在當(dāng)時(shí)是最好的選擇。

答案:在算法的每一步，必須做出若干可能的選擇中的一個(gè)。;這種策略通常是不能保證找到所求解問(wèn)題的全局最優(yōu)解。;可以得到局部最優(yōu)解。;貪婪策略主張所做的選擇在當(dāng)時(shí)是最好的選擇。

第七章測(cè)試

計(jì)算機(jī)中的查找方法是與數(shù)據(jù)的組織方式有著密切的關(guān)系。（

）

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

答案:對(duì)

二分查找的前提是線性表有序。（

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）

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

答案:對(duì)

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

）

A:表無(wú)限大B:選擇合適的散列函數(shù)。C:|U|≤m；D:占滿整個(gè)空間

答案:選擇合適的散列函數(shù)。;|U|≤m；

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

）

A:舍入乘法B:隨機(jī)數(shù)法C:除基取余法D:平方取中法

答案:舍入乘法;除基取余法;平方取中法

第八章測(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:基數(shù)排序B:直接插入排序C:以第一元素為界值元素的快速排序D:二路歸并排序

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

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

)。

A:歸并排序B:直接選擇排序C:直接插入排序D:快速排序

答案:快速排序

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

)。

A:(208，306，9，33，55，859，179，271，984，93)B:（271，93，33，984，55，306，208，179，859，9)C:(93，55，9，33，179，208，271，306，859，984)D:（9，33，55，93，179，208，271，306，859，984)

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

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

)有關(guān)。

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

B:所需輔助存儲(chǔ)空間的大小C:所采用的存儲(chǔ)結(jié)構(gòu)

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

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

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

)。

A:n

B:n-1C:2n

D:2n-1

答案:n

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

)位置。

A:A[1]

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

C:A[1...n/2]

D:A[1...(n+1)/2]

答案:A[(n+1)/2...n]

對(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)單選擇排序

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

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

)次比較。