1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題（含部分參考答案版）一、 單項(xiàng)選擇題1. 按照數(shù)據(jù)邏輯結(jié)構(gòu)的不同，可以將數(shù)據(jù)結(jié)構(gòu)分成 C 。 A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2. 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是 A 。 A. 數(shù)組是同類型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為復(fù)雜 C. 樹是一種線性的數(shù)據(jù)結(jié)構(gòu)D. 用一維數(shù)組存儲(chǔ)二叉樹，總是以先序順序遍歷各結(jié)點(diǎn) 3. 在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 B A.邏輯結(jié)構(gòu) B.順序存儲(chǔ)結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2、D.以上都不對4. 以下關(guān)于算法特性的描述中， B 是正確的。 （1）算法至少有一個(gè)輸入和一個(gè)輸出（2）算法至少有一個(gè)輸出但是可以沒有輸入（3）算法可以永遠(yuǎn)運(yùn)行下去A. （1） B. （2） C. （3） D. （2）和（3）5. 對順序存儲(chǔ)的線性表（a1,a2,an）進(jìn)行插入操作的時(shí)間復(fù)雜度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1)6. 鏈表不具有的特點(diǎn)是 A 。 A.可隨機(jī)訪問任一元素 B.插入和刪除時(shí)不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間 D.所需空間與線性表的長度成正比7.線性鏈表中各鏈結(jié)點(diǎn)之間的地址 C 。 A.必須連續(xù) B.部分地址必須連續(xù)C

3、.不一定連續(xù) D.連續(xù)與否無關(guān)8. 以下關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中， C 是不正確的。 A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接C.可以通過計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址D.插入、刪除操作方便，不必移動(dòng)結(jié)點(diǎn)9. 設(shè)依次進(jìn)入一個(gè)棧的元素序列為d, a, c, b,得不到出棧的元素序列為 D 。A. dcba B. acdb C. abcd D. cbda10. 將新元素插入到鏈?zhǔn)疥?duì)列中時(shí)，新元素只能插入到 B 。A. 鏈頭 B. 鏈尾 C. 鏈中 D. 第i個(gè)位置，i大于等于1，大于等于表長加111. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1

4、、e2、e3、e4、e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、和e1，則棧S容量至少應(yīng)該是 C 。 A. 6 B. 4 C. 3 D. 212.下面 D 是abcd321ABCD的子串。A. abcd B. 321ab C. abc ABC D. 21AB13.假設(shè)8行10列的二維數(shù)組A18，110分別以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍蝽樞虼鎯?chǔ)時(shí)，其首地址相同，那么以行序?yàn)橹餍驎r(shí)元素a3，5的地址與以列序?yàn)橹餍驎r(shí) C 元素相同。A. a7，3 B. a8，3 C. a1，4 D. ABC都不對14. 數(shù)組A05，06的每個(gè)元素占5個(gè)字節(jié)，將

