洛陽理工學(xué)院數(shù)據(jù)結(jié)構(gòu)試題

1、一、判斷（每小題1分，共10分）1 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象，不僅要存儲數(shù)據(jù)元素的 值，還要存儲元素之間的相互關(guān)系。2用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的 相互關(guān)系。3 完全二叉樹的葉子結(jié)點只能出現(xiàn)在最后一層上。4 折半查找方法要求待查表必須是有序的順序表。5在有向圖G中， 2 ，V 1 和 1，V 2 是兩條不同的邊。6圖的最小生成樹是唯一的。7從循環(huán)單鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的 前趨結(jié)點。8 在單鏈表中，頭結(jié)點是必不可少的。9 對快速排序來說，初始序列為正序和反序，都是最壞情況。10廣義表是特殊的線性表。二、選擇（每題1

2、分，共15分）1 .設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。 若每個元素出棧后立即進(jìn)入隊列 Q ,且7個元素出隊的順序是bdcfeag ，則 棧S的容量至少是（）。A. 1B. 2C . 3D . 4C（用虛線表示線索），符合后序線索樹定義的是（3. 已知廣義表 A= ( a,b ) ,(c,d),則 head(A)等于()。A. (a,b)B. (a,b)C. a,bD. a4. 設(shè)字符串 s仁'ABCDEFG',s2=卩QRST',則運算 s=strcat(strsub(s1,2,strle n(s2),strsub (s1,strle n(

3、s2),2)后結(jié)果為()。A. BCQRB. BCDEFC. BCDEFGD. BCDEFEF5. 具有8個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為()。A. 8B. 9C. 7D. 66 .算法分析的兩個主要方面是()。A.空間復(fù)雜性和時間復(fù)雜性C可讀性和文檔性B .正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性7. 下列四種排序中（）的空間復(fù)雜度最大。A.插入排序B .冒泡排序C .堆排序D .歸并排序8. 下列關(guān)于無向連通圖特性的敘述中，正確的是（）。I .所有頂點的度之和為偶數(shù)II .邊數(shù)大于頂點個數(shù)減1 III .至少有一個頂點的度為1A.只有IB.只有II C . I和IID. I 和 I

4、II9.在一棵度為4的樹T中，若有20個度為4的結(jié)點,10個度為3的結(jié)點，1個度為2的結(jié)點,10個度為1的結(jié)點，則數(shù)T的葉結(jié)點個數(shù)是()。A. 41B . 82C. 113D . 12210 .對下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€數(shù)是（ ）A . 4A . 4B . 512 .對一組數(shù)據(jù)（2 , 12 , 16 趟排序結(jié)果如下：第一趟：2 ，12 ，16 ，10 ，16 ，88 第三趟：2 ，則采用的排序方法可能是（） A.起泡排序13 .設(shè)有二維數(shù)組 A5060 基地址為200，則元素A1825B.希爾排序C歸并排序D.基數(shù)排序 按行優(yōu)先順序存儲A .3700B . 4376C.

5、390014 .隊列操作的原則是（）。A .先進(jìn)先出B.后進(jìn)先出C.只能進(jìn)行插入D .15 .已知關(guān)鍵序列5 , 8,12 ,19 , 28 , 20,15堆（最小堆），插入關(guān)鍵字3，調(diào)整后得到的小根堆是A .3,5, 12,8 ,28,20,15 , 22 ,19B .3 , 5 , 12,19 ,20,15 , 22 , 8 ,28C.3 , 8 , 12,5 ,20,15,22 , 28 ,19D.3 , 12 , 5,8 ,28,20,15 , 22 ,19三、填空（每空1分，共25分）D. 4620只能進(jìn)行刪除，22是小根，其元素長度為4字節(jié), 的存儲地址為（）。11 .已知一個長度

6、為16的順序表L，其元素按關(guān)鍵字有序排列，若采用 折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（）C . 6D . 7，88 ， 5 ， 10 ）進(jìn)行排序，若前三10 ，88 第二趟：2 ， 12 ，5 ，10 ， 12 ， 16 ，88I 在一個有向圖的鄰接表中，一個頂點的邊表中結(jié)點的個數(shù)等于這個頂點的（），在逆鄰接表中，一個頂點的邊表中結(jié)點的個數(shù)等于這個頂點的（）。2四類基本邏輯結(jié)構(gòu)是集合、（）、（）、圖狀結(jié)構(gòu)。3當(dāng)一個AOV網(wǎng)用鄰接表表示時，可按下列方法進(jìn)行拓?fù)渑判?。?）查鄰接表中入度為（）的頂點，并進(jìn)棧；（2）若棧不空，則輸出棧頂元素Vj ，并退棧；查Vj的直接后繼Vk， 對V

