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

第一章測(cè)試數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。

A:錯(cuò)

B:對(duì)

答案:B樹型結(jié)構(gòu)元素之間是（）關(guān)系

A:一對(duì)一

B:沒有關(guān)系

C:多對(duì)多

D:一對(duì)多

答案:D圖或網(wǎng)狀結(jié)構(gòu)元素之間是（）關(guān)系

A:多對(duì)多

B:一對(duì)一

C:沒有關(guān)系

D:一對(duì)多

答案:A計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象統(tǒng)稱為（）。

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

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

C:數(shù)據(jù)對(duì)象

D:數(shù)據(jù)結(jié)構(gòu)

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

A:對(duì)

B:錯(cuò)

答案:B數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（）結(jié)構(gòu)。

A:數(shù)據(jù)元素之間的關(guān)系

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

C:數(shù)據(jù)的邏輯結(jié)構(gòu)

D:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

答案:D在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將其分為（）

A:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

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

C:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

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

答案:B數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。

A:錯(cuò)

B:對(duì)

答案:B事后統(tǒng)計(jì)是利用計(jì)算機(jī)的時(shí)鐘進(jìn)行算法執(zhí)行時(shí)間的統(tǒng)計(jì)

A:對(duì)

B:錯(cuò)

答案:A求解橋梁結(jié)構(gòu)中的應(yīng)用力學(xué)數(shù)學(xué)模型為線性方程組，是數(shù)值計(jì)算問題。

A:對(duì)

B:錯(cuò)

答案:A第二章測(cè)試在線性表數(shù)據(jù)元素的非空有限集中（）。

A:存在惟一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素

B:除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼

C:存在惟一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素

D:除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)

答案:ABCD線性表的（）是指在內(nèi)存中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各元素

A:順序存儲(chǔ)

B:散列存儲(chǔ)

C:索引存儲(chǔ)

D:鏈?zhǔn)酱鎯?chǔ)

答案:A下列符合順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)的是（）

A:做插入或刪除操作時(shí)需移動(dòng)大量元素，效率不高

B:適合做查詢操作

C:只要確定了存儲(chǔ)線性表的起始位置，可以計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址

D:線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）一致

答案:ABCDListsize指示順序表當(dāng)前分配的存儲(chǔ)空間的大小。

A:錯(cuò)

B:對(duì)

答案:B在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。

A:對(duì)

B:錯(cuò)

答案:A在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上一定不相鄰。

A:對(duì)

B:錯(cuò)

答案:A在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

A:對(duì)

B:錯(cuò)

答案:B線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。是n（n≥0）個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。

A:對(duì)

B:錯(cuò)

答案:A在單鏈表中刪除第i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第(i-1)個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。

A:錯(cuò)

B:對(duì)

答案:B雙向鏈表的特點(diǎn)—-表中的每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向后繼結(jié)點(diǎn)，一個(gè)指向前趨結(jié)點(diǎn)。

A:對(duì)

B:錯(cuò)

答案:A第三章測(cè)試循環(huán)隊(duì)列也存在空間溢出問題。

A:對(duì)

B:錯(cuò)

答案:A棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。

A:錯(cuò)

B:對(duì)

答案:B棧和隊(duì)列都是受限的線性結(jié)構(gòu)。

A:錯(cuò)

B:對(duì)

答案:B設(shè)C語(yǔ)言數(shù)組Data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語(yǔ)句為（

）

A:rear=(rear+1)%m

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

C:front=front+1

D:front=（front+1）%m

答案:D棧和隊(duì)列的共同點(diǎn)是（

）。

A:沒有共同點(diǎn)

B:只允許在端點(diǎn)處插入和刪除元素

C:都是先進(jìn)后出

D:都是先進(jìn)先出

答案:B向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行（

）。(不帶空的頭結(jié)點(diǎn))

A:s—＞next=HS;HS=s;

B:s—＞next=HS—＞next;HS—＞next=s;

