(完整版)十套數(shù)據(jù)結(jié)構(gòu)試題及答案,推薦文檔

1、數(shù)據(jù)結(jié)構(gòu)試卷（一）1數(shù)據(jù)結(jié)構(gòu)試卷（二）4數(shù)據(jù)結(jié)構(gòu)試卷（三）6數(shù)據(jù)結(jié)構(gòu)試卷（四）8數(shù)據(jù)結(jié)構(gòu)試卷（五）11數(shù)據(jù)結(jié)構(gòu)試卷（六）14數(shù)據(jù)結(jié)構(gòu)試卷（七）16數(shù)據(jù)結(jié)構(gòu)試卷（八）18數(shù)據(jù)結(jié)構(gòu)試卷（fh）20數(shù)據(jù)結(jié)構(gòu)試卷（十）23數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案26數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案27數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案28數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案30數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案32數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案33數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案36數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案37數(shù)據(jù)結(jié)構(gòu)試卷（fh）參考答案38數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案390數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題 2 分，共 20 分）1. 棧和隊(duì)列的共同特點(diǎn)

2、是()。a. 只允許在端點(diǎn)處插入和刪除元素b. 都是先進(jìn)后出c.都是先進(jìn)先出d.沒(méi)有共同點(diǎn)2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( ).a. 僅修改頭指針b. 頭、尾指針都要修改c. 僅修改尾指針d.頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( )a. 隊(duì) 列 b. 棧 c. 線 性 表 d. 二 叉 樹4. 設(shè)有一個(gè)二維數(shù)組 amn，假設(shè) a00存放位置在 644(10)，a22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn) a33(10)存放在什么位置？腳注(10)表示用 10 進(jìn)制表示。a688b678c692d6965. 樹最適合用來(lái)表示()。a. 有序數(shù)據(jù)

3、元素b.無(wú)序數(shù)據(jù)元素c.元素之間具有分支層次關(guān)系的數(shù)據(jù)d.元素之間無(wú)聯(lián)系的數(shù)據(jù)6. 二叉樹的第 k 層的結(jié)點(diǎn)數(shù)最多為().a2k-1b.2k+1c.2k-1d. 2k-17. 若有 18 個(gè)元素的有序表存放在一維數(shù)組 a19中，第一個(gè)元素放 a1中，現(xiàn)進(jìn)行二分查找，則查找 a3的比較序列的下標(biāo)依次為()a. 1，2，3b. 9，5，2，3c. 9，5，3d. 9，4，2，38. 對(duì) n 個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為a. o（1）b. o（n）c. o（1og2n）d. o（n2）9. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用 h（

4、k）=k %9 作為散列函數(shù)，則散列地址為 1 的元素有（）個(gè)，a1b2c3d410. 設(shè)有 6 個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有()條邊才能確保是一個(gè)連通圖。a.5b.6c.7d.8二、填空題（每空 1 分，共 26 分）1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：、和。2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為。3. 假定一棵樹的廣義表表示為 a（c，d（e，f，g），h（i，j），則樹中所含的結(jié)點(diǎn)數(shù)為個(gè)，樹的深度為，樹的度為。4. 后綴算式 9 2 3 +- 10 2 / -的值為。中綴算式（3+4x）-2y/3 對(duì)應(yīng)的后綴算式為。5. 若用鏈表存儲(chǔ)一棵二叉樹

5、時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n 個(gè)結(jié)點(diǎn)的二叉樹共有個(gè)指針域，其中有 個(gè)指針域是存放了地址，有個(gè)指針是空指針。6. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。7. aov 網(wǎng)是一種的圖。8. 在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有 n 個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。9. 假定一個(gè)線性表為(12,23,74,55,63,40)，若按 key % 4 條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為 、 和。10. 向一棵 b_樹插入元素的過(guò)程中，若最

