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

PAGE第7頁共7頁班級(jí)：專業(yè)：姓名：考號(hào)：密封裝訂線信息技術(shù)學(xué)院2006-2007學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)試卷1（適用班級(jí)：）（答題時(shí)間：120分鐘，滿分：100分）題號(hào)第一部分第二部分第三部分第四部分總分核分人得分得分評(píng)卷人一、判斷題：（共10分，每題1分）1.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問。（）2.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。（）3.只有用面向?qū)ο蟮挠?jì)算機(jī)語言才能描述數(shù)據(jù)結(jié)構(gòu)算法。（）4.在對(duì)雙向循環(huán)鏈表做刪除一個(gè)結(jié)點(diǎn)操作時(shí)，應(yīng)先將被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鏈接好再執(zhí)行刪除結(jié)點(diǎn)操作。（）5.遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。（）6.在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。（）7.二叉樹是一棵無序樹。（）8.在任何情況下，快速排序需要進(jìn)行關(guān)鍵碼比較的次數(shù)都是O(nlog2n)。（）9.圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。（）10.當(dāng)從一個(gè)最小堆中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（）得分評(píng)卷人二、填空題（20分，每題2分）假定一棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)為32，則它的最小深度為______。在一棵二叉樹中，度為2的結(jié)點(diǎn)有5個(gè)，度為1的結(jié)點(diǎn)有6個(gè)，那么葉子結(jié)點(diǎn)有______個(gè)。一棵深度為5的滿二叉樹的結(jié)點(diǎn)總數(shù)為______個(gè)。假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為______。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為______。若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出元素的值序列按增序排列，應(yīng)對(duì)該二叉排序樹采用____________遍歷法。元素關(guān)鍵字轉(zhuǎn)換為該元素存儲(chǔ)位置的函數(shù)f稱為____________。每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做____________排序。假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則利用堆排序方法建立的初始大頂堆為__________________。對(duì)20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行______趟歸并。得分評(píng)卷人三、選擇題（共20分，每題2分）樹中所有結(jié)點(diǎn)的度數(shù)之和等于結(jié)點(diǎn)總數(shù)加______。A.0B.1C.-1D.2在一棵樹中，每個(gè)結(jié)點(diǎn)最多有______個(gè)直接前驅(qū)結(jié)點(diǎn)。A.0B.1C.2D.任意多個(gè)在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加______。A.2B.1C.0D.-1頂點(diǎn)個(gè)數(shù)為n的無向圖最多有______條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)n個(gè)頂點(diǎn)的連通圖至少有______條邊。A.n-1B.nC.n+1D.0在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的______倍。A.3B.2C.1D.1/2對(duì)于順序存儲(chǔ)的有序表(5,12,20,26,37,42,46,50,64)，為查找元素26，若采用順序查找，需要比較______次才能查找成功。A.3B.4C.5D.6設(shè)哈希表長為14，哈希函數(shù)f（k）=k％11，已知表中已有4個(gè)元素，關(guān)鍵字分別為15，38，61，84，存儲(chǔ)位置分別為4，5，6，7，其它存儲(chǔ)位置為空，如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的存儲(chǔ)位置是______。A.8B.3C.5D.9在對(duì)n個(gè)元素進(jìn)行簡單選擇排序的過程中，需要進(jìn)行______趟選擇和交換。A.n/2B.n-1C在對(duì)n個(gè)元素進(jìn)行快速排序的過程中，第一趟排序最多需要交換______對(duì)元素。A.n/2B.n-1C得分評(píng)卷人四、應(yīng)用題（共30分，每題6分）已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，nk個(gè)度為k的結(jié)點(diǎn)，問該樹有多少個(gè)葉子結(jié)點(diǎn)？（6分）對(duì)于下面兩個(gè)圖，求出：無向圖中每個(gè)頂點(diǎn)的度，有向圖中每個(gè)頂點(diǎn)的入度，出度和度。是否是連通圖/強(qiáng)連通圖，如果不是，畫出連通分量/強(qiáng)連通分量。（6分）010124340312分別畫出在線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找，以查關(guān)鍵字等于e、f和g的過程。（6分）已知一組元素的關(guān)鍵字{46,74,16,53,14,26,40,38,86,65,27,34}，利用直接插入排序法，寫出每次向前面的有序表插入一個(gè)元素后的排列結(jié)果。（6分）5、將下圖轉(zhuǎn)換為二叉樹，對(duì)轉(zhuǎn)換后的二叉樹進(jìn)行先序、中序、后序遍歷序列。（6分）AABCDEFGJ五、程序題（20分）將下面算法填完整。（10分，每空2分）intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若找到，則返回該元素//在表中的位置，否則返回0low=1;high=ST.length;while(low<=high){mid=____________;if(EQ(key,ST.elem[mid].key))return____________;elseif(LT(key,ST.elem[mid].key))high=____________;elselow=____________;}return____________;}將下面算法填完整。（10分，每空2分）voidInsertSort(SqList&L){//對(duì)順序表L作直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=____________;L.r[i]=____________;for(j=____________;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=____________;L.r[j+1]=____________;}}班級(jí)：專業(yè)：姓名：考號(hào)：密封裝訂線信息技術(shù)學(xué)院2006-2007學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)試卷2（適用班級(jí)：）（答題時(shí)間：120分鐘，滿分：100分）題號(hào)第一部分第二部分第三部分第四部分總分核分人得分得分評(píng)卷人一、判斷題（10分，每題1分）1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）2.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（）3.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問。（）4.鏈?zhǔn)綏Ｅc順序棧相比,一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（）5.一個(gè)廣義表((a),((b),c),(((d))))的長度為3，深度為4。（）6.在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。（）7.進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。（）8.用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（）9.直接選擇排序是一種穩(wěn)定的排序方法。（）10.對(duì)于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。（）得分評(píng)卷人二、填空題（20分，每題2分）假定一棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)為32，則它的最大深度為______。在一棵二叉樹中，度為2的結(jié)點(diǎn)有5個(gè)，度為1的結(jié)點(diǎn)有6個(gè)，那么葉子結(jié)點(diǎn)有______個(gè)。一棵深度為5的滿二叉樹的結(jié)點(diǎn)總數(shù)為______個(gè)。假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點(diǎn)H的孩子結(jié)點(diǎn)為______。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為______。若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出元素的值序列按增序排列，應(yīng)對(duì)該二叉排序樹采用____________遍歷法。元素關(guān)鍵字轉(zhuǎn)換為該元素存儲(chǔ)位置的函數(shù)f稱為____________。先將整個(gè)待排序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列“基本有序”時(shí)，再對(duì)全體進(jìn)行一次直接插入排序，此種排序方法叫做____________排序。假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則利用堆排序方法建立的初始小頂堆為__________________。假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則以第一個(gè)記錄為樞軸，對(duì)其進(jìn)行第一趟快速排序的結(jié)果為__________________。得分評(píng)卷人三、選擇題（20分，每題2分）在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于______。A.nB.n-1C.n+1D.2*n在一棵二叉樹的第5層上，最多具有______個(gè)結(jié)點(diǎn)。A.14B.16C.31D.32在一棵深度為h的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不少于______。A.2hB.2h+1C.2h-1D.2有向圖的一個(gè)頂點(diǎn)的度為該頂點(diǎn)的______。A.入度B.出度C.入度與出度之和D.(入度＋出度)/2一個(gè)連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)______子圖。A.極小B.連通C.極小連通D.無環(huán)具有e條邊無向圖，它的鄰接表中有______個(gè)邊結(jié)點(diǎn)。A.e-1B.eC.2(e-1)D.2e長度為m的哈希表，采用線性探測(cè)再散列處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的存儲(chǔ)地址為d，則下一次的存儲(chǔ)地址為______。A.dB.d+1C.(d+1)/mD.(d+1)%m適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是______。A.有序表B.順序表C.二叉排序樹D.鏈表在對(duì)n個(gè)元素進(jìn)行簡單選擇排序的過程中，需要進(jìn)行______趟選擇和交換。A.n/2B.n-1C若對(duì)n個(gè)元素進(jìn)行直接插入排序，在進(jìn)行i趟(2≤i≤n)排序時(shí)，為尋找插入位置最多需要進(jìn)行______次元素的比較。A.i+1B.i-1C.iD.得分評(píng)卷人三、應(yīng)用題（30分，每題6分）寫出下圖所示二叉樹的先序、中序、后序序列。（6分）AABCDEF先序序列：中序序列：后序序列：對(duì)于下面兩個(gè)圖，求出：無向圖中每個(gè)頂點(diǎn)的度，有向圖中每個(gè)頂點(diǎn)的入度，出度和度。每個(gè)圖的鄰接矩陣。（6分）010124340312已知一組關(guān)鍵字{26,38,12,45,73,64,30,56}試依次插入關(guān)鍵字生成一棵二叉排序樹畫出分別刪除38和73后樹的結(jié)構(gòu)（6分）已知一組元素的關(guān)鍵字{46,74,16,53,14,26,40,38,86,65,27,34}，利用起泡排序法，寫出每趟排序后的排列結(jié)果。（6分）5、什么是赫夫曼（Huffman）樹？有一組數(shù)值14、21、32、15、28，畫出赫夫曼樹，并計(jì)算其WPL。（6分）得分評(píng)卷人四、程序題（20分）將下面算法填完整。（10分，每空2分）intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若找到，則返回該元素//在表中的位置，否則返回0low=1;high=ST.length;while(low<=high){mid=____________;if(EQ(key,ST.elem[mid].key))return____________;elseif(LT(key,ST.elem[mid].key))high=____________;elselow=____________;}return____________;}將