福建師范《數(shù)據(jù)結(jié)構(gòu)概論》作業(yè)答案

福建師范大學(xué)試卷紙第1頁共7頁福建師范大學(xué)試卷紙第1頁共7頁福建師范大學(xué)試卷紙第1頁共7頁福建師范大學(xué)試卷紙第1頁共7頁數(shù)據(jù)結(jié)構(gòu)概論期末考核試卷一、單項選擇題（每小題2分，共30分）.下列編碼中屬前綴碼的是（A）A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次進(jìn)棧，一個元素退棧后即進(jìn)入隊列Q，若6個元素的出隊的序列是b,d,c,f,e,a，則棧S的容量至少應(yīng)當(dāng)是（C）A.6B.4C.3D.2.在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復(fù)雜度是（B）A.O⑴B.O（n）C.O（nlogn）D.O（n2）.要表示省，市，區(qū)，街道的有關(guān)數(shù)據(jù)及其關(guān)系，選擇（D）比較合適。A.線性結(jié)構(gòu)B.樹結(jié)構(gòu)C.圖結(jié)構(gòu)D.集合結(jié)構(gòu).鏈棧與順序棧相比，比較明顯的優(yōu)點是（D）A.插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況.二叉樹中第5層上的結(jié)點個數(shù)最多為（C）A.8B.15C.16D.32.在表長為n的鏈表中進(jìn)行線性查找，查找成功時，它的平均查找長度為（B）A.ASL;nB.ASL=（n+1）/2C.ASL="n+1D.ASL心log2（n+1）-1.對22個記錄的有序表進(jìn)行折半查找，當(dāng)查找失敗時，至少需要比較（C）次關(guān)鍵字。A.3B.4C.5D.6.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是（A）福建師范大學(xué)試卷紙第福建師范大學(xué)試卷紙第頁共7頁該二叉狗是af\bd/Ice/\f9h先序遍歷是：abcdefgh5.已知閉散列表的長度為10(散列地址空間為0..9),散列函數(shù)為H(K)=K%8,采用線性重新散列技術(shù)解決沖突，將下列一組數(shù)據(jù)｛25,17,39,47,83,55,99,34｝依次插入到散列表中，請畫出散列表。TOC\o"1-5"\h\z⑴H(25)=1H(16)=0⑶H(38)=6H(47)=7H(79)=7與(4)沖突，于是線性重新散列即查找7后面的空槽，此時8為空，因此將79放入(第九個位置)中H(82)=2H(51)=3H(39)=7與(4)沖突，于是線性重新散列即查找7后面的空槽，此時8已經(jīng)有元素(5),9為空，因此將39放入9(第十個位置)中,所以最終閉散列表的存儲情況如下所示：位置：(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)值：16258251空空38477939。四、算法閱讀、設(shè)計(共5分)1閱讀下列函數(shù)algo,并回答問題：(5分)voidalgo(Queue*Q)｛StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}⑴假設(shè)隊列q中的元素為(2,4,5,7,8)，其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；(2)簡述算法algo的功能。答：(1)87542(2)隊列倒置五、程序設(shè)計題(共10分)1、已知r□為一維數(shù)組，其中r[0]到r[n-1]為待排序的n個元素，排序好的元素仍放在r[0]到r[n-1]中，請寫出對該數(shù)組進(jìn)行非遞歸的直接插入排序算法，取名為insertsort(elemtyper[],intn)。(10分)voidTii5t?rtSort^tliJintj,p&r