熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

《數據結構》練習題

2013-11-15 15:39:06  來源: 數據結構 

  一單項選擇(每空 分)

  若某線性表中最常用的操作是在最後一個元素之前插入和刪除元素則采用___________最節省運算時間

  A單鏈表                B僅有頭指針的單循環鏈表

  C僅有尾指針的單循環鏈表        D雙鏈表

  哈夫曼樹的帶權路徑長度WPL等於___________

  A除根以外的所有結點的權植之和     B所有結點權值之和

  C各葉子結點的帶權路徑長度之和     D根結點的值

  設輸入序列為借助一個棧不可能得到的輸出序列是___________

  A              B

  C              D

  對於下面二叉樹按後序遍歷所得的結點序列為___________

  

  A               B

  C               D

  棧和隊列都是___________

  A順序存儲的線性結構 B鏈式存儲的線性結構

  C限制存儲點的線性結構 D限制存儲點的非線性結構

  已知完全二叉樹有個結點則整個二叉樹有___________個度為的結點

  A                  B

  C                  D不確定

  對下圖不能得到的拓撲序列是___________

  

  A           B

  C           D

  下列排序算法中第一趟排序完畢後其最大或最小元一定在其最終位置上的算法是___________

  A歸並排序 B直接選擇排序

  C快速排序               D基數排序

  下列排序方法中排序所花費時間不受數據初始排列特性影響的算法是___________

  A直接插入排序 B冒泡排序

  C直接選擇排序             D快速排序

  下列排序方法中最好情況下時間復雜度為O(N)的算法是___________

  A選擇排序               B歸並排序

  C快速排序               D直接插入排序

  二判斷題(每小題 分)

  ( )線性表的長度是線性表占用的存儲空間的大小

  ( )雙循環鏈表中任一結點的後繼指針均指向其邏輯後繼

  ( )隊列只能采用鏈式存儲方式

  ( )樹(或森林)轉化為對應的二叉樹後兩者的分支數相等

  ( )由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹

  ( )圖中一個頂點i的出度等於其鄰接矩陣中第i列的非元個數

  ( )在用線性探查法解決沖突所構造的閉散列表中每組同義詞中至少有一個元素的地址正好等於其散列地址

  ( )所謂沖突即是兩個關鍵字的值相同的元素其散列地址相同

  ( )對n個元素的有序表用快速排序方法進行排序時間復雜是O(n )

  ( )存在有偶數個結點的滿二叉樹

  三填空題(每空 分)

  在單鏈表中若要刪除指針P所指結點的後繼結點則需執行下列三條語句 U=P↑next;P↑next=U↑next;___________

  設有一個鏈隊列結點結構為隊尾指針為Ls(≠nil)則執行入隊操作時 S↑next=Ls↑next;___________;___________

  

  單鏈表中指針P所指結點不為尾結點的條件是___________

  設數組B[]中的任一元素均占個單元從首地址SA開始把數組B按行優先存儲 則元素B[]的地址為___________

  在有n(n>)個結點的二叉鏈表中非空鏈域的個數為___________

  深度為(根的層次號為i)的完全二叉樹至多有___________個結點

  一個具有n個頂點的連通有向圖至多有___________條邊

  一棵二叉排序樹中若存在個結點其成功的查找長度≤則有___________個結點其成功的查找長度=

  在對有個數據的有序表作二分查找時有___________個結點的查找長度是

  在完全二叉樹中編號為i的結點的左孩子結點的編號為___________

  四解答下列各題(共 分)

   以數據集{}為葉子結點的權值

  ()構造一棵哈夫曼樹 (分)

  ()計算其帶權路徑長度(分)

  已知二叉樹的先序中序和後序序列分別如下但其中有一些已模糊不清構造出該二叉樹(分)

  先序序列 _BC_EF__

  中序序列 BDE_AG_H

  後序序列 _DC_GH_A

  如圖所示

  

  ()寫出鄰接矩陣(分)

  ()求出其最小生成樹(分)

  設散列函數H(X)=K MOD 若輸入序列為 {}

  ()構造出開散列表

  ()求出在等概率查找情況下查找成功的平均查找長度

  有一個數據序列現采用堆排序算法進行排序寫出每趟的結果

  五算法設計題(共 分)

  設計一個用帶頭結點的單鏈表表示的直接插入排序算法各結點結構如圖

  

  要求用類PASCAL語言寫出算法(分)

  設二叉樹采用二叉鏈表表示各結點結構為其中data為整數型字段設計算法判別一棵二叉樹是否是二叉排序樹(分)

  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23741.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.