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

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

2、和反序，都是最壞情況。 10廣義表是特殊的線性表。 二、選擇（每題 1 分，共 15 分） 1設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)均為空，元素 abcdefg 依次進(jìn)入棧 S 。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列 Q ，且 7 個(gè)元素出隊(duì)的順序是 bdcfeag ，則棧 S 的容量至少是（ ）。A1       B2       C3       D4 2下列線索二叉樹(shù)中（用虛線表示線索），符合后序線索樹(shù)定義的是(  )。 &

3、#160;3已知廣義表 A= （ a,b ） ,(c,d) ） , 則 head(A) 等于 (  )。A(a,b)       B(a,b)    Ca,b        Da 4設(shè)字符串 s1='ABCDEFG',s2='PQRST', 則運(yùn)算 s=strcat(strsub(s1,2,strlen(s2),strsub (s1,strlen(s2),2) 后結(jié)果為（ ）。 ABCQR

4、60;       BBCDEF      CBCDEFG     DBCDEFEF 5具有 8 個(gè)頂點(diǎn)的連通圖的深度優(yōu)先生成樹(shù)，其邊數(shù)為（ ）。 A8    B9           C7         

5、D6 6算法分析的兩個(gè)主要方面是（ ）。 A空間復(fù)雜性和時(shí)間復(fù)雜性        B正確性和簡(jiǎn)明性 C可讀性和文檔性                D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 7下列四種排序中（ ）的空間復(fù)雜度最大。 A插入排序    B冒泡排序     C堆排序    

6、   D歸并排序 8下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（ ）。 I所有頂點(diǎn)的度之和為偶數(shù) II邊數(shù)大于頂點(diǎn)個(gè)數(shù)減 1 III至少有一個(gè)頂點(diǎn)的度為 1 A只有 I    B只有 II  CI 和 II      DI 和 III 9在一棵度為 4 的樹(shù) T 中，若有 20 個(gè)度為 4 的結(jié)點(diǎn)， 10 個(gè)度為 3 的結(jié)點(diǎn)， 1 個(gè)度為 2 的結(jié)點(diǎn)， 10 個(gè)度為 1 的結(jié)點(diǎn)，則數(shù) T 的葉結(jié)點(diǎn)個(gè)數(shù)是（ ）。 A41  B82   &#

7、160;     C113          D122 10對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是（ ）。  A4       B3         C2          D1 11已知一個(gè)長(zhǎng)度為 16 的順序表 L

8、 ，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多的是（ ）。 A4     B5          C6          D7 12對(duì)一組數(shù)據(jù)（ 2 ， 12 ， 16 ， 88 ， 5 ， 10 ）進(jìn)行排序，若前三趟排序結(jié)果如下： 第一趟： 2 ， 12 ， 16 ， 5 ，  10 ， 88 第二趟： 2 ， 12 ，

9、5 ， 10 ， 16 ， 88 第三趟： 2 ， 5 ， 10 ， 12 ， 16 ， 88 則采用的排序方法可能是（ ）。A起泡排序    B希爾排序   C歸并排序    D基數(shù)排序 13設(shè)有二維數(shù)組 A5060 ，其元素長(zhǎng)度為 4 字節(jié)，按行優(yōu)先順序存儲(chǔ)基地址為 200 ，則元素 A1825 的存儲(chǔ)地址為（ ）。 A3700      B4376     C3900  

10、     D4620 14隊(duì)列操作的原則是（ ）。A先進(jìn)先出  B后進(jìn)先出  C只能進(jìn)行插入   D只能進(jìn)行刪除 15已知關(guān)鍵序列 5 ， 8 ， 12 ， 19 ， 28 ， 20 ， 15 ， 22 是小根堆（最小堆），插入關(guān)鍵字 3 ，調(diào)整后得到的小根堆是 A3 ， 5 ， 12 ， 8 ， 28 ， 20 ， 15 ， 22 ， 19  B3 ， 5 ， 12 ， 19 ， 20 ， 15 ， 22 ， 8 ， 28 C3 ， 8 ， 12 ， 5 ， 20 ， 15 ， 22

