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

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

A:錯

B:對

答案:B樹型結構元素之間是（）關系

A:一對一

B:沒有關系

C:多對多

D:一對多

答案:D圖或網(wǎng)狀結構元素之間是（）關系

A:多對多

B:一對一

C:沒有關系

D:一對多

答案:A計算機識別、存儲和加工處理的對象統(tǒng)稱為（）。

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

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

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

D:數(shù)據(jù)結構

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

A:對

B:錯

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

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

B:數(shù)據(jù)結構

C:數(shù)據(jù)的邏輯結構

D:數(shù)據(jù)的存儲結構

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

A:緊湊結構和非緊湊結構

B:線性結構和非線性結構

C:內(nèi)部結構和外部結構

D:動態(tài)結構和靜態(tài)結構

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

A:錯

B:對

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

A:對

B:錯

答案:A求解橋梁結構中的應用力學數(shù)學模型為線性方程組，是數(shù)值計算問題。

A:對

B:錯

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

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

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

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

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

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

A:順序存儲

B:散列存儲

C:索引存儲

D:鏈式存儲

答案:A下列符合順序存儲結構的特點的是（）

A:做插入或刪除操作時需移動大量元素，效率不高

B:適合做查詢操作

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

D:線性表的邏輯結構與存儲結構（物理結構）一致

答案:ABCDListsize指示順序表當前分配的存儲空間的大小。

A:錯

B:對

答案:B在線性表的順序存儲結構中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關。

A:對

B:錯

答案:A在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上一定不相鄰。

A:對

B:錯

答案:A在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

答案:B雙向鏈表的特點—-表中的每個結點有兩個指針域，一個指向后繼結點，一個指向前趨結點。

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

答案:B棧和隊列都是受限的線性結構。

A:錯

B:對

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

）

A:rear=(rear+1)%m

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

C:front=front+1

D:front=（front+1）%m

答案:D棧和隊列的共同點是（

）。

A:沒有共同點

B:只允許在端點處插入和刪除元素

C:都是先進后出

D:都是先進先出

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

）。(不帶空的頭結點)

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從一個棧頂指針為HS的鏈棧中刪除一個結點時，用x保存被刪結點的值，則執(zhí)行（

）。(不帶空的頭結點)

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個元素進S棧的順序是a、b、c、d，進行兩次Pop(S,x)操作后，棧頂元素的值是（）

A:b

B:a

C:d

D:c

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

A:變量

B:鏈表

C:數(shù)組

D:循環(huán)鏈表

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

A:b

B:a

C:1

D:2

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

A:空表

B:元素

C:元素或廣義表

D:廣義表

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

A:空表

B:元素或廣義表

C:元素

D:廣義表

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

A:可以順序存儲

B:可以鏈式存儲

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

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

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

A:BCDEFG

B:BCDEFEF

C:BCPQRST

D:BCDEF

答案:B串是任意有限個（）

A:符號構成的集合

B:符號構成的序列

C:字符構成的序列

D:字符構成的集合

答案:C對稀疏矩陣進行壓縮存儲可以（）

A:提高矩陣運算速度

B:簡化矩陣運算

C:便于對矩陣元素存取

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

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

A:aij

B:i,j

C:非零元素

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

