《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期末考試試卷試題及答案一、簡(jiǎn)答題（每題5分，共20分）1、一棵有n個(gè)結(jié)點(diǎn)的k叉樹采用k叉鏈表存儲(chǔ)，空鏈域的總數(shù)目是多少？寫出求解過程。2、在圖的遍歷中，設(shè)置訪問標(biāo)志數(shù)組的作用是什么？3、折半查找的前提條件是什么？4、分析冒泡排序的最好性能和最壞性能（性能即關(guān)鍵字比較次數(shù)和移動(dòng)元素的次數(shù)）。二、單項(xiàng)選擇題（每題1分，共10分） 1、棧和隊(duì)列的共同特點(diǎn)是( )。 A）只允許在端點(diǎn)處插入和刪除元素 B）都是先進(jìn)后出 C）都是先進(jìn)先出 D）沒有共同點(diǎn) 2、 100個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲(chǔ)，從1開始按層次編號(hào)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)應(yīng)該是（ ）。 A) 100 B) 49 C) 50

2、D) 51 3、在順序存儲(chǔ)的線性表上R3上，從前向后進(jìn)行順序查找。若查找第一個(gè)元素的概率是1/2，查找第二個(gè)元素的概率是1/3，查找第三個(gè)元素的概率是1/6。則查找成功的平均查找長(zhǎng)度為（ ）。 A）7/3 B）2 C）3 D）5/3 4、在一個(gè)有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s，則所有頂點(diǎn)的入度之和為（ ） A) n-s B) n C) s D) s-1 5、設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ ）。 A) N0=N1+1 B) N0=Nl+N2 C) N0=N2+1 D) N0=2N1+l 6、設(shè)有6個(gè)結(jié)點(diǎn)的無向

3、圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。 A）5 B）6 C）7 D）87、已知單鏈表中的指針p所指的結(jié)點(diǎn)不是鏈尾結(jié)點(diǎn)，若在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)，應(yīng)執(zhí)行（ ）。 A)s-next=p; p-next=s; B) p-next=s;s-next=p; C)s-next=p-next; p=s; D) s-next=p-next;p-next=s;8、設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。 A) 第i行非0元素的個(gè)數(shù)之和 B) 第i列非0元素的個(gè)數(shù)之和 C) 第i行0元素的個(gè)數(shù)之和 D) 第i列0元素的個(gè)數(shù)之和9、排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)

4、元素的大小，逆序時(shí)就交換位置。這是（ ）排序方法的基本思想。 A）堆排序B）直接插入排序C）快速排序D）冒泡排序10、設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（ ）方法可以達(dá)到此目的。 A）快速排序 B）堆排序 C）歸并排序 D）基數(shù)排序三、填空題（每空2分，共20分）1、下面算法的時(shí)間復(fù)雜度是 。 i=1; while(i=n) i=i*2;2、設(shè)線索二叉樹中，判斷p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_。2、對(duì)任意一棵有n個(gè)結(jié)點(diǎn)的樹，這n個(gè)結(jié)點(diǎn)的度之和為 。3、Prim算法適合求解 連通網(wǎng)的最小生成樹。（填稀疏或稠密）4、關(guān)鍵路徑是從源點(diǎn)到匯

5、點(diǎn)的 路徑。5、深度為k的二叉樹中最少有 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。6、設(shè)有向圖G中有向邊的集合E=，則該圖的一種拓?fù)湫蛄袨開7、根據(jù)初始關(guān)鍵字序列(25，22，11，38，10)建立的二叉排序樹的高度為_。8、用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84則所采用的排序方法是 。四、構(gòu)造題（共30分）1、(8分) 設(shè)一棵樹T中邊的集合為(A，B)，(A，C)，(A，D

6、)，(B，E)，(C，F(xiàn))，(C，G)，要求： 用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)；（2分） 將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。（2分） 寫出該樹的先序和后序遍歷序列。（4分）2、（8分）某圖的鄰接表存儲(chǔ)結(jié)構(gòu)為圖1所示： 畫出從V1出發(fā)的深度優(yōu)先生成樹； 給出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。圖1 第四題 第2小題圖3、（8分）一個(gè)線性序列（36，13，40，63，22，6），假定采用散列函數(shù)Hash(key)=key%7來計(jì)算散列地址，將其散列存儲(chǔ)在A09中，采用線性探測(cè)再散列解決沖突。構(gòu)造哈希表，并計(jì)算等概率情況下的查找成功和不成功的平均查找長(zhǎng)度。4、（6分）欲對(duì)關(guān)鍵字36，15,13，40，

