數(shù)據(jù)結(jié)構(gòu)（A）智慧樹知到課后章節(jié)答案2023年下山東理工大學(xué)

數(shù)據(jù)結(jié)構(gòu)（A）智慧樹知到課后章節(jié)答案2023年下山東理工大學(xué)山東理工大學(xué)

第一章測試

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

A:對B:錯

答案:錯

數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。（）

A:錯B:對

答案:錯

順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）

A:錯B:對

答案:錯

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

A:錯B:對

答案:錯

邏輯結(jié)構(gòu)是（）關(guān)系的整體。（）

A:數(shù)據(jù)元素之間邏輯

B:數(shù)據(jù)項之間邏輯

C:存儲結(jié)構(gòu)之間

D:數(shù)據(jù)類型之間

答案:數(shù)據(jù)元素之間邏輯

數(shù)據(jù)結(jié)構(gòu)有（）種基本邏輯結(jié)構(gòu)。（）

A:2

B:1

C:3

D:4

答案:4

下列四種基本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（）。

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

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

C:集合

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

答案:集合

從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。（）

A:動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

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

C:順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

D:初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

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

for（i=0；i＜n；i++）

c[i][i]=i+i算法的時間復(fù)雜度是（）。

A:O(n2)

B:O(log2n)

C:O(1)

D:O(n)

答案:O(n)

下列時間復(fù)雜度中最好的是（）。

A:O(n)

B:O(1)

C:O(n2)

D:O(log2n)

答案:O(1)

第二章測試

對任何數(shù)據(jù)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（）

A:錯B:對

答案:錯

循環(huán)鏈表不是線性表。（）

A:錯B:對

答案:錯

在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的指針即可；因此，單鏈表是一種隨機存儲結(jié)構(gòu)。（）

A:錯B:對

答案:錯

順序存儲的線性表可以隨機存取。（）

A:錯B:對

答案:對

帶頭結(jié)點的單鏈表（以head為頭指針）為空判斷條件是（）。

A:head!=NULL

B:head==NULL

C:head-＞next==head

D:head-＞next==NULL

答案:head-＞next==NULL

在單鏈表中，一個結(jié)點有（）個指針。（）

A:2

B:4

C:3

D:1

答案:1

對于只在表的首尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為（）。

A:用頭指針表示的單循環(huán)鏈表

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

C:單鏈表

D:順序表

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

在一個以h為頭指針的單循環(huán)鏈中，p指針指向鏈尾的條件是：（）。

A:p-＞next-＞next=h

B:p-＞next=NIL

C:p-＞next=h

D:p-＞data=-1

答案:p-＞next=h

P和q兩個指針分別指向雙向循環(huán)鏈表L的兩個結(jié)點，p所指結(jié)點是q所指結(jié)點后繼的條件是（）。

A:q-＞next==p-＞next

B:p==q

C:p-＞next==q

D:q-＞next==p

答案:q-＞next==p

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

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

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

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

D:單鏈表

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

第三章測試

若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1。（）

A:錯B:對

答案:對

兩個棧共用靜態(tài)存儲空間，相向增長使用，也存在空間溢出問題。（）

A:對B:錯

答案:對

隊列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（）

A:錯B:對

答案:錯

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

A:錯B:對

答案:對

某棧的輸入序列為a,b，c，d，下面的四個序列中，不可能是它的輸出序列的是：（）。

A:b,c，d，a

B:a，c，b，d

C:c,d，b,a

D:d,c，a，b

答案:d,c，a，b

一個遞歸算法必須包括：（）。

A:終止條件和迭代部分

B:迭代部分

C:終止條件和遞歸部分

D:遞歸部分

答案:終止條件和遞歸部分

中綴表達(dá)式A-(B+C／D)*E的后綴形式是：（）。

A:ABCD/E*+

B:ABCD／+E*

C:AB-C+D／E*

D:ABC+D/-E*

答案:ABCD／+E*

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

A:1和5

B:4和2

C:5和1

D:2和4

答案:2和4

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

A:棧

B:線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

C:隊列

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

答案:棧

經(jīng)過InitStack（S）；Push（S，a）；Push（S，b）；Pop（S，x）；Pop（S，x）；的運算后EmptyStack（S）的值是（）。

