石大 《數(shù)據(jù)結(jié)構(gòu)》 在線作業(yè)試題題庫及參考答案

注：找到所考試題直接看該試題所有題目和答案即可。

查找按鍵：Ctrl+F

1(5.0分)最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的

條件是()

A)(rear+1)%n=front

B)rear=front

C)rear+l=front

D)(rear-1)%n=front

參考答案：B

2(5.0分)在有序表中使用折半查找法的平均時間是()

A)0(1)B)0(n)C)O(log2n)D)0(n2)參考答案：C

3(5.0分)用堆棧求算術(shù)表達式ab*(c-d)-e/f的后綴表達式為()

A)abed-*ef/-

B)ab*(c-d)-e/f

C)abedef-*/-

D)abc-d*ef/-

參考答案：A

4(5.0分)以下說法錯誤的是()

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

B)散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。

C)裝填因子是散列法的一個重要參數(shù)，它反映散列表的裝填程度。

D)散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理沖突的

方法。

參考答案：B

5(5.0分)已知廣義表LS=((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中元素e

的運算是()

A)head(tail(LS))B)tail(head(LS))C)head(tail(head(tail(LS))))D)

head(tail(tail(head(LS))))參考答案：C

6（5.0分）在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的

語句是（）

A）p=p-＞；next；

B）p-＞；next=p-＞；next-＞；next；

C）p-＞；next=p；

D）p=p-＞；next-＞；next；

參考答案：B

7（5.0分）在最好和最壞情況下的時間復(fù)雜度均為O（nlogn）且穩(wěn)定的排序方法是

（）

A）快速排序

B）堆排序

C）歸并排序

D）基數(shù)排序

參考答案：C

8（5.0分）在順序存儲（空間大小為m）的循環(huán)隊列q中，下列判滿正確的是

（）

A）q.front%m=0；

B）q.rear%m=0；

C）q.front=q.rear；

D）（q.front+1）%m=q.rear；

參考答案：D

9（5.0分）已知含10個結(jié)點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在

等概率情況下查找成功的平均查找長度等于（）

A）1.0

B）2.9

C）3.4

D）5.5

參考答案：B

10（5.0分）以下判斷不正確的是（）

A)順序存儲的線性表可隨機存取。

B)同一線性表中的數(shù)據(jù)元素應(yīng)具有相同的特性。

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

D)在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定

相鄰。

參考答案：C

11(5.0分)在線索二叉樹中，t所指結(jié)點沒有左子樹的充要條件是()

A)t->lchild!=NULL

B)t->ltag==l

C)t->ltag==l且t->left!=NULL

D)以上都不對

參考答案：C

12(5.0分)已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運算的結(jié)果：

tail(head(tail(C)))=()A)(a)

B)A

C)(b)D)(A)參考答案：D

13(5.0分)以下說法錯誤的是()

A)對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后操作而掃描整個循環(huán)

鏈表。

B)對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點。

C)雙鏈表的特點是找結(jié)點的前趨和后繼都很容易。

D)對雙鏈表來說，結(jié)點*P的存儲位置既存放在其前趨結(jié)點的后繼指針域

中，也存放在它的后繼結(jié)點的前趨指針域中。

參考答案：A

14(5.0分)在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置

(),在鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置()

A)必相鄰必相鄰

B)必相鄰不一定相鄰

C)不一定相鄰必相鄰

D）不一定相鄰不一定相鄰

參考答案：B

15（5.0分）以下說法錯誤的是（）

A）哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近

B）若一個二叉樹的樹葉是某子樹中序遍歷序列中的第一個結(jié)點，則它必是該

子樹后序遍歷序列中的第一個結(jié)點

C）已知二叉樹的前序遍歷和后序遍歷并不能唯一地確定這棵樹，因為不知道

樹的根結(jié)點是哪一個

D）前序遍歷二叉樹的序列中，任何結(jié)點其子樹的所有結(jié)點都是直接跟在該結(jié)

點之后的

參考答案：C

16（5.0分）一維數(shù)組和線性表的區(qū)別為（）

A）前者長度固定，后者長度可變

B）兩者長度均固定

C）前者長度可變，后者長度固定

D）兩者長度均可變

參考答案：A

17（5.0分）在數(shù)據(jù)結(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)和非線性結(jié)構(gòu)

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

參考答案：C

18（5.0分）在具有n個結(jié)點的二叉樹（二叉鏈表表示）中，值為空的鏈域數(shù)為