7、k入度處理，處理方法是（）；（3）若棧空時，輸出頂點數(shù)小于圖的頂點數(shù)，說明有（），否則拓?fù)渑判蛲?成。4 空格串是指（），其長度等于（）。5. 我們學(xué)過的構(gòu)造散列函數(shù)的方法有（）、平方取中法、分段疊加法、（）、 偽隨機(jī)數(shù)法。6 設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順 序從1開始順序編號，則編號為8的結(jié)點的雙親結(jié)點的編號是（），編號為 8的結(jié)點的左孩子結(jié)點的編號是（）。7 順序存儲結(jié)構(gòu)是通過（）表示兀素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通（）表示元素之間的關(guān)系的。8僅允許在表的一端進(jìn)行插入和刪除運算的線性表被稱為（）。9在分塊查找中雖不要求整個表有序，但要求表（）有序。10根據(jù)

8、二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。II 設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該 二叉鏈表中共有（）個指針域，（）個空指針域。12.用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度（）的次序來得到最短路徑的。13在散列法中要解決兩個問題：構(gòu)造一個（）的散列函數(shù)、給出解決（） 的方法。14.在順序隊列中做入隊運算時，應(yīng)先判別隊列是否（）；在做出隊運算時， 應(yīng)先判別隊列是否（）。四、簡答題（每題5分，共30分）1設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù) ABCDE，如圖，要求給出該二 叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。1 23

9、45ABCDE2 設(shè)給定一個權(quán)值集合 W=（3，5 ，7 ，9，11），要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。3設(shè)無向圖G （如下圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷 的序列并給出該圖的最小生成樹。14 設(shè)一組初始記錄關(guān)鍵字集合為 (25 , 10 , 8 , 27 , 32 , 68), 散列表的長度為8，散列函數(shù)H(k)=k mod 7 ，要求用線性探測法作為解決沖 突的方法設(shè)計哈希表。并計算該表查找成功的平均查找長度和查找不成功的平均 查找長度。5. 已知一棵樹如下圖所示，要求將該樹轉(zhuǎn)化為二叉樹。6. 已知關(guān)鍵字集合： 46 , 55 , 1

10、3 , 42 , 94 , 17 , 05 , 7 0 ，用冒泡排序從小到大排序，分別寫出第一趟、第二趟、第三趟排序結(jié)束時 的序列，該排序方法穩(wěn)定嗎？五、算法設(shè)計題(每題10分，共20分)1. 設(shè)有一個由正整數(shù)組成的無序(向后)單鏈表，編寫完成下列功能的算 法：(1) 找出最小值結(jié)點，且打印該數(shù)值；(2) 若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除； 單鏈表類型描述：typedef struct Node ElemType data ;struct Node* n ext;Node, *L in kList；2. 已知一個二叉樹采用二叉鏈表存放，寫一算法，統(tǒng)計出二叉樹中葉子結(jié) 點的個數(shù)。二叉鏈表類

11、型描述為：typedef struct Node DataType data;struct Node * Ichild;struct Node * rchild;BiTNode, *BiTree;一、判斷（每小題1分，共10分）1 V 2 V 3 X 4 V 5 V 6 X 7 X 8 X 9 V 10 V二、選擇（每題1分，共15分）I. C 2. D 3. A 4. D 5. C6. A 7. D 8. A 9. B 10. AII. B 12. A 13. B 14. A 15. A三、填空（每空1分，共25分）1 .出度 入度2 .線性結(jié)構(gòu)樹狀結(jié)構(gòu)3. 0 Vk入度減1，若為0進(jìn)棧環(huán)（

12、回路）4. 由空格組成的串空格的個數(shù)5. 數(shù)字分析法除留余數(shù)法6. 4 167. 位置相鄰指針8. 棧9. 塊間10. 511. 2n n+112. 遞增13. 均勻沖突14. 滿空四、簡答題（每題5分，共30分）中序序列:DBEAC、后序序列:DEBCA、前序序列：ABDEC、2.哈夫曼樹：WPL= （ 7*2+3*3+5*3+9*2+11*2） =78（ 1 分）3.深度優(yōu)先遍歷序列：123,4,6,5（不唯一）廣度優(yōu)先遍歷序列：1,2,3,4,5,6 （不唯一） 最小生成樹：4.01234567310253227111213查找成功的平均查找長度為：(1*4+2+3 ) 16=96查找不

13、成功的平均查找長度為：(1+2+1+6+5+4+3 ) /7=22/75.轉(zhuǎn)化后的二叉樹：6. 第一趟：46 13 42 55 17 05 70 94第二趟：13 42 46 17 05 55 70 94第三趟：13 42 17 05 46 55 70 94該排序方法穩(wěn)定五、算法設(shè)計題(每題10分，共20分)本題無統(tǒng)一答案。每道題編寫算法時完成題目功能即可1.參考答案：void fun(Lin kList head) int min;Node * p , * q;if(p!=NULL) p=head;min=p->data;while(p!=NULL)if( min >p->data) min=p->data; q=p;p=p->n ext;printf(“min=%dn” ,min);if(mi n%2=0 && q-> next!=NULL) p=q->n ext;q->n ext=p->n ext;free(p);2 參考答案：/*node為保存葉子結(jié)點數(shù)目的全局變量，調(diào)用之前初始化為0 */void Cou ntNode(Bi nTree root) /*求二叉樹中葉子結(jié)點個數(shù) */if (root!=NULL) Count