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

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

A:對(duì)

B:錯(cuò)

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

A:錯(cuò)

B:對(duì)

答案:A順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

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

A:存儲(chǔ)結(jié)構(gòu)之間

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

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

D:數(shù)據(jù)項(xiàng)之間邏輯

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

A:3

B:1

C:2

D:4

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

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

B:集合

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

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

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

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

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

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

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

答案:Bfor（i=0；i＜n；i++）c[i][i]=i+i算法的時(shí)間復(fù)雜度是（）。

A:O(n)

B:O(n2)

C:O(1)

D:O(log2n)

答案:A下列時(shí)間復(fù)雜度中最好的是（）。

A:O(n)

B:O(log2n)

C:O(n2)

D:O(1)

答案:D第二章測試對(duì)任何數(shù)據(jù)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）

A:錯(cuò)

B:對(duì)

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

A:錯(cuò)

B:對(duì)

答案:A在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的指針即可；因此，單鏈表是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。（）

A:錯(cuò)

B:對(duì)

答案:A順序存儲(chǔ)的線性表可以隨機(jī)存取。（）

A:錯(cuò)

B:對(duì)

答案:B帶頭結(jié)點(diǎn)的單鏈表（以head為頭指針）為空判斷條件是（）。

A:head==NULL

B:head-＞next==NULL

C:head!=NULL

D:head-＞next==head

答案:B在單鏈表中，一個(gè)結(jié)點(diǎn)有（）個(gè)指針。（）

A:2

B:3

C:4

D:1

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

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

B:順序表

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

D:單鏈表

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

A:p-＞next=NIL

B:p-＞next-＞next=h

C:p-＞next=h

D:p-＞data=-1

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

A:p==q

B:p-＞next==q

C:q-＞next==p-＞next

D:q-＞next==p

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

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

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

C:單鏈表

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

答案:B第三章測試若輸入序列為1,2,3,4,5,6,則通過一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1。（）

A:錯(cuò)

B:對(duì)

答案:B兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，相向增長使用，也存在空間溢出問題。（）

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

答案:A某棧的輸入序列為a,b，c，d，下面的四個(gè)序列中，不可能是它的輸出序列的是：（）。

A:a，c，b，d

B:d,c，a，b

C:c,d，b,a

D:b,c，d，a

答案:B一個(gè)遞歸算法必須包括：（）。

A:終止條件和迭代部分

B:遞歸部分

C:迭代部分

D:終止條件和遞歸部分

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

A:ABCD／+E

B:AB-C+D／E*

C:ABC+D/-E*

D:ABCD/E*+

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

A:1和5

B:4和2

C:5和1

D:2和4

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

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

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

C:隊(duì)列

D:棧

答案:D經(jīng)過InitStack（S）；Push（S，a）；Push（S，b）；Pop（S，x）；Pop（S，x）；的運(yùn)算后EmptyStack（S）的值是（）。

A:a

B:1

C:0

D:b

答案:B第四章測試KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的整型指針值不會(huì)減小。（）

A:錯(cuò)

B:對(duì)

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

A:對(duì)

B:錯(cuò)

答案:AINDEX（‘DATASTRUCTURE’，‘STR’）=4。（）

A:對(duì)

B:錯(cuò)

答案:B空串是零個(gè)字符的串，其長度等于零。（）

A:對(duì)

B:錯(cuò)

答案:A已知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:對(duì)

B:錯(cuò)

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

A:錯(cuò)

B:對(duì)

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

A:錯(cuò)

B:對(duì)

答案:B串又稱字符串，（）。

A:串中元素只能是字符

B:串長度不為零

C:串中元素只能是字母

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

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

A:01110013101100701

B:01112211123456712

C:01112231123456712

D:01112121123456112

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

A:01112231123456712

B:01110013101100701

C:01102131011021701

D:01100111011001701

答案:C第五章測試對(duì)于數(shù)組的操作，最常見的兩種是（）

A:查找和索引

B:查找和修改

C:建立和刪除

D:索引和修改

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

A:三元組和十字鏈表

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

C:散列和十字鏈表

D:三元組和散列

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

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

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

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

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

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

A:(i+3)i/2

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

C:(i+1)i/2

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

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

A:240

B:100

C:270

D:80

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

A:50

B:55

C:51

D:66

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