6、終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度 。11. 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為。12. 在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。三、計(jì)算題（每題 6 分，共 24 分）1. 在如下數(shù)組 a 中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為 a 0.next，試寫出該線性表。6050789034403572041a01234567data next2. 請(qǐng)畫出下圖的鄰接矩陣和鄰接表。3. 已知一個(gè)圖的頂點(diǎn)集 v 和邊集 e 分別為：v=1,2,3,4,5,6,7;e=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,

7、4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 畫出向小根堆中加入數(shù)據(jù) 4, 2, 5, 8, 3 時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、閱讀算法（每題 7 分，共 14 分）1. linklist mynote(linklist l)/l 是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(l&l-next)q=l；l=lnext；p=l； s1：while(pnext) p=pnext；s2：pnext=q；qnext=null；returnl；請(qǐng)回答下列問(wèn)題：（1） 說(shuō)明語(yǔ)句 s1

8、 的功能；（2） 說(shuō)明語(yǔ)句組 s2 的功能；40（3） 設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。2. void abc(btnode * bt)ifbt abc (bt-left);abc (bt-right); coutdatadata)item=bst-data;/查找成功return;else if(itemdata)return find(,item); else return find(,item);/if六、編寫算法（共 8 分）統(tǒng)計(jì)出單鏈表 hl 中結(jié)點(diǎn)的值等于給定值 x 的結(jié)點(diǎn)數(shù)。int countx(lnode* hl,elemty

9、pe x)數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24 分)1. 下面關(guān)于線性表的敘述錯(cuò)誤的是（）。(a) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(b) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(c) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(d) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2. 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為 m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。(a) 2m-1(b) 2m(c) 2m+1(d) 4m3. 設(shè)順序循環(huán)隊(duì)列 q0：m-1的頭指針和尾指針?lè)謩e為 f 和r，頭指針 f 總是指向隊(duì)頭元素的前一位置，尾指針 r 總是指向隊(duì)尾元素的當(dāng)前位置，

10、則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。(a) r-f(b) f-r(c) (r-f+m)m(d) (f-r+m)m4. 設(shè)某棵二叉樹的中序遍歷序列為 abcd，前序遍歷序列為 cabd，則后序遍歷該二叉樹得到序列為（）。(a) badc(b) bcda(c) cdab(d) cbda 5設(shè)某完全無(wú)向圖中有 n 個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（ ）條邊。(a) n(n-1)/2(b) n(n-1)(c) n2(d) n2-16. 設(shè)某棵二叉樹中有 2000 個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（ ）。(a) 9(b) 10(c) 11(d) 127. 設(shè)某有向圖中有 n 個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ ）

11、個(gè)表頭結(jié)點(diǎn)。(a) n-1(b) n(c) n+1(d) 2n-18. 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字 5 為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。(a) 2，3，5，8，6(b) 3，2，5，8，6(c) 3，2，5，6，8(d) 2，3，6，5，8二、填空題(24 分)1. 為了能有效地應(yīng)用 hash 查找技術(shù)，必須解決的兩個(gè)問(wèn)題是和 。2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù) x 進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。typedef struct int s100; int top; sqstack; void push(sqstack &stack,int x)if

12、 (stack.top=m-1) printf(“overflow”);else ;3. 中序遍歷二叉排序樹所得到的序列是序列（填有序或無(wú)序）。4. 快速排序的最壞時(shí)間復(fù)雜度為，平均時(shí)間復(fù)雜度為。5. 設(shè)某棵二叉樹中度數(shù)為 0 的結(jié)點(diǎn)數(shù)為 n0，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為 n1，則該二叉樹中度數(shù)為 2 的結(jié)點(diǎn)數(shù)為；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有個(gè)空指針域。6. 設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為 n 和 e，所有頂點(diǎn)的度數(shù)之和為 d，則 e= 。7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為。8 已知一有向圖的鄰接表

