1、1 北京工業大學1999 年碩士研究生入學考試試題考試科目：數據結構一、 （26 分）填空、選擇（一個或多個）題，1-6 題每小題 2 分：1 下面的敘述中，不正確的是（）a 關鍵活動不按期完成就會影響整個工程的完工時間。b 任何一個關鍵工程提前完成，將使整個工程提前完成。c 所有關鍵活動都提前完成，則使整個工程提前完成。d 提些關鍵活動若提前完成，則將使整個工程提前完成。2 下面的排序算法中，不穩定得是（） a 起泡排序 b 折半插入排序c 簡單選擇排序d 希爾排序e 基數排序f堆排序。3 包含結點a，b，c 的二叉樹有 - 種不同的狀態，- 種不同的二叉樹。4 包含結點a，b，c 的樹有

2、- 種不同形態，- 種不同的樹。5 分塊檢索中， 若索引表和各塊內存均用順序查找，則有 900 各元素的線性表分成- 塊最好：若分成 25 塊；其平均查找長度為- 。6 下面的程序段中，對的賦值語句的頻度為- （表示為n 的函數） ： ： ： ：；（分）設有字符序列 要求按字符升列排序：采用初是長為的希爾（）排序，一趟掃描的結果是 采用以元素為分界元素的快速排序，一躺掃描的結果是- 。8（6 分）已知廣義表：a-（0） ，b-（） ， c-（a，b，c，d） ，d-（a，b，c）它們的存儲結構圖為（接兩種結構種的任一種即可）：二（ 6 分）編寫遞歸程序將二叉樹逆時針旋轉90 度打印出來。如右圖

3、： （要求用類pascal 語言，并描述結構） 。2 三 （8 分）用依次輸入的關鍵字13，29，41，19，5，1，7 和 6 建一棵三階b-樹，畫出建該樹的變化過程示意圖（每插入一個結點至少用一張圖）。四（共 20 分）已知頂點1 6 和輸入邊與權值的序列（如右框中）：2 4 6 每行三個數表示一條邊的兩個端點和其權值，共11 行。2 3 2 請你：1（8 分）采用鄰接多重表表示該無向網，用類pascal 語言描述該數據結構，畫出存儲結構示意圖，要求符和在邊結點鏈表頭部插入的算法和輸入序列的次序。3 4 4 3 6 10 2（4 分）分別寫出從頂點1 出發的深度優先和廣度優先遍歷頂點序列，

4、以及相應的生成樹。4 5 7 3（8 分）按 prim 算法列表計算，從頂點1 始求最小生成樹，并圖示該樹。5 6 151 2 5 1 3 8 1 4 3 3 5 1 4 6 11 五（ 12 分）下面函數的功能是在一個按訪問頻度不增有序的，帶頭結點的雙向鏈環上檢索關鍵值為x 的結點，對該結點訪問頻度計數，并維護該鏈環有序。若為找到，則插入該結點。所有結點的頻度域初值在建表時都為零。請將程序中四處空缺補寫完整。type link=node node=record key:char; freq:integer; pre,next:link; end; var l:link; function l

5、oc(l:link;x:char):link; var p,q:link; begin p:=l.next; while p.keyx do p:=p.next; if p=1 then new(q);q.key:=x;q.freq:=0 else p.freq:=p.freq+1;q:=p; while q.freqp.pre.freq do p:=p.pre; if pq then if then q.next:=p,q.pre;=p.pre;p.pre.next:=q; p.pre:=q retuen(q); end; 六（ 8 分）置換選擇排序得到初始歸并段長（k 個節數）為37，34，300，41，70，120， 35，3 4 43 該圖示這些磁盤文件進行歸并所用的4 階最佳歸并樹，算出歸并的總讀寫字節段，每讀寫1 字節計為1。七（ 10 分）樹形選擇排序通常采用順序存儲結構（1）試指出n 個元素的原始序列一般如何在該存儲結構中存數（起始存儲位置，次序），請說明理由。 （2）討論樹形選擇排序的穩定性。若穩定，須說明理由；不穩定，須舉反例，并嘗試找出使它穩定的方法。八（ 10 分）已知一棵以線索鏈表為存儲結構的中序全線索二叉樹t，試在該二叉樹上求任意結點 x 的前序前趨。敘述思路并編寫算法