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

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。22040分)分，共一、單項選擇題(每小題小題，共計1.某算法的空間復(fù)雜度為0(1)，則A.該算法執(zhí)行不需要任何輔助空間B.該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C.該算法執(zhí)行不需要任何空間D.該算法執(zhí)行所需全部空間大小與問題規(guī)模n無關(guān)2.在長度為n的順序表中插入個元素，對應(yīng)算法的時間復(fù)雜度為2)D.O(nC.O(n)A.O(l)B.O(logn)23.設(shè)線性表中有n個元素，以下運算中，在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。A.刪除指定位置元素的后一個元素B.在最后個元素的后面插入個新元素C.順序輸

2、出前k個元素D.交換第i個元素和第n-i+1個元素的值(i=l,2,n)4 .以下數(shù)據(jù)結(jié)構(gòu)中元素之間為非線性關(guān)系的是oA.棧B.隊列C.線性表D,以上都不是5 .若個棧用數(shù)組dataL.n存儲，初始棧頂指針top為n+1,則以下元素x進(jìn)棧的正確操作是。A.top+;datatop=x;B.datatop=x;top+;C.top-;data(top=x;D.datatop=x;top-;6 .若某循環(huán)隊列有隊首指針front和隊尾指針rear,在隊不滿時進(jìn)隊操作僅會改變。A.frontB.rearC.front和rearD.以上都不隊7 .設(shè)循環(huán)隊列中數(shù)組的下標(biāo)是。N-1,其隊頭、隊尾指針分別

3、為f和r(f指向隊首元素的前位置，r指向隊尾元素)，則其元素個數(shù)為0A.r-fB.r-f-1C.(r-f)%N+lD.(r-f+N)%N8 .設(shè)樹T的度為4,其中度為1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1,則T中的葉/結(jié)點個數(shù)是。A.5B.6C.7D.89 .一棵哈夫曼樹中共有199個結(jié)點，它用于多少個字符的編碼oA.99B.100C.101D.199,將森林d、c、b、a棵樹的結(jié)點個數(shù)分別為4、3、2、1棵樹，第4中有F設(shè)森林10.F轉(zhuǎn)換為顆二叉樹B,則二叉樹B根結(jié)點的左子樹上的結(jié)點個數(shù)是0A.a-1B.aC.a+b+cD.b+c+d11.下列關(guān)于圖的敘述中，正確的是I.回路是簡單路徑

4、H.存儲稀疏圖，用鄰接矩陣比鄰接及更省空間H1.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅IIB.僅I、IIC,僅川D.僅I、HIo12.以下關(guān)于有向圖的說法中，正確的是A.強(qiáng)連通圖是任何頂點到其他所有頂點都有邊完全有向圖定是強(qiáng)連通圖B.有向圖中任頂點的入度等于出度C,有向圖邊集的廣集和頂點集的廣集可構(gòu)成原有向圖的夕圖D.o13.無向圖的鄰接矩陣是一個D.對角矩陣零矩陣C.上三角矩陣A.對稱矩陣B.14.如果從無向圖的任頂點出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點，則該圖一定是。A.完全圖B.連通圖C.有回路D.一棵樹15 .用Dijkstra算法求個帶權(quán)有向圖G中從頂點。出發(fā)的最短路徑，

5、在算法執(zhí)行的某時刻，S=0,2,3,4,下一步選取的目標(biāo)頂點可能是。A.頂點2B.頂點3C.頂點4D.頂點716 .哈希表中出現(xiàn)沖突是指。A,兩個元素具有相同的序號17 兩個元素的關(guān)鍵字不同，而其他屬性相同C.數(shù)據(jù)元素過多D,兩個元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值（存儲地址）相同18 .適合于折半查找的數(shù)據(jù)組織方式是A,以鏈及存儲的線性表B.以順序表存儲的任意線性表C.以鏈表存儲的有序線性及D,以順序及存儲的有序線性衣19 .對有n個記錄的表進(jìn)行直接插入排序，在最好情況下需比較次關(guān)鍵字。A.n-1B.n+1C.n/2D.n（n-l）/220 .若數(shù)據(jù)元素序列11,12,15,7,8,9,23

6、,1,5是采用下列排序方法之得到的第二趟排序后的結(jié)果,則該排序算法只能是A.冒泡排序B.直接插入排序C.選擇排序D.二路歸并排序21 .對組數(shù)據(jù)（25,84,21,47,15,27,68,35,20）進(jìn)行排序，前3趟的排序結(jié)果如下：1第848484,35,68,27,47,25,21,15,20趟：第2趟：15,20,21,25,35,27,47,68,第3趟：15,20,21,25,27,35,47,68,則所采用的排序方法是oA簡單選擇排序B,希爾排序C,二路歸并排序D.快速排序435分）小題，共計二、問答題（共1.（10分）對于如圖1所示的帶權(quán)無向圖，直接給出利用普里姆算法（從頂點0開始

7、構(gòu)造）和克魯斯卡爾算法構(gòu)造出的最小生成樹的結(jié)果（注意：按求解的順序給出最小生成樹的所有邊，每條邊用（i，j）表示）。1713454206583G1一個帶權(quán)無向圖圖2.（10分）假設(shè)棵二叉排序樹的關(guān)鍵字為單個字母，其后序遍歷序列為ACDBFIJHGE,回答以下問題：（1）畫出該二叉排序樹。（6分）（2）求在等概率下的查找成功的平均查找長度。（2分）（3）求在等概率下的查找不成功的平均查找長度。（2分）3（8分）已如序列15,5,16,2,25,8,20,9,18,12,給出采用二路歸并排序法對該序列作升序排序時的每一趟的結(jié)果。4. （7分）簡要回答下列關(guān)于堆排序中堆的些問題：（1）通常堆采用順序

8、還是鏈?zhǔn)酱鎯Y(jié)構(gòu)？（3分）)儂(3)ASL=(6X3+3X4+2X5)/11=40/11=3.64.(2分)不出3.(8分)答案：分)2(每趟所示。3采用二路歸并排序法排序的各趟結(jié)果如圖排序:15,5,16,2,25,8,20,9,18,12length:515,2,16,8,25,9,20,12.18length=2:2,5,15,16,8,9,20,25,12,ISlength=1:2,5,8,9,15,16,20,25,12,ISlength=S:2,5,8,9,12,15,16,18,20,25排序:2,5,8,9,12,15,16,18,20f253各趟排序結(jié)果圖4,（7分）答案：（

9、1）通常堆采用順序存儲結(jié)構(gòu)。（3分）（2）小根堆中具有最大關(guān)鍵字的結(jié)點只可能出現(xiàn)在葉夕結(jié)點中。因為最小堆的最小關(guān)鍵字的結(jié)點必是根結(jié)點，而最大關(guān)鍵字的結(jié)點由偏序關(guān)系可知，只有葉子結(jié)點可能是最大關(guān)鍵字的結(jié)點。（4分）225分）三、算法設(shè)計題（共小題，共計L（1。分）答案：voidMove(UnkNode*&L)(LinkNode*p=L-next/pre=L；跳過小于0的站點while(p!=NULL&p-datanext；)while(p!=NULL)if(p-datanext=p-next；p-next=L-next；/4*p結(jié)點插入到頭結(jié)點之后L-next=p；指向*pre之后結(jié)點,不變prepp=prenext；結(jié)點值不小于elseXiH*pOPre=p；同步后移一個結(jié)點(p/pre、p=p-next；)2.(15分)答案：(7分)BTNodeFindx(BTNode*,由#x)在二叉樹b中查找x結(jié)點BTNode*p；if(b=NULL)returnNULL；elseif(b-data=x)returnb；p=Findx(b-lchild/x)；if(p!=NULL)returnp；returnFindx(b-rchild,x)；)算法的時間復(fù)雜度為0(n)(1分)。(2)(7分)voidSons(BTNode*b,charx)輸出x結(jié)點的子孫，初始時b指向x結(jié)點if(b!=