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

《數(shù)據(jù)結構Ⅱ》在線平時作業(yè)2試卷總分:100得分:100一、單選題(共20道試題,共100分)判斷兩個串大小的基本準則是兩個串長度的大小兩個串中首字符的大小兩個串中大寫字母的多少對應的第一個不等字符的大小答案:D2.已知一棵樹的前序序列為ABCDEF，后序序列為CEDFBA，則對該樹進行層次遍歷得到的序列為ABCDEFABCEFDABFCDEABCDFE答案:D3.采用ISAM或VSAM組織的文件是索引非順序文件順序文件索引順序文件散列文件答案:C4.如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用深度優(yōu)先搜索算法廣度優(yōu)先搜索算法求最小生成樹的prim算法拓撲排序算法答案:B5.鏈棧與順序棧相比，比較明顯的優(yōu)點是插入操作更加方便刪除操作更加方便不會出現(xiàn)下溢的情況不會出現(xiàn)上溢的情況答案:D6.用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數(shù)為n-1nn+l2n答案:C7.一棵樹高為K的完全二叉樹至少的結點是2k–12k-1–12k-12k答案:C8.設有一個順序棧，6個元素1、2、3、4、5、6依次入棧，如果6個元素出棧的順序是2、3、4、6、5、1，則棧的容量至少應該是2356答案:B9.當采用分快查找時，數(shù)據(jù)的組織方式為數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同答案:B10.抽象數(shù)據(jù)類型的三個組成部分分別為數(shù)據(jù)對象、數(shù)據(jù)關系和基本操作數(shù)據(jù)元素、邏輯結構和存儲結構數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型數(shù)據(jù)元素、數(shù)據(jù)結構和數(shù)據(jù)類型答案:A11.下面關于線性表的敘述中，錯誤的是線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。線性表采用順序存儲，便于進行插入和刪除操作。線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。線性表采用鏈接存儲，便于插入和刪除操作。答案:B12.設哈希表長為14，哈希函數(shù)H(key)=key％11，表中已有數(shù)據(jù)的關鍵字為15，38，61，84，四個，現(xiàn)將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是8359答案:A13.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是G中有弧<Vi，Vj>G中有一條從Vi到Vj的路徑G中沒有弧<Vi,Vj>G中有一條從Vj到Vi的路徑答案:D14.在待排關鍵字序列基本有序的前提下，效率最高的排序方法是直接插入排序快速排序直接選擇排序歸并排序答案:A15.樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應的二叉樹。下面的說法正確的是樹的后根遍歷與其對應的二叉樹的后根遍歷相同樹的后根遍歷與其對應的二叉樹的中根遍歷相同樹的先根遍歷與其對應的二叉樹的中根遍歷相同以上都不對答案:B16.若在9階B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數(shù)為4589答案:C17.下面的敘述不正確的是線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比線性表在鏈式存儲時，查找第i個元素的時間同i的值無關線性表在順序存儲時，查找第i個元素的時間同i的值成反比線性表在順序存儲時，查找第i個元素的時間同i的值無關答案:B18.若度為m的哈夫曼樹中，其葉結點個數(shù)為n，則非葉結點的個數(shù)為n-1ën/mû-1é(n-1)/(m-1)ùén/(m-1)ù-1答案:C19.在平衡二叉樹中插入一個結點后引起了不平衡，設最低(最接近于葉子)的不平衡點是