5、其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址為 A 。 A. 1175 B. 1180 C. 1205 D.1210 15.下列廣義表中，長度為3的廣義表為 B 。A.（a,b,c,( )） B. (g),(a,b,c,d,f),( ) C. (a,(b,(d) D. ( )16. 以下關(guān)于廣義表的敘述中，正確的是 A 。 A. 廣義表是0個(gè)或多個(gè)單元素或子表組成的有限序列B. 廣義表至少有一個(gè)元素是子表C. 廣義表不可以是自身的子表D. 廣義表不能為空表17.若樹T有a個(gè)度為1的結(jié)點(diǎn)，b個(gè)度為2的結(jié)點(diǎn)，c個(gè)度為3的結(jié)點(diǎn)，則該樹有 D 個(gè)葉結(jié)點(diǎn)。A. 1+2b+3c

6、 B. a+2b+3c C.2b+3c D. 1+b+2c18.若一棵二叉樹有102片葉子結(jié)點(diǎn)，則度二叉樹度為2的結(jié)點(diǎn)數(shù)是 B 。A. 100 B. 101 C. 102 D. 103 19. 在有n 個(gè)葉子結(jié)點(diǎn)的霍夫曼樹中，其結(jié)點(diǎn)總數(shù)為： 。 A. n B. 2n C. 2n +1 D. 2n - 120.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有 B 。A. 5個(gè)葉子結(jié)點(diǎn) B. 5個(gè)度為2的結(jié)點(diǎn)C. 7個(gè)分支結(jié)點(diǎn) D. 2個(gè)度為1的結(jié)點(diǎn)21.設(shè)結(jié)點(diǎn)x和y是二叉樹中的任意兩結(jié)點(diǎn)，若在先根序列中x在y之前，而后根序列中x在y之后，則x和y的關(guān)系是 C 。A. x是y的左兄弟 B. x是y的右兄弟C. x是y

7、的祖先 D. x是y的后代22. 先序遍歷序列與中序遍歷序列相同的二叉樹為 。 A. 根結(jié)點(diǎn)無左子樹的二叉樹 B.根結(jié)點(diǎn)無右子樹的二叉樹C. 只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有左子樹的二叉樹D. 只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有右子樹的二叉樹23.若二叉樹T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf，則其后序遍歷序列為 A 。A. ceadfb B. feacdb C. eacdfb D. 以上都不對 24.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有 C 條邊。A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.對于一個(gè)有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接

8、表表示，鄰接表中的結(jié)點(diǎn)總數(shù)是 C 。A. e/2 B. e C. n+2e D. n+e26. 無向圖G=（V，E），其中V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)。對該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列是 D 。A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不屬于內(nèi)排序方法的是 C 。A. 插入排序法 B. 選擇排序法 C. 拓?fù)渑判蚍?D. 歸并排序法28. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為 B 。A. O(log2n) B. O(n) C. O(nl

9、og2n) D. O(n2) 29.對有n個(gè)記錄的表作快速排序，在最壞情況，算法的時(shí)間復(fù)雜度是 D 。A. O(n3) B. O(n) C. O(nlog2n) D. O(n2) 30.下面的排序算法中，穩(wěn)定是 A 。A. 直接插入排序法 B. 快速排序法 C. 直接選擇排序法 D. 堆排序法二、 填空題1. 一個(gè)算法具有5個(gè)特性： 、 、 、有零個(gè)或多個(gè)輸入，一個(gè)或多個(gè)輸出。2. .設(shè)數(shù)組a150，180的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a45，68的存儲(chǔ)地址為 9174 ；若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a45，68的存儲(chǔ)地址為 8788 。3. 當(dāng)線

10、性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用 存儲(chǔ)結(jié)構(gòu)。4.兩個(gè)字符串相等的充分必要條件是 長度相等且對應(yīng)位置上的字符相等 。5. 字符串“abcd”中共有 個(gè)長度大于0的字串。6. 廣義表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10）的長度及深度分別為 和 。7.若二叉樹的先序序列和后序序列相反，則該二叉樹一定滿足只有一個(gè)葉子結(jié)點(diǎn) 。8.若無向圖滿足 有n-1條邊的連通圖 ，則該圖是樹。9.若無向圖中有n個(gè)頂點(diǎn)，則其邊數(shù)最少為 n-1 ，最多為 n(n-1)/2 。10.堆排序的時(shí)間復(fù)雜度和空間復(fù)雜度分別為 O

