數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下哈爾濱金融學(xué)院

數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下哈爾濱金融學(xué)院哈爾濱金融學(xué)院

第一章測試

數(shù)據(jù)的邏輯結(jié)構(gòu)有（）

A:樹形結(jié)構(gòu)

B:圖狀結(jié)構(gòu)

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

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

答案:樹形結(jié)構(gòu)

;圖狀結(jié)構(gòu)

;線性結(jié)構(gòu)

據(jù)組織的三個層次，從小到大，分別是（）

A:數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)

B:數(shù)據(jù)元素、數(shù)據(jù)和數(shù)據(jù)項(xiàng)

C:數(shù)據(jù)、數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素

D:數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)

答案:數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)

以下哪個存儲結(jié)構(gòu)是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算（根據(jù)散列函數(shù)）出結(jié)點(diǎn)的存儲地址（）

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

B:散列結(jié)構(gòu)

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

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

答案:散列結(jié)構(gòu)

（）是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作

A:數(shù)據(jù)類型

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

C:數(shù)據(jù)集合

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

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

以下時間復(fù)雜度最小的是（）

A:O(nlog2n)

B:O(n2)

C:O(log2n)

D:O(n)

答案:O(log2n)

一個算法必須滿足的特性有（）

A:健壯性和可無輸入

B:可讀性和可無輸入

C:有窮性和必有輸出

D:確定性和可行性

答案:有窮性和必有輸出

;確定性和可行性

線性表的順序存儲結(jié)構(gòu)，表中元素的邏輯順序與物理順序不一定相同（）

A:錯B:對

答案:錯

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

A:錯B:對

答案:錯

邏輯結(jié)構(gòu)在存儲器中的映象，稱為數(shù)據(jù)類型（）

A:對B:錯

答案:錯

一個算法的時間復(fù)雜度越小，則算法的空間復(fù)雜度也越?。ǎ?/p>

A:對B:錯

答案:錯

第二章測試

若某線性表最常用的操作是取第i個元素和找第i個元素的前驅(qū)元素，則采?。ǎ┐鎯Ψ绞阶罟?jié)省時間。

A:單鏈表

B:單項(xiàng)循環(huán)鏈表

C:順序表

D:雙鏈表

答案:順序表

在長度為n的順序表上刪除第i個元素，需要移動（）個元素。

A:n-i-1

B:i

C:n-i+1

D:n-i

答案:n-i

線性表的順序存儲優(yōu)于鏈?zhǔn)酱鎯?。（?/p>

A:對B:錯

答案:錯

在順序表中，插入元素時，移動元素的個數(shù)與該元素的位置無關(guān)。（）

A:對B:錯

答案:錯

對雙向鏈表來說，結(jié)點(diǎn)*p的存儲位置既存放在其前驅(qū)結(jié)點(diǎn)的后繼指針域中，也存放在它的后繼結(jié)點(diǎn)的前驅(qū)指針域中。

A:對B:錯

答案:對

設(shè)rear是指向非空帶頭結(jié)點(diǎn)的循環(huán)鏈表的尾指針，則刪除首結(jié)點(diǎn)的操作表示為（

）。

A:rear=rear->next;free(rear);B:rear=rear->next->next;free(rear);free(s);C:s=rear;rear=rear->next;free(s);

D:s=rear->next->next;rear->next->next=s->next;free(s);

答案:s=rear->next->next;rear->next->next=s->next;free(s);

從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需平均比較（

）個結(jié)點(diǎn)。

A:n/2

B:(n-1)/2

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

答案:(n+1)/2

線性表采用鏈?zhǔn)酱鎯r，不同結(jié)點(diǎn)的存儲地址（

）。

A:和頭結(jié)點(diǎn)的存儲地址相連續(xù)B:連續(xù)與否均可C:必須是連續(xù)的D:必須是不連續(xù)的

答案:連續(xù)與否均可

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

）。

A:所需的空間與線性表長度成正比B:隨機(jī)訪問

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

D:不必事先估計(jì)存儲空間

答案:隨機(jī)訪問

帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是（

）。

A:head->next==head

B:head!==NULLC:head==NULL

D:head->next==NULL

答案:head->next==NULL

第三章測試

以下不屬于隊(duì)列的基本運(yùn)算是（）。

A:刪除隊(duì)首元素

B:將隊(duì)列置空

C:判斷隊(duì)列是否為空

D:刪除隊(duì)尾元素

答案:刪除隊(duì)尾元素

循環(huán)隊(duì)列Q是空隊(duì)列的條件是（）。

A:Q-＞front==0

B:Q-＞rear==Q-＞front

C:（Q-＞rear+1）%maxsize==Q-＞front

D:Q-＞rear==0

答案:Q-＞rear==Q-＞front

有六個元素6，5，4，3，2，1的順序進(jìn)棧，下列哪一個不是合法的出棧序列？（）

A:453126

B:234156

C:346521

D:543612

答案:346521

循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素個數(shù)是()。

A:rear-front-1

B:rear-front

C:rear-front+1

D:(rear-front+m)%m

答案:(rear-front+m)%m

輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（）。