（）

A）n-1

B）2n-1

C）n1

D）2n1

參考答案：B

19（5.0分）有六個元素6,5,4,3,2,1的順序進棧，問下列哪一個不是合法

的出棧序列？（）

A）543612

B）453126

0346521

D）234156

參考答案：C

20（5.0分）在二叉樹的先序遍歷，中序遍歷和后序遍歷算法中，所有葉子結(jié)點

的先后順序（）

A）都不相同

B）完全相同

C）前序遍歷和中序遍歷相同，而與后序遍歷不同

D）前序遍歷和后序遍歷相同，而與中序遍歷不同

參考答案：B

1（5.0分）下面關(guān)于圖的存儲的敘述中正確的是（）

A）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與

邊數(shù)無關(guān)

B）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點

個數(shù)無關(guān)

C）用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與邊

數(shù)無關(guān)

D）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個

數(shù)無關(guān)

參考答案：A

2（5.0分）一個堆棧的入棧序列為abcde,若出棧和入棧操作可間隔進行，則出

棧序列不可能的為（）

A)edcba

B）decba

C）decab

D）abcde

參考答案：c

3（5.0分）下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）

A）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。

B）線性表采用順序存儲，便于進行插入和刪除操作。

C）線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。

D）線性表采用鏈接存儲，便于插入和刪除操作。

參考答案：B

4（5.0分）下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的敘述是（）

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

B）鏈表中每個結(jié)點都恰好包含一個指針

C）包含n個結(jié)點的二叉排序樹的最大檢索長度為log2n

D）將一棵樹轉(zhuǎn)為二叉樹后，根結(jié)點無右子樹

參考答案：D

5（5.0分）下列說法正確的是（）

A）樹的先根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同

B）樹的先根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同

C）樹的后根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同

D）樹的后根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同

參考答案：A

6（5.0分）圖結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法中使用了（）

A）堆棧

B）隊列

C）堆棧和隊列

D）以上都不正確。

參考答案：B

7（5.0分）一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是:

（）

A）edcba

B）decba

C）dceab

D）abcde

參考答案：c

8（5.0分）希爾排序和快速排序分別屬于（）

A）交換排序選擇排序

B）插入排序選擇排序

C）選擇排序歸并排序

D）交換排序選擇排序

參考答案：B

9（5.0分）一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則

計算該有向圖中某個頂點出度的時間復(fù)雜度為（）

A）O（n）B）0（e）C）O（ne）D）O（n2）參考答案：B

10（5.0分）下面哪一種方法可以判斷出一個有向圖中是否有環(huán)（回路）（）

A）深度優(yōu)先遍歷

B）拓撲排序

C）求最短路徑

D）求關(guān)鍵路徑

參考答案：B

11（5.0分）下列哪一個關(guān)鍵碼序列不符合堆的定義？（）

A）（102,87,100,79,82,62,84,42,22,12,68）B）（102,100,

87,84,82,79,68,62,42,22,12）C）（12,22,42,62,68,79,82,

84,87,100,102）D）（102,87,42,79,82,62,68,100,84,12,22）

參考答案：D

12（5.0分）下面關(guān)于完全二叉樹的特點敘述不正確的是（）

A）只有最后一層是不滿的，不滿層的結(jié)點首先出現(xiàn)在左邊；

B）至多只有最下面的兩層結(jié)點的度小于2；

C）左子樹的高度不會小于右子樹的高度，且左、右子樹高度最大相差±1；

D）葉子只能出現(xiàn)在最后兩層上；

參考答案：C

13（5.0分）下列排序方法中，哪一個是穩(wěn)定的排序方法？（）

A）直接選擇排序

B）堆排序

C）希爾排序

D）快速排序

參考答案：A

14（5.0分）下面程序段的時間復(fù)雜度是（）for（i=0;ifor（j=l;jA[i][j]=0；

A）O（n）B）O（mn1）C）O（mn）D）O（m*n）參考答案：D

15（5.0分）下列關(guān)于遞歸特點的描述不正確的是：

A）結(jié)構(gòu)清晰、可讀性強。

B）算法正確性易證明。

C）時間效率高。

D）空間效率低。

參考答案：C

16（5.0分）下面關(guān)于哈希（Hash,雜湊）查找的說法正確的是（）

A）哈希函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機性好，沖突小

B）除留余數(shù)法是所有哈希函數(shù)中最好的