11、(nlog2n) 和 O(1) 。三、 名詞解釋（1）抽象數(shù)據(jù)類型 （2）算法及其特性 （3）串的模式匹配 （4）優(yōu)先級隊(duì)列（5）完全二叉樹 （6）堆（7）Huffman編碼（8）Huffman樹（9）連通分量及重連通分量（10）最小生成樹（11）克魯斯卡爾算法（12）普里姆算法（13）希爾排序（14）快速排序（15）教材等等相關(guān)名次解釋題四、 簡答題1. 請對線性表進(jìn)行順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)作比較。（西電2004年考研試題）2. 單鏈表為什么要引入頭結(jié)點(diǎn)？3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有單鏈表、循環(huán)鏈表、雙向鏈表，試問它們各有什么優(yōu)點(diǎn)和缺點(diǎn)？參考答案：l 單鏈表的優(yōu)點(diǎn)是空間動(dòng)態(tài)分配，插入和刪除時(shí)

12、不需要移動(dòng)數(shù)據(jù)，缺點(diǎn)是不能隨機(jī)訪問數(shù)據(jù)。和其它兩種相比，它還節(jié)省了空間。l 循環(huán)鏈表除了具有單鏈表的優(yōu)點(diǎn)外，它從任意結(jié)點(diǎn)出發(fā)可以找到其它結(jié)點(diǎn)。缺點(diǎn)同單鏈表的缺點(diǎn)。l 雙向鏈表除了具有循環(huán)鏈表的優(yōu)點(diǎn)，它還可以方便地找到某個(gè)結(jié)點(diǎn)的前驅(qū)。缺點(diǎn)是增加了空間開銷。4.內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個(gè)棧使用，怎樣分配這部分存儲(chǔ)空間，使得對任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。5. 假設(shè)有一個(gè)適當(dāng)大小的棧S，輸入棧的序列為A，B，C，D，E。問：（1）能否得到下列的輸出序列： B，C，D，E，A； E，A，B，C，D；E，D，C，B，A。（2）寫出所有可能正確的輸出序列（至少5種）

13、。6.用向量表示的循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾位置分別為1和max_size，試給出判斷隊(duì)列為空和為滿的邊界條件。l 參考答案： 隊(duì)空條件為max_size=1; 隊(duì)滿的條件為（max_size+1）%MAXSIZE.7. 設(shè)一棵二叉樹后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，要求： （1）畫出該二叉樹； （2）寫出該二叉樹的先序遍歷序列；（3）畫出該二叉樹對應(yīng)的森林。8.對二叉樹中的結(jié)點(diǎn)按層次順序（每一層自左向右）進(jìn)行的訪問操作稱為二叉樹的層次遍歷。現(xiàn)已知一棵二叉樹的層次序列為AEBGFDIMH，中序遍歷序列為GEFAMDBHI。請畫出該二叉樹并寫出其先序序列。若將該二

14、叉樹看作是一個(gè)森林的孩子 兄弟表示，請畫出該森林。（西電2004年考研試題）9. 已知某通信電文僅由A、B、C、D、E、F這6個(gè)字符構(gòu)成，其出現(xiàn)的頻率分別為23、5、14、8、25、7，請給出它們的霍夫曼樹及其對應(yīng)的霍夫曼編碼。10.給定下列圖G用兩種不同表示法畫出該圖的存儲(chǔ)結(jié)構(gòu)圖。ABGFEDC4812242012151011. 針對上圖分別用卡魯斯卡爾及普里姆算法給出該圖的最小生成樹，畫出其邏輯結(jié)構(gòu)。12.總結(jié)直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、錦標(biāo)賽排序、堆排序及歸并排序等在最好情況下、最壞情況及平均的時(shí)間復(fù)雜度，輔助空間復(fù)雜度及穩(wěn)定性。13.判斷下面

15、的每個(gè)結(jié)點(diǎn)序列是否表示一個(gè)堆，如果不是堆，請把它調(diào)整為堆。 （1）100，90，80，60，85，75，20，25，10，70，65，50 （2）100，70，50，20，90，75，60，25，10，85，65，8014.已知一序列（12，70，33，65，24，56，48，92，86，33），問該序列是否是堆？如果不是，則把它調(diào)整為小頂堆。并問把該序列調(diào)整為堆共需要多少次元素間的比較？多少次元素間的交換。（西電2005年考研試題）15.試為下列情況選擇合適的排序算法：（西電2006年考研試題） （1）n=30，且要求最壞情況下速度最快； （2）n=30，且要求既要快，又要排序穩(wěn)定； （3）

