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

精選文檔，供參考!精選文檔，供參考!一、判斷（每小題1分，共10分）.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象，不僅要存儲數(shù)據(jù)元素的值，還要存儲元素之間的相互關(guān)系。.用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系。.完全二叉樹的葉子結(jié)點只能出現(xiàn)在最后一層上。.折半查找方法要求待查表必須是有序的順序表。.在有向圖G中，＜V2,V1＞和＜V1,V2＞是兩條不同的邊。.圖的最小生成樹是唯一的。.從循環(huán)單鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的前趨結(jié)點。.在單鏈表中，頭結(jié)點是必不可少的。.對快速排序來說，初始序列為正序和反序，都是最壞情況。.廣義表是特殊的線性表。二、選擇（每題1分，共15分）1.設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個元素出棧后立即進(jìn)入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量至少是（）。TOC\o"1-5"\h\zA.1 B.2 C.3 D.4.下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）,3.已知廣義表A=((a,b),(c,d)),則head(A)等于()。A.(a,b) B.((a,b)) C.a,b D.a4.設(shè)字符串s1='ABCDEFG',s2='PQRSr,則運算s=strcat(strsub(s1,2,strlen(s2)),strsub(s1,strlen(s2),2)) 后結(jié)果為()。A.BCQR B.BCDEF C.BCDEFGD.BCDEFEF.具有8個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為( )。A.8B.9 C.7 D.6.算法分析的兩個主要方面是()。

