山東科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)（c）復(fù)習(xí)思考題一一、單選題（每題2分，共20分）1、棧和隊(duì)列的共同特點(diǎn)是（A ）oA、只允許在端點(diǎn)處插入和刪除元素B、都是先進(jìn)后出C、都是先進(jìn)先出D、沒(méi)有共同點(diǎn)2、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)（C ）oA、數(shù)據(jù)的處理方法B、數(shù)據(jù)元素的類(lèi)型C、數(shù)據(jù)元素之間的關(guān)系D、數(shù)據(jù)的存儲(chǔ)方法3、計(jì)算機(jī)中的算法指的是解決某一個(gè)問(wèn)題的有限運(yùn)算序列，它必須具備輸入、 輸出、（B ）等5個(gè)特性。A、可執(zhí)行性、可移植性和可

2、擴(kuò)充性 B、可執(zhí)行性、有窮性和確定性C、確定性、有窮性和穩(wěn)定性 D、易讀性、穩(wěn)定性和確定性4、設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（A ）條邊。A、n（n-l）/2 B、n（n-l） C、n（n+l）/2 D、（nT）/25、用某種排序方法對(duì)關(guān)鍵字序列（25, 84, 21, 47, 15, 27, 68, 35, 20）進(jìn) 行排序時(shí)，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25

3、,35,27,47,68,8415,20,21,25,27,35,47,68,84則所采用的排序方法是（D ）。A、選擇排序B、希爾排序 C、歸并排序 D、快速排序6、設(shè)某棵二叉樹(shù)的中 序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該 二叉樹(shù)得到序列為 （A ）oA、BADCB、BCDAC、CDABD、CBDA7、設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為（C ）oA、9B、 10C、 11D、 128、若長(zhǎng)度為n

4、的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的10、字符串的長(zhǎng)度是指（C ）o二、填空題（每空2分，共20分）1、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元 素el,e2,e3,e4,e5,初依次通過(guò)棧S, 一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè) 元素出隊(duì)的序列是e2, e4, e3, e6, e5, el, 則棧的容量至少應(yīng)該是3 。2、n個(gè)頂點(diǎn)的連通圖至少有nT條邊。3、數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種情況。4、設(shè)一

5、棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為 9；若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有 501 個(gè)空指針域。5、通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：時(shí)間 正確性、占用內(nèi)存易讀性、復(fù)雜 度強(qiáng)壯性和準(zhǔn)確度高效率。6、設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有 n（n-l）條有向條; 設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有n（nT）/2條無(wú)向邊。三、判斷題。（每題1分，共10分）1、線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)， 結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)

6、部的存儲(chǔ)空間可以是不連續(xù)的。（X ）2、對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（X ）3、在單鏈表中，給定任一結(jié)點(diǎn)的地址p,則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p 的后面：p— >next； （ X ）4、隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線(xiàn)性表，是一種先進(jìn)后出 的結(jié)構(gòu)。（X ）5、二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。（V ） 6、用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（X ）

7、7、在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（X ）8、在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過(guò)排序，這些記 錄的相對(duì)次序仍然保持不變，稱(chēng)這種排序?yàn)榉€(wěn)定排序。(V )9、完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。(J )10、哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。(V )四、簡(jiǎn)答題(每題10分，共20分)1、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型兩個(gè)概念之間 有區(qū)別嗎？答：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類(lèi) A、