A:1

B:0

C:b

D:a

答案:1

第四章測試

KMP算法的特點是在模式匹配時指示主串的整型指針值不會減小。（）

A:對B:錯

答案:對

設(shè)有兩個串P和Q，其中Q是P的子串，把Q在P中首次出現(xiàn)的位置作為子串Q在P中的位置的算法稱為模式匹配。（）

A:對B:錯

答案:對

INDEX（‘DATASTRUCTURE’，‘STR’）=4。（）

A:錯B:對

答案:錯

空串是零個字符的串，其長度等于零。（）

A:對B:錯

答案:對

已知U=‘xyxyxyxxyxy’；t=‘xxy’；

ASSIGN（S，U）；

ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；

ASSIGN（m，‘ww’）

求REPLACE（S，V，m）=‘xyxyxywwy’。（）

A:錯B:對

答案:對

設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復(fù)雜度可達(dá)到O(n+m)。（）

A:錯B:對

答案:對

字符串’ababaaab’的nextval函數(shù)值為01010421。（）

A:錯B:對

答案:對

串又稱字符串，（）。

A:串中可以含有空格字符

B:串中元素只能是字符

C:串中元素只能是字母

D:串長度不為零

答案:串中元素只能是字符

模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（）。

A:01112211123456712

B:01112231123456712

C:01110013101100701

D:01112121123456112

答案:01112231123456712

模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的nextval數(shù)組的值為（）。

A:01102131011021701

B:01110013101100701

C:01112231123456712

D:01100111011001701

答案:01102131011021701

第五章測試

對于數(shù)組的操作，最常見的兩種是（）

A:索引和修改

B:查找和修改

C:查找和索引

D:建立和刪除

答案:查找和修改

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

A:三元組和十字鏈表

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

C:散列和十字鏈表

D:三元組和散列

答案:三元組和十字鏈表

若將n階下三角矩陣A按列優(yōu)先順序壓縮存放在一維數(shù)組B[1...n(n+1)/2+1]中，則存放到B[k]中的非零元素aij(1≤i,j≤n）的下標(biāo)i,j與k的對應(yīng)關(guān)系是（)。

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

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

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

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

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

