計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)平時(shí)測(cè)試試題二

1、臨沂大學(xué) 2015-2016 學(xué)年度第一學(xué)期數(shù)據(jù)結(jié)構(gòu)平時(shí)測(cè)試試題一一、判斷題(共14題，每題 1分，共 14分)1. 線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。( )2. 順序存儲(chǔ)結(jié)構(gòu)只能用來(lái)存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用來(lái)存放非線性結(jié)構(gòu)。( )3. 線性表采用鏈表方式和順序表方式存儲(chǔ)，執(zhí)行插入和刪除運(yùn)算的時(shí)間復(fù)雜度都是O(N) ，因而兩種存儲(chǔ)方式的插入、刪除運(yùn)算所花費(fèi)的時(shí)間相同。()4. 雙循環(huán)鏈表中，任一個(gè)結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。( )5. 在鏈隊(duì)列中，即便不設(shè)置尾指針也能進(jìn)行入隊(duì)列操作。( )6. 在順序表中取出第 i 個(gè)元素所花費(fèi)的時(shí)間與 i 成正比。 ( )7. 已知指針

2、 P指向鏈表 L中某結(jié)點(diǎn)，執(zhí)行語(yǔ)句 P=P-next 不會(huì)刪除該鏈表中結(jié)點(diǎn)。 ( )8. 在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，任一結(jié)點(diǎn)的后繼指針均不空。( )9. 完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉。( )10. 二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。( )11. 設(shè)與一棵樹(shù) T 所對(duì)應(yīng)的二叉樹(shù)為 BT ，則與 T 中的葉子結(jié)點(diǎn)所對(duì)應(yīng)的 BT 中的結(jié)點(diǎn)也一定 是葉子結(jié)點(diǎn)。 ( )12. 當(dāng)一棵具有 n 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的 WPL 值為最小時(shí)， 稱其樹(shù)為 Huffman 樹(shù)，且其二叉 樹(shù)的形狀必是唯一的。 ( )13. 二叉樹(shù)的前序遍歷并不能唯一確定這棵樹(shù)，是因?yàn)槲覀?/p>

3、不知道該樹(shù)的根結(jié)點(diǎn)是哪一個(gè)。( )14. 對(duì)于有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為 log 2n。 ()二、選擇題(共40題，每題 1分，共 40分)1. 通常從正確性、易讀性、健壯性、高效性等四個(gè)方面評(píng)價(jià)算法( 包括程序 )的質(zhì)量。以下解釋錯(cuò)誤的是 ( )A 、正確性 算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能 (即處理要求 )B、易讀性 算法應(yīng)易于閱讀和理解 以便于調(diào)試 修改和擴(kuò)充C、健壯性 當(dāng)環(huán)境發(fā)生變化時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不需要的運(yùn) 行結(jié)果D、高效性 即達(dá)到所需要的時(shí)間性能2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指( )B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C、數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D、存儲(chǔ)在外

4、存中的數(shù)據(jù)A、數(shù)據(jù)所占的存儲(chǔ)空間量3. 下列屬于線性數(shù)據(jù)結(jié)構(gòu)的是 ( )D.不確定D數(shù)據(jù)項(xiàng)A. 隊(duì)列B.樹(shù)C.圖4. 線性表是具有 n 個(gè) ()的有限序列A 表元素B字符C數(shù)據(jù)元素5. 對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是( )A、無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)C、插入和刪除運(yùn)算較方便D、容易造成一部分空間長(zhǎng)期閑置而得不到充分利用6. 對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來(lái)說(shuō)，通常以( )為標(biāo)準(zhǔn)操作A、結(jié)點(diǎn)移動(dòng)B、條件判斷C、算術(shù)表達(dá)式D 、賦值語(yǔ)句7若線性表最常用的操作是存取第i 個(gè)元素及其前驅(qū)的值，則采用( ) 存儲(chǔ)方式節(jié)省時(shí)間A.

5、 單鏈表B.雙向鏈表C.單循環(huán)鏈表D. 順序表8. 單鏈表的每個(gè)結(jié)點(diǎn)中包括一個(gè)指針 link ，它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。現(xiàn)要將指針 q 指向 的新結(jié)點(diǎn)插入到指針 p 指向的結(jié)點(diǎn)之后，下面的操作序列中哪一個(gè)是正確的？( )A 、 p-link = q-link; q = p-link;B、 p-link = q; q-link = p-link;C、 q-link = p-link; p-link=q;D、q = p-link; p-link = q-link;9在雙向循環(huán)鏈表中 ,在 p 指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q 所指向的新結(jié)點(diǎn) ,其修改指針的操作是 ( )注 :雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為

6、(prior,data,next) 。 供選擇的答案：A.p-prior=q ； q-next=p ； p-prior-next=q ； q-prior=q ；B. p-prior=q ； p-prior-next=q ； q-next=p ； q-prior=p-prior ；C. q-next=p ； q-prior=p-prior ； p-prior-next=q; p-prior=q;D. q-prior=p-prior ； q-next=p ； p-prior=q ； p-prior-next =q ；10. 設(shè)有一順序棧 S，元素 s1,s2,s3,s4,s5,s6 依次進(jìn)棧，如果