答案:C三角矩陣可壓縮存儲到數(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設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作()

A:模式匹配

B:求子串

C:求串長

D:連接

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

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

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

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

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

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

A:2^h-1

B:2^(h-1)

C:2^h

D:2^(h+1)

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

A:4

B:7

C:6

D:5

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

A:右子樹的最右下結點

B:左子樹的最右下結點

C:左子樹的最左下結點

D:右子樹的最左下結點

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

A:順序存儲結構和鏈式存儲結構都不能使用

B:它不能用順序存儲結構存儲

C:它不能用鏈式存儲結構存儲

D:順序存儲結構和鏈式存儲結構都能存儲

答案: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前序遍歷和中序遍歷結果相同的二叉樹為((1));前序遍歷和后序遍歷結果相同的二叉樹為((2))。

A:根結點無右孩子的二叉樹

B:只有根結點的二叉樹

C:所有結點只有右孩子的二叉樹

D:一般二叉樹

E:所有結點只有左孩子的二叉樹

F:根結點無左孩子的二叉樹

答案:BC下面幾個符號串編碼集合中，不是前綴編碼的是（）。

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:加快查找結點的前驅(qū)或后繼的速度

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

D:使二叉樹的遍歷結果唯一

答案:B在完全二叉樹中，若一個結點是葉結點，則它沒（）。

A:右子結點

B:左子結點，右子結點和兄弟結點

C:左子結點

D:左子結點和右子結點

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

A:任一結點無右子樹

B:空或只有一個結點

C:任一結點無左子樹

D:高度等于其結點數(shù)

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

A:錯

B:對

答案:An個定點的無向完全圖有n(n-1)條邊

A:對

B:錯

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

A:錯

B:對

答案:B強連通分量是針對無向圖來定義的

A:對

B:錯

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

A:對

B:錯

答案:B無向圖的鄰接矩陣一定是對稱的

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

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

A:對

B:錯

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

A:錯

B:對

答案:B關鍵路徑就是最短路徑

A:對

B:錯

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

A:錯

B:對

答案:A在有n個頂點的有向圖中，每個頂點的度最大可達()

A:2n

B:n-2

C:2n-2

D:2n-1

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

A:2n-2

B:n*(n-1)/2

C:2n-1

D:2n

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

A:生成樹

B:關鍵路徑

C:網(wǎng)

D:圖

答案:A具有10個頂點的無向圖，邊的總數(shù)最多為()

A:50

B:45

C:36

D:40

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

A:極小

B:有向

C:極大

D:無向

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

A:n10

B:n2

C:n

D:n*n

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

A:棧

B:隊列

C:滿二叉樹

D:二叉樹

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

A:二叉樹

B:棧

C:滿二叉樹

D:隊列

答案:B第七章測試依次輸入關鍵字序列{15,30,50,3,26,20}，構建一棵平衡二叉樹，則結點15的右孩子的關鍵字是（）。

A:26

B:20

C:不存在

D:3

答案:B

依次輸入關鍵字序列{15,30,50,3,26,20}，構建一棵平衡二叉樹，則根結點的關鍵字是（）。

A:26

B:20

C:5

D:15

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

A:3

B:4

C:1

D:2

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

A:僅II和III

B:僅II

C:僅I和II

D:僅I

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

A:8

B:9

C:5

D:3

答案:C如果希望對二叉排序樹的遍歷結果是升序的，應采用（）遍歷方法。

A:先序

B:層次

C:中序

D:后序

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

A:所有結點的右子樹都為空的二叉排序樹

B:所有結點的左子樹都為空的二叉排序樹。

C:平衡二叉樹

D:所有結點的右子樹都為空的二叉排序樹。

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

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

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

C:根結點最多有m棵子樹

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

答案:A采用二叉鏈表存儲的二叉排序樹，關鍵字最大的結點的（）。

A:左右指針均為空

B:左指針一定為空

C:左右指針均不為空

D:右指針一定為空

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

A:錯

B:對

答案:B先序遍歷一棵二叉排序樹可以得到一個關鍵字升序序列。

A:對

B:錯

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

A:對

B:錯

答案:A第八章測試2路歸并排序的時間復雜度為（）。

A:O(nlog2n)

B:O(n2)

C:O(1og2n)

D:O(n)

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

A:歸并排序

B:簡單選擇排序

C:直接插入排序

D:快速排序

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

A:堆排序

B:歸并排序

C:直接插入排序

D:快速排序

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

A:希爾排序

B:快速排序

C:冒泡排序

D:堆排序

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

A:O(1og2n)

B:O(n)

C:O(n2)

D:O(nlog2n)

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