一單項選擇(每空 分共分)
若某線性表中最常用的操作是在最後一個元素之前插入和刪除元素則采用___________最節省運算時間
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