7、 6 個(gè)元素出棧的順序是 s2,s3,s4,s6,s5,s1則, 棧的容量至少應(yīng)該是 ( )A、2B、3C、5D、611. 設(shè)有六列火車，編號(hào)為 1，2，3，4，5，6 順序開(kāi)進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)，問(wèn)下列輸出序 列中，哪個(gè)是不可能出現(xiàn)的 ( )A.1,2,3,4,5,6B.6,5,4,3,2,1C.3,1,2,6,5,4D.3,2,1,6,5,412. 一個(gè)隊(duì)列的入隊(duì)列順序是 1， 2， 3，4，則隊(duì)列的輸出系列是( )A、4，3，2，1B、1， 2，3，4C、1，4，3，2D、3， 2，4，113. 將一棵有 100 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn) 編號(hào)，根

8、結(jié)點(diǎn)的編號(hào)為 1，則編號(hào)為 49 的結(jié)點(diǎn)的左孩子編號(hào)為 ( )A.98B.99C.50D.4814.二叉樹(shù)的第I 層上最多含有結(jié)點(diǎn)數(shù)為 ()IA.2II-1B.2I-1-1I-1C.2I-1ID.2I -115. 設(shè)深度為 k 的二叉樹(shù)上只有度為 0 和度為 2 的結(jié)點(diǎn)， 則這類二叉樹(shù)上所含結(jié)點(diǎn)總數(shù)最少 ( )A.k+1 B.2k C.2k-1 D.2k+116. 下列有關(guān)二叉樹(shù)的說(shuō)法正確的是 ( )A. 二叉樹(shù)的度為 2 B.一棵二叉樹(shù)度可以小于 2 C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任一個(gè)結(jié)點(diǎn)的度都為 217. 將含有 83個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始編號(hào)，根為1 號(hào)，按從上

9、到下、從左到右順序結(jié)點(diǎn)編號(hào)，那么編號(hào)為 41的雙親結(jié)點(diǎn)編號(hào)為 ()A.42B.40C.21D.2018.一棵具有n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 ()A. log2n +1B.log 2n+1C. log2nD.log 2n-119. 設(shè)樹(shù) T的度為 4，其中度為 1，2，3和 4的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2，1，1 則 T中的葉子 數(shù)為 ( )A.5 B.6 C.7 D.820. 設(shè)有 13個(gè)值 ,用它們組成一棵哈夫曼樹(shù) ,則該哈夫曼樹(shù)共有 ( )個(gè)結(jié)點(diǎn).A.13B.12C.26D.2521樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的A. 先序序列 B.中序序列C.后序序列 D. 層次序列22. 為解

10、決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將 要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)， 而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。 該緩沖區(qū)的邏輯 結(jié)構(gòu)應(yīng)該是 ( )A. 棧 B. 隊(duì)列 C. 樹(shù) D. 圖23. 設(shè)棧 S和隊(duì)列 Q 的初始狀態(tài)均為空，元素abcdefg 依次進(jìn)入棧 S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列 Q，且 7 個(gè)元素出隊(duì)的順序是 bdcfeag，則棧 S 的容量至少是 ( )A1B. 2C. 3D. 424. 給定二叉樹(shù)圖所示。設(shè) N 代表二叉樹(shù)的根， L 代表根結(jié)點(diǎn)的左子樹(shù)， R 代 表根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列為3，1，7，5，6，2，4，則其遍歷 方

11、式是 ( )ALRNB. NRLC. RLN D. RNL25. 已知一棵完全二叉樹(shù)的第 6層(設(shè)根為第 1層)有 8 個(gè)葉結(jié)點(diǎn)，則完全二叉樹(shù)的結(jié)點(diǎn)個(gè) 數(shù)最多是 ( )A39B. 52 C. 111D. 11926. 將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn) u 是結(jié)點(diǎn) v 的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則 在原來(lái)的森林中， u 和 v 可能具有的關(guān)系是 I父子關(guān)系II.兄弟關(guān)系 III. u 的父結(jié)點(diǎn)與 v的父結(jié)點(diǎn)是兄弟關(guān)系 ( )A. 只有 II B.I 和 II C.I 和 IIID.I 、 II 和 III27、若元素 a,b,c,d,e,f 依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)

12、 三次進(jìn)行退棧工作，則不可能得到的出棧序列是( )A：dcebfa B： cbdaefC：dbcaef D：afedcb28、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作， 但僅允許在一端進(jìn)行出隊(duì)操作， 則不可 能得到的順序是( )A：bacdeB：dbaceC：dbcaeD： ecbad29、下列線索二叉樹(shù)中(用虛線表示線索) ，符合后序線索樹(shù)定義的是( )30、在下列所示的平衡二叉樹(shù)中插入關(guān)鍵字 48 后得到一棵新平衡二叉樹(shù)，在新 平衡二叉樹(shù)中，關(guān)鍵字 37 所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（）A：13，48B： 24，48C：24， 53D： 24，9031、在一棵度為 4 的樹(shù) T中，若有

