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

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

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