數(shù)據(jù)結(jié)構(gòu)考試試題

1、數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題一一、簡答問題：1. 四類數(shù)據(jù)結(jié)構(gòu)2. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別3. 簡述算法的定義與特性。4. 設(shè)有1000個(gè)無序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中(歸并排序、 基數(shù)排序、快速排序、堆排序、插入排序)哪一種方法最好，為什么二、判斷正誤：(每小題1分，共5分)正確在()內(nèi)打V,否則打 。1. ()二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值，若它的右子樹非空，則根結(jié)點(diǎn)的值大于其右孩子的值。2. ()索引順序表的特點(diǎn)是塊內(nèi)可無序，塊間要有序。3. ()子串是主串中任意個(gè)連續(xù)字符組成的序列。4. ()線性結(jié)構(gòu)只

2、能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。5. ()快速排序的樞軸元素可以任意選定。三、單項(xiàng)選擇題：(每小題1分，共4分)1. 棧S最多能容納4個(gè)元素?，F(xiàn)有6個(gè)元素按A B、C、D E、F的順序進(jìn)棧，問下列哪 一個(gè)序列是可能的出棧序列A)E、DC、B、A FB)B、C、E、F、A、DC)C、B、E、DA FD)A、DF、E、B、C2. 將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為：A、98B 、99C 、50D 、483. 對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：A) 21、25、5、1

3、7、9、23、30 B ) 25、23、30、17、21、5、9B) 21、9、17、30、25、23、5 D ) 5、9、17、21、23、25、304. 設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是：A) M1B ) M1+M2 C ) M3 D ) M2+M3四、填空題：(每小題2分，共20分)1. 設(shè)一哈希表表長 M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即 H(K) =K MOD P( Pnext= 禾廿 p-next= 的操作.&廣義表(a,b),c,d) 的9 .循環(huán)單鏈表 LA中，指針P所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的

4、條件是 10.在一個(gè)待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正 確位置都不遠(yuǎn)，則使用 排序方法最好。五、構(gòu)造題：(每小題5分，共25分1. 已知一棵二叉樹，其中序序列DBCAFG，后序序列DCBGFE，構(gòu)造該二叉樹。2. 設(shè)哈希表長度為11,哈希函數(shù) H( K) = (K的第一字母在字母表中的序號(hào))MOD11若 輸入順序?yàn)?D, BA TN, M, Cl，I，K，X，TA)，處理沖突方法為線性探測(cè)再散列或鏈 地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。3. 有一組關(guān)鍵字50, 52 , 85, 22, 96,17, 36, 55，請(qǐng)用快速排序，寫出

5、第一趟排序 結(jié)果。4. 已知葉子結(jié)點(diǎn)值2, 3, 5, 6, 9, 11,構(gòu)造哈夫曼樹，計(jì)算其帶權(quán)路徑長度。5. 畫出8個(gè)結(jié)點(diǎn)的折半判定樹。六、算法設(shè)計(jì)題：（每小題15分，共30分）（僅要求給出子程序）1. 編寫算法，判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱。（15分）對(duì)稱是指：設(shè)各元素值 a1,a2,.,an,則有ai=an-i+1,即指：a1= an , a2= an-1 。結(jié)點(diǎn)結(jié)構(gòu)為：priordatan ext2. 二叉排序樹T用二叉鏈表表示，其中各元素均不相同。（1） 寫出遞歸算法，按遞減順序打印各元素的值。（10 分）（2） 寫出完成上述要求的非遞歸算法。（5分）1.集合結(jié)構(gòu)、線性結(jié)構(gòu)

6、、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)試卷參考答案、簡答問題：（每小題4分，共16分）2. 線性結(jié)構(gòu)的前驅(qū)與后繼之間為一對(duì)一關(guān)系，非線性結(jié)構(gòu) 的前驅(qū)與后繼之間通常為一對(duì)多或多對(duì)多關(guān)系。堆排序。因?yàn)橐惶硕雅判蚺哦ㄒ粋€(gè)元素，只需進(jìn)行前103. 解決特定問題的有限指令序列。有限性、確定性、可行 性、有0個(gè)或多個(gè)輸入數(shù)據(jù)、有 1個(gè)或多個(gè)輸出結(jié)果。趟堆排序就可以了。其它排序方法均需進(jìn)行完全排序。二、判斷正誤：（每小題1分,共5分）正確在（）內(nèi)打否則打。1.()2. (2)3. (2)4.()5.(2)三、單項(xiàng)選擇題:（每小題1 分,共4分）1. C)2 . A)3.A)4.D)四、填空題：（每小題2分，共20分）

