東北大學22秋《數(shù)據(jù)結構Ⅱ》在線平時作業(yè)2答卷

《數(shù)據(jù)結構II》在線平時作業(yè)2

試卷總分：100得分：100

一、單選題（共20道試題，共100分）

1,判斷兩個串大小的基本準則是

A.兩個串長度的大小

B.兩個串中首字符的大小

C.兩個串中大寫字母的多少

D.對應的第一個不等字符的大小

答案:D

2.己知一棵樹的前序序列為ABCDEF,后序序列為CEDFBA,則對該樹進行層次遍歷

得到的序列為

A.ABCDEF

B.ABCEFD

C.ABFCDE

D.ABCDFE

答案:D

3.采用ISAM或VSAM組織的文件是

A.索引非順序文件

B.順序文件

C.索引順序文件

D.散列文件

答案:C

4.如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用

A.深度優(yōu)先搜索算法

B.廣度優(yōu)先搜索算法

C.求最小生成樹的prim算法

D.拓撲排序算法

答案:B

5.鏈棧與順序棧相比，比較明顯的優(yōu)點是

A.插入操作更加方便

B.刪除操作更加方便

C.不會出現(xiàn)下溢的情況

D.不會出現(xiàn)上溢的情況

答案:D

6.用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數(shù)為

A.n-1

B.n

C.n+1

D.2n

答案:c

7.一棵樹高為K的完全二叉樹至少的結點是

A.2k–1

B.2k-1–1

C.2k-1

D.2k

答案:C

8.設有一個順序棧，6個元素1、2、3、4、5、6依次入棧，如果6個元素出棧的

順序是2、3、4、6、5、1,則棧的容量至少應該是

A.2

B.3

C.5

D.6

答案:B

9.當采用分快查找時，數(shù)據(jù)的組織方式為

A.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序

B.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序，每塊內最大（或最

?。┑臄?shù)據(jù)組成索引塊

C.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，每塊內最大（或最?。┑臄?shù)據(jù)組成索引塊

D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同

答案:B

10.抽象數(shù)據(jù)類型的三個組成部分分別為

A.數(shù)據(jù)對象、數(shù)據(jù)關系和基本操作

B.數(shù)據(jù)元素、邏輯結構和存儲結構

C.數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型

D.數(shù)據(jù)元素、數(shù)據(jù)結構和數(shù)據(jù)類型

答案:A

11.下面關于線性表的敘述中，錯誤的是

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

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

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

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

答案:B

12.設哈希表長為14,哈希函數(shù)H（key）=key%ll,表中已有數(shù)據(jù)的關鍵字為15,

38,61,84,四個，現(xiàn)將關鍵字為49的結點加到表中，用二次探測再散列法解決

沖突，則放入的位置是

A.8

B.3

C.5

D.9

答案:A

13.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)

的是

A.G中有弧<Vi,Vj>

B.G中有一條從Vi到Vj的路徑

C.G中沒有弧〈Vi,Vj>

D.G中有一條從Vj到Vi的路徑

答案:D

14.在待排關鍵字序列基本有序的前提下，效率最高的排序方法是

A.直接插入排序

B.快速排序

C.直接選擇排序

D.歸并排序

答案:A

15.樹有先根遍歷和后根遍歷，樹可以轉化為對應的二叉樹。下面的說法正確的是

A.樹的后根遍歷與其對應的二叉樹的后根遍歷相同

B.樹的后根遍歷與其對應的二叉樹的中根遍歷相同

C.樹的先根遍歷與其對應的二叉樹的中根遍歷相同

D.以上都不對

答案:B

16.若在9階B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字

個數(shù)為

A.4

B.5

C.8

D.9

答案:C

17.下面的敘述不正確的是

A.線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比

B.線性表在鏈式存儲時，查找第i個元素的時間同i的值無關

C.線性表在順序存儲時，查找第i個元素的時間同i的值成反比

D.線性表在順序存儲時，查找第i個元素的時間同i的值無關

答案:B

18.若度為m的哈夫曼樹中，其葉結點個數(shù)為n,則非葉結點的個數(shù)為

A.n-1

B.ën/mû-1

C.feeacute;(n-1)/(m-l)ù

D.én/(m-l)ù-l

答案:C

19.在平衡二叉樹中插入一個結點后引起了不平衡，設最低(最接近于葉子)的不平

衡點是A,并已知A的左、右孩子的平衡因子分別為T