7、63，22，6從小到大排序，若采用堆排序，寫出將關(guān)鍵字序列建初堆過程。五、算法設(shè)計(jì)題（每小題10分，共20分）注：只要求給出描述算法的子函數(shù)，不需要編寫完整的實(shí)現(xiàn)程序。1、 編寫折半查找算法。（遞歸、非遞歸均可） 2、已知二叉樹采用二叉鏈表存放，該結(jié)點(diǎn)結(jié)構(gòu)為：LChilddataRChildlevel編寫算法，將二叉樹中每個(gè)結(jié)點(diǎn)所在的層次值置入相應(yīng)的level域。數(shù)據(jù)結(jié)構(gòu)期末考試試卷2參考答案一、簡(jiǎn)答題1、n個(gè)結(jié)點(diǎn)的k叉樹采用k叉鏈表存儲(chǔ)，鏈域總數(shù)為k*n，又：n=B+1,B為分支總數(shù)即非空鏈域總數(shù)，B=n-1,所以空鏈域總數(shù)為：（k-1）*n+1。2、訪問標(biāo)志數(shù)組的作用是：保證圖中的每個(gè)頂點(diǎn)

8、都被訪問到，且僅訪問一次。3、折半查找的前提條件是1）列表元素順序存儲(chǔ)；2）列表元素按關(guān)鍵字有序存儲(chǔ)；4、冒泡排序最好情況：移動(dòng)元素次數(shù)為0，關(guān)鍵字比較次數(shù)為：n-1次；冒泡排序最壞情況：移動(dòng)元素次數(shù)為3n*(n-1)/2,關(guān)鍵字比較次數(shù)為n*(n-1)/2。二、選擇題1.A2.D3.D4.C5.C6. A 7.D8.B9.D10.B三、填空題1、O（log2n）2、p-ltag= =1&p-rtag= =1 3、n-14、稠密5、最少k,最多 2k-16、1,4,2,37、高度為48、快速排序四、構(gòu)造題1.1) 該樹的孩子兄弟表示法為：（2分）2)轉(zhuǎn)化的二叉樹為:（2分）3）先序遍歷序列為：

9、ABECFGD（2分）后序遍歷序列為:EBFGCDA（2分）2. 1）此為有向圖的鄰接表表示法，該圖為：2）深度優(yōu)先搜索得到的遍歷序列為：V1，V4，V5，V6，V2，V7，V3;深度優(yōu)先生成樹為： 3）其鄰接矩陣表示法為：頂點(diǎn)數(shù)組： 鄰接矩陣：1V12V23V34V45V56V67V700011010001000000001100000000100010000000000111003、1）構(gòu)造的哈希表為：（4分）地址0123456789元素63362240136比較次數(shù)1121122）（2分）查找成功時(shí)的（）/（2分）查找不成功時(shí)的（）/4、據(jù)題意，欲得到遞增有序，需要建大根堆（1分）。建初

10、堆過程如下：五算法設(shè)計(jì)題1、折半查找算法：1）非遞歸算法：int BinSearch (RecordList L,KeyType k)low=1;high=L.length; while(lowrmid.key= =k) return mid;else if(krmid.key) high=mid-1;else low=mid+1; return 0;2)遞歸算法int BinSearch (RecordList L,KeyType k，int low,int high)/首次調(diào)用，low=1，high=L.length; if(lowrmid.key= =k) return mid;else if(krmid.key) return(BinSearch (L, k,low,mid-1);else return(BinSearch (L, k,mid+1,high);2、二叉樹中每個(gè)結(jié)點(diǎn)的level域置值算法：利用二叉樹的先序遍歷給每個(gè)結(jié)點(diǎn)的level域