西安電子科技大學數據結構期末復習題.doc

所有試卷資料免費下載西安電子科技大學數據結構復習題（含部分參考答案版）一、 單項選擇題1. 按照數據邏輯結構的不同，可以將數據結構分成 C 。 A. 動態(tài)結構和靜態(tài)結構 B. 緊湊結構和非緊湊結構C. 線性結構和非線性結構 D. 內部結構和外部結構2. 下列關于數據結構的敘述中正確的是 A 。 A. 數組是同類型值的集合 B. 遞歸算法的程序結構比迭代算法的程序結構更為復雜 C. 樹是一種線性的數據結構D. 用一維數組存儲二叉樹，總是以先序順序遍歷各結點 3. 在計算機的存儲器中表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 B A.邏輯結構 B.順序存儲結構C.鏈式存儲結構 D.以上都不對4. 以下關于算法特性的描述中， B 是正確的。 （1）算法至少有一個輸入和一個輸出（2）算法至少有一個輸出但是可以沒有輸入（3）算法可以永遠運行下去A. （1） B. （2） C. （3） D. （2）和（3）5. 對順序存儲的線性表（a1,a2,an）進行插入操作的時間復雜度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1)6. 鏈表不具有的特點是 A 。 A.可隨機訪問任一元素 B.插入和刪除時不需要移動元素C.不必事先估計存儲空間 D.所需空間與線性表的長度成正比7.線性鏈表中各鏈結點之間的地址 C 。 A.必須連續(xù) B.部分地址必須連續(xù)C.不一定連續(xù) D.連續(xù)與否無關8. 以下關于鏈式存儲結構的敘述中， C 是不正確的。 A.結點除自身信息外還包括指針域，因此存儲密度小于順序存儲結構B.邏輯上相鄰的結點物理上不必鄰接C.可以通過計算直接確定第i個結點的存儲地址D.插入、刪除操作方便，不必移動結點9. 設依次進入一個棧的元素序列為d, a, c, b,得不到出棧的元素序列為 D 。A. dcba B. acdb C. abcd D. cbda10. 將新元素插入到鏈式隊列中時，新元素只能插入到 B 。A. 鏈頭 B. 鏈尾 C. 鏈中 D. 第i個位置，i大于等于1，大于等于表長加111. 設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、和e1，則棧S容量至少應該是 C 。 A. 6 B. 4 C. 3 D. 212.下面 D 是abcd321ABCD的子串。A. abcd B. 321ab C. abc ABC D. 21AB13.假設8行10列的二維數組A18，110分別以行序為主序和以列序為主序順序存儲時，其首地址相同，那么以行序為主序時元素a3，5的地址與以列序為主序時 C 元素相同。A. a7，3 B. a8，3 C. a1，4 D. ABC都不對14. 數組A05，06的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內存單元中，則元素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. 以下關于廣義表的敘述中，正確的是 A 。 A. 廣義表是0個或多個單元素或子表組成的有限序列B. 廣義表至少有一個元素是子表C. 廣義表不可以是自身的子表D. 廣義表不能為空表17.若樹T有a個度為1的結點，b個度為2的結點，c個度為3的結點，則該樹有 D 個葉結點。A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c18.若一棵二叉樹有102片葉子結點，則度二叉樹度為2的結點數是 B 。A. 100 B. 101 C. 102 D. 103 19. 在有n 個葉子結點的霍夫曼樹中，其結點總數為： 。 A. n B. 2n C. 2n +1 D. 2n - 120.具有12個結點的完全二叉樹有 B 。A. 5個葉子結點 B. 5個度為2的結點C. 7個分支結點 D. 2個度為1的結點21.設結點x和y是二叉樹中的任意兩結點，若在先根序列中x在y之前，而后根序列中x在y之后，則x和y的關系是 C 。A. x是y的左兄弟 B. x是y的右兄弟C. x是y的祖先 D. x是y的后代22. 先序遍歷序列與中序遍歷序列相同的二叉樹為 。 A. 根結點無左子樹的二叉樹 B.根結點無右子樹的二叉樹C. 只有根結點的二叉樹或非葉子結點只有左子樹的二叉樹D. 只有根結點的二叉樹或非葉子結點只有右子樹的二叉樹23.若二叉樹T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf，則其后序遍歷序列為 A 。A. ceadfb B. feacdb C. eacdfb D. 以上都不對 24.設無向圖的頂點個數為n，則該圖最多有 C 條邊。A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.對于一個有n個頂點和e條邊的無向圖，若采用鄰接表表示，鄰接表中的結點總數是 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)。對該圖進行深度優(yōu)先遍歷，下面不能得到的序列是 D 。A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不屬于內排序方法的是 C 。A. 插入排序法 B. 選擇排序法 C. 拓撲排序法 D. 歸并排序法28. 直接插入排序在最好情況下的時間復雜度為 B 。A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 29.對有n個記錄的表作快速排序，在最壞情況，算法的時間復雜度是 D 。A. O(n3) B. O(n) C. O(nlog2n) D. O(n2) 30.下面的排序算法中，穩(wěn)定是 A 。A. 直接插入排序法 B. 快速排序法 C. 直接選擇排序法 D. 堆排序法二、 填空題1. 一個算法具有5個特性： 、 、 、有零個或多個輸入，一個或多個輸出。2. .設數組a150，180的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a45，68的存儲地址為 9174 ；若以列序為主序順序存儲，則元素a45，68的存儲地址為 8788 。3. 當線性表的元素總數基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用 存儲結構。4.兩個字符串相等的充分必要條件是 長度相等且對應位置上的字符相等 。5. 字符串“abcd”中共有 個長度大于0的字串。6. 廣義表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10）的長度及深度分別為 和 。7.若二叉樹的先序序列和后序序列相反，則該二叉樹一定滿足只有一個葉子結點 。8.若無向圖滿足 有n-1條邊的連通圖 ，則該圖是樹。9.若無向圖中有n個頂點，則其邊數最少為 n-1 ，最多為 n(n-1)/2 。10.堆排序的時間復雜度和空間復雜度分別為 O(nlog2n) 和 O(1) 。三、 名詞解釋（1）抽象數據類型 （2）算法及其特性 （3）串的模式匹配 （4）優(yōu)先級隊列（5）完全二叉樹 （6）堆（7）Huffman編碼（8）Huffman樹（9）連通分量及重連通分量（10）最小生成樹（11）克魯斯卡爾算法（12）普里姆算法（13）希爾排序（14）快速排序（15）教材等等相關名次解釋題四、 簡答題1. 請對線性表進行順序存儲和鏈式存儲的特點作比較。（西電2004年考研試題）2. 單鏈表為什么要引入頭結點？3.線性表的鏈式存儲結構有單鏈表、循環(huán)鏈表、雙向鏈表，試問它們各有什么優(yōu)點和缺點？參考答案：l 單鏈表的優(yōu)點是空間動態(tài)分配，插入和刪除時不需要移動數據，缺點是不能隨機訪問數據。和其它兩種相比，它還節(jié)省了空間。l 循環(huán)鏈表除了具有單鏈表的優(yōu)點外，它從任意結點出發(fā)可以找到其它結點。缺點同單鏈表的缺點。l 雙向鏈表除了具有循環(huán)鏈表的優(yōu)點，它還可以方便地找到某個結點的前驅。缺點是增加了空間開銷。4.內存中一片連續(xù)空間（不妨假設地址從1到m），提供給兩個棧使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。5. 假設有一個適當大小的棧S，輸入棧的序列為A，B，C，D，E。問：（1）能否得到下列的輸出序列： B，C，D，E，A； E，A，B，C，D；E，D，C，B，A。（2）寫出所有可能正確的輸出序列（至少5種）。6.用向量表示的循環(huán)隊列的隊首和隊尾位置分別為1和max_size，試給出判斷隊列為空和為滿的邊界條件。l 參考答案： 隊空條件為max_size=1; 隊滿的條件為（max_size+1）%MAXSIZE.7. 設一棵二叉樹后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，要求： （1）畫出該二叉樹； （2）寫出該二叉樹的先序遍歷序列；（3）畫出該二叉樹對應的森林。8.對二叉樹中的結點按層次順序（每一層自左向右）進行的訪問操作稱為二叉樹的層次遍歷?，F(xiàn)已知一棵二叉樹的層次序列為AEBGFDIMH，中序遍歷序列為GEFAMDBHI。請畫出該二叉樹并寫出其先序序列。若將該二叉樹看作是一個森林的孩子 兄弟表示，請畫出該森林。（西電2004年考研試題）9. 已知某通信電文僅由A、B、C、D、E、F這6個字符構成，其出現(xiàn)的頻率分別為23、5、14、8、25、7，請給出它們的霍夫曼樹及其對應的霍夫曼編碼。10.給定下列圖G用兩種不同表示法畫出該圖的存儲結構圖。ABGFEDC4812242012151011. 針對上圖分別用卡魯斯卡爾及普里姆算法給出該圖的最小生成樹，畫出其邏輯結構。12.總結直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、錦標賽排序、堆排序及歸并排序等在最好情況下、最壞情況及平均的時間復雜度，輔助空間復雜度及穩(wěn)定性。13.判斷下面的每個結點序列是否表示一個堆，如果不是堆，請把它調整為堆。 （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），問該序列是否是堆？如果不是，則把它調整為小頂堆。并問把該序列調整為堆共需要多少次元素間的比較？多少次元素間的交換。（西電2005年考研試題）15.試為下列情況選擇合適的排序算法：（西電2006年考研試題） （1）n=30，且要求最壞情況下速度最快； （2）n=30，且要求既要快，又要排序穩(wěn)定； （3）n=2000，要求平均情況下速度最快； （4）n=2000，要求最壞情況下速度最快，又要節(jié)省存儲空間。五、 算法設計題1. 實現(xiàn)一個算法，完成在不帶表頭結點的單鏈表第i個結點之前插入新元素x的操作。 （教材P74頁）2.（a）實現(xiàn)一個函數，完成在帶表頭結點的雙向循環(huán)鏈表中，建立一個包含有值value的新結點并將其插入到當前結點之后。（教材P91頁）（b）實現(xiàn)一個函數，完成在帶表頭結點的雙向循環(huán)鏈表中刪除當前結點，同時讓當前指針指到鏈表中下一個結點位置。（教材P91頁）3.（a）實現(xiàn)一個函數完成刪除鏈式棧頂結點，返回被刪棧頂元素的值。（教材P107頁） （b）實現(xiàn)一個函數完成刪除鏈式隊列隊頭結點，并返回被刪對頭元素的值。（教材P117頁）4.對二叉鏈表，實現(xiàn)一個函數Parent(*BinTreeNode*start, *BinTreeNode*curent)從結點start開始，搜索結點current的雙親結點，并返回其地址，否則返回NULL。（教材P171頁）5. 若用二叉鏈表作為二叉樹的存儲表示，試針對下列問題編寫遞歸算法： （1）統(tǒng)計二叉樹中葉子結點的個數； （2）交換每個結點的左子女和右子女。6.熟練掌握直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序等其它排序的算法7.若以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和隊列中元素的個數。請完成下面的入隊列和出隊列的算法：（西電2004年考研試題）#define MAXQSIZE 100 /最大隊列長度Type structQelemtype *base; /base為隊列所在區(qū)域的首地址int length; /隊列長度int rear; /隊尾元素位置SqQueue; Status EnQueue(SqQueue &Q, Qelemtype e) if ( ) return ERROR; / 隊列滿，無法插入Q.rear= ; /計算元素e的插入位置 = e; /在隊尾加入新的元素Q.length+; /隊列長度加1return OK;Status DeQueue(SqQueue &Q, Qelemtype &e) /刪除對頭元素，并用e帶回其值 if ( )return ERROR; /隊列滿e=Q.base ; /取隊頭元素Qlength -; /隊列長度減1return OK;8.請運用快速排序思想，設計遞歸算法實現(xiàn)求n（n1）個不同元素集合中的第i（1in）小元素。（西電2004年考研試題）9.閱讀下列函數說明及相應代碼，在空白處填入相應語句。(西電2005年考研試題)函數1 函數palinddrome(char s)的功能是：判斷字符串s是否為回文字符串，