13、 20 個(gè)度為 4 的結(jié)點(diǎn)， 10 個(gè)度為 3 的結(jié)點(diǎn)， 1 個(gè)度為 2 的結(jié)點(diǎn)， 10個(gè)度為 1 的結(jié)點(diǎn)，則樹(shù) T的葉節(jié)點(diǎn)個(gè)數(shù)是（）A：41B： 82C：113D：12232、對(duì) n（n 大于等于 2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)， 關(guān)于該樹(shù)的敘述中， 錯(cuò)誤的是（）A：該樹(shù)一定是一棵完全二叉樹(shù)B：樹(shù)中一定沒(méi)有度為 1 的結(jié)點(diǎn)C：樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) D：樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值33、求整數(shù) n（n0）階乘的算法如下，其時(shí)問(wèn)復(fù)雜度是 （ ）int fact（int n）if （n一 1）return 1;return n*fact（n 一 1）;A

14、. O(logzn)B. 0(n)C. (nlogzn)D. 0(n2)34、已知操作符包括 +、一、*、/、(和 )。將中綴表達(dá)式 a+b-a* (c+d)/e-f)+g 轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放暫時(shí)還不 能確定運(yùn)算次序的操 作符，若棧初始時(shí)為空， 則轉(zhuǎn)換過(guò)程中同時(shí)保存棧中的 操作符的最大個(gè)數(shù)是 ( )A. 5B. 7C. 8D. 1135、若一顆二叉樹(shù)的前序遍歷序列為 a, e, b, d, c，后續(xù)遍歷序列為 b, c, d, e, a， 則根節(jié)點(diǎn)的孩子節(jié)點(diǎn) ( )A. 只有 e B. 有 e、bC. 有 e、cD. 無(wú)法確定36. 已知兩個(gè)長(zhǎng)

15、度分別為 m 和 n 的升序鏈表，若將它們合并為一個(gè)長(zhǎng)度為 m+n 的降序鏈表，則最壞情況下的時(shí)間復(fù)雜度是A. O ( n )B. O( m *n)C. O( min( m, n) )D. O( max( m, n)37. 一個(gè)棧的入棧序列為 1, 2, 3, ,n ，其出棧序列是 P1 ,P2, P3, ,Pn, 。若 P2= 3， 則 P3 可能取值的個(gè)數(shù)是A. n-3B. n- 2 C. n -1D . 無(wú)法確定38. 若將關(guān)鍵字 1，2，3，4，5，6，7 依次插入到初始為空的平衡二叉樹(shù) T 中， 則 T 中平衡因子為 0 的分支結(jié)點(diǎn)的個(gè)數(shù)是A. 0B. 1C. 2D. 339. 已知

16、三叉樹(shù) T 中 6 個(gè)葉結(jié)點(diǎn)的權(quán)分別是 2，3，4，5，6，7，T 的帶權(quán)(外 部)路徑長(zhǎng)度最小是A. 27B. 46C. 54D. 5640. 若 X 是后序線索二叉樹(shù)中的葉結(jié)點(diǎn)，且 X 存在左兄弟結(jié)點(diǎn) Y，則 X 的右 線索指向的是A. X 的父結(jié)點(diǎn)B. 以 Y 為根的子樹(shù)的最左下結(jié)點(diǎn)C. X 的左兄弟結(jié)點(diǎn) YD. 以 Y 為根的子樹(shù)的最右下結(jié)點(diǎn)三、構(gòu)造題 (共 2 題，每題 10 分，共 20 分)1. 已知某二叉樹(shù)的先序遍歷序列為： ABDGCEFH ；中序遍歷序列為： DGBAECHF 。 (1)試畫(huà)出該二叉樹(shù)。 ( 4 分)2）求二叉樹(shù)的后序遍歷序列（ 2 分） （3）試畫(huà)出該二叉樹(shù)對(duì)應(yīng)的森林。 （2 分）2.已知字符 A-F 的出現(xiàn)頻率依次為 2， 3，5，6，11，9，（1） 給出上述字符最優(yōu)編碼對(duì)應(yīng)的 Huffman 樹(shù)，并在葉子旁標(biāo)注相應(yīng)字符； （3 分 ）（2）計(jì)算上述 Huffman 樹(shù)的帶權(quán)路徑長(zhǎng)度。 （2 分）四、算法設(shè)計(jì) （26 分）1. 帶頭結(jié)點(diǎn)的單鏈表，其長(zhǎng)度存放在頭結(jié)點(diǎn)的數(shù)據(jù)域中，設(shè)計(jì)一算法求 倒數(shù) 第 k 個(gè)結(jié)點(diǎn)的 值，并且刪除該結(jié)點(diǎn)。要求：（