13、存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn) 1 出發(fā)，dfs 遍歷的輸出序列是 ，bfs 遍歷的輸出序列是 三、應(yīng)用題(36 分)1. 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第 4 趟簡(jiǎn)單選擇排序和第 4 趟直接插入排序后的結(jié)果。2. 設(shè)指針變量 p 指向雙向鏈表中結(jié)點(diǎn) a，指針變量 q 指向被插入結(jié)點(diǎn) b，要求給出在結(jié)點(diǎn)a 的后面插入結(jié)點(diǎn) b 的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為 llink 和rlink）。3 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字 62 時(shí)的比較次數(shù)并計(jì)算出查

14、找成功時(shí)的平均查找長(zhǎng)度。4 設(shè)一棵樹 t 中邊的集合為(a，b)，(a，c)，(a，d)，(b，e)，(c，f)，(c，g)，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。5. 設(shè)有無(wú)向圖 g，要求給出用普里姆算法構(gòu)造最小生成樹所走過(guò)的邊的集合。6. 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過(guò)程。四、算法設(shè)計(jì)題(16 分)1. 設(shè)有一組初始記錄關(guān)鍵字序列（k1，k2，kn），要求設(shè)計(jì)一個(gè)算法能夠在o(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于 ki，右半部分的每個(gè)關(guān)鍵字均大于等

15、于 ki。2. 設(shè)有兩個(gè)集合 a 和集合 b，要求設(shè)計(jì)生成集合 c=ab 的算法，其中集合 a、b 和 c 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(每題 1 分，共 20 分)1. 設(shè) 某 數(shù) 據(jù) 結(jié) 構(gòu) 的 二 元 組 形 式 表 示 為 a=(d，r)，d=01，02，03，04，05，06，07，08，09，r=r， r=，則數(shù)據(jù)結(jié)構(gòu) a 是（ ）。(a) 線性結(jié)構(gòu)(b) 樹型結(jié)構(gòu)(c) 物理結(jié)構(gòu)(d) 圖型結(jié)構(gòu)2. 下面程序的時(shí)間復(fù)雜為（ ）for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext；p-data=q-data；p-next=q-next；

16、free(q)；(b) q=p-next；q-data=p-data；p-next=q-next；free(q)；(c) q=p-next；p-next=q-next；free(q)；(d) q=p-next；p-data=q-data；free(q)；4. 設(shè)有 n 個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個(gè)輔助記錄單元。(a) 1(b) n(c) nlog2n(d)n2 5設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以 20 為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(a) 10，15，14，18，20，36，40，21(b) 10，15，14，

17、18，20，40，36，21(c) 10，15，14，20，18，40，36，2l (d) 15，10，14，18，20，36，40，216. 設(shè)二叉排序樹中有 n 個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長(zhǎng)度為（ ）。(a) o(1)(b) o(log2n)(c)(d) o(n2)7. 設(shè)無(wú)向圖 g 中有 n 個(gè)頂點(diǎn) e 條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（）。(a) n，e (b) e，n (c) 2n，e(d) n，2e8. 設(shè)某強(qiáng)連通圖中有 n 個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（ ）條邊。(a) n(n-1)(b) n+1(c) n(d) n(n+1)9. 設(shè)有 5000

18、個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的 10 個(gè)記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。(a) 快速排序(b) 堆排序(c) 歸并排序(d) 插入排序10. 下列四種排序中（ ）的空間復(fù)雜度最大。(a) 插入排序(b) 冒泡排序(c) 堆排序(d) 歸并排序二、填空殖(每空 1 分 共 20 分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括和兩種情況。2. 設(shè)一棵完全二叉樹中有 500 個(gè)結(jié)點(diǎn)，則該二叉樹的深度為；若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則共有個(gè)空指針域。3. 設(shè)輸入序列為 1、2、3，則經(jīng)過(guò)棧的作用后可以得到種不同的輸出序列。4. 設(shè)有向圖 g 用鄰接矩陣 ann作為存

19、儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第 i 行上所有元素之和等于頂點(diǎn) i 的，第 i 列上所有元素之和等于頂點(diǎn) i 的。5. 設(shè)哈夫曼樹中共有 n 個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有個(gè)度數(shù)為 1 的結(jié)點(diǎn)。6. 設(shè)有向圖 g 中有 n 個(gè)頂點(diǎn) e 條有向邊，所有的頂點(diǎn)入度數(shù)之和為 d，則 e 和 d 的關(guān)系為。7. 遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或后序）。8. 設(shè)查找表中有 100 個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素 x，則最多需要比較 次就可以斷定數(shù)據(jù)元素 x 是否在查找表中。9. 不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為。10. 設(shè)有 n

20、個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從 1 開(kāi)始順序編號(hào)，則第 i 個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為，右孩子結(jié)點(diǎn)的編號(hào)為。11. 設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字 72 為基準(zhǔn)的一趟快速排序結(jié)果為。12. 設(shè)有向圖 g 中有向邊的集合 e=，則該圖的一種拓?fù)湫蛄袨椤?3. 下列算法實(shí)現(xiàn)在順序散列表中查找值為 x 的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j;j=i=k % p;

21、while (hashtablej.key!=k&hashtablej.flag!=0)j=() %m; if (i=j) return(-1); if () return(j); else return(-1);14. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值 k，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree; bitree*bstsearch(bitree *t, intk)if (t=0 ) return(0);elsewhile (t!=0)if (t-ke

22、y=k); else if (t-keyk) t=t-lchild; else;三、計(jì)算題(每題 10 分，共 30 分)1.已知二叉樹的前序遍歷序列是 aefbgcdhikj，中序遍歷序列是 efagbchkijd，畫出此二叉樹，并畫出它的后序線索二叉樹。2已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為0.6，假定選用的散列函數(shù)是 h（k）= k mod 7，若發(fā)生沖突采用線性探查法處理，試：（1） 計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：0123456（2） 求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。3已知序列（10，18，4，3，6，12，

23、1，9，18，8）請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計(jì)題(每題 15 分，共 30 分)1. 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。2. 設(shè)計(jì)一個(gè)求結(jié)點(diǎn) x 在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題(每題 1 分共 20 分)1設(shè)一維數(shù)組中有 n 個(gè)數(shù)組元素，則讀取第 i 個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（ ）。(a) o(n)(b) o(nlog2n)(c) o(1)(d) o(n2) 2設(shè)一棵二叉樹的深度為 k，則該二叉樹中最多有（ ）個(gè)結(jié)點(diǎn)。(a) 2k-1(b) 2k(c) 2k-1(d) 2k-13. 設(shè)某無(wú)向圖中有 n 個(gè)頂點(diǎn) e 條邊，則該無(wú)向圖中所有頂點(diǎn)

24、的入度之和為（）。(a) n(b) e(c) 2n(d) 2e 4在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。(a) o(1)(b) o(n)(c) o(log2n)(d) o(n2)5設(shè)某有向圖的鄰接表中有 n 個(gè)表頭結(jié)點(diǎn)和 m 個(gè)表結(jié)點(diǎn)，則該圖中有（ ）條有向邊。(a) n(b) n-1(c) m(d)m-1 6設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(a) 3(b) 4(c) 5(d) 87. 設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（ ）。(a) 必須判別棧是否為滿(b) 必須判別棧是否

25、為空(c) 判別棧元素的類型(d) 對(duì)棧不作任何判別8. 下列四種排序中（ ）的空間復(fù)雜度最大。(a) 快速排序(b) 冒泡排序(c) 希爾排序(d) 堆9. 設(shè)某二叉樹中度數(shù)為 0 的結(jié)點(diǎn)數(shù)為 n0，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為 nl，度數(shù)為 2 的結(jié)點(diǎn)數(shù)為n2，則下列等式成立的是（）。(a) n0=n1+1(b) n0=nl+n2(c) n0=n2+1(d) n0=2n1+l10. 設(shè)有序順序表中有 n 個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素 x 的最多比較次數(shù)不超過(guò)（ ）。(a) log2n+1(b) log2n-1(c) log2n(d) log2(n+1)二、填空題(每空 1 分共 20

26、 分)1. 設(shè)有 n 個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為，快速排序的平均時(shí)間復(fù)雜度為。2. 設(shè)指針變量 p 指向雙向循環(huán)鏈表中的結(jié)點(diǎn) x，則刪除結(jié)點(diǎn) x 需要執(zhí)行的語(yǔ)句序列為 （設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為 llink 和 rlink）。3. 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為 。4. 深度為 k 的完全二叉樹中最少有個(gè)結(jié)點(diǎn)。5. 設(shè)初始記錄關(guān)鍵字序列為(k1，k2，kn)，則用篩選法思想建堆必須從第個(gè)元素開(kāi)始進(jìn)行篩選。6. 設(shè)哈夫曼樹中共有 99 個(gè)結(jié)點(diǎn)，則該樹中有個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹中有 個(gè)空指針域。7. 設(shè)有一

27、個(gè)順序循環(huán)隊(duì)列中有 m 個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)個(gè)隊(duì)列元素（設(shè)頭指針 f 指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。8. 設(shè)順序線性表中有 n 個(gè)數(shù)據(jù)元素，則第 i 個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中 個(gè)數(shù)據(jù)元素；刪除第 i 個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中個(gè)元素。9. 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以 20 為中軸的一趟快速排序結(jié)果為。10. 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為。11. 設(shè)某無(wú)向圖 g 中有 n 個(gè)頂點(diǎn)，用鄰接矩