A.空間復(fù)雜性和時間復(fù)雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性.下列四種排序中（）的空間復(fù)雜度最大。A.插入排序 B.冒泡排序 C.堆排序 D.歸并排序.下列關(guān)于無向連通圖特性的敘述中，正確的是（ ）。I.所有頂點的度之和為偶數(shù)II.邊數(shù)大于頂點個數(shù)減1III.至少有一個頂點的度為1A.只有I B.只有IIC.I和II D.I和III.在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則數(shù)T的葉結(jié)點個數(shù)是（）。A.41B.82 C,113 D.122.對下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€數(shù)是A.4 B.A.4 B.3 C.2D.1.已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（ ）。A.4 A.4 B.512.對一組數(shù)據(jù)（2,12,16趟排序結(jié)果如下：第一趟：2,12,16,5,10,16,88第三趟：2,5,則采用的排序方法可能是（）。A.起泡排序 B.希爾排序C.6 D.7,88,5,10）進(jìn)行排序，若前三10,88第二趟：2,12,5,10,12,16,88C.歸并排序 D,基數(shù)排序D.D.4620D,只能進(jìn)行刪除,15,22是小根19281919.設(shè)有二維數(shù)組A[50][60],其元素長度為4字節(jié)，按行優(yōu)先順序存儲基地址為200,則元素A[18][25] 的存儲地址為（）。A.3700 B.4376 C.3900.隊列操作的原則是（）。A.先進(jìn)先出 B.后進(jìn)先出 C.只能進(jìn)行插入.已知關(guān)鍵序列5,8,12,19,28,20堆（最小堆），插入關(guān)鍵字3,調(diào)整后得到的小根堆是TOC\o"1-5"\h\zA.3 , 5 , 12 , 8 , 28 , 20 , 15 ,22 ,B.3 , 5 , 12 , 19,20 ,15 ,22, 8 ,3 , 8 , 12 , 5 , 20 , 15 , 22 , 28 ,3 , 12 , 5 , 8 , 28 , 20 , 15 , 22 ,三、填空（每空1分，共25分）.在一個有向圖的鄰接表中，一個頂點的邊表中結(jié)點的個數(shù)等于這個頂點的（），在逆鄰接表中，一個頂點的邊表中結(jié)點的個數(shù)等于這個頂點的（ ）。.四類基本邏輯結(jié)構(gòu)是集合、（）、（）、圖狀結(jié)構(gòu)。3.當(dāng)一個AOV網(wǎng)用鄰接表表示時，可按下列方法進(jìn)行拓?fù)渑判颉＃?）查鄰接表中入度為（）的頂點，并進(jìn)棧；（2）若棧不空，則①輸出棧頂元素Vj,并退棧；②查Vj的直接后繼Vk,對Vk入度處理，處理方法是（）；（3）若?？諘r，輸出頂點數(shù)小于圖的頂點數(shù)，說明有（），否則拓?fù)渑判蛲瓿伞?空格用是指（）,其長度等于（）。.我們學(xué)過的構(gòu)造散列函數(shù)的方法有（）、平方取中法、分段疊加法、（）、偽隨機(jī)數(shù)法。.設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的結(jié)點的雙親結(jié)點的編號是（），編號為8的結(jié)點的左孩子結(jié)點的編號是（）。.順序存儲結(jié)構(gòu)是通過 （）表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通（）表示元素之間的關(guān)系的。.僅允許在表的一端進(jìn)行插入和刪除運算的線性表被稱為（）。.在分塊查找中雖不要求整個表有序，但要求表（）有序。.根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。.設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有（）個指針域，（）個空指針域。.用Dijkstra 算法求某一頂點到其余各頂點間的最短路徑是按路徑長度（）的次序來得到最短路徑的。.在散列法中要解決兩個問題：構(gòu)造一個（）的散列函數(shù)、給出解決（）的方法。.在順序隊列中做入隊運算時，應(yīng)先判別隊列是否（）；在做出隊運算時，應(yīng)先判別隊列是否（）。四、簡答題（每題5分，共30分）.設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE,如圖，要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2 3 4 5A B C D E.設(shè)給定一個權(quán)值集合W=（3,5,7,9,11）,要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度 WPL。.設(shè)無向圖G（如下圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。.設(shè)一組初始記錄關(guān)鍵字集合為(25,10,8,27,32,68),散列表的長度為8,散列函數(shù)H(k尸kmod7,要求用線性探測法作為解決沖突的方法設(shè)計哈希表。并計算該表查找成功的平均查找長度和查找不成功的平均查找長度。.已知一棵樹如下圖所示，要求將該樹轉(zhuǎn)化為二叉樹。.已知關(guān)鍵字集合：{46,55,13,42,94,17,05,70},用冒泡排序從小到大排序，分別寫出第一趟、第二趟、第三趟排序結(jié)束時的序列，該排序方法穩(wěn)定嗎？五、算法設(shè)計題(每題10分，共20分).設(shè)有一個由正整數(shù)組成的無序(向后)單鏈表，編寫完成下列功能的算法：(1)找出最小值結(jié)點，且打印該數(shù)值；(2)若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除；單鏈表類型描述：typedefstructNode{ElemTypedata;structNode*next；}Node,*LinkList；.已知一個二叉樹采用二叉鏈表存放，寫一算法，統(tǒng)計出二叉樹中葉子結(jié)點的個數(shù)。二叉鏈表類型描述為：typedefstructNode{DataTypedata;structNode*Ichild;structNode*rchild;}BiTNode,*BiTree;

一、判斷（每小題1分，共10分）1V2V3X4V5V6X7X8X9V10V二、選擇（每題1分，共15分）1.C2.D3.A4.D5.C6.A7.D8.A9.B10.AB12.A13.B14.A15.A三、填空（每空1分，共25分）.出度入度.線性結(jié)構(gòu) 樹狀結(jié)構(gòu).0Vk入度減1,若為0進(jìn)棧環(huán)（回路）4,由空格組成的用 空格的個數(shù).數(shù)字分析法 除留余數(shù)法.416.位置相鄰 指針.棧.塊間.5.2nn+1.遞增.均勻沖突.滿空四、簡答題（每題5分，共30分）中序序列:DBEAC、后序序歹hDEBCA、前序序列：ABDEC、2.哈夫曼樹：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（不唯一）最小生成樹：

4.012345673102532271 112 13查找成功的平均查找長度為：(1*4+2+3)16=916查找不成功的平均查找長度為：(1+2+1+6+5+4+3)/7=22/7.轉(zhuǎn)化后的二叉樹：.第一趟：4613425517057094第二趟：1342461705557094第三趟：1342170546557094該排序方法穩(wěn)定五、算法設(shè)計題(每題10分，共20分)本題無統(tǒng)一答案。每道題編寫算法時完成題目功能即可.參考答案：voidfun(LinkListhead){intmin;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->next;}printf( "min=%d\n”,min);if(min%2==0&&q->next!=NULL){p=q->next;q->next=p->next;free(p)；}}.參考答案：/*node為保存葉子結(jié)點數(shù)目的全局變量，調(diào)用之前初始化為0*/voidCountNode(BinTreeroot)/*求二叉樹中葉子結(jié)點個數(shù)*/{if(roo