1、數(shù)據(jù)結(jié)構(gòu)模擬試題02一、單項(xiàng)選擇題（每題 2 分，共8分）1、 在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、 在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( )。A slink=plink; plink=s; B plink=s; slink=q;C plink=slink; slink=p; D q link=s; slink =p;3、 棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂

2、B 棧底 C 任意位置 D 指定位置4、 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、填空題（每空1分，共32分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、 _ 、_和_四種。2. 一種抽象數(shù)據(jù)類型包括_和_兩個(gè)部分。3. 在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為a0.next，則該線性表為_。a 0 1 2 3 4 5 6 7 8   60 56 42 38  74 25  4 3 7 6 2 0 1 datanext 4. 在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單

3、鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和_。5. 用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的_，該循環(huán)隊(duì)列的最大長度為_。6. 當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用_表示。7. 一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；8. 一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。9. 在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為_，通常它包含三個(gè)域：一是_；二是_；三是_。10. 在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的_和_兩項(xiàng)數(shù)據(jù)。11. 假定一棵樹的廣義表表示為A（B（C，D

4、（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_,樹的度為_, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_,孩子結(jié)點(diǎn)為_ 。12. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_,整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。13. 在對(duì)m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于_個(gè)，則必須把它分裂為_個(gè)結(jié)點(diǎn)。三、算法簡答題（每題 6 分，共24分）1. 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。2. 一個(gè)線性表為B=（12，23，45，57，20，

5、03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3. 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4. 已知一個(gè)圖的頂點(diǎn)集V各邊集G如下：V = 0，1，2，3，4，5，6，7，8，9；E = （0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分

6、別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)  鄰接表表示時(shí)      四、閱讀算法（每題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 1，請(qǐng)寫出輸出結(jié)果。# include < iostream.h># include < stdlib.h >consst int stackmaxsize = 30;typedef int

7、elemtype;struct stack elemtype stack stackmaxsize; int top;# include “stack.h”Void main ( ) stack a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” ;cout <<end1;該算法的輸出結(jié)果為：_. 2、閱讀以下二叉樹操作算法，指出該算法的功能。Template &

8、lt;calss type > void BinTree <Type> ：unknown (BinTreeNode<Type>*t) BinTreeNode< Type> *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 該算法的功能是：_五、算法填空（共10分）對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法 。 int Binsch( El

9、emType A ,int low ,int high,KeyType K ) if (low <= high) int mid = 1 if ( K= = A mid .key ) return mid; else if ( K < Amid.key) return 2 else return 3 else return 4  六、編寫算法（共8分）編寫算法，將一個(gè)結(jié)點(diǎn)類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)閍1，an-1，an，則逆序鏈接后變?yōu)? an，an-1，a1。Void contrary (Lnode * & HL) 

10、; 6數(shù)據(jù)結(jié)構(gòu)模擬試題02參考答案一、單項(xiàng)選擇題（每題 2 分，共8分）題 號(hào) 1 2 3 4答 案 C D A B二、填空題（每空1分，共32分）1： 集合、線性、樹、圖；2： 數(shù)據(jù)描述、操作聲名；3： （38，56，25，60，42，74）；4： HLnext =NULL； HL=HLnext；5： 前一個(gè)位置； n-1；6： S.stack S.top; HSdata;7： 5 318： 邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；9： 索引值域、開始位置域；10： 10、3、3、B、I和J；11： O（log2n）、O(nlog2n);12： m 、 m - 1三、算法簡答題（每題 6 分

11、，共24分）1、劃分次序劃分結(jié)果第一次38 24 40 46 56 80 95 79第二次24 38 40 46 56 80 95 79第三次24 38 40 46 56 80 95 79第四次24 38 40 46 56 80 95 79第五次24 38 40 46 56 79 80 95第六次24 38 40 46 56 79 80 95 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 1503 57452031 233612  查找成功的平均查找長度：ASL SUCC=14/10= 1.43、此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA4、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9鄰接表表示時(shí)0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，5四、閱讀算法（每題8分，共16分）1、  該算法的輸入結(jié)果是：34 91 30 45 63 782、  該算法的功能是：交換二叉樹的左右子樹的遞歸算法。五、算法填空（共8分）1：（low + hi