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

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