數(shù)據(jù)結(jié)構(gòu)模擬題(開卷)

1、中國(guó)地質(zhì)大學(xué)（北京）繼續(xù)教育學(xué)院 2014年12課程考試數(shù)據(jù)結(jié)構(gòu)模擬題（補(bǔ)）一 單項(xiàng)選擇題1. 在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是【 】。a單鏈表b雙鏈表c順序表d循環(huán)鏈表2. 設(shè)計(jì)一個(gè)判定表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用【 】數(shù)據(jù)結(jié)構(gòu)最佳。a集合b線性表c隊(duì)列d棧3. n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為【 】。a2nbn-1cndn+14. 設(shè)廣義表d=(a,(b,c),則tail(d）=【 】。ab,c b(b,c) c(b,c) dc5. 由4個(gè)結(jié)點(diǎn)可以構(gòu)造出【 】種不同的二叉樹。a12b13c14d156. 在棧中，出棧操作的時(shí)間復(fù)雜度為【 】。ao(1)b

2、o(n)co(log2n)do(n2)7. 假設(shè)q0.len-1表示循環(huán)隊(duì)列，f為隊(duì)頭指針，r為隊(duì)尾指針，則進(jìn)隊(duì)操作語句是【 】。af=f+1br=r+1cf=(f+1)%lendr=(r+1)%len8. 一個(gè)n*n的對(duì)稱矩陣，如果以行或列為主序放入內(nèi)存，則其容量為【 】。an*nbn*n/2cn*(n+1)/2d(n+1)*(n+1)/29. 隊(duì)列操作的原則是【 】。a進(jìn)優(yōu)于出b出優(yōu)于進(jìn)c先進(jìn)先出d后進(jìn)先出10. 下列數(shù)據(jù)結(jié)構(gòu)中，【 】是非線性數(shù)據(jù)結(jié)構(gòu)。a棧b串c隊(duì)列d樹11. 兩個(gè)指針p和q，分別指向單鏈表的兩個(gè)元素，p所指元素是q所指元素的前驅(qū)，則【 】。ap=qbq-next=pcp

3、-next=qdp-next=q-next12. 數(shù)組a中，每個(gè)元素的長(zhǎng)度為4個(gè)字節(jié)，行下標(biāo)i從1到5，列下標(biāo)j從1到4，從首地址sa開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素a32的起始地址為【 】。asa+20bsa+36csa+40dsa+4513. 已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為d1，則第i個(gè)結(jié)點(diǎn)的地址為【 】。ad1+(i-1)*mbd1+i*mcd1+(i+1)mdd1-i*m14. 分析下列算法suanfa1(n)的時(shí)間復(fù)雜度是【 】。 void suanfa1(int n) int i,j,x=1； for(i=0；in；i+)

4、for(j=0；jn；j+) x=x*2； ao(2n) bo(2n) co(n2) do(n2+2)15. 將一個(gè)a1.10,1.10的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組b1,30中，a中元素a6,5在b數(shù)組中的位置i為【 】。a15b16c55d6516. 深度為6的二叉樹最多有【 】個(gè)結(jié)點(diǎn)。a62b63c64c6517. 由3個(gè)結(jié)點(diǎn)可以構(gòu)造出【 】種不同的二叉樹。a2b3c4d518. 棧的插入和刪除操作在【 】進(jìn)行。a棧頂b棧底c指定位置d隨機(jī)位置19. 數(shù)組a中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到5，列下標(biāo)j從1到4，從首地址sa開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組占用的字節(jié)數(shù)為【 】

5、。a20b60c80d12020. 下面語句的時(shí)間復(fù)雜度為【 】。s=0;for(i=1;inext=pcp-next=q-nextdp-next=q28. 線性表在【 】時(shí), 宜用順序表作存儲(chǔ)結(jié)構(gòu)。a經(jīng)常隨機(jī)存取 b經(jīng)常作插入、刪除 c無足夠連續(xù)存儲(chǔ)空間 d經(jīng)常作動(dòng)態(tài)增減二、 判斷題1. 【 】二叉排序樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空孩子（若存在的話）的關(guān)鍵字值，且小于其右非空孩子（若存在的話）結(jié)點(diǎn)的關(guān)鍵字值。2. 【 】算法必須具備的5個(gè)特征是：有窮性、確定性、可行性、有0或多個(gè)輸入量，至少有1個(gè)輸出量。3. 【 】完全二叉樹的某結(jié)點(diǎn)若沒有左孩子，則它必是葉子結(jié)點(diǎn)。4. 【 】哈夫曼樹是

6、帶權(quán)路徑最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。5. 【 】空棧就是所有元素都為0的棧。6. 【 】在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的指針即可；因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。7. 【 】n*n對(duì)稱矩陣經(jīng)過壓縮存儲(chǔ)后占用的存儲(chǔ)單元是原來的1/2。8. 【 】一個(gè)棧的輸入序列是12345，則棧的輸出序列可以是54312。9. 【 】對(duì)于一個(gè)非空二叉樹，它的根節(jié)點(diǎn)作為第一層，則第i層上最多能有2i-1個(gè)結(jié)點(diǎn)。10. 【 】稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。11. 【 】完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。12. 【 】用帶表頭結(jié)點(diǎn)的單鏈表表示隊(duì)列，則判斷隊(duì)列為空的標(biāo)

7、準(zhǔn)是頭指針和尾指針均指向同一個(gè)結(jié)點(diǎn)。13. 【 】做進(jìn)棧運(yùn)算時(shí)應(yīng)先判別,棧是否為空。14. 【 】廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。三、 填空題1. 數(shù)據(jù)結(jié)構(gòu)包含四種基本結(jié)構(gòu)，它們是集合、【 1 】、樹形結(jié)構(gòu)、【 2 】。2. 二叉樹的深度為k的二叉樹最多有【 3 】個(gè)結(jié)點(diǎn)，其中第i層最多有【 4 】個(gè)結(jié)點(diǎn)。3. n個(gè)結(jié)點(diǎn)的完全二叉樹，使用一維數(shù)組t存儲(chǔ)結(jié)點(diǎn)元素的值，假設(shè)ti存儲(chǔ)第i個(gè)結(jié)點(diǎn)，那么ti的雙親是【 5 】，左小孩是【 6 】，右小孩是t2*i+1。4. 由權(quán)值分別為11,8,6,2,5的葉子結(jié)點(diǎn)生成一顆哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為【 7 】。5. 若串s=hello，其子串個(gè)數(shù)是【

8、 8 】。6. 將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為24的結(jié)點(diǎn)x的左孩子編號(hào)為【 9 】，右孩子編號(hào)為【 10 】。7. 長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法時(shí)間復(fù)雜度為【 11 】。8. wpl(t)指的是樹的【 12 】，即每個(gè)葉子的權(quán)與根到該葉子的路徑長(zhǎng)度的乘積之和。9. 深度為k且有【 13 】個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。10. 3層完全二叉樹至少有【 14 】個(gè)結(jié)點(diǎn)。四、簡(jiǎn)答題1. 畫出二叉樹的5種基本形態(tài)。2. 線性表的順序存儲(chǔ)結(jié)構(gòu)相比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，有什么優(yōu)缺點(diǎn)？適用于什么情況的存儲(chǔ)？3. 已知一顆非空二叉樹

9、，按前序遍歷的結(jié)果是acbgdehfji，按中序遍歷的結(jié)果是cgbahedjfi，請(qǐng)畫出該二叉樹，并寫出后序遍歷的序列結(jié)果。4. 若比較頻繁的對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表適合采用哪種存儲(chǔ)結(jié)構(gòu)？為5. 簡(jiǎn)述二叉排序樹（二叉查找樹）的定義及特點(diǎn)。參考答案：一單項(xiàng)選擇題12345678910caddbdcacb11121314151617181920aabbcbdaba2122232425262728acdcdcda二判斷題1234567891011121314三填空題12345線性結(jié)構(gòu)圖狀結(jié)構(gòu)2k-12i-1ti/2678910t2*i3215484911121314o(n)帶權(quán)路徑長(zhǎng)

10、度2k-14四、簡(jiǎn)答題1. 畫出二叉樹的5種基本形態(tài)。2. 線性表的順序存儲(chǔ)結(jié)構(gòu)相比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，有什么優(yōu)缺點(diǎn)？適用于什么情況的存儲(chǔ)？?jī)?yōu)點(diǎn)：1）是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù)，速度快；2）結(jié)構(gòu)簡(jiǎn)單，邏輯上相鄰的元素在物理上也是相鄰的；3）不使用指針，節(jié)省存儲(chǔ)空間。缺點(diǎn)：1）插入和刪除元素要移動(dòng)大量元素，消耗大量時(shí)間；2）需要一個(gè)連續(xù)的存儲(chǔ)空間；3）插入元素可能發(fā)生“溢出”；4）自由區(qū)中的存儲(chǔ)空間不能被其他數(shù)據(jù)占用（共享）。適用于經(jīng)常用于檢索、存取元素，但是插入和刪除元素操作較少的情況。3. 已知一顆非空二叉樹，按前序遍歷的結(jié)果是acbgdehfji，按中序遍歷的結(jié)果是cgbahedjfi，請(qǐng)畫出該二叉樹，并寫出后序遍歷的序列結(jié)果。二叉樹：后序遍歷的結(jié)果是gbchejifda4.若比較頻繁的對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表適合采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？時(shí)間復(fù)雜度是多少？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)殒準(zhǔn)酱鎯?chǔ)的線性表，插入和刪除操作只需要改變指針，時(shí)間復(fù)雜度為o（1