東大21秋《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時作業(yè)2

1、數(shù)據(jù)結(jié)構(gòu)在線平時作業(yè)2試卷總分:100 得分:100一、單選題 (共 20 道試題,共 100 分)1.判斷兩個串大小的基本準(zhǔn)則是【A】.兩個串長度的大小【B】.兩個串中首字符的大小【C】.兩個串中大寫字母的多少【D】.對應(yīng)的第一個不等字符的大小【正確答案】：D2.已知一棵樹的前序序列為ABCDEF，后序序列為CEDFBA，則對該樹進行層次遍歷得到的序列為【A】.ABCDEF【B】.ABCEFD【C】.ABFCDE【D】.ABCDFE【正確答案】：D3.采用ISAM或VSAM組織的文件是【A】.索引非順序文件【B】.順序文件【C】.索引順序文件【D】.散列文件【正確答案】：C4.如果求一個連通

2、圖中以某個頂點為根的高度最小的生成樹，應(yīng)采用【A】.深度優(yōu)先搜索算法【B】.廣度優(yōu)先搜索算法【C】.求最小生成樹的prim算法【D】.拓撲排序算法【正確答案】：B5.鏈棧與順序棧相比，比較明顯的優(yōu)點是【A】.插入操作更加方便【B】.刪除操作更加方便【C】.不會出現(xiàn)下溢的情況【D】.不會出現(xiàn)上溢的情況【正確答案】：D6.用二叉鏈表表示具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為【A】.n-1【B】.n【C】.n+l【D】.2n【正確答案】：C7.一棵樹高為K的完全二叉樹至少的結(jié)點是【A】.2k 1【B】.2k-1 1【C】.2k-1【D】.2k【正確答案】：C8.設(shè)有一個順序棧，6個元素1、2

3、 、3、4、5、6依次入棧，如果6個元素出棧的順序是2、3、4、6、5、1，則棧的容量至少應(yīng)該是【A】.2【B】.3【C】.5【D】.6【正確答案】：B9.當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為【A】.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序【B】.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引塊【C】.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊【D】.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同【正確答案】：B10.抽象數(shù)據(jù)類型的三個組成部分分別為【A】.數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作【B】.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)【C】.數(shù)據(jù)項

4、、數(shù)據(jù)元素和數(shù)據(jù)類型【D】.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型【正確答案】：A11.下面關(guān)于線性表的敘述中，錯誤的是【A】.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元?！綛】.線性表采用順序存儲，便于進行插入和刪除操作。【C】.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元?！綝】.線性表采用鏈接存儲，便于插入和刪除操作。【正確答案】：B12.設(shè)哈希表長為14，哈希函數(shù)H(key)=key11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是【A】.8【B】.3【C】.5【D】.9【正確答案】：A13.在有向圖G的拓撲

5、序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是【A】.G中有弧【B】.G中有一條從Vi到Vj的路徑【C】.G中沒有弧【D】.G中有一條從Vj到Vi的路徑【正確答案】：D14.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是【A】.直接插入排序【B】.快速排序【C】.直接選擇排序【D】.歸并排序【正確答案】：A15.樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應(yīng)的二叉樹。下面的說法正確的是【A】.樹的后根遍歷與其對應(yīng)的二叉樹的后根遍歷相同【B】.樹的后根遍歷與其對應(yīng)的二叉樹的中根遍歷相同【C】.樹的先根遍歷與其對應(yīng)的二叉樹的中根遍歷相同【D】.以上都不對【正確答案】：B16.若在9階

6、B-樹中插入關(guān)鍵字引起結(jié)點分裂，則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為【A】.4【B】.5【C】.8【D】.9【正確答案】：C17.下面的敘述不正確的是【A】.線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比【B】.線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)【C】.線性表在順序存儲時，查找第i個元素的時間同i 的值成反比【D】.線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)【正確答案】：B18.若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為【A】.n-1【B】.n/m-1【C】.(n-1)/(m-1)【D】.n/(m-1)-1【正確答案】：C19.在平衡二叉樹中插入一個結(jié)點后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點是A，并已知A的左、右孩子的平衡因子分別為-1和0