數(shù)據(jù)結(jié)構(gòu)學(xué)期樣卷一

1、學(xué)期樣卷一單項選擇題1有一個帶頭結(jié)點(diǎn)的單鏈表HEAD,則判斷其是否為空鏈表的條件是（B。A. HEAD=NULLB. HEAD-NEXT=NULLC. HEAD-NEXT=HEADD. HEAD!=NULL注:不帶頭結(jié)點(diǎn)若L為頭指針，指向鏈表的第一個結(jié)點(diǎn)_L=NULL,為空表2 .若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，可采用（D存儲方式最節(jié)省時間。A.單向鏈表B.雙向鏈表C.單向循環(huán)鏈表D.順序表注:當(dāng)線性表的長度變化較大、難以估計其存儲規(guī)模時，采用動態(tài)鏈表存儲比較好;當(dāng)線性表的長度變化不大、易于事先確定其大小時，為了節(jié)約存儲空間，應(yīng)采用順序表作為存儲結(jié)構(gòu)；若線性表的操作主要是進(jìn)行

2、查找，很少做插入或者刪除操作，基于時間考慮，宜采用順序表作為存儲結(jié)構(gòu)；對于頻繁進(jìn)行采用鏈表存儲，若表的插入或刪除發(fā)生在首尾倆端，則采用帶尾指針的單循環(huán)鏈表。3 .某個棧的入棧的序列為A,B,C,D,E,則可能的出棧序列是（CA.ADBECB. EBCADC. BCDEAD. EABCD注AA進(jìn)棧就出棧,B,C,D進(jìn)棧,D出棧，但B不能在C前面出棧B.A,B,C,D,E進(jìn)棧,E出棧，但B不能先出棧C. A先進(jìn)棧,B進(jìn)棧就出棧,C進(jìn)棧就出棧，D進(jìn)出,E進(jìn)出最后出AD. -8工加建進(jìn)棧,先出棧,人不能先出4.廣義表(a,(b,(c的表尾是(DoA. (cB. (cC. (cD. (b,(c注：(1D

3、二(:空表，其長度為0(2A=(a,(b,c:表長度為2的廣義表,其中第一個元素為單個數(shù)據(jù)a,第二個元素是一個子表(b,c。(3B;(A,A,D:表長度為3,其前倆個元素為表A,第三個元素是空表D。(4C=C:長度為2遞歸定義的廣義表,C相當(dāng)于無窮表C=(a,(a,(a,(-o(5Head(A=a,即表A的表頭是a。（6Tail（A=（b,c,即表A的表尾是（b,c。廣義表的表尾一定是一個表6 .一棵深度為h的二叉樹，其結(jié)點(diǎn)總數(shù)最多為（2Ah-lo在二叉樹的第i層上至多有2A（i-1個結(jié)點(diǎn)對任意一顆二叉樹T,若終端結(jié)點(diǎn)數(shù)為nO,而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+l具有n個結(jié)點(diǎn)的完全二叉

4、樹的深度為log2An+17 .AVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點(diǎn)的（B。A.左右子樹的高度均相同8 .左右子樹高度差的絕對值不超過1C.左子樹的高度大于右子樹的高度D.左子樹的高度小于右子樹的高度注：左右子樹也是平衡二叉排序樹8 .在關(guān)鍵字隨機(jī)分布的前提下，用二叉排序樹的方法進(jìn)行查找，其平均長度同（折半查找數(shù)量級相同。9 .對于一個有向圖，若一個頂點(diǎn)的度為kl,出度為k2,則對應(yīng)的鄰接表中，該結(jié)點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為（B。A. klB. k2C. kl-k2D.kl+k2注:在無向圖的鄰接表中，頂點(diǎn)Vi的度恰好就是第i個單鏈表上結(jié)點(diǎn)的個數(shù)在有向圖中，第i個單鏈表上結(jié)點(diǎn)的個數(shù)只是頂點(diǎn)

5、Vi的出度只需通過表頭向量表中找到第i個頂點(diǎn)的邊鏈表的頭指針。10.下列關(guān)鍵字序列中，（D是堆A. 16,72,31,23,94,53B. 94,23,31,72,16,53C. 16,53,23,94,31,72D. 16,23,53,31,94,72注:堆可以看成一棵完全二叉樹：任一根節(jié)點(diǎn)二左右孩子（或者白（大的叫大根堆,小的叫小根堆。注意一個堆中的這種性質(zhì)有一致性，不能既有大于又有小于情況存.填空題1 .如下程序段：for（i=1;iNEXT=Lao注:單鏈表中判別條件為p!二NULL或p-next!二NULL;而單循環(huán)鏈表的判斷條件是p!=La或p-next!=Lao3 .在一棵度為3

6、的樹中，其中度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個,則度為0的結(jié)點(diǎn)數(shù)為（6個。注:一個結(jié)點(diǎn)的子樹個數(shù)稱為此結(jié)點(diǎn)的度；樹中所有結(jié)點(diǎn)的度的最大值是數(shù)的度。樹中結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)度數(shù)的和加lo所以：2+l+2+X=2*3+l*2+2*l+X*0+l所以X=65 .在待排序的兀素序列基本有序的前提下，效率最高的排序方法是（直接排序或冒泡排序。7 .若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊列,且當(dāng)前的rear和front的值為0和3,當(dāng)從隊列中刪除1個元素后，front的值為（4,再加入2個元素后，rear的值為（2o注:front為頭指針指示器，出隊front+l;rear為尾指針

7、指示器進(jìn)隊,rear+2。Rear-front=Max,隊列為滿;求元素個數(shù)可以用這個公式：（尾指針-頭指針隊列長度+18 .設(shè)有一個二維數(shù)組AL.12,1.10,采用以行序為主序存儲，每個數(shù)據(jù)元素占有2個字節(jié),該數(shù)組的首元素的地址為1200,則A6,5的地址為（。注:任意兀素Aij的地址計算公式:Loc(Aij=Loc(All+(n*(i-l+j-l*sizeA6,5=1200+(10*(6-1+5-1*2=13089 .設(shè)一哈希表表長必為100用除留余數(shù)法構(gòu)造哈希函數(shù)，即H(K二K%P,為使函數(shù)具有較好性能,P應(yīng)選(爛100的素數(shù)。注:P為小于等于M的最大素數(shù)三.構(gòu)造題1給定權(quán)值8,12,4,5,26,16,9,構(gòu)造一棵帶權(quán)路徑最短的二叉樹，并計算其帶權(quán)路徑長度。注：803347161721268991245WPL=(4+5*4+(8+9+12*3+(16+26*2=207WPL二刀Wi*LiWi為第i個葉子結(jié)點(diǎn)的權(quán)值,Li為第i個葉子結(jié)點(diǎn)的路