C:s—＞next=HS;HS=HS—＞next;

D:HS—＞next=s;

答案:A從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（

）。(不帶空的頭結(jié)點(diǎn))

A:x=HS—＞data;HS=HS—＞next;

B:x=HS;HS=HS—＞next;

C:x=HS—＞data;

D:HS=HS—＞next;x=HS—＞data;

答案:A4個(gè)元素進(jìn)S棧的順序是a、b、c、d，進(jìn)行兩次Pop(S,x)操作后，棧頂元素的值是（）

A:b

B:a

C:d

D:c

答案:A順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（）存儲(chǔ)棧元素。

A:變量

B:鏈表

C:數(shù)組

D:循環(huán)鏈表

答案:C經(jīng)過InitStack(s);Push(s,a);Push(s,b);Pop(s)棧的運(yùn)算后，GetTop(s)的值是（）

A:b

B:a

C:1

D:2

答案:B第四章測(cè)試一個(gè)廣義表的表頭總是一個(gè)（）。

A:空表

B:元素

C:元素或廣義表

D:廣義表

答案:C一個(gè)廣義表的表尾總是一個(gè)（）。

A:空表

B:元素或廣義表

C:元素

D:廣義表

答案:D串是一種特殊的線性表，其特殊性體現(xiàn)在（）

A:可以順序存儲(chǔ)

B:可以鏈?zhǔn)酱鎯?chǔ)

C:數(shù)據(jù)元素是一個(gè)字符

D:數(shù)據(jù)元素可以是多個(gè)字符

答案:C設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是（）

A:BCDEFG

B:BCDEFEF

C:BCPQRST

D:BCDEF

答案:B串是任意有限個(gè)（）

A:符號(hào)構(gòu)成的集合

B:符號(hào)構(gòu)成的序列

C:字符構(gòu)成的序列

D:字符構(gòu)成的集合

答案:C對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)可以（）

A:提高矩陣運(yùn)算速度

B:簡(jiǎn)化矩陣運(yùn)算

C:便于對(duì)矩陣元素存取

D:節(jié)省存儲(chǔ)空間

答案:D稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)()

A:aij

B:i,j

C:非零元素

D:三元祖（i,j,aij）

答案:C三角矩陣可壓縮存儲(chǔ)到數(shù)組（）中。

A:M[1:n(n+1)/2]

B:M[n(n+1)/2]

C:M[n(n+1)/2+1]

D:M[1:n(n+1)/2+1]

答案:C設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作()

A:模式匹配

B:求子串

C:求串長(zhǎng)

D:連接

答案:A已知廣義表L=((x,y,z),a,(u,t,w))，從L表中取出的原子項(xiàng)ASCII碼最大的運(yùn)算是（）。

A:head(tail(tail(L)))

B:tail(head(head(tail(L))))

C:head(tail(tail(tail(L))))

D:head(tail(tail(head(L))))

答案:D第五章測(cè)試在一棵深度為h的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于()

A:2^h-1

B:2^(h-1)

C:2^h

D:2^(h+1)

答案:B若二叉樹有14個(gè)節(jié)點(diǎn)且度為1的節(jié)點(diǎn)有5個(gè)，則葉子節(jié)點(diǎn)有()個(gè)

A:4

B:7

C:6

D:5

答案:D在中序線索二叉樹中，若某結(jié)點(diǎn)有右孩子，則該結(jié)點(diǎn)的直接后繼是()。

A:右子樹的最右下結(jié)點(diǎn)

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

C:左子樹的最左下結(jié)點(diǎn)

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

答案:D二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以()

A:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用

B:它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)

C:它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)

D:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)

答案:D某二叉樹以前序遍歷法得到1，2，3，6，4，5，7，8，9，10的訪問順序，以中序遍歷法3，6，2，5，4，1，9，8，10，7的訪問順序，則其后序遍歷法的訪問順序是()

A:5,3,6,4,2,9,10,8,7,1

B:6,3,4,5,9,2,10,7,8,1

