數(shù)據(jù)結(jié)構(gòu)期末試卷A

數(shù)據(jù)結(jié)構(gòu)期末試卷A一、判斷題：（共10分，每題1分）1、深度為h的非空二叉樹(shù)的第i層最多有2i-1個(gè)結(jié)點(diǎn)。（）2、在完全二叉樹(shù)中,若某結(jié)點(diǎn)無(wú)左孩子,則它必是葉結(jié)點(diǎn)。（）3、一組權(quán)值，可以唯一構(gòu)造出一棵赫夫曼樹(shù)。（）4、在n個(gè)結(jié)點(diǎn)的無(wú)向圖中,若邊數(shù)多于n-1,則該圖必是連通圖。（）5、對(duì)于有向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。（）6、無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣是不對(duì)稱的。（）7、折半查找只適用于有序表，包括有序的順序表和有序的鏈表。（）8、一個(gè)好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲(chǔ)空間的有效地址范圍內(nèi)，以盡可能減少?zèng)_突。（）9、在初始數(shù)據(jù)為逆序時(shí)，冒泡排序所執(zhí)行的比較次數(shù)最多。（）10、希爾排序在效率上較直接插入排序有較大的改進(jìn)。但是不穩(wěn)定的。（）二、填空題：（共20分，每空2分）1、在樹(shù)結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)________,，且存在一條從根到該結(jié)點(diǎn)的___________。2、三個(gè)結(jié)點(diǎn)的二叉樹(shù)，最多有__________種形狀。3、任何一棵二叉樹(shù)，若n0，n2分別是度為0，2的結(jié)點(diǎn)的個(gè)數(shù)，則n0和n2的關(guān)系為_(kāi)_______。4、設(shè)有10個(gè)值，構(gòu)成赫夫曼樹(shù)，則該赫夫曼樹(shù)共有_______個(gè)結(jié)點(diǎn)。5、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_______倍。6、一個(gè)連通圖的生成樹(shù)是該圖的________連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn),則它的生成樹(shù)有________條邊。7、如果從一無(wú)向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是____________。8、將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫_____。三、選擇題：（共20分，每題2分）1、設(shè)x是一棵樹(shù)，x’是對(duì)應(yīng)于x的二叉樹(shù)，則x的后根次序遍歷和x’的____次序遍歷相同A.先序B.中序C.后序D.都不是2、設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，在查找成功的情況下，最大比較次數(shù)是_____。A.100B.50C.99D.73、設(shè)散列表長(zhǎng)m=14,散列函數(shù)H（K）=K％11，已知表中已有4個(gè)結(jié)點(diǎn)：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址為空，如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是________。A.8B.3C.5D.94、在含有n個(gè)項(xiàng)點(diǎn)有e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為_(kāi)_______。A.eB.2eC.n2-eD.n2-2e5、圖的深度優(yōu)先遍歷類似于樹(shù)的_______。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷6、下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的。________A、用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與邊數(shù)無(wú)關(guān)B、用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)C．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)D．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)7、從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為_(kāi)_______。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)8、用某種排序方法對(duì)關(guān)鍵字序列（23，72，21，47，15，27，59，35，20）進(jìn)行排序時(shí)，前三趟的結(jié)果情況如下________：23，21，47，15，27，59，35，20，7221，23，15，27，47，35，20，59，7221，15，23，27，35，20，47，59，72則所采用的排序方法是________A.選擇排序B.起泡排序C.歸并排序D.快速排序9、將一棵有40個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為15的結(jié)點(diǎn)的左孩子的編號(hào)為_(kāi)_____。A.30B.31C.16D.3210、如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是_______A.有向完全圖B.連通圖C.強(qiáng)連通圖D.有向無(wú)環(huán)圖四、應(yīng)用題：（共28分，每題4分）1、將下圖轉(zhuǎn)換為二叉樹(shù)，對(duì)轉(zhuǎn)換后的二叉樹(shù)進(jìn)行先序、中序、后序遍歷序列。2、什么是赫夫曼（Huffman）樹(shù)？有一組數(shù)值14、21、32、15、28，畫(huà)出赫夫曼樹(shù)，并計(jì)算其WPL。3、設(shè)一個(gè)有向圖為G=(V,E),其中V={v1,v2,v3,v4}，E={<v2,v1>,<v2,v3>,<v4,v1>,<v1,v4>,<v4,v2>},畫(huà)出該有向圖，畫(huà)出相應(yīng)鄰接表，寫(xiě)出從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。4、用序列（46，88，45，39，70，58，101，10，66，34）建立一個(gè)平衡的二叉排序樹(shù)，畫(huà)出該樹(shù)。5、已知一組鍵值序列為(41，66，73，52，40，37，65，43)，試采用快速排序法對(duì)該組序列作升序排序，并給出每一趟的排序結(jié)果。6、已知一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的哈希表。表長(zhǎng)取13，哈希函數(shù)H(key)=keyMOD13。7、已知一棵三階的B-樹(shù)如下圖所示，假定依次插入關(guān)鍵字50，83請(qǐng)畫(huà)出插入個(gè)結(jié)點(diǎn)后樹(shù)的情況：五、程序題（共22分）1、完成下列程序,并說(shuō)出該算法所完成的功能。（8分）voidweizhisort(structnoder[n],intn){intlow,high,mid,j,i;for(i=2;i<=n;i++){?r[0]=r[i];low=_____r[0]_____;high=____r[0]_____;while(low<=high){mid=(low+high)/2;if(r[0].key<r[mid].key)________low=mid_______;elselow=mid+1;}for(j=i-1;j>=l;j--)r[j+1]=r[j];r[high+1]=r[0];}}其中數(shù)據(jù)類型定義為:structnode{intkey;Infotypeotherinfo;}2、完成程序，并說(shuō)出程序的功能（8分）Bitreptr*bstsearch(Bitreptr*t,Keytypek){while(t!=null){if(t->key==k)_________;if(t->key>k)______________;else___________________;}returnnull;}其中，類型定義typedefstructBitnode{Keytypekey;StructBitnode*lchild,*rchild;}Bitreptr;3．完成程序，說(shuō)明其功能(6分)#defineNULL0;typedefstructBitnode{chardata;StructBitnode*lchild,*rchild;}Bitreptr;voidinorder_notrecursive(Bitreptrbt,Status(Visit)(Telem