7、1.972.n+13.鏈域數(shù)目不同4.哈希查找法5. 26-16.11687. p-next、s8.(a,b)、(c,d)4.9. P- next=LA10.直接插入五、構(gòu)造題：（每小題 5分，共25 分）2.012345678910KTABAMDCIXTNIASL=20/90123456789100123415678!10L1TrBAC1DTNMXTAASL=15/93.36 , 17, 22, 50, 96, 85, 52, 55 4.WPL=112+6x 2+9X 2 +5 x 3 +2 x 4+3x 4=87注:哈夫曼樹的左右子樹可以互換5.4注:如果求中點(diǎn)時(shí)采用向上取整，則二叉樹的形

8、態(tài)為左子樹偏長。(2)六、算法設(shè)計(jì)題：(每小題15分，共30分)(僅要求給出子程序)1. 解答:in t judge(DLi nkList L)p=L- n ext;q=L-prior;while(p!二q) if(p-data!=q-data) return 0;if(p-n ext=q) return 1;p=p-n ext;q=q-prior;return 1;注:可以不用返回值，而用打印信息。2. 解答:(1)void prin t_1(BiTree T)if(T!二NULL) prin t_1(T-RChild);printf( “%c , T -data);prin t_1(T-L

9、Child);void Print_2 (BiTree T ) In itStack (&S);p=T;while(p!=NULL | ! IsEmpty(S) while (p!=NULL) Push(&S,p);p=p-RChild;if ( ! IsEmpty(S) ) Pop(&S, &p);printf ( “%c”, p - data ); p = p - LChild;鏈表最后一個(gè)結(jié)點(diǎn)的地址為t,則應(yīng)執(zhí)行操作:數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題二一、 簡答題：(每小題3分，共15分)1. 什么情況下二叉排序樹的查找性能較好什么情況下二叉排序樹的查找性能最差2. 比較順序表與單鏈表的優(yōu)缺點(diǎn)。3. 請(qǐng)

10、寫出棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義。4. 在起泡排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移 動(dòng)，試舉例說明之。5. 簡述參數(shù)傳遞的主要方式及其特點(diǎn)。二、 判斷正誤：(每小題1分，共5分) 正確在()內(nèi)打，否則打 。()(1)在拓樸序列中，如果結(jié)點(diǎn)Vi排在結(jié)點(diǎn)Vj的前面，則一定存在從 Vi到Vj的路徑。 ()(2)在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中一定相鄰。()(3)在一個(gè)小根堆中，具有最大值的元素一定是葉結(jié)點(diǎn)。()(4)索引順序表的特點(diǎn)是塊間可無序，但塊內(nèi)一定要有序。()(5)哈夫曼樹中沒有度為1的結(jié)點(diǎn)，所以必為滿二叉樹。三、單項(xiàng)選擇題：(每小題1分，共5分

11、)1 對(duì)于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為：A) 順序表B)用頭指針表示的單循環(huán)鏈表C)用尾指針表示的單循環(huán)鏈表D) 單鏈表2 假設(shè)以第一個(gè)元素為分界元素，對(duì)字符序列(Q, H, C, Y, P, A, M, S, R, D, F, X)進(jìn)行快速排序，則第一次劃分的結(jié)果是：A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S,Y, X)C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y,R