C:6,3,5,4,2,9,10,8,7,1

D:6,3,5,2,4,10,9,7,8,1

答案:C前序遍歷和中序遍歷結(jié)果相同的二叉樹為((1));前序遍歷和后序遍歷結(jié)果相同的二叉樹為((2))。

A:根結(jié)點(diǎn)無(wú)右孩子的二叉樹

B:只有根結(jié)點(diǎn)的二叉樹

C:所有結(jié)點(diǎn)只有右孩子的二叉樹

D:一般二叉樹

E:所有結(jié)點(diǎn)只有左孩子的二叉樹

F:根結(jié)點(diǎn)無(wú)左孩子的二叉樹

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

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

B:{00,010,0110,1000

C:{b,c,aa,ac,aba,abb,abc}

D:{0,10,110,1111}

答案:A引入二叉線索樹的目的是（）

A:為了能方便的找到雙親

B:加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度

C:為了能在二叉樹中方便的進(jìn)行插入與刪除

D:使二叉樹的遍歷結(jié)果唯一

答案:B在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（）。

A:右子結(jié)點(diǎn)

B:左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

C:左子結(jié)點(diǎn)

D:左子結(jié)點(diǎn)和右子結(jié)點(diǎn)

答案:D某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。

A:任一結(jié)點(diǎn)無(wú)右子樹

B:空或只有一個(gè)結(jié)點(diǎn)

C:任一結(jié)點(diǎn)無(wú)左子樹

D:高度等于其結(jié)點(diǎn)數(shù)

答案:A第六章測(cè)試有向圖和無(wú)向圖沒有區(qū)別

A:錯(cuò)

B:對(duì)

答案:An個(gè)定點(diǎn)的無(wú)向完全圖有n(n-1)條邊

A:對(duì)

B:錯(cuò)

答案:B連通分量是極大連通子圖

A:錯(cuò)

B:對(duì)

答案:B強(qiáng)連通分量是針對(duì)無(wú)向圖來定義的

A:對(duì)

B:錯(cuò)

答案:B一個(gè)圖的連通分量不可能是自身

A:對(duì)

B:錯(cuò)

答案:B無(wú)向圖的鄰接矩陣一定是對(duì)稱的

A:對(duì)

B:錯(cuò)

答案:A鄰接表的表節(jié)點(diǎn)比十字鏈表的表節(jié)點(diǎn)要復(fù)雜

A:對(duì)

B:錯(cuò)

答案:B圖的遍歷分為長(zhǎng)度優(yōu)先和廣度優(yōu)先

A:錯(cuò)

B:對(duì)

答案:A生成樹只能由深度優(yōu)先生成

A:對(duì)

B:錯(cuò)

答案:B普利姆算法是用來生成最小生成樹的

A:錯(cuò)

B:對(duì)

答案:B關(guān)鍵路徑就是最短路徑

A:對(duì)

B:錯(cuò)

答案:B事件發(fā)生的最早事件和最遲事件一定不相等

A:錯(cuò)

B:對(duì)

答案:A在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)()

A:2n

B:n-2

C:2n-2

D:2n-1

答案:C若用n表示圖中頂點(diǎn)數(shù)目，則有()條邊的無(wú)向圖成為完全圖

A:2n-2

B:n*(n-1)/2

C:2n-1

D:2n

答案:B一個(gè)連通圖的()是一個(gè)極小連通子圖

A:生成樹

B:關(guān)鍵路徑

C:網(wǎng)

D:圖

答案:A具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為()

A:50

B:45

C:36

D:40

答案:B有向圖G的強(qiáng)連通分量是指()連通子圖。

A:極小

B:有向

C:極大

D:無(wú)向

答案:C對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣大小()

A:n10

B:n2

C:n

D:n*n

答案:D圖的廣度優(yōu)先搜索算法，需要的輔助數(shù)據(jù)結(jié)構(gòu)是()

A:棧

B:隊(duì)列