28、陣 a 作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn) i 和頂點(diǎn) j互為鄰接點(diǎn)的條件是。12. 設(shè)無(wú)向圖對(duì)應(yīng)的鄰接矩陣為 a，則 a 中第 i 上非 0 元素的個(gè)數(shù)第 i 列上非 0 元素的個(gè)數(shù)（填等于，大于或小于）。13. 設(shè)前序遍歷某二叉樹的序列為 abcd，中序遍歷該二叉樹的序列為 badc，則后序遍歷該二叉樹的序列為。14. 設(shè)散列函數(shù) h(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語(yǔ)句完成在散列表 hashtalbe 中查找關(guān)鍵字值等于 k 的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志 0。typedef struct node int key; struc

29、t node *next; lklist; void createlkhash(lklist *hashtable )int i,k;lklist *s;for(i=0;im;i+); for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;三、計(jì)算題(每題 10 分，共 30 分)1、畫出廣義表 ls=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。2、下圖所示的森林：(1) 求樹（a）的先根序列和后根序列；(2) 求森林先序序列和中序序列；（3） 將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；abcdefg hijk(a) (b)3、設(shè)散列表的地

30、址范圍是 0.9 ，散列函數(shù)為 h（key）= （key 2 +2）mod 9,并采用鏈表處理沖突，請(qǐng)畫出元素 7、4、5、3、6、2、8、9 依次插入散列表的存儲(chǔ)結(jié)構(gòu)。四、算法設(shè)計(jì)題(每題 10 分，共 30 分)1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題(20 分)1. 數(shù)據(jù)的最小單位是（ ）。(a) 數(shù)據(jù)項(xiàng)(b) 數(shù)據(jù)類型(c) 數(shù)據(jù)元素(d) 數(shù)據(jù)變量2

31、設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量 d=4 的一趟希爾排序結(jié)束后前 4 條記錄關(guān)鍵字為（）。(a) 40，50，20，95(b) 15，40，60，20(c) 15，20，40，45(d) 45，40，15，203設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5 個(gè)長(zhǎng)度為 2 的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。(a) 15，25，35，50，20，40，80，85，36，70 (b) 15，25，35，50，80，20，85，40，70，36 (c)

32、 15，25，35，50，80，85，20，36，40，70 (d) 15，25，35，50，80，20，36，40，70，854. 函數(shù) substr(“datastructure”，5，9)的返回值為（ ）。(a) “structure”(b) “data”(c) “astructur”(d)“datastructure” 5設(shè)一個(gè)有序的單鏈表中有 n 個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（）。(a) o(log2n)(b) o(1)(c) o(n2)(d) o(n)6. 設(shè)一棵m叉樹中度數(shù)為0 的結(jié)點(diǎn)數(shù)為n0，度數(shù)為1 的結(jié)點(diǎn)數(shù)為nl，度數(shù)為m 的

33、結(jié)點(diǎn)數(shù)為 nm，則 n0=（ ）。(a) nl+n2+nm(b) l+n2+2n3+3n4+(m-1)nm (c) n2+2n3+3n4+(m-1)nm(d) 2nl+3n2+(m+1)nm7. 設(shè)有序表中有 1000 個(gè)元素，則用二分查找查找元素 x 最多需要比較（）次。(a) 25(b) 10(c) 7(d) 18設(shè)連通圖 g 中的邊集 e=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn) a 出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（ ）。(a) abedfc(b) acfebd(c) aebdfc(d)aedfcb 9設(shè)輸入序列是 1、2、3

