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

《西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題.doc》由會員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題.doc（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

www.juanjuantx.com 所有試卷資料免費(fèi)下載 西安電子科技大學(xué) 《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題 （含部分參考答案版） 一、 單項(xiàng)選擇題 1. 按照數(shù)據(jù)邏輯結(jié)構(gòu)的不同，可以將數(shù)據(jù)結(jié)構(gòu)分成 C 。 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 。 A. 數(shù)組是同類型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為復(fù)雜 C. 樹是一種線性的數(shù)據(jù)結(jié)構(gòu) D. 用一維數(shù)組存儲二叉樹，總是以先序順序遍歷各結(jié)點(diǎn) 3. 在計(jì)算機(jī)的存儲器中表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 B A.邏輯結(jié)構(gòu) B.順序存儲結(jié)構(gòu) C.鏈?zhǔn)酱鎯Y(jié)構(gòu) 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. 對順序存儲的線性表（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í)不需要移動元素 C.不必事先估計(jì)存儲空間 D.所需空間與線性表的長度成正比 7.線性鏈表中各鏈結(jié)點(diǎn)之間的地址 C 。 A.必須連續(xù) B.部分地址必須連續(xù) C.不一定連續(xù) D.連續(xù)與否無關(guān) 8. 以下關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中， C 是不正確的。 A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu) B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接 C.可以通過計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲地址 D.插入、刪除操作方便，不必移動結(jié)點(diǎn) 9. 設(shè)依次進(jìn)入一個(gè)棧的元素序列為d, a, c, b,得不到出棧的元素序列為 D 。 A. dcba B. acdb C. abcd D. cbda 10. 將新元素插入到鏈?zhǔn)疥?duì)列中時(shí)，新元素只能插入到 B 。 A. 鏈頭 B. 鏈尾 C. 鏈中 D. 第i個(gè)位置，i大于等于1，大于等于表長加1 11. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、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. 2 12.下面 D 是‘a(chǎn)bcd321ABCD’的子串。 A. abcd B. 321ab C. ‘a(chǎn)bc ABC’ D. ‘21AB’ 13.假設(shè)8行10列的二維數(shù)組A[1…8，1…10]分別以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍蝽樞虼鎯r(shí)，其首地址相同，那么以行序?yàn)橹餍驎r(shí)元素a[3，5]的地址與以列序?yàn)橹餍驎r(shí) C 元素相同。 A. a[7，3] B. a[8，3] C. a[1，4] D. ABC都不對 14. 數(shù)組A[0…5，0…6]的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，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 B. a+2b+3c C.2b+3c D. 1+b+2c 18.若一棵二叉樹有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 - 1 20.具有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的祖先 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條邊的無向圖，若采用鄰接表表示，鄰接表中的結(jié)點(diǎn)總數(shù)是 C 。 A. e/2 B. e C. n+2e D. n+e 26. 無向圖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(nlog2n) 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ù)組a[1…50，1…80]的基地址為2000，每個(gè)元素占2個(gè)存儲單元，若以行序?yàn)橹餍蝽樞虼鎯Γ瑒t元素a[45，68]的存儲地址為 9174 ；若以列序?yàn)橹餍蝽樞虼鎯?，則元素a[45，68]的存儲地址為 8788 。 3. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用 存儲結(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(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)行順序存儲和鏈?zhǔn)酱鎯Φ奶攸c(diǎn)作比較。（西電2004年考研試題） 2. 單鏈表為什么要引入頭結(jié)點(diǎn)？ 3.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)有單鏈表、循環(huán)鏈表、雙向鏈表，試問它們各有什么優(yōu)點(diǎn)和缺點(diǎn)？ 參考答案： l 單鏈表的優(yōu)點(diǎn)是空間動態(tài)分配，插入和刪除時(shí)不需要移動數(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è)棧使用，怎樣分配這部分存儲空間，使得對任一個(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種）。 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)行的訪問操作稱為二叉樹的層次遍歷?，F(xiàn)已知一棵二叉樹的層次序列為AEBGFDIMH，中序遍歷序列為GEFAMDBHI。請畫出該二叉樹并寫出其先序序列。若將該二叉樹看作是一個(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用兩種不同表示法畫出該圖的存儲結(jié)構(gòu)圖。 A B G F E D C 4 8 122 4 20 12 15 10 11. 針對上圖分別用卡魯斯卡爾及普里姆算法給出該圖的最小生成樹，畫出其邏輯結(jié)構(gòu)。 12.總結(jié)直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、錦標(biāo)賽排序、堆排序及歸并排序等在最好情況下、最壞情況及平均的時(shí)間復(fù)雜度，輔助空間復(fù)雜度及穩(wěn)定性。 13.判斷下面的每個(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，80 14.已知一序列（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）n=2000，要求平均情況下速度最快； （4）n=2000，要求最壞情況下速度最快，又要節(jié)省存儲空間。 五、 算法設(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)，并返回被刪對頭元素的值。（教材P117頁） 4.對二叉鏈表，實(shí)現(xiàn)一個(gè)函數(shù)Parent(*BinTreeNode*start, *BinTreeNode*curent)從結(jié)點(diǎn)start開始，搜索結(jié)點(diǎn)current的雙親結(jié)點(diǎn)，并返回其地址，否則返回NULL。（教材P171頁） 5. 若用二叉鏈表作為二叉樹的存儲表示，試針對下列問題編寫遞歸算法： （1）統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)； （2）交換每個(gè)結(jié)點(diǎn)的左子女和右子女。 6.熟練掌握直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序等其它排序的算法 7.若以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和隊(duì)列中元素的個(gè)數(shù)。請完成下面的入隊(duì)列和出隊(duì)列的算法：（西電2004年考研試題） #define MAXQSIZE 100 //最大隊(duì)列長度 Type struct｛ Qelemtype *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ì)列長度加1 return OK; ｝ Status DeQueue(SqQueue &Q, Qelemtype &e) //刪除對頭元素，并用e帶回其值 ｛ if ( ④ )return ERROR; //隊(duì)列滿 e=Q.base[ ⑤ ]; //取隊(duì)頭元素 Q．length --; //隊(duì)列長度減1 return OK; ｝ 8.請運(yùn)用快速排序思想，設(shè)計(jì)遞歸算法實(shí)現(xiàn)求n（n＞1）個(gè)不同元素集合中的第i（1≤i≤n）小元素。（西電2004年考研試題） 9.閱讀下列函數(shù)說明及相應(yīng)代碼，在空白處填入相應(yīng)語句。 (西電2005年考研試題) [函數(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的串長 While（pi＜pj && ① ）{ Pi ++; pi - - ; } if ( ② )return - 1; else return 0; } [函數(shù)2] 函數(shù)insert_sort(int a[],int count)是用直接插入排序法對指定數(shù)組的前count個(gè)元素從小到大排序。 Void insert_sort(int a[], int count) { int i, j, t; for (i=1;i＜count;i++){//控制a[i]，…a[count-1]的比較和插入 t = a[i]; j= ③ ; while (j≥0&&t＜a[j]){ //在有序部分尋找元素a[i]的插入位置 ④ ; j - -; } ⑤ ; } } 10. 假設(shè)以數(shù)組seq[0…m-1]存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中的隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。(西電2006年考研試題) 請給出： （1）給出循環(huán)隊(duì)列的隊(duì)滿條件和隊(duì)空條件； （2）寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法，并分別分析其時(shí)間代價(jià)； （3）如果用數(shù)組sequ[m…n]來存放循環(huán)隊(duì)列中的元素，則（2）中的入隊(duì)列和出隊(duì)列的算法中的哪些語句要修改？如何修改？ 第 9 頁 共 9 頁