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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題一、 單項選擇題1. 按照數(shù)據(jù)邏輯結(jié)構(gòu)的不同，可以將數(shù)據(jù)結(jié)構(gòu)分成 。 A. 動態(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. 數(shù)組是同類型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為復(fù)雜 C. 樹是一種線性的數(shù)據(jù)結(jié)構(gòu)D. 用一維數(shù)組存儲二叉樹，總是以先序順序遍歷各結(jié)點(diǎn) 3. 在計算機(jī)的存儲器中表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 A.邏輯結(jié)構(gòu) B.順序存儲結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu) D.以上都不對4. 以下關(guān)于算法特性的描述中， 是正確

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

3、不正確的。 A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu)B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接C.可以通過計算直接確定第i個結(jié)點(diǎn)的存儲地址D.插入、刪除操作方便，不必移動結(jié)點(diǎn)9. 設(shè)依次進(jìn)入一個棧的元素序列為d, a, c, b,得不到出棧的元素序列為 。A. dcba B. acdb C. abcd D. cbda10. 將新元素插入到鏈?zhǔn)疥犃兄袝r，新元素只能插入到 。A. 鏈頭 B. 鏈尾 C. 鏈中 D. 第i個位置，i大于等于1，大于等于表長加111. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素

4、出隊的順序是e2、e4、e3、e6、e5、和e1，則棧S容量至少應(yīng)該是 。 A. 6 B. 4 C. 3 D. 212.下面 是abcd321ABCD的子串。A. abcd B. 321ab C. abc ABC D. 21AB13.假設(shè)8行10列的二維數(shù)組A18，110分別以行序為主序和以列序為主序順序存儲時，其首地址相同，那么以行序為主序時元素a3，5的地址與以列序為主序時 元素相同。A. a7，3 B. a8，3 C. a1，4 D. ABC都不對14. 數(shù)組A05，06的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址為 。 A. 1175

5、 B. 1180 C. 1205 D.1210 15.下列廣義表中，長度為3的廣義表為 。A.（a,b,c,( )） B. (g),(a,b,c,d,f),( ) C. (a,(b,(d) D. ( )16. 以下關(guān)于廣義表的敘述中，正確的是 。 A. 廣義表是0個或多個單元素或子表組成的有限序列B. 廣義表至少有一個元素是子表C. 廣義表不可以是自身的子表D. 廣義表不能為空表17.若樹T有a個度為1的結(jié)點(diǎn)，b個度為2的結(jié)點(diǎn)，c個度為3的結(jié)點(diǎn)，則該樹有 個葉結(jié)點(diǎn)。A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c18.若一棵二叉樹有102片葉子結(jié)點(diǎn)，則度二叉樹度為

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

7、右子樹的二叉樹C. 只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有左子樹的二叉樹D. 只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有右子樹的二叉樹23.若二叉樹T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf，則其后序遍歷序列為 。A. ceadfb B. feacdb C. eacdfb D. 以上都不對 24.設(shè)無向圖的頂點(diǎn)個數(shù)為n，則該圖最多有 條邊。A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.對于一個有n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，鄰接表中的結(jié)點(diǎn)總數(shù)是 。A. e/2 B. e C. n+2e D. n+e26. 無向圖G=（V，E），其中V=a,b,

8、c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)。對該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列是 。A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不屬于內(nèi)排序方法的是 。A. 插入排序法 B. 選擇排序法 C. 拓?fù)渑判蚍?D. 歸并排序法28. 直接插入排序在最好情況下的時間復(fù)雜度為 。A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 29.對有n個記錄的表作快速排序，在最壞情況，算法的時間復(fù)雜度是 。A. O(n3) B. O(n) C. O(nl

9、og2n) D. O(n2) 30.下面的排序算法中，穩(wěn)定是 。A. 直接插入排序法 B. 快速排序法 C. 直接選擇排序法 D. 堆排序法二、 填空題1. 一個算法具有5個特性： 、 、 、有零個或多個輸入，一個或多個輸出。2. .設(shè)數(shù)組a150，180的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a45，68的存儲地址為 9174 ；若以列序為主序順序存儲，則元素a45，68的存儲地址為 8788 。3. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用 存儲結(jié)構(gòu)。4.兩個字符串相等的充分必要條件是 長度相等且

10、對應(yīng)位置上的字符相等 。5. 字符串“abcd”中共有 個長度大于0的字串。6. 廣義表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10）的長度及深度分別為 和 。7.若二叉樹的先序序列和后序序列相反，則該二叉樹一定滿足只有一個葉子結(jié)點(diǎn) 。8.若無向圖滿足 有n-1條邊的連通圖 ，則該圖是樹。9.若無向圖中有n個頂點(diǎn)，則其邊數(shù)最少為 n-1 ，最多為 n(n-1)/2 。10.堆排序的時間復(fù)雜度和空間復(fù)雜度分別為 O(nlog2n) 和 O(1) 。三、 名詞解釋（1）算法及其特性（2）優(yōu)先級隊列 （3）串的模式匹配 （4）完全二叉樹（5） Huffman編碼 （6）