A:head(tail(head(tail(LS)))

B:tail(head(LS))

C:head(tail(LS))

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

答案:A廣義表（（a,b,c,d））的表尾是（）。

A:（）

B:（a,b,c,d）

C:a

D:（b,c,d）

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

A:2和3

B:1和1

C:1和3

D:1和2

答案:D下面說法不正確的是()。

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

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

C:廣義表的表頭總是一個(gè)廣義表

D:廣義表的表尾總是一個(gè)廣義表

答案:C第六章測試一棵有n個(gè)結(jié)點(diǎn)的樹的所有結(jié)點(diǎn)的度數(shù)之和為（）

A:2n

B:n

C:n-1

D:n+1

答案:C對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為4的樹來說，()

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

B:第i層上至多有4(i-1)個(gè)結(jié)點(diǎn)

C:至少在某一層上正好有4個(gè)結(jié)點(diǎn)

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

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

A:6

B:5

C:3

D:4

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

A:10~1024

B:11

C:11~1025

D:10

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

A:k2

B:2k

C:2k+1

D:2k-1

答案:D在任何一棵二叉樹中，若結(jié)點(diǎn)a有左孩子b、右孩子c，則在結(jié)點(diǎn)的先序序列、中序序列、后序序列中，()。

A:結(jié)點(diǎn)a一定在結(jié)點(diǎn)c的前面

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

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

D:結(jié)點(diǎn)b一定在結(jié)點(diǎn)a的前面

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

A:1,2,3,4

B:4,3,2,1

C:2,3,4,1

D:3,2,4,1

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

A:g

B:c

C:d

D:f

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

A:d,c

B:b,a

C:e,a

D:e,c

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

A:15

B:14

C:13

D:16

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

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

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

C:X的雙親

D:X的右子樹中最左的結(jié)點(diǎn)

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

A:條件不足，無法確定

B:m-n-1

C:n+l

D:m-n

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

A:T中右孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)

B:T中葉結(jié)點(diǎn)的個(gè)數(shù)

C:T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)

D:T中度為1的結(jié)點(diǎn)個(gè)數(shù)

答案:C若森林F有15條邊、25個(gè)結(jié)點(diǎn)，則F包含樹的個(gè)數(shù)是（）。

A:11

B:9

C:8

D:10

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

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

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

C:樹中一定沒有度為1的結(jié)點(diǎn)

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

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

A:如圖B

B:如圖A

C:如圖D

D:如圖C

答案:D對(duì)n個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115個(gè)結(jié)點(diǎn)，則n的值是（）。

A:57

B:60

C:56

D:58

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

A:中序遍歷

B:先序遍歷

C:后序遍歷

D:按層遍歷

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

A:M是N的兒子

B:M是N的左兄弟

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

D:M和N有同一雙親

答案:C某二叉樹結(jié)點(diǎn)的中序序列為BDAECF，后序序列為DBEFCA，則該二叉樹對(duì)應(yīng)的森林包括（）棵樹。（）

A:1

B:3

C:2

D:4

答案:B第七章測試十字鏈表是無向圖的一種存儲(chǔ)結(jié)構(gòu)。（）

A:對(duì)

B:錯(cuò)

答案:B要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要n條弧。（）

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

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

A:17

B:23

C:18

D:24

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

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

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

C:其他定義都不是。

D:由不同頂點(diǎn)所形成的序列。

答案:B下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（）

A:有向圖

B:AOV網(wǎng)

C:AOE網(wǎng)

D:無向圖

答案:D在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。

A:1/2

B:4

C:2

D:1

答案:D無向圖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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。

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

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

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

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

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

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

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

C:一個(gè)事件的最早開始時(shí)間和以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同。

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

答案:B圖G有n個(gè)頂點(diǎn)，求其最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為（）

A:O（n）

B:O（n2）

C:O（n3）

D:O（n+e）

答案:C第八章測試中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（）

A:錯(cuò)

B:對(duì)

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

A:錯(cuò)

B:對(duì)

答案:B二叉排序樹的查找和折半查找時(shí)間的性能相同。（）

A:錯(cuò)

B:對(duì)

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

A:錯(cuò)

B:對(duì)

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

A:錯(cuò)

B:對(duì)

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

A:對(duì)

B:錯(cuò)

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

A:(d+l)％m

B:(d–4)％m

C:(d–1)％m

D:(d+4)％m

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

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

B:元素按值有序

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

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

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

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

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

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

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

答案:D在一棵平衡二叉樹中，每個(gè)結(jié)點(diǎn)的平衡因子取值范圍是（）

A:1～2

B:-2～2

C:0～l

D:-1～l

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

A:9

B:3

C:5

D:8

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

A:(n+1)／2

B:n

C:+1

D:n+1

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

A:(n+l)/2

B:(n-1)/2

C:n

D:n／2

答案:A第九章測試有一小根堆，堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左、右孩子關(guān)鍵字。則其具有最大值的結(jié)點(diǎn)一定是一個(gè)葉結(jié)點(diǎn)并可能在堆的最后兩層中。（）

A:對(duì)

B:錯(cuò)

答案:A堆排序所需時(shí)間與待排序記錄的個(gè)數(shù)無