華中科技大學(xué)計算機學(xué)院數(shù)據(jù)結(jié)構(gòu)(計算機專業(yè))

1、華中科技大學(xué)計算機學(xué)院 數(shù)據(jù)結(jié)構(gòu)試卷 (A卷)2010 2011 年度第二學(xué)期計算機學(xué)院班級_ 學(xué)號_ 姓名_考試時間：2011年 月 日 考試形式：閉卷題號一二三四五六七八總分核對人題分101010123210610100得分得分評卷人一、單項選擇題(從下列各題四個備選答案中選出一個正確答案,將其代號(A,B,C,D)寫在下表中,每小題1分,共10分)題號12345678910答案1對于棧的進(jìn)棧和出棧運算，采用_存儲結(jié)構(gòu)時運算效率最高。A單鏈表 B容量足夠大的順序表C單向循環(huán)鏈表 D雙向循環(huán)鏈表2鏈?zhǔn)疥犃泻晚樞蜿犃斜容^，具有_這個優(yōu)勢。A進(jìn)隊操作方便 B出隊操作方便C通常不會出現(xiàn)滿隊列情況

2、D求隊列元素個數(shù)方便3下列關(guān)于串的敘述中，正確的是_。 A2個串的長度相等，則2個串相等 B空串至少包一個空格 C替換操作可以實現(xiàn)字符的刪除 D一個串的長度至少是14二叉樹在線索化后，下列問題中相對難解決的是_。A先根線索二叉樹中求先根后繼B中根線索二叉樹中求中根前趨C中根線索二叉樹中求中根后繼D后根線索二叉樹中求后根后繼5對序列（30，26，18，16，5，66）進(jìn)行2遍 _排序后得到序列（5，16，18，26，30，66）。A選擇 B冒泡 C插入 D歸并6在下列排序算法中，_算法可能出現(xiàn)如下情況：在最后一趟排序之前，所有元素均不在其最終的位置上。A堆排序 B快速排序 C冒泡排序 D插入排序

3、7由4個結(jié)點可以組成_棵不同形態(tài)的二叉樹。A10 B12 C14 D16 8對包含n個元素的散列表進(jìn)行檢索，平均查找長度為_。 AO(logn) BO(n) CO(nlogn) D不直接依賴于n9廣義表 (a,(b),c),(),(d),(e),f),()的長度是_。A2 B3 C4 D510對某無向圖進(jìn)行一次深度優(yōu)先搜索遍歷，如果能訪問到所有的頂點，則該無向圖一定是_。A連通圖 B樹圖 C有回路的連通圖 D完全圖得分評卷人二、填空題(在下表中填寫正確的答案,每空1分,共10分) 題號12345678910答案1 具有n個單元、用首尾指針、無標(biāo)志位的循環(huán)隊列中，隊滿時共有_個元素。2 設(shè)頂點數(shù)

4、為n，弧數(shù)為e的有向圖的用鄰接表存儲，求頂點值為V的頂點的入度的算法時間復(fù)雜度為_。3 某哈夫曼樹有11個結(jié)點，則它有_個度為2的結(jié)點。4 設(shè)森林T中有三棵樹，第一、二、三棵樹的結(jié)點個數(shù)分別是n1，n2，n3，那么當(dāng)把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有_個結(jié)點。5 當(dāng)線性表經(jīng)常進(jìn)行插入和刪除操作時，應(yīng)該選擇使用_存儲結(jié)構(gòu)。6 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S，一個元素出棧后即進(jìn)入隊列Q。若這6個元素出隊列的順序是b、d、c、f、e、a，則棧S的容量至少應(yīng)該是_。7 滿足先根遍歷序列為a、b、c，后根序列為c、b、a的二叉樹共有_棵。8 按廣度優(yōu)先搜索遍