34、、n，經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是 n，則輸出序列中第 i 個(gè)輸出元素是（ ）。(a) n-i(b) n-1-i(c) n+1-i(d) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字 45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。(a) 40，42，45，55，80，83(b) 42，40，45，80，85，88 (c) 42，40，45，55，80，85(d) 42，40，45，85，55，80二、填空題(共 20 分)1. 設(shè)有一個(gè)順序共享?xiàng)?s0：n-1，其中第一個(gè)棧項(xiàng)指針 top1 的初值為-1，第二個(gè)棧頂指針 top2 的初

35、值為 n，則判斷共享?xiàng)M的條件是。2. 在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是。3. 設(shè)有一個(gè) n 階的下三角矩陣 a，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在 n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則 aij與 a00之間有 個(gè)數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為 表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為表。5. 設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為 abcdef，則該二叉樹的前序遍歷序列為，中序遍歷序列為，后序遍歷序列為。6. 設(shè)一棵完全二叉樹有 128

36、 個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為，有 個(gè)葉子結(jié)點(diǎn)。7. 設(shè)有向圖 g 的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣 a 來(lái)表示，則 a 中第 i 行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn) i 的，第 i 列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn) i 的。8. 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，kn)是堆，則對(duì) i=1，2，n/2 而言滿足的條件為。9. 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。void bubble(intrn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;rj=temp;exchange=1; if (exchange=0)

37、return；10. 下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。struct recordint key; int others; int bisearch(struct record r , int k)int low=0,mid,high=n-1; while(lownext=0(c) head-next=head(d)head!=0 4時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為 o(nlog2n)的是（ ）。(a) 堆排序(b) 冒泡排序(c) 希爾排序(d) 快速排序5. 設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。(a) 空或只有一個(gè)結(jié)

38、點(diǎn)(b) 高度等于其結(jié)點(diǎn)數(shù)(c) 任一結(jié)點(diǎn)無(wú)左孩子(d) 任一結(jié)點(diǎn)無(wú)右孩子6. 一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（ ）。(a) 堆排序(b) 冒泡排序(c) 快速排序(d) 希爾排序7. 設(shè)某棵三叉樹中有 40 個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為（ ）。(a) 3(b) 4(c) 5(d) 68. 順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（ ）。(a) o(n)(b) o(n2)(c) o(n1/2)(d) o(1og2n)9. 二路歸并排序的時(shí)間復(fù)雜度為（ ）。(a) o(n)(b) o(n2)(c) o(nlog2n)(d) o(1og2n)10. 深

39、度為 k 的完全二叉樹中最少有（）個(gè)結(jié)點(diǎn)。(a) 2k-1-1(b) 2k-1(c) 2k-1+1(d) 2k-111. 設(shè)指針變量 front 表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量 rear 表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針， 指針變量 s 指向?qū)⒁腙?duì)列的結(jié)點(diǎn) x，則入隊(duì)列的操作序列為（ ）。(a) front-next=s；front=s；(b) s-next=rear；rear=s；(c) rear-next=s；rear=s；(d) s-next=front；front=s；12. 設(shè)某無(wú)向圖中有 n 個(gè)頂點(diǎn) e 條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（）。(a) o(n+e)(b) o(n2)(c

40、) o(ne)(d) o(n3)13. 設(shè)某哈夫曼樹中有 199 個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（ ）個(gè)葉子結(jié)點(diǎn)。(a) 99(b) 100(c) 101(d) 10214. 設(shè)二叉排序樹上有 n 個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（ ）。(a) o(n)(b) o(n2)(c) o(nlog2n)(d) o(1og2n)15. 設(shè)用鄰接矩陣 a 表示有向圖 g 的存儲(chǔ)結(jié)構(gòu)，則有向圖 g 中頂點(diǎn) i 的入度為（ ）。(a) 第 i 行非 0 元素的個(gè)數(shù)之和(b) 第 i 列非 0 元素的個(gè)數(shù)之和(c) 第 i 行 0 元素的個(gè)數(shù)之和(d) 第 i 列 0 元素的個(gè)數(shù)之和二、判斷題(2

41、0 分)1. 調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。（ ）2. 分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（ ）3. 冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）4. 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5. 設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）6. 層次遍歷初始堆可以得到一個(gè)有序的序列。（ ）7. 設(shè)一棵樹 t 可以轉(zhuǎn)化成二叉樹 bt，則二叉樹 bt 中一定沒(méi)有右子樹。（ ）8. 線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ ）9. 中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（ ）1

