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

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

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