5、歷圖的算法需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是_。9高度為4的平衡二叉樹至少有_個結(jié)點。10對n個元素的序列進(jìn)行簡單選擇排序，最多進(jìn)行_次元素的交換。得分評卷人三、判斷題(判斷下列各題敘述的正確性,用表示正確，×表示錯誤，每小題1分,共10分) 題號12345678910答案1 可以以隨機方式訪問以三元組方式存放的稀疏矩陣的非零元素。2 對完全二叉樹，如已知高度h和第h層的結(jié)點數(shù)，一定能求二叉樹的結(jié)點數(shù)。3 算法分析的目的之一是分析算法的效率以求改進(jìn)。 4 正確性是算法的特征之一。5 線性表的邏輯結(jié)構(gòu)與存儲順序總是一致的。6 在循環(huán)鏈表中，任何一個結(jié)點的指針部分都指向其直接后繼元素的結(jié)點。7 將

6、遞歸算法改寫成非遞歸算法時，通常需要使用的數(shù)據(jù)結(jié)構(gòu)為棧。 8 有n個頂點，n2-2n+2條弧的有向圖不一定是強連通圖。 9 某二叉樹的中根遍歷序列得到的關(guān)鍵字序列是遞增有序的，則該二叉樹一定是二叉排序樹。10快速排序方法的每一趟都能找到一個元素把它放到最終的位置上。 得分評卷人四、存儲結(jié)構(gòu)圖(要求標(biāo)明各結(jié)點的數(shù)據(jù)域、指針域、權(quán)值等，每小題6分，共12分)1 如下圖所示為二叉樹排序樹T的一種線索二叉樹邏輯結(jié)構(gòu)圖，試畫出插入結(jié)點48后的線索二叉樹的物理存儲結(jié)構(gòu)圖。 2 試畫出如下圖所示無向網(wǎng)的鄰接多重表存儲結(jié)構(gòu)圖。得分評卷人五、求解問題(每小題8分，共32分)1 如下圖所示為n行2n-1列矩陣A1

7、.n，1.2n-1，現(xiàn)以行為主序進(jìn)行壓縮存儲到一維數(shù)組SA1m中。（1）試問m值是什么？（2）假定非零元素Ai，j保存在SAk中，試寫出由下標(biāo)(i，j)到k的轉(zhuǎn)換公式。2如下圖所示為有序表（10，15，21，33，44，60，67，68，70，86）的判定樹，試問該判定樹是否正確？如果正確，說明理由，錯誤則指出錯誤處并給出正確結(jié)果。3試用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序樹T,(1)按步驟畫出該平衡二叉排序樹T,(2)寫出平衡二叉排序樹T的中序遍歷序列,(3)假定每個元素的查找概率相等,計算查找成功時的平均查找長度。4已知圖的鄰接表法存儲結(jié)構(gòu)如下，從頂點A出

8、發(fā)求圖的深度遍歷的結(jié)果。得分評卷人六、證明題(每小題5分，共10分)1， 證明在哈夫曼樹中最小權(quán)值所對應(yīng)的葉結(jié)點的層數(shù)正好是哈夫曼樹的高度。2證明有n個結(jié)點的完全二叉樹的高度為élog2(n+1)ù。得分評卷人七、編程題(6分)根據(jù)二叉樹的先根和中根遍歷序列，試編寫函數(shù)CreateBiTree構(gòu)造該二叉樹。相關(guān)說明如下：typedef struct node ElemType data; struct node *lchild,*rchild; NODE,*bitTree;bitTree CreateBiTree(ElemType X，ElemType Y，int n); /*要實現(xiàn)的函數(shù)原型說明,其中X、Y分別表示n個結(jié)點的二叉樹的先根和中根遍歷序列*/得分評卷人八、閱讀并改進(jìn)算法(每小題5分，共10分)#define N 10void main() int aN =1,4,5,6, 8,10,11,13,15,20 , bN,i,j,k; scanf（”%d”,&k）;for(i=0;i<N;i+)bN-i-1=k-ai;i=j=0;while(i<N && j<N)if (ai=bj)break;else if (ai<bj) i+; else j+;if (i>=N |j>=N