數(shù)據(jù)結(jié)構(gòu)網(wǎng)上教學(xué)活動文本(2006511).doc

《數(shù)據(jù)結(jié)構(gòu)網(wǎng)上教學(xué)活動文本(2006511).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)網(wǎng)上教學(xué)活動文本（2006.5.11）徐孝凱：歡迎大家積極參加計算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程網(wǎng)絡(luò)答疑活動賀桂英：徐老師，能否請您將剛考過的試題(06年1月已考)上傳給我們，供學(xué)習(xí)和復(fù)習(xí)參考!謝謝您!徐孝凱：上學(xué)期試卷供參考！中央廣播電視大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)試題（6）2004年9月題號一二三四五六總分得分一、單項選擇題，在括號內(nèi)填寫所選擇的標(biāo)號（9小題，每小題2分，共18分）1.一種抽象數(shù)據(jù)類型包括數(shù)據(jù)和()兩個部分。A.數(shù)據(jù)類型B.操作C.數(shù)據(jù)抽象D.類型說明2.在一個長度為n的順序

2、表的表尾插入一個新元素的時間復(fù)雜度為（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)3.已知L是帶表頭附加結(jié)點的單鏈表,刪除第一個結(jié)點的語句是（）。A.L=L->link;B.L->link=L->link->link;C.L=L;D.L->link=L;4.下列廣義表中的線性表是（）。A．E(a,(b,c))B．E(a,E)C．E(a,b)D．E(a,())5.在一棵樹的左子女-右兄弟表示法中，一個結(jié)點的右子女是該結(jié)點的()結(jié)點。A.兄弟B.父子C.祖先D.子孫6.向一棵AVL樹插入元素

3、時，可能引起對最小不平衡子樹的雙向旋轉(zhuǎn)的調(diào)整過程，此時需要修改相關(guān)()個指針域的值。A.2B.3C.4D.57.在一個有向圖的鄰接矩陣表示中，刪除一條邊需要的時間復(fù)雜度為()。A．O(1)B．O(i)C．O(j)D．O(i+j)8.在一棵高度為h的B樹中，插入一個新關(guān)鍵碼時，為搜索插入位置需讀?。ǎ﹤€結(jié)點。A.h-1B.hC.h+1D.h+29.對存儲有n個元素的長度為m的散列表進(jìn)行搜索，平均搜索長度與（）有關(guān)。A.nB.mC.n/mD.n*m二、填空題，在橫線處填寫合適內(nèi)容（12小題，每小

4、題1分，共12分）1.抽象數(shù)據(jù)類型的特點是________、信息隱蔽、使用與實現(xiàn)分離。2.利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個三元組元素對應(yīng)一個非零元素的行號、列號和_________。3.在單鏈表中邏輯上相鄰的結(jié)點而在物理位置上_______相鄰。4.向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點時，首先把棧頂指針的值賦給新結(jié)點的指針域，然后把新結(jié)點的存儲位置賦給________。5.迷宮問題是一個回溯控制的問題，最好使用__________的方法來解決。6.在一棵高度為3的四叉樹中，最多含有_____

5、___個結(jié)點，假定樹根結(jié)點的高度為0。7.在一個堆的順序存儲中，若一個元素的下標(biāo)為i(0≤i≤n-1)，則它的右子女元素的下標(biāo)為________。8.根據(jù)一組記錄(56,42,73,50,48,22)依次插入結(jié)點生成一棵AVL樹時，當(dāng)插入到值為_______的結(jié)點時才出現(xiàn)不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整。9.在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時，只有當(dāng)一條候選邊的兩個端點不在同一個________上，才會被加入到生成樹中。10.在堆排序中，對n個記錄建立初始堆需要調(diào)用__________次調(diào)整算法。

6、11.在對n個數(shù)據(jù)對象的二路歸并排序中，每趟歸并的時間復(fù)雜度為____________。12.在一棵m階B樹上，每個非根結(jié)點的關(guān)鍵碼數(shù)最少為__________個。三、判斷題，在每小題前面打?qū)μ柋硎菊_或打叉號表示錯誤（10小題，每小題1分，共10分）1.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。2.若每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素,則稱這種隊列為優(yōu)先級隊列。3.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常不需要用遞歸的算法來實現(xiàn)對它的操作。4.當(dāng)從一個最小堆中刪除一個元素時，需要把堆

7、尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。5.對于一棵具有n個結(jié)點，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為O(n)。6.對于同一組記錄，生成二叉搜索樹的形態(tài)與插入記錄的次序無關(guān)。7.在每個AOE網(wǎng)絡(luò)中只有一條關(guān)鍵路徑。8.圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。9.裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度。10.在一棵B樹中，所有葉結(jié)點都處在同一層上，所有葉結(jié)點中空指針數(shù)等于所有關(guān)鍵碼的總數(shù)加1。四、運算題（5小題，

8、每小題6分，共30分）1.假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進(jìn)行中序、后序、按層遍歷的結(jié)果。中序：后序：按層：2.一個一維數(shù)組a[10]中存儲著有序表(15,26,34,39,45,56,58,63,74,76)，根據(jù)折半搜索所對應(yīng)的判定樹，寫出該判定樹中度為1的結(jié)點個數(shù)，并求出在等概率情況下進(jìn)行成功搜索時的平均搜索長度。度為1的結(jié)點個數(shù)：平均搜索長度：3.假定一個線性序列為(38,42,55