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

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

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

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

4、出隊(duì)的順序是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分別以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍蝽樞虼鎯?chǔ)時(shí)，其首地址相同，那么以行序?yàn)橹餍驎r(shí)元素a3，5的地址與以列序?yàn)橹餍驎r(shí) 元素相同。A. a7，3 B. a8，3 C. a1，4 D. ABC都不對(duì)14. 數(shù)組A05，06的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址為 。 A. 1175

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

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

7、右子樹(shù)的二叉樹(shù)C. 只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)D. 只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)23.若二叉樹(shù)T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf，則其后序遍歷序列為 。A. ceadfb B. feacdb C. eacdfb D. 以上都不對(duì) 24.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有 條邊。A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.對(duì)于一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，鄰接表中的結(jié)點(diǎn)總數(shù)是 。A. e/2 B. e C. n+2e D. n+e26. 無(wú)向圖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)。對(duì)該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列是 。A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不屬于內(nèi)排序方法的是 。A. 插入排序法 B. 選擇排序法 C. 拓?fù)渑判蚍?D. 歸并排序法28. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為 。A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 29.對(duì)有n個(gè)記錄的表作快速排序，在最壞情況，算法的時(shí)間復(fù)雜度是 。A. O(n3) B. O(n) C. O(nl

9、og2n) D. O(n2) 30.下面的排序算法中，穩(wěn)定是 。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)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用 存儲(chǔ)結(jié)構(gòu)。4.兩個(gè)字符串相等的充分必要條件是 長(zhǎng)度相等且

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

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

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

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

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

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

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

17、列所在區(qū)域的首地址int length; /隊(duì)列長(zhǎng)度int rear; /隊(duì)尾元素位置SqQueue; Status EnQueue(SqQueue &Q, Qelemtype e) if ( ) return ERROR; / 隊(duì)列滿，無(wú)法插入Q.rear= ; /計(jì)算元素e的插入位置 = e; /在隊(duì)尾加入新的元素Q.length+; /隊(duì)列長(zhǎng)度加1return OK;Status DeQueue(SqQueue &Q, Qelemtype &e) /刪除對(duì)頭元素，并用e帶回其值 if ( )return ERROR; /隊(duì)列滿e=Q.base ; /取隊(duì)頭元素Ql

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