C:滿二叉樹

D:二叉樹

答案:B圖的深度優(yōu)先搜索算法，需要的輔助數(shù)據(jù)結(jié)構(gòu)是()

A:二叉樹

B:棧

C:滿二叉樹

D:隊(duì)列

答案:B第七章測(cè)試依次輸入關(guān)鍵字序列{15,30,50,3,26,20}，構(gòu)建一棵平衡二叉樹，則結(jié)點(diǎn)15的右孩子的關(guān)鍵字是（）。

A:26

B:20

C:不存在

D:3

答案:B

依次輸入關(guān)鍵字序列{15,30,50,3,26,20}，構(gòu)建一棵平衡二叉樹，則根結(jié)點(diǎn)的關(guān)鍵字是（）。

A:26

B:20

C:5

D:15

答案:A對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有幾個(gè)

A:3

B:4

C:1

D:2

答案:B為提高哈希（散列）表的查找效率，可以采用的正確措施是（）。I.增大裝填因子αII.設(shè)計(jì)沖突少的哈希函數(shù)III.處理沖突時(shí)，避免產(chǎn)生“聚集”現(xiàn)象。

A:僅II和III

B:僅II

C:僅I和II

D:僅I

答案:A設(shè)哈希表長(zhǎng)為14，哈希函數(shù)為H(key)=key%11,哈希表中只有4個(gè)元素H(15)=4,H(49)=5,H(50)=6,H(73)=7，若采用線性探測(cè)法解決沖突，則關(guān)鍵字60的元素的地址是（）。

A:8

B:9

C:5

D:3

答案:C如果希望對(duì)二叉排序樹的遍歷結(jié)果是升序的，應(yīng)采用（）遍歷方法。

A:先序

B:層次

C:中序

D:后序

答案:C查找效率最高的二叉排序樹是()。

A:所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹

B:所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。

C:平衡二叉樹

D:所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。

答案:C下列敘述中，不符合m階B-樹定義的是（）。

A:葉子節(jié)點(diǎn)之間通過指針鏈接

B:所有葉子節(jié)點(diǎn)在同一層次上

C:根結(jié)點(diǎn)最多有m棵子樹

D:各節(jié)點(diǎn)內(nèi)的關(guān)鍵字按升序或降序排列

答案:A采用二叉鏈表存儲(chǔ)的二叉排序樹，關(guān)鍵字最大的結(jié)點(diǎn)的（）。

A:左右指針均為空

B:左指針一定為空

C:左右指針均不為空

D:右指針一定為空

答案:D哈希表的平均查找長(zhǎng)度與哈希函數(shù)、處理沖突的方法，以及裝填因子有關(guān)。

A:錯(cuò)

B:對(duì)

答案:B先序遍歷一棵二叉排序樹可以得到一個(gè)關(guān)鍵字升序序列。

A:對(duì)

B:錯(cuò)

答案:B用線性探測(cè)法解決沖突，容易引起“堆積”現(xiàn)象。

A:對(duì)

B:錯(cuò)

答案:A第八章測(cè)試2路歸并排序的時(shí)間復(fù)雜度為（）。

A:O(nlog2n)

B:O(n2)

C:O(1og2n)

D:O(n)

答案:A在待排序的記錄基本有序的前提下，效率最高的排序方法是

A:歸并排序

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

C:直接插入排序

D:快速排序

答案:C以下排序方法中時(shí)間復(fù)雜度是O(nlog2n)且穩(wěn)定的排序方法是（）。

A:堆排序

B:歸并排序

C:直接插入排序

D:快速排序

答案:B時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是

A:希爾排序

B:快速排序

C:冒泡排序

D:堆排序

答案:D快速排序算法最壞情況下的空間復(fù)雜度是（）

A:O(1og2n)

B:O(n)

C:O(n2)

D:O(nlog2n)

答案:B下列4中排序方法中，排序過程中的比較次數(shù)與序列的初始狀態(tài)無(wú)