11、Huffman樹（7）連通分量及重連通分量（8）最小生成樹（9）克魯斯卡爾算法（10）普里姆算法（11）希爾排序（12）快速排序（13）堆四、 簡答題1. 請對線性表進(jìn)行順序存儲和鏈?zhǔn)酱鎯Φ奶攸c(diǎn)作比較。2. 單鏈表為什么要引入頭結(jié)點(diǎn)？3.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)有單鏈表、循環(huán)鏈表、雙向鏈表，試問它們各有什么優(yōu)點(diǎn)和缺點(diǎn)？4.內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個棧使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當(dāng)這部分空間全滿時才發(fā)生上溢。5. 假設(shè)有一個適當(dāng)大小的棧S，輸入棧的序列為A，B，C，D，E。問：（1）能否得到下列的輸出序列： B，C，D，E，A； E，A，B，C，D；E

12、，D，C，B，A。（2）寫出所有可能正確的輸出序列（至少5種）。6.用向量表示的循環(huán)隊列的隊首和隊尾位置分別為1和max_size，試給出判斷隊列為空和為滿的邊界條件。7. 設(shè)一棵二叉樹后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，要求： （1）畫出該二叉樹； （2）寫出該二叉樹的先序遍歷序列；（3）畫出該二叉樹對應(yīng)的森林。8.對二叉樹中的結(jié)點(diǎn)按層次順序（每一層自左向右）進(jìn)行的訪問操作稱為二叉樹的層次遍歷。現(xiàn)已知一棵二叉樹的層次序列為AEBGFDIMH，中序遍歷序列為GEFAMDBHI。請畫出該二叉樹并寫出其先序序列。若將該二叉樹看作是一個森林的孩子 兄弟表示，請畫出

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

14、請把它調(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)整為堆共需要多少次元素間的比較？多少次元素間的交換。15.試為下列情況選擇合適的排序算法： （1）n=30，且要求最壞情況下速度最快； （2）n=30，且要求既要快，又要排序穩(wěn)定； （3）n=2000，要求平均情況下速度最快； （4）n=2000，要求最壞情況下速度最快，又要節(jié)省存

15、儲空間。五、 算法設(shè)計題1. 實現(xiàn)一個算法，完成在不帶表頭結(jié)點(diǎn)的單鏈表第i個結(jié)點(diǎn)之前插入新元素x的操作。 2.（a）實現(xiàn)一個函數(shù)，完成在帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，建立一個包含有值value的新結(jié)點(diǎn)并將其插入到當(dāng)前結(jié)點(diǎn)之后。（b）實現(xiàn)一個函數(shù)，完成在帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表中刪除當(dāng)前結(jié)點(diǎn)，同時讓當(dāng)前指針指到鏈表中下一個結(jié)點(diǎn)位置。3.（a）實現(xiàn)一個函數(shù)完成刪除鏈?zhǔn)綏ｍ斀Y(jié)點(diǎn)，返回被刪棧頂元素的值。 （b）實現(xiàn)一個函數(shù)完成刪除鏈?zhǔn)疥犃嘘狀^結(jié)點(diǎn)，并返回被刪對頭元素的值。4.對二叉鏈表，實現(xiàn)一個函數(shù)Parent(*BinTreeNode<Type>*start, *BinTreeNode&l

16、t;Type>*curent)從結(jié)點(diǎn)start開始，搜索結(jié)點(diǎn)current的雙親結(jié)點(diǎn)，并返回其地址，否則返回NULL。5. 若用二叉鏈表作為二叉樹的存儲表示，試針對下列問題編寫遞歸算法： （1）統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)； （2）交換每個結(jié)點(diǎn)的左子女和右子女。6.熟練掌握直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序等其它排序的算法7.若以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和隊列中元素的個數(shù)。請完成下面的入隊列和出隊列的算法： #define MAXQSIZE 100 /最大隊列長度Type structQelemtype *base; /base為隊

17、列所在區(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 ; /取隊頭元素Ql

18、ength -; /隊列長度減1return OK;8.請運(yùn)用快速排序思想，設(shè)計遞歸算法實現(xiàn)求n（n1）個不同元素集合中的第i（1in）小元素。9.閱讀下列函數(shù)說明及相應(yīng)代碼，在空白處填入相應(yīng)語句。 函數(shù)1 函數(shù)palinddrome(char s)的功能是：判斷字符串s是否為回文字符串，若是，則返回0，否則返回-1。若一個字符串順讀和倒讀都一樣時，稱該字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。Int palindrome (char s)char *pi, *pj;Pi = s; pj =s + strlen(s) 1; /*strlen(s)函數(shù)用于求得串s的串長While（pipj && ）Pi +; pi - - ; if ( )return - 1;else return 0;函數(shù)2 函數(shù)insert_sort(int a,int count)是用直接插入排序法對指定數(shù)組的前count個元素從小到大排序。 Void insert_sort(int a, int count) int i, j