C）不存在特別好與壞的哈希函數(shù)，要視情況而定

D）在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元

素刪去即可

參考答案：C

17（5.0分）下程序段的時間復(fù)雜度為（）oi=0;k=0;while（i<N）{i;k=k

10*i;}

A)O(1)

B)O(n)

C）0（n2）

D）0（n3）

參考答案：B

18（5.0分）下列判斷正確的是（）

A）二叉樹是樹的特例。

B）具有n個結(jié)點的完全二叉樹的深度為n/2o

?Huffman樹是帶權(quán)路徑長度最小的二叉樹，樹中權(quán)值越大的葉子結(jié)點距離

根結(jié)點越遠。

D）棧和隊列都是限制存取點的線性結(jié)構(gòu)。

參考答案：D

19（5.0分）線性結(jié)構(gòu)中的一個結(jié)點代表一個（）

A）數(shù)據(jù)元素

B）數(shù)據(jù)項

C）數(shù)據(jù)

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

參考答案：A

20（5.0分）下列說法不正確的是（）

A）圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次

B）圖的深度遍歷不適用于有向圖

C）遍歷的基本算法有兩種：深度遍歷和廣度遍歷

D）圖的深度遍歷是一個遞歸過程

參考答案：B

1（5.0分）下面關(guān)于圖的存儲的敘述中正確的是（）

A）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與

邊數(shù)無關(guān)

B）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點

個數(shù)無關(guān)

C）用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與邊

數(shù)無關(guān)

D）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個

數(shù)無關(guān)

參考答案：A

2（5.0分）一個堆棧的入棧序列為abcde,若出棧和入棧操作可間隔進行，則出

棧序列不可能的為（）

A）edcba

B）decba

C）decab

D）abcde

參考答案：C

3（5.0分）下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）

A）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。

B）線性表采用順序存儲，便于進行插入和刪除操作。

C）線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。

D）線性表采用鏈接存儲，便于插入和刪除操作。

參考答案：B

4（5.0分）下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的敘述是（）

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

B）鏈表中每個結(jié)點都恰好包含一個指針

C）包含n個結(jié)點的二叉排序樹的最大檢索長度為log2n

D）將一棵樹轉(zhuǎn)為二叉樹后，根結(jié)點無右子樹

參考答案：D

5（5.0分）下列說法正確的是（）

A）樹的先根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同

B）樹的先根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同

C）樹的后根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同

D）樹的后根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同

參考答案：A

6（5.0分）圖結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法中使用了（）

A）堆棧

B）隊列

C）堆棧和隊列

D）以上都不正確。

參考答案：B

7（5.0分）一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是：

（）

A）edcba

B）decba

C）dceab

D）abcde

參考答案：C

8（5.0分）希爾排序和快速排序分別屬于（）

A）交換排序選擇排序

B）插入排序選擇排序

C）選擇排序歸并排序

D）交換排序選擇排序

參考答案：B

9（5.0分）一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則

計算該有向圖中某個頂點出度的時間復(fù)雜度為（）

A）O（n）B）0（e）C）O（ne）D）O（n2）參考答案：B

10（5.0分）下面哪一種方法可以判斷出一個有向圖中是否有環(huán)（回路）（）

A）深度優(yōu)先遍歷

B）拓撲排序

C）求最短路徑

D）求關(guān)鍵路徑

參考答案：B

11（5.0分）下列哪一個關(guān)鍵碼序列不符合堆的定義？（）

A）（102,87,100,79,82,62,84,42,22,12,68）B）（102,100,

87,84,82,79,68,62,42,22,12）C）（12,22,42,62,68,79,82,

84,87,100,102）D）（102,87,42,79,82,62,68,100,84,12,22）

參考答案：D

12（5。分）下面關(guān)于完全二叉樹的特點敘述不正確的是（）

A）只有最后一層是不滿的，不滿層的結(jié)點首先出現(xiàn)在左邊；

B）至多只有最下面的兩層結(jié)點的度小于2；

C）左子樹的高度不會小于右子樹的高度，且左、右子樹高度最大相差±1；

D）葉子只能出現(xiàn)在最后兩層上；

參考答案：C

13（5.0分）下列排序方法中，哪一個是穩(wěn)定的排序方法？（）

A）直接選擇排序

B）堆排序

C）希爾排序

D）快速排序

參考答案：A

14（5.0分）下面程序段的時間復(fù)雜度是