11、 ， 28 ， 19  D3 ， 12 ， 5 ， 8 ， 28 ， 20 ， 15 ， 22 ， 19 三、填空（每空 1 分，共 25 分） 1在一個(gè)有向圖的鄰接表中，一個(gè)頂點(diǎn)的邊表中結(jié)點(diǎn)的個(gè)數(shù)等于這個(gè)頂點(diǎn)的（ ），在逆鄰接表中，一個(gè)頂點(diǎn)的邊表中結(jié)點(diǎn)的個(gè)數(shù)等于這個(gè)頂點(diǎn)的（ ）。2四類基本邏輯結(jié)構(gòu)是集合、（）、（）、圖狀結(jié)構(gòu)。 3當(dāng)一個(gè) AOV 網(wǎng)用鄰接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判颉?(1)查鄰接表中入度為（ ）的頂點(diǎn)，并進(jìn)棧； (2)若棧不空，則輸出棧頂元素 Vj ，并退棧；查 Vj 的直接后繼 Vk ，對(duì) Vk 入度處理，處理方法是（ ）； (3)若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于

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

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

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

15、 6已知關(guān)鍵字集合： 46 ， 55 ， 13 ， 42 ， 94 ， 17 ， 05 ， 70 ，用冒泡排序從小到大排序，分別寫(xiě)出第一趟、第二趟、第三趟排序結(jié)束時(shí)的序列，該排序方法穩(wěn)定嗎？ 五、算法設(shè)計(jì)題（每題 10 分，共 20 分） 1設(shè)有一個(gè)由正整數(shù)組成的無(wú)序（向后）單鏈表，編寫(xiě)完成下列功能的算法： (1)找出最小值結(jié)點(diǎn)，且打印該數(shù)值； (2)若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除； 單鏈表類型描述： typedef struct Node    ElemType data ；   struct Node  * next ； Node,

16、 *LinkList ；   2已知一個(gè)二叉樹(shù)采用二叉鏈表存放，寫(xiě)一算法，統(tǒng)計(jì)出二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)。 二叉鏈表類型描述為： typedef struct Node   DataType data;    struct Node * lchild;    struct Node * rchild; BiTNode, *BiTree; 一 、判斷（每小題 1 分，共 10 分） 1 2 3 4 5 6 7 8 9 10 二、選擇（每題 1 分，共 15 分） 1C 2D 3A 4D 5C   6

17、A 7D 8A 9B 10A 11B 12A 13B 14A 15A 三、填空（每空 1 分，共 25 分） 1出度   入度 2線性結(jié)構(gòu)  樹(shù)狀結(jié)構(gòu) 30  Vk 入度減 1，若為 0 進(jìn)棧 環(huán)（回路） 4由空格組成的串  空格的個(gè)數(shù) 5數(shù)字分析法  除留余數(shù)法 64 16 7位置相鄰  指針 8棧 9塊間 105 112n n+1 12遞增 13均勻   沖突 14滿   空 四、簡(jiǎn)答題（每題 5 分，共 30

18、分） 1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、  前序序列： ABDEC 、 中序序列： DBEAC 、 后序序列： DEBCA 、 2哈夫曼樹(shù)：WPL= （ 7*2+3*3+5*3+9*2+11*2 ） =78 （ 1 分） 3深度優(yōu)先遍歷序列： 1,2,3,4,6,5 （不唯一） 廣度優(yōu)先遍歷序列： 1,2,3,4,5,6 （不唯一） 最小生成樹(shù)：   4查找成功的平均查找長(zhǎng)度為：（ 1*4+2+3 ） /6=9/6 查找不成功的平均查找長(zhǎng)度為：（ 1+2+1+6+5+4+3 ） /7=22/7 5轉(zhuǎn)化后的二叉樹(shù)：   6第一趟： 46 13 42 55 17 05 70

19、94    第二趟： 13 42 46 17 05 55 70 94    第三趟： 13 42 17 05 46 55 70 94 該排序方法穩(wěn)定 五、算法設(shè)計(jì)題（每題 10 分，共 20 分） 本題無(wú)統(tǒng)一答案。每道題編寫(xiě)算法時(shí)完成題目功能即可。 1參考答案： void fun(LinkList head)  int min;   Node * p , * q;   if(p!=NULL)   p=head;     min=p->data;   while(p!=NULL)   if(min>