12、, X)3. 下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：(1)求有向圖結(jié)點(diǎn)的拓?fù)湫蛄校浣Y(jié)果必定是唯一的(2 )求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的(3)求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(gè)(些)是正確的A)只有(1) B) (1)和(2) C) 都正確 D)都不正確4. 若進(jìn)棧序列為 a, b, c ，則通過入出棧操作可能得到的a, b, c的不同排列個(gè)數(shù)為：A) 4 B) 5 C) 6 D) 75. 以下關(guān)于廣義表的敘述中，正確的是：A) 廣義表是由0個(gè)或多個(gè)單元素或子表構(gòu)成的有限序列B) 廣義表至少有一個(gè)元素是子表C) 廣義表不能遞歸定義D)廣義表不能為空表四、 填空題：(每

13、小題2分，共20分)1. 一棵含有101個(gè)結(jié)點(diǎn)的完全二叉樹存儲(chǔ)在數(shù)組A1.101中，對(duì) K k n ext=rear(a),b),c),(d)t-n ext=p-next, p-n ext=s8. 13009.n+110n-1五、構(gòu)造題：(每小題6分，共30分)1.2.3.或:WPL=8 x 3+4X 4+5X 4+16X 2+9X 3+12X 3+26X 2 =207注:哈夫曼樹的左右子樹可以互換。4.解 1:161U5解 2:注:邊上的權(quán)值可以省略5.初始堆:趟排序后的序列狀態(tài):篩成堆后為：16， 23, 61， 58， 94, 72, 87, 05注:如果采用大根堆，應(yīng)適當(dāng)減分六、算法設(shè)

14、計(jì)題：（共25分）3. 15 分void min(Lin kList L) if(L-n ext=NULL) return;q=L; r=L-n ext; m=r-data; while(r- next!二NULL) if(r- n ext-datan ext-data; q=r; r=r- n ext;p=q-n ext;if(m%2=1) q-n ext=p-n ext; free(p); 4. 10 分void layer(CSTree root)Ini tQueue(&Q); En terQueue(&Q, root); while(!Empty(Q) DelQueue(&Q, & p

15、); visit(p); p=p-FirstChild;while(p!=NULL) EnterQueue(&Q, p); p=p-NextSibling; 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題三、簡答題( 15分，每小題 3 分)1. 簡要說明算法與程序的區(qū)別。2. 在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)為什么3. 說明在圖的遍歷中，設(shè)置訪問標(biāo)志數(shù)組的作用。4. 說明以下三個(gè)概念的關(guān)系：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)5. 在一般的順序隊(duì)列中，什么是假溢出怎樣解決假溢出問題、判斷題( 10分，每小題 1 分)正確在括號(hào)內(nèi)打V,錯(cuò)誤打x( ) ( 1)廣義表 ( a ), b), c )的表頭是 ( a ), b)

16、 ，表尾是 ( c ) 。( ) ( 2)在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。( ) ( 3)基數(shù)排序是高位優(yōu)先排序法。( ) (4)在平衡二叉樹中， 任意結(jié)點(diǎn)左右子樹的高度差 (絕對(duì)值) 不超過 1。 ()(5)在單鏈表中，給定任一結(jié)點(diǎn)的地址 p，則可用下述語句將新結(jié)點(diǎn)s 插入結(jié)點(diǎn) p 的后面 ： p-next = s; s-next = p-next;()(6)抽象數(shù)據(jù)類型(ADT包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于 實(shí)現(xiàn)的，定義僅給出一個(gè) ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。( )(7)數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長。( )(8)用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓

17、縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。()(9)拓?fù)渑判蚴前?AOE網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對(duì)結(jié)點(diǎn)進(jìn)行 排序。( )( 10)長度為 1的串等價(jià)于一個(gè)字符型常量。三、單項(xiàng)選擇題( 10 分, 每小題 1分) 1排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交 換位置。這是哪種排序方法的基本思想A、堆排序B直接插入排序C快速排序D冒泡排序2 已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i 個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該：A)將鄰接矩陣的第i行刪除 B )將鄰接矩陣的第i行元素全部置為0C)將鄰接矩陣的第i列刪除 D )將鄰接矩陣的第i列元素全部

18、置為0 3有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為 head, 則其為空的條件是：A. head-priro=NULLB. head-next=NULLC. head-next=headD. head-next- priro=NULL4. 在順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找關(guān)鍵碼值 11，所需的關(guān)鍵碼比較次數(shù)為：A) 2 B) 3 C) 4 D) 55. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算A)從隊(duì)尾插入一個(gè)新元素B)從隊(duì)列中刪除第i個(gè)元素C )判斷一個(gè)隊(duì)列是否為空 D )讀取隊(duì)頭元素的值6. 在長度為n的順序表的第i個(gè)位置上

19、插入一個(gè)元素(K i n+1)，元素的 移動(dòng)次數(shù)為：A) n - i + 1 B) n - i C) iD) i-17 對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為：A)順序表B)用頭指針表示的循環(huán)單鏈表C)用尾指針表示的循環(huán)單鏈表D) 單鏈表8 對(duì)包含n個(gè)元素的哈希表進(jìn)行查找，平均查找長度為：A) O(log 2n)B) 0(n)C) 0(nlog2n) D)不直接依賴于 n9 將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì) 結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：A、48 B 49C、50 D 5110某二叉樹結(jié)點(diǎn)的中序序列為 A

