數(shù)據(jù)結(jié)構(gòu)本科A.doc

數(shù)據(jù)結(jié)構(gòu)試題3武漢大學計算機學院 “數(shù)據(jù)結(jié)構(gòu)”考試試題（A）要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。一、單項選擇題（共20小題，每小題2分，共40分）1. 下列各選項中屬于邏輯結(jié)構(gòu)的是 。A.哈希表B.有序表C.單鏈表D.順序表2. 對于數(shù)據(jù)結(jié)構(gòu)，以下敘述中不正確的是 。A.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無關(guān)B.數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系C.數(shù)據(jù)元素是數(shù)據(jù)的基本單位D.數(shù)據(jù)項是數(shù)據(jù)的最小單位3. 某算法的時間復雜度為O(n2)，表明該算法的 。A.問題規(guī)模是n2B.執(zhí)行時間等于n2C.執(zhí)行時間與n2成正比D.問題規(guī)模與n2成正比4. 通常在單鏈表中增加一個頭節(jié)點，其目的是為了 。A.使單鏈表至少有一個節(jié)點B.標識表節(jié)點中首節(jié)點的位置C.方便單鏈表運算的實現(xiàn)D.說明單鏈表是線性表的鏈式存儲5. 刪除某個雙鏈表中的一個節(jié)點（非首、尾節(jié)點），需要修改 個指針域。A.1B.2C.3D.46. 棧和隊列是兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們中的元素具有相同的 。A.抽象數(shù)據(jù)類型B.邏輯結(jié)構(gòu)C.存儲結(jié)構(gòu)D.運算7. 元素a、b、c、d、e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有的元素都出棧，則所有可能的出棧序列中，以元素d開頭的序列個數(shù)是 。A.3B.4C.5D.68. 設(shè)環(huán)形隊列中數(shù)組的下標是0N-1，其頭尾指針分別為f和r（f指向隊列中隊頭元素的前一個位置，r指向隊尾元素的位置），則其元素個數(shù)為 。A.r-fB.r-f-1C.(r-f)N+1D.(r-f+N)N9. 已知循環(huán)隊列存儲在一維數(shù)組A0.n-1中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列空，且要求第一個進入隊列的元素存儲在A0處，則初始時front和rear的值分別是 。A.0，0B.0，n-1C.n-1，0D.n-1，n-110. 對于n階（n2）對稱矩陣，采用壓縮方法以行序優(yōu)先存放到內(nèi)存中，則需要 個存儲單元。A.n(n+1)/2B.n(n-1)/2C.n2D.n2/211. 一棵度為4的樹T中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則樹T的葉子節(jié)點個數(shù)是 。A.41B.82C.113D.12212. 一個具有n（n2）個頂點的無向圖，至少有 個連通分量，最多有 個連通分量。A.0B.1C.n-1D.n13. 含有n（n2）個頂點的無向圖的鄰接矩陣必然是一個 。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣14. 對如圖1所示的無向圖，從頂點A出發(fā)得到的廣度優(yōu)先序列可能是 。A.ABECDB.ACBDEC.ACDBED.ABDEC圖1 一個無向圖15. 設(shè)有100個元素的有序順序表，用折半查找時，成功時最大的比較次數(shù)是 。A.25B.50C.10D.716. 已知一個長度為16的順序表，其元素按關(guān)鍵字有序排序，若采用折半查找法查找一個不存在的元素，則平均關(guān)鍵字比較的次數(shù)是 。A.70/17B.70/16C.60/17D.60/1617. 以下關(guān)于m階B-樹的敘述中正確的是 。A.每個節(jié)點至少有兩棵非空子樹B.樹中每個節(jié)點至多有m/2-1個關(guān)鍵字C.所有葉子節(jié)點均在同一層上D.當插入一個關(guān)鍵字引起B(yǎng)-樹節(jié)點分裂時，樹增高一層18. 為提高散列（哈希）表的查找效率，可以采取的正確措施是 。.增大裝填（載）因子.設(shè)計沖突（碰撞）少的散列函數(shù).處理沖突（碰撞）時避免產(chǎn)生聚集（堆積）現(xiàn)象A.僅B.僅C.僅、D.僅、19. 數(shù)據(jù)序列8,9,10,4,5,6,20,1,2只能是 的兩趟排序后的結(jié)果。A.簡單選擇排序B.冒泡排序C.直接插入排序D.堆排序20. 用某種排序方法對順序表24,88,21,48,15,27,69,35,20進行排序，各趟元素序列的變化情況如下：（1）24,88,21,48,15,27,69,35,20（2）20,15,21,24,48,27,69,35,88（3）15,20,21,24,35,27,48,69,88（4）15,20,21,24,27,35,48,69,88則所采用的排序方法是 。A.快速排序B.簡單選擇排序C.直接插入排序D.歸并排序二、問答題（共3小題，每小題10分，共30分）1. 一棵二叉排序樹按先序遍歷得到的關(guān)鍵字序列為：(50,38,30,45,40,48,70,60,75,80)?；卮鹨韵聠栴}： （1）畫出該二叉排序樹。（2）求在等概率條件下的查找成功的平均查找長度。2. 有一個無向帶權(quán)圖如圖2所示，采用Dijkstra算法求頂點0到其他頂點的最短路徑和最短路徑長度，要求給出求解過程（即給出求最短路徑中各步驟的S、dist和path值）。圖2 一個無向圖3. 簡要敘述堆和二叉排序樹的區(qū)別，并給出關(guān)鍵字序列3,26,12,61,38,40,97,75,53,87調(diào)整為大根堆后的結(jié)果（直接畫出調(diào)整后的大根堆）。三、算法設(shè)計題（共3小題，每小題10分，共30分）1有一個線性表(a1,a2,an)，采用帶頭節(jié)點的單鏈表L存儲，設(shè)計一個就地算法將其所有元素逆置。所謂就地算法是指算法的空間復雜度為O(1)。2假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)