A:push,pop,push,push,pop,pop

B:push,push,push,pop,pop,pop

C:push,push,pop,pop,push,pop

D:push,pop,push,pop,push,pop

答案:push,push,push,pop,pop,pop

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

A:1和5

B:5和1

C:2和4

D:4和2

答案:2和4

下面哪些選項(xiàng)是棧的應(yīng)用（）。

A:哈夫曼樹問題

B:表達(dá)式計(jì)算

C:函數(shù)調(diào)用

D:括號匹配

E:進(jìn)制轉(zhuǎn)換

答案:表達(dá)式計(jì)算

;函數(shù)調(diào)用

;括號匹配

;進(jìn)制轉(zhuǎn)換

遞歸操作不一定需要使用棧，通常也使用隊(duì)列。（）

A:對B:錯

答案:錯

棧與隊(duì)列都是特殊操作的線性表。（）

A:對B:錯

答案:對

無論是順序隊(duì)列還是鏈隊(duì)列，插入、刪除運(yùn)算的時間復(fù)雜度都是O（1）。（）

A:錯B:對

答案:對

第四章測試

下面關(guān)于串的的敘述中，哪一個是不正確的（）。

A:模式匹配是串的一種重要運(yùn)算

B:串是字符的有限序列

C:串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

D:空串是由空格構(gòu)成的串

答案:空串是由空格構(gòu)成的串

設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）。

A:求串長

B:求子串

C:模式匹配

D:聯(lián)接

答案:模式匹配

模式串‘a(chǎn)babaabab’的next數(shù)組值為（）。

A:(-1,0,0,1,1,2,1,2,1)

B:(-1,0,0,1,2,3,1,2,3)

C:(-1,0,0,1,1,1,2,0,1)

D:(-1,0,0,1,2,2,1,2,3)

答案:(-1,0,0,1,2,3,1,2,3)

串的長度是指（）。

A:串中所含字符的個數(shù)

B:串中所含非空格字符的個數(shù)

C:串中所含不同字母的個數(shù)

D:串中所含不同字符的個數(shù)

答案:串中所含字符的個數(shù)

設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S的子串的個數(shù)為（）。

A:n(n+1)/2+1

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

C:n(n-1)/2

D:n(n+1)/2

答案:n(n+1)/2+1

若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。

A:“Shanghai＆Nanjing”

B:“Nanjing＆Shanghai”

C:“ShanghaiNanjing”

D:“Nanjing＆Nanjing”

答案:“Shanghai＆Nanjing”

設(shè)s=”C:\document\Mary.docx”，則strlen(s)的值為（）。

A:23

B:21

C:25

D:19

答案:21

若串S1=‘ABCDEFG’，S2=‘PQRST’，函數(shù)concat(x,y)返回x和y串的連接串，substr(s,i,j)返回串s從序號i開始的j個字符組成的子串中，len(s)返回串s的長度，則執(zhí)行concat(substr(s1,2,len(s2)),substr(s1,len(s2),2))，結(jié)果為（）。

A:BCDEFG

B:BCPQRST

C:BCDEFEF

D:BCDEF

答案:BCDEFEF

對于串，只能對其中多個連續(xù)的字符進(jìn)行操作，不能對其中的一個字符進(jìn)行操作。（）

A:錯B:對

答案:錯

信息檢索中經(jīng)常會用到串模式匹配算法。（）

A:錯B:對

答案:對

第五章測試

數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)I從1到8，列下標(biāo)J從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組占用的字節(jié)數(shù)為（）。

A:270

B:80

C:100

D:240

答案:240

數(shù)組A中每個元素的長度為3個字節(jié)，行下標(biāo)I從1到8，列下標(biāo)J從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（）。

A:SA＋144

B:SA＋225

C:SA＋222

D:SA＋141

答案:SA＋222

一個n*n的對稱矩陣，如果以行或列為主序放入內(nèi)存，則其所需容量為（）。

A:n*n

B:（n+1）*n／2

C:（n+1）*（n+1）／2

D:n*n／2

答案:（n+1）*n／2

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

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

B:三元組和十字鏈表

C:三元組和散列

D:散列和十字鏈表

答案:三元組和十字鏈表

設(shè)有廣義表D=（a,b,D），則深度為（）。

A:1

B:5

C:∞

D:3

答案:∞

廣義表運(yùn)算式Tail（a，b，（c，d））的操作結(jié)果是（）。

A:（（c，d））

B:d

C:(b,（c，d）)D:c,d

答案:(b,（c，d）)

下面說法不正確的是()。

A:廣義表難以用順序存儲結(jié)構(gòu)

B:廣義表可以是一個多層次的結(jié)構(gòu)

C:廣義表的表頭總是一個廣義表

D:廣義表的表尾總是一個廣義表

答案:廣義表的表頭總是一個廣義表

數(shù)組中存儲的數(shù)，可以是任意類型的任何數(shù)據(jù)。（）

A:對B:錯

答案:錯

數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入，刪除等操作。（）

A:對B:錯

答案:錯

稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。（）

A:對B:錯

答案:對

第六章測試

完全二叉樹中第5層最多有（）個結(jié)點(diǎn)。

