數(shù)據(jù)結構本科A.doc_第1頁
數(shù)據(jù)結構本科A.doc_第2頁
數(shù)據(jù)結構本科A.doc_第3頁
數(shù)據(jù)結構本科A.doc_第4頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

數(shù)據(jù)結構試題3武漢大學計算機學院 “數(shù)據(jù)結構”考試試題(A)要求:所有的題目的解答均寫在答題紙上,需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。一、單項選擇題(共20小題,每小題2分,共40分)1. 下列各選項中屬于邏輯結構的是 。A.哈希表B.有序表C.單鏈表D.順序表2. 對于數(shù)據(jù)結構,以下敘述中不正確的是 。A.數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的形式和內(nèi)容無關B.數(shù)據(jù)的邏輯結構是數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系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ù)結構,但它們中的元素具有相同的 。A.抽象數(shù)據(jù)類型B.邏輯結構C.存儲結構D.運算7. 元素a、b、c、d、e依次進入初始為空的棧中,若元素進棧后可停留、可出棧,直到所有的元素都出棧,則所有可能的出棧序列中,以元素d開頭的序列個數(shù)是 。A.3B.4C.5D.68. 設環(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. 設有100個元素的有序順序表,用折半查找時,成功時最大的比較次數(shù)是 。A.25B.50C.10D.716. 已知一個長度為16的順序表,其元素按關鍵字有序排序,若采用折半查找法查找一個不存在的元素,則平均關鍵字比較的次數(shù)是 。A.70/17B.70/16C.60/17D.60/1617. 以下關于m階B-樹的敘述中正確的是 。A.每個節(jié)點至少有兩棵非空子樹B.樹中每個節(jié)點至多有m/2-1個關鍵字C.所有葉子節(jié)點均在同一層上D.當插入一個關鍵字引起B(yǎng)-樹節(jié)點分裂時,樹增高一層18. 為提高散列(哈希)表的查找效率,可以采取的正確措施是 。.增大裝填(載)因子.設計沖突(碰撞)少的散列函數(shù).處理沖突(碰撞)時避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅B.僅C.僅、D.僅、19. 數(shù)據(jù)序列8,9,10,4,5,6,20,1,2只能是 的兩趟排序后的結果。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. 一棵二叉排序樹按先序遍歷得到的關鍵字序列為:(50,38,30,45,40,48,70,60,75,80)?;卮鹨韵聠栴}: (1)畫出該二叉排序樹。(2)求在等概率條件下的查找成功的平均查找長度。2. 有一個無向帶權圖如圖2所示,采用Dijkstra算法求頂點0到其他頂點的最短路徑和最短路徑長度,要求給出求解過程(即給出求最短路徑中各步驟的S、dist和path值)。圖2 一個無向圖3. 簡要敘述堆和二叉排序樹的區(qū)別,并給出關鍵字序列3,26,12,61,38,40,97,75,53,87調(diào)整為大根堆后的結果(直接畫出調(diào)整后的大根堆)。三、算法設計題(共3小題,每小題10分,共30分)1有一個線性表(a1,a2,an),采用帶頭節(jié)點的單鏈表L存儲,設計一個就地算法將其所有元素逆置。所謂就地算法是指算法的空間復雜度為O(1)。2假設二叉樹采用二叉鏈存儲結構,設

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論