試題五北京郵電大學1992年碩士研究生入學考試試題-Read(20211109203306)

1、試 5田試題五 北京郵電大學1992年碩士研究生入學考試試題一.答復以下問題：1 利用兩個棧sl,s2模擬一個隊列時，如何用棧的運算實現(xiàn)隊列的插入，刪除以及判隊空 運算。請簡述這些運算的算法思想。2現(xiàn)有n*n階對角矩陣 M非零元素集中在以主對角線為中心的帶狀區(qū)域，其示意圖如圖1所示。試問:(1) 該對角矩陣有多少非零元素 ？帶狀區(qū)域的非零 mi的下標i , j與a之 間有何關系？試題5圖13.設T是一棵二叉樹，除葉子結點外，其 它結點的度數(shù)皆為2，假設T中有6個葉結點，試問：(1) T樹的最大深度 Kmax=?最小可能深度 Kmi n=?(2) T樹中共有多少非葉結點？(3) 假設葉結點的權值

2、分別為1, 2, 3, 4, 5, 6。請構造一棵哈曼夫樹，并計算該哈曼夫樹的權路徑長度wpl。、圖2中兩線性表A和B分別表示兩個集合。兩表中的元素皆為遞增有序。請寫一算法表養(yǎng)站點 data MX.E.釦-表頭結點 data rwatt述輛52；*A夜b.-求A和B的并集AUB要求該集合中的元素仍保持遞增有序。且要利用A和B的原有結點空間。(15分)三、寫出以下各題的結果：(25分)1 用無回溯法的模式匹配法 (KMP法)及快速的無回溯的模式匹配法求模式串T的nextj值，添入下面表中：j1 2 3 4 5 6 7ta a b b a a bKmp法求得的 n extj值快速無回溯法求 得的n

3、extj 值2 .廣義表L=(a),(b),(c),d)，試利用head和tail運算把原子項c從L中別離出來。3 .現(xiàn)有一組關鍵字序列為(13,29,23,44,55,87,25,21,10,79) 。利用除留余數(shù)法(即H(key) = key MOD p)構造哈希表，并用線性探測再散列的方法解決沖突。設P=15,填裝因子a=0.7(1) 畫出構造出的哈希表。(2) 求在查找此哈希表的元素時，在等概率的情況下，查找成功的平均查找長度ASL=?4 寫出圖3雙鏈表中對換值為23和l5的兩個結點相互位置時修改指針的有關語句。llink15-30dutn rlink試1 Sffl 3-四、二叉樹的中序遍歷序列為GFBEANH，后序遍歷的結點序列為GEBFHNMA20 分1畫出此二叉樹的形態(tài)。2寫出根據二叉樹的中序和后序遍歷的結點序列，建立它的二叉鏈表存儲結構的遞歸 算法。五、某工程的 AOE網絡如圖4所示。15分圖中弧上的權值分別為aiaio的t個活動的期限。1. 畫出該AOE網絡的十字鏈表存儲結構。2. 求各事件的最早發(fā)生時間ve和最遲發(fā)生時間vl，以及各項活動的最早開始時間e和最遲開始時間I.填于下面表中。事件vevl活動eI1a12a23as4a45as6a6a7a8a9a1o3. 完成該項工程