有一個n的對稱矩陣A，將其下三角部分按行存放在一維數(shù)組B中，而A[0][0存放于B[0]中，則第i行的對角元素A[i][i]存放于B中的（）處。（）

A:(2n-i-1)i/2

B:(i+3)i/2

C:(i+1)i/2

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

答案:(i+3)i/2

數(shù)組A中，每個元素的長度為3B，行下標(biāo)i從0~7，列下標(biāo)j從0~9，從首地址開始連續(xù)存放在存儲器內(nèi)，則存放該數(shù)組至少需要的單元數(shù)是（）。

A:240

B:270

C:80

D:100

答案:240

設(shè)有一個12×12的對稱矩陣M，將其上三角部分的元素mi,j(1＜i≤j≤12)按行優(yōu)先存入C語言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是()。

A:66

B:51

C:55

D:50

答案:50

已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是()。

A:head(tail(LS))

B:head(tail(tail(head(LS))))

C:tail(head(LS))

D:head(tail(head(tail(LS)))

答案:head(tail(head(tail(LS)))

廣義表（（a,b,c,d））的表尾是（）。

A:（）

B:（a,b,c,d）

C:（b,c,d）

D:a

答案:（a,b,c,d）

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

A:1和1

B:1和2

C:1和3

D:2和3

答案:1和2

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

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

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

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

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

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

第六章測試

一棵有n個結(jié)點的樹的所有結(jié)點的度數(shù)之和為（）

A:2n

B:n-1

C:n

D:n+1

答案:n-1

對于一棵具有n個結(jié)點、度為4的樹來說，()

A:至少在某一層上正好有4個結(jié)點

B:樹的高度至多是n-3

C:第i層上至多有4(i-1)個結(jié)點

D:樹的高度至多是n-4

答案:樹的高度至多是n-3

假定―棵度為3的樹中，結(jié)點數(shù)為50，則其最小高度為（）

A:3

B:4

C:6

D:5

答案:5

一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）

A:10~1024

B:11

C:11~1025

D:10

答案:11~1025

設(shè)一棵非空完全二叉樹T的所有葉結(jié)點均位于同一層，且每個非葉結(jié)點都有2個子結(jié)點。若T有k個葉結(jié)點，則T的結(jié)點總數(shù)是（）

A:2k

B:2k-1

C:k2

D:2k+1

答案:2k-1

在任何一棵二叉樹中，若結(jié)點a有左孩子b、右孩子c，則在結(jié)點的先序序列、中序序列、

后序序列中，()。

A:結(jié)點b一定在結(jié)點a的前面

B:結(jié)點α一定在結(jié)點b的前面

C:結(jié)點b一定在結(jié)點c的前面

D:結(jié)點a一定在結(jié)點c的前面

答案:結(jié)點b一定在結(jié)點c的前面

若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹的中序遍歷序列不會是()。

A:3,2,4,1

B:2,3,4,1

C:1,2,3,4

D:4,3,2,1

答案:3,2,4,1

某二叉樹的樹形所示，其后序序列為e，a，c，b，d，g，f，樹中與結(jié)點a同層的結(jié)點是（）。

A:f

B:g

C:d

D:c

答案:d

所示的二叉樹進(jìn)行中序線索化，則結(jié)點X的左、右線索指向的結(jié)點分別是（）。

A:d,c

B:e,a

C:e,c

D:b,a

答案:b,a

先序序列為a,b,c,d的不同二叉樹的個數(shù)是（）。

A:16

B:13

C:14

D:15

答案:14

若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）。

A:X的左子樹中最右葉結(jié)點

B:X的右子樹中最左的結(jié)點

C:X的左子樹中最右結(jié)點

D:X的雙親

答案:X的左子樹中最右葉結(jié)點

設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹結(jié)點個

數(shù)為n，森林F中第一棵樹的結(jié)點個數(shù)是（）。

A:n+l

B:m-n

C:條件不足，無法確定

D:m-n-1

答案:m-n

將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點的個數(shù)等于()。

A:T中左孩子指針為空的結(jié)點個數(shù)

B:T中度為1的結(jié)點個數(shù)

C:T中右孩子指針為空的結(jié)點個數(shù)

D:T中葉結(jié)點的個數(shù)

答案:T中左孩子指針為空的結(jié)點個數(shù)

若森林F有15條邊、25個結(jié)點，則F包含樹的個數(shù)是（）。

A:8

B:11

C:9

D:10

答案:10

n(n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中錯誤的是（）。

A:樹中一定沒有度為1的結(jié)點

B:樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值

C:樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點

D:該樹一定是一棵完全二叉樹

答案:該樹一定是一棵完全二叉樹

給定整數(shù)集合{3,5,6,9,12}，與之對應(yīng)的哈夫曼樹是（）

A:如圖B

B:如圖A

C:如圖C

D:如圖D

答案:如圖C

對n個互不相同的符號進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115個結(jié)點，則n的值是（）。

A:60

B:57

C:58

D:56

答案:58

若將一棵樹T轉(zhuǎn)化為對應(yīng)的二叉樹BT，則不列對BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是（）。

A:按層遍歷

B:先序遍歷

C:后序遍歷

D:中序遍歷

答案:中序遍歷

在森林的二叉樹表示中，結(jié)點M和結(jié)點N是同一父結(jié)點的左兒子和右心子，則在該森林中().

A:M和N有同一雙親

B:M和N可能無公共祖先

C:M是N的兒子

D:M是N的左兄弟

答案:M和N可能無公共祖先

某二叉樹結(jié)點的中序序列為BDAECF，后序序列為DBEFCA，則該二叉樹對應(yīng)的森林包括（）棵樹。（）

A:4

B:3

C:2

D:1

答案:3

第七章測試

十字鏈表是無向圖的一種存儲結(jié)構(gòu)。（）

A:錯B:對

答案:錯

要連通具有n個頂點的有向圖，至少需要n條弧。（）

A:錯B:對

答案:對

若連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹是唯一的。（）

A:錯B:對

答案:對

給定有權(quán)無向圖的鄰接矩陣如下，其最小生成樹的總權(quán)重是（）。

A:18

B:23

C:24

D:17

答案:23

圖中關(guān)于路徑的定義是（）。

A:其他定義都不是。

B:由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列。

C:由不同頂點所形成的序列。

D:由不同邊所形成的序列。

答案:由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列。

下列哪一種圖的鄰接矩陣是對稱矩陣？（）

A:有向圖

B:無向圖

C:AOV網(wǎng)

D:AOE網(wǎng)

答案:無向圖

在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（）倍。

A:1

B:1/2

C:4

D:2

答案:1

無向圖G=(V，E)，其中：V={a，b，c，d，e，f}E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。

A:a,e,d,f,c,b

B:a,e,b,c,f,d

C:a,c,f,e,b,d

D:a,b,e,c,d,f

答案:a,e,d,f,c,b

下面關(guān)于求關(guān)鍵路徑的說法不正確的是（）。

A:關(guān)鍵活動一定位于關(guān)鍵路徑上。

B:一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差。

C:求關(guān)鍵路徑是以拓?fù)渑判驗榛A(chǔ)的。

D:一個事件的最早開始時間和以該事件為尾的弧的活動最早開始時間相同。

答案:一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差。

圖G有n個頂點，求其最短路徑的Dijkstra算法的時間復(fù)雜度為（）

A:O（n+e）

B:O（n）

C:O（n2）

D:O（n3）

答案:O（n3）

第八章測試

中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。（）

A:錯B:對

答案:對

哈希表的查找效率主要取決于哈希表造表時選取的哈希函數(shù)和處理沖突的方法。（）

A:對B:錯

答案:對

二叉排序樹的查找和折半查找時間的性能相同。（）

A:對B:錯

答案:錯

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

A:對B:錯

答案:對

散列法存儲的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。（）

A:對B:錯

答案:對

折半查找是先確定待查有序表記錄的范圍，然后逐步縮小范圍，直到找到或找不到該記錄為止。（）

A:錯B:對

答案:對

若根據(jù)查找表建立長度為m的閉散列表并采用二次探測處理沖突，假定對一個元素第一次計算的散列地址為d，則第4次計算的散列地址為（）

A:(d+4)％m

B:(d+l)％m

C:(d--4)％m

D:(d--1)％m

答案:(d+4)％m

若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（）

A:采用順序存儲結(jié)構(gòu)

B:元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

C:元素按值有序

D:元素按值有序，且采用順序存儲結(jié)構(gòu)

答案:元素按值有序，且采用順序存儲結(jié)構(gòu)

下面關(guān)于二叉排序樹論述中，錯誤的是（）

A:當(dāng)所有結(jié)點的權(quán)值都相等時，用這些結(jié)點構(gòu)造的二叉排序樹除根結(jié)點外只有右子樹

B:中序遍歷二叉排序樹的結(jié)點就可以得到排好序的結(jié)點序列

C:對兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹，按中序遍歷得到的序列是一樣的

D:任一二叉排序樹的平均查找時間都小于用順序查找法查找同樣結(jié)點的線性表的平均查找時間

答案:任一二叉排序樹的平均查找時間都小于用順序查找法查找同樣結(jié)點的線性表的平均查找時間

在一棵平衡二叉樹中，每個結(jié)點的平衡因子取值范圍是（）

A:-2～2

B:-1～l

C:0～l

D:1～2

答案:-1～l

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

A:3

B:8

C:5

D:9

答案:9

在順序表(n足夠大)中進(jìn)行順序查找，其查找不成功的平均長度是（）

A:+1

B:(n+1)／2

C:n+1

D:n

答案:n+1

在一個具有n個結(jié)點的單鏈表中查找值為m的某結(jié)點，若查找成功，則平均比較（）個結(jié)點。

A:n

B:(n-1)/2

C:n／2

D:(n+l)/2

答案:(n+l)/2

第九章測試

有一小根堆，堆中任意結(jié)點的關(guān)鍵字均小于它的左、右孩子關(guān)鍵字。則其具有最大值的結(jié)點一定是一個葉結(jié)點并可能在堆的最后兩層中。（）

A:對B:錯

答案:對

堆