42、0. 快速排序是排序算法中平均性能最好的一種排序。（ ）三、填空題(30 分)1for(i=1，t=1，s=0；i=n；i+) t=t*i；s=s+t；的時(shí)間復(fù)雜度為。2設(shè)指針變量 p 指向單鏈表中結(jié)點(diǎn) a，指針變量 s 指向被插入的新結(jié)點(diǎn) x，則進(jìn)行插入操作的語(yǔ)句序列為 （設(shè)結(jié)點(diǎn)的指針域?yàn)?next）。3設(shè)有向圖 g 的二元組形式表示為 g=（d，r），d=1，2，3，4，5，r=r， r=，則給出該圖的一種拓?fù)渑判蛐蛄?。4. 設(shè)無(wú)向圖 g 中有 n 個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是。5. 設(shè)二叉樹中度數(shù)為 0 的結(jié)點(diǎn)數(shù)為 50，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為 30，則該二叉樹中總共有 個(gè)

43、結(jié)點(diǎn)數(shù)。6. 設(shè) f 和r 分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為 。7. 設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為 lchild 和 rchild，則判斷指針變量 p 所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是。8. 簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為。9. 快速排序算法的空間復(fù)雜度平均情況下為，最壞的情況下為。10. 散列表中解決沖突的兩種方法是和。四、算法設(shè)計(jì)題(20 分)設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題(30 分)1. 設(shè)某無(wú)向圖有 n 個(gè)頂點(diǎn)，則該無(wú)向圖的

44、鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。(a) 2n(b) n(c) n/2(d) n(n-1)2. 設(shè)無(wú)向圖 g 中有 n 個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹上有（ ）條邊。(a) n(b) n-1(c) 2n(d) 2n-13. 設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字 45 為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。(a) 40，42，60，55，80，85(b) 42，45，55，60，85，80 (c) 42，40，55，60，80，85(d) 42，40，60，85，55，804（）二叉排序樹可以得到一個(gè)從小到大的有序序列。(a) 先序遍歷(b) 中序遍歷(c

45、) 后序遍歷(d) 層次遍歷5. 設(shè)按照從上到下、從左到右的順序從 1 開(kāi)始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為 i 結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。(a) 2i+1(b) 2i(c) i/2(d) 2i-16. 程序段 s=i=0；do i=i+1； s=s+i；while(inext=0(c) head-next=head(d)head!=0 8設(shè)某棵二叉樹的高度為 10，則該二叉樹上葉子結(jié)點(diǎn)最多有（ ）。(a) 20(b) 256(c) 512(d) 10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個(gè)數(shù)為（ ）。(a) 1(b) 2(c) 3(d