A:16

B:31

C:15

D:32

答案:16

高度為6的滿二叉樹中有（）個結(jié)點(diǎn)。

A:63

B:65

C:32

D:31

答案:63

對給定的一組權(quán)值W=｛7，5，12，9，3，6，8｝，構(gòu)造相應(yīng)的哈夫曼樹，計(jì)算它的帶權(quán)路徑長度是（）。

A:137

B:138

C:136

D:135

答案:137

已知二叉樹的先序遍歷結(jié)果為ABECDFGHIJ，中序遍歷結(jié)果為EBCDAHIGFJ，這棵二叉樹的后序遍歷序列為（）。

A:EDGBCIHJFA

B:EDCIHGBJFA

C:EDBJFACIHG

D:EDCBIHGJFA

答案:EDCBIHGJFA

樹和二叉樹的轉(zhuǎn)換是基于樹的（）存儲結(jié)構(gòu)。

A:孩子兄弟表示法

B:雙親兄弟表示法

C:孩子表示法

D:雙親表示法

答案:孩子兄弟表示法

二叉樹一共有三種基本形態(tài)。（）

A:對B:錯

答案:錯

樹的孩子兄弟表示法是一種順序存儲結(jié)構(gòu)。（）

A:對B:錯

答案:錯

二叉單支樹適合采用順序存儲結(jié)構(gòu)。（）

A:錯B:對

答案:錯

哈夫曼編碼中把最短編碼分配給出現(xiàn)頻率最高的字符。（）

A:錯B:對

答案:對

完全二叉樹中，若一個結(jié)點(diǎn)沒有右孩子，則它必然沒有左孩子。（）

A:對B:錯

答案:錯

第七章測試

一個具有n個頂點(diǎn)的圖，最少有（）個連通分量。

A:0

B:n-1

C:1

D:n

答案:1

設(shè)G為一個有向圖，擁有n個頂點(diǎn)，則其所含邊的條數(shù)最多為()。

A:n-1

B:n(n-1)

C:n

D:n(n+1)

答案:n(n-1)

（）的鄰接矩陣是對稱矩陣。

A:無向圖

B:AOE網(wǎng)

C:AOV網(wǎng)

D:有向圖

答案:無向圖

具有7個頂點(diǎn)的有向圖至少應(yīng)有（）條邊才能確保一個強(qiáng)連通圖。

A:7B:6C:8D:9

答案:7

對如圖所示的無向圖，若從頂點(diǎn)V1開始進(jìn)行深度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)序列為（）。

A:1234576

B:1243567

C:1245637

D:1243576

答案:1243576

若在一個有向圖的鄰接矩陣中，主對角線以下的元素均為零，則該圖存在拓?fù)湫蛄校ǎ?/p>

A:錯B:對

答案:對

在一個無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（）倍。

A:1/2

B:3

C:2

D:1

答案:2

對于含有n個頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個（）。

A:由n－1條權(quán)值最小的邊構(gòu)成的子圖。

B:由n－1條權(quán)值之和最小的邊構(gòu)成的子圖。

C:由n－1條權(quán)值之和最小的邊構(gòu)成的連通子圖。

D:由n個頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的無回路的連通子圖。

答案:由n個頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的無回路的連通子圖。

關(guān)鍵路徑是AOE網(wǎng)中（）。

A:從源點(diǎn)至匯點(diǎn)的最長路徑

B:從源點(diǎn)到匯點(diǎn)的最短路徑

C:最短的回路

D:最長的回路

答案:從源點(diǎn)至匯點(diǎn)的最長路徑

最短路徑一定是簡單路徑。（）

A:錯B:對

答案:對

第八章測試

順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。

A:散列存儲

B:壓縮存儲

C:順序存儲或鏈?zhǔn)酱鎯?/p>

D:索引存儲

答案:順序存儲或鏈?zhǔn)酱鎯?/p>

采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為（）。

A:O(n2)

B:O(nlog2n)

C:O(log2n)

D:O(n)

答案:O(log2n)

有一個有序表為（1，5，9，12，28，41，44，55，71，77，80，95，100），當(dāng)采用二分查找值為80的結(jié)點(diǎn)時，（）次比較后查找成功。

A:2

B:1

C:8

D:4

答案:4

設(shè)哈希表長度為11，哈希函數(shù)H(key)=key%11。表中已有4個結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是（）。

A:9

B:8

C:3

D:5

答案:9

有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（）。

A:37/12

B:35/12

C:43/12

D:39/12

答案:37/12

已知10個元素｛51，28，16，73，62，95，60，26，43，79｝，按照依次插入的方法生成一棵二叉排序樹。查找值為95的結(jié)點(diǎn)所需比較的次數(shù)為（）。

A:5

B:4

C:3

D:2

答案:3

在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是哈希表查找方法。（）

A:錯B:對

答案:對

完全二叉樹不一定是平衡二叉樹。（）

A:對B:錯

答案:對

中序遍歷二叉排序樹的結(jié)點(diǎn)能得到排好序的結(jié)點(diǎn)序列。（）

A:錯B:對

答案:對

對線性表