《數(shù)據(jù)結(jié)構(gòu)2264》23春在線作業(yè)2答卷

《數(shù)據(jù)結(jié)構(gòu)2264》22秋在線作業(yè)2-00001試卷總分:100得分:100一、單選題(共25道試題,共50分)1.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。A.11B.35C.19D.53答案:B2.一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（）。A.231B.321C.312D.123答案:C3.帶有頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（）。A.head==NULB.head->next==NULLC.head!=NULLD.head->next==head答案:D4.一散列表長(zhǎng)度m為100，采用除留余數(shù)法構(gòu)造散列函數(shù)，即H（）=K%P（）,，為使散列函數(shù)具有較好的性能，P的選擇應(yīng)是（）。A.99B.100C.97D.93答案:C5.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）。A.m-n-1B.n+1C.m-n+1D.m-n答案:D6.在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系的運(yùn)算是（）。A.插入B.刪除C.排序D.查找答案:D7.對(duì)于線性表（）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè)。A.1B.2C.3D.4答案:D8.k層（）二叉樹的結(jié)點(diǎn)總數(shù)最多為（）。A.2k-1B.2K+1C.2K-1D.2k-1答案:A9.樹最適合用來(lái)表示（）。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)答案:C10.采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（）。A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找答案:B11.中綴表達(dá)式2+X*（）的后綴形式是（）。A.3YX2+*+B.Y3+X*2+C.2XY3*++D.2XY3+*+答案:D12.如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用（）方法比較次數(shù)較少。A.直接插入排序B.快速排序C.歸并排序D.選擇排序答案:A13.對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（）。A.O（1og2nB.O（n）C.O（1）D.O（n2）答案:C14.含有10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的點(diǎn)數(shù)為（）。A.3B.4C.5D.6答案:A15.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度答案:B16.下面關(guān)于廣義表的敘述中，不正確的是（）。A.廣義表可以是一個(gè)多層次的結(jié)構(gòu)B.廣義表至少有一個(gè)元素C.廣義表可以被其他廣義表所共享D.廣義表可以是一個(gè)遞歸表答案:B17.對(duì)關(guān)鍵字序列（）進(jìn)行增量為3的一趟希爾排序的結(jié)果為（）。A.(19,23,56,34,78,67,88,92)B.(23,56,78,66,88,92,19,34)C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88)答案:D18.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為（）。A.24B.5C.98D.99答案:A19.若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)方式是（）。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表答案:D20.設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（）。A.2mB.2m-1C.2m+1D.m+1答案:B21.若有序表為（），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（）。A.f,c,bB.f,d,bC.g,c,bD.g,d,b答案:A22.隊(duì)列的特點(diǎn)是（）。A.先進(jìn)后出B.先進(jìn)先出C.任意位置進(jìn)出D.前面都不正確答案:B23.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（）。A.數(shù)組是不同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C.樹是一種線性結(jié)構(gòu)D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法答案:D24.在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過(guò)程中，每一趟都要從無(wú)序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無(wú)序區(qū)中元素的個(gè)數(shù)為（）。A.iB.i+1C.n-iD.n-i+1答案:C25.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下（）語(yǔ)句序列。A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;答案:D二、多選題(共4道試題,共20分)26.對(duì)一個(gè)算法的評(píng)價(jià)，主要包括如下（）方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度E.界面友好性答案:ACD27.以下哪些是隊(duì)列的基本運(yùn)算？（）A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值E.將隊(duì)列中的元素排序答案:BCD28.下述（）是順序存儲(chǔ)方式的優(yōu)點(diǎn)。A.存儲(chǔ)密度大B.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快E.可以很方便地存取第i個(gè)元素答案:AE29.以下序列中，是堆（）的有（）。A.{15,26,38,49,27,51,39,62}B.{15,23,71,94,72,68,26,73}C.{15,27,26,49,38,62,39,51}D.{15,23,26,68,94,72,71,73}E.{94,72,73,26,71,23,68,15}答案:ACDE三、判斷題(共15道試題,共30分)30.用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。答案:正確31.快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終的位置上。答案:正確32.棧和隊(duì)列都是順序存取的線性表，但它們對(duì)存取位置的限制不同。答案:正確33.鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。答案:錯(cuò)誤34.用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串，數(shù)組長(zhǎng)度至少為n+1。答案:正確35.一個(gè)廣義表（）,（）,c),（）)))的表尾是（）,c),（）))。答案:錯(cuò)誤36.線性表若采用鏈?zhǔn)酱鎯?chǔ)表示,在刪除時(shí)不需要移動(dòng)元素。答案:正確37.線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。答案:錯(cuò)誤38.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。答案:正確39.若一棵二叉樹的任一非葉子結(jié)點(diǎn)的度為2，則該二叉樹為滿二叉樹。答案:錯(cuò)誤40.在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和后序遍歷，則具有相同的結(jié)果。答案:錯(cuò)誤41.圖G的某一最小