16、n=2000，要求平均情況下速度最快； （4）n=2000，要求最壞情況下速度最快，又要節(jié)省存儲(chǔ)空間。五、 算法設(shè)計(jì)題1. 實(shí)現(xiàn)一個(gè)算法，完成在不帶表頭結(jié)點(diǎn)的單鏈表第i個(gè)結(jié)點(diǎn)之前插入新元素x的操作。 （教材P74頁）2.（a）實(shí)現(xiàn)一個(gè)函數(shù)，完成在帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，建立一個(gè)包含有值value的新結(jié)點(diǎn)并將其插入到當(dāng)前結(jié)點(diǎn)之后。（教材P91頁）（b）實(shí)現(xiàn)一個(gè)函數(shù)，完成在帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表中刪除當(dāng)前結(jié)點(diǎn)，同時(shí)讓當(dāng)前指針指到鏈表中下一個(gè)結(jié)點(diǎn)位置。（教材P91頁）3.（a）實(shí)現(xiàn)一個(gè)函數(shù)完成刪除鏈?zhǔn)綏ｍ斀Y(jié)點(diǎn)，返回被刪棧頂元素的值。（教材P107頁） （b）實(shí)現(xiàn)一個(gè)函數(shù)完成刪除鏈?zhǔn)疥?duì)列隊(duì)頭結(jié)點(diǎn)

17、，并返回被刪對頭元素的值。（教材P117頁）4.對二叉鏈表，實(shí)現(xiàn)一個(gè)函數(shù)Parent(*BinTreeNode<Type>*start, *BinTreeNode<Type>*curent)從結(jié)點(diǎn)start開始，搜索結(jié)點(diǎn)current的雙親結(jié)點(diǎn)，并返回其地址，否則返回NULL。（教材P171頁）5. 若用二叉鏈表作為二叉樹的存儲(chǔ)表示，試針對下列問題編寫遞歸算法： （1）統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)； （2）交換每個(gè)結(jié)點(diǎn)的左子女和右子女。6.熟練掌握直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序等其它排序的算法7.若以域變量rear和length分別指示循環(huán)隊(duì)列中

18、隊(duì)尾元素的位置和隊(duì)列中元素的個(gè)數(shù)。請完成下面的入隊(duì)列和出隊(duì)列的算法：（西電2004年考研試題）#define MAXQSIZE 100 /最大隊(duì)列長度Type structQelemtype *base; /base為隊(duì)列所在區(qū)域的首地址int length; /隊(duì)列長度int rear; /隊(duì)尾元素位置SqQueue; Status EnQueue(SqQueue &Q, Qelemtype e) if ( ) return ERROR; / 隊(duì)列滿，無法插入Q.rear= ; /計(jì)算元素e的插入位置 = e; /在隊(duì)尾加入新的元素Q.length+; /隊(duì)列長度加1return OK;Status DeQueue(SqQueue &Q, Qelemtype &e) /刪除對頭元素，并用e帶回其值 if ( )return ERROR; /隊(duì)列滿e=Q.base ; /取隊(duì)頭元素Qlength -; /隊(duì)列長度減1return OK;8.請運(yùn)用快速排序思想，設(shè)計(jì)遞歸算法實(shí)現(xiàn)求n（n1）個(gè)不同元素集合中的第i（1in）小元素。（西電2004年考研試題）9.閱讀下列函數(shù)說明及相應(yīng)代碼，在空白處填入相應(yīng)語句。(西電2005年考研試題)函數(shù)1 函數(shù)palinddrome(char s)的功能是：判斷字符串s是否為回文字符串，若是，則返回0，否則