20、、B、C、D E、F、G,后序序列為B DC A、F、G E,則其左子樹中結(jié)點(diǎn)數(shù)目為：A) 3B ) 2C ) 4D) 5四、填空題(10分，每空1分)1 填空完成下面一趟快速排序算法：int QKPass ( RecordType r , i nt low， int high) x = r low ；while ( low high ) while ( low =)high -;if ( low high ) r = r high ； low+; while ( low high & r . key x. key )low+; if ( low high ) r = r low ; high

21、-; r low = x ； return low ;2假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)隊(duì)列，若隊(duì)列非空，且隊(duì)尾指針為R,則將新結(jié)點(diǎn)S加入隊(duì)列時(shí)，需執(zhí)行下面語句： ; ;R=S3 通常是以算法執(zhí)行所耗費(fèi)的 和所占用的來判斷一個(gè)算法的優(yōu)劣。4. 已知一個(gè)3行、4列的二維數(shù)組A (各維下標(biāo)均從1開始)，如果按“以列為 主”的順序存儲(chǔ)，則排在第8個(gè)位置的元素是： 5 .高度為h的完全二叉樹最少有 個(gè)結(jié)點(diǎn)。五、構(gòu)造題(20分)1. (4分)已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請(qǐng)給出其邏輯結(jié)構(gòu)圖示DS = (D, R)D = a, b, c, d, e, f, g R = T T = , , , , , , , , , ,

22、 , 2. ( 6 分)對(duì)以下關(guān)鍵字序列建立哈希表： ( SUN,MON,TUE, WED,THU, FRI, SAT) ,哈希函數(shù)為H(K) =( K中最后一個(gè)字母在字母表中的序號(hào))MOD 7用線性探測(cè)法處理沖突，要求構(gòu)造一個(gè)裝填因子為的哈希表，并計(jì)算出在等概率情況下查 找成功的平均查找長度。3. (6分)將關(guān)鍵字序列( 3， 26， 12， 61， 38， 40， 97， 75， 53， 87)調(diào)整為 大根堆。4. (4分)已知權(quán)值集合為： 5， 7， 2， 3， 6， 9 ，要求給出哈夫曼樹，并計(jì) 算其帶權(quán)路徑長度 WPL。六、算法分析題( 10 分)閱讀下面程序，并回答有關(guān)問題。其中B

23、STree為用二叉鏈表表示的二叉排序樹類型。( 1 ) 簡要說明程序功能。 ( 5 分)(2) n 個(gè)結(jié)點(diǎn)的滿二叉樹的深度 h 是多少( 3 分)(3) 假設(shè)二叉排序樹 *bst 是有 n 個(gè)結(jié)點(diǎn)的滿二叉樹 , 給出算法的時(shí)間復(fù)雜 度。(2 分)int Proc (BSTree *bst, KeyType K) BSTree f, q, s;s=(BSTree)malloc(sizeof(BSTNode);s- key = K; s- lchild = NULL; s- rchild = NULL;if ( *bst = NULL ) *bst = s; return 1; f = NULL;

24、 q = *bst;while( q != NULL ) if ( K key ) f = q; q = q - lchild; else f = q; q = q - rchild; if ( K key ) f - lchild = s;elsef - rchild = s;return 1;七、算法設(shè)計(jì)題( 25 分)1. 已知一個(gè)帶頭結(jié)點(diǎn)的整數(shù)單鏈表和一個(gè)負(fù)整數(shù)單鏈表L2。( 9分)L,要求將其拆分為一個(gè)正整數(shù)單鏈表L12. 無向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)， 編寫算法輸出圖中各連通分量的結(jié)點(diǎn)序列。 (8 分)8 分）3 編寫一個(gè)建立二叉樹的算法，要求采用二叉鏈表存儲(chǔ)結(jié)構(gòu)SUN MON THU FRIWED TUE SAT數(shù)據(jù)結(jié)構(gòu)試卷參考答案、簡答題（15分，每小題3分）1. 算法是解決特定問題的操作序列，可以用多