大學課件--上海交大計算機電子-數(shù)據(jù)結(jié)構(gòu)九七.doc

本文檔由標準美女（標準王國）整理，僅作學習交流使用。如文檔存在缺頁、字跡模糊、亂碼等情況，請大家通過論壇消息與我聯(lián)系。 上海交通大學一九九七年碩士研究生入學考試試題 試題名稱：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計技術(shù) 試題編號：題一（分）有五個數(shù)依次進棧：1,2,3,4,5.在各種出棧的序列中，以3,4先出的序列有哪幾個。（在之前出棧）題二（分）試寫出進棧操作，出棧操作算法的時間復雜性。題三（分）已知串匹配算法的模式串是AABBAAB,試寫出改進后的NEXT信息幀。題四（分）設(shè)某通信電文由、六個字符組成，它們在電文中出現(xiàn)的次數(shù)分別是16,5,9,3,20,1。試畫出編碼用的哈夫曼樹。題五（分）已知某排序平衡二叉樹具有下列特點：（）結(jié)點的關(guān)鍵字均在1到9范圍內(nèi)；（）在中存在一個關(guān)鍵字為n1的葉結(jié)點，若刪去該結(jié)點，立即插入一個關(guān)鍵字為n1的結(jié)點，得到的平衡樹與原不相同；（）在中存在另一個關(guān)鍵字為n2的非葉結(jié)點，刪去它，并立即插入n2結(jié)點，得到與原相同的平衡樹；（）在中插入某n3結(jié)點后立即刪除它，得到的平衡樹與原不相同。試畫出具有上述特點的最簡單（結(jié)點個數(shù)最少）的平衡樹，并寫明n1,n2,n3分別等于幾？題六（分）某整型數(shù)組的個元素值依次為6,2,9,7,3,8,4,5,0,1,用下列各排序方法，將中元素由小到大排序。（1）取第一個元素值作為分割數(shù)，（2）試寫出快速排序第一次分隔后中的結(jié)果。（3）用堆排序，（4）試寫出將第一個選出的數(shù)據(jù)放在的最后位置上，（5）將調(diào)整成堆后的中結(jié)果。（6）用基數(shù)為的基數(shù)排序法，（7）試寫出第一次分配和收集后中的結(jié)果。題七（分）某賦權(quán)有向圖及它的單鄰接表如下：（1）試寫出深度優(yōu)先搜索順序。（2）畫出深度優(yōu)先生成樹。（3）將該圖作為網(wǎng)絡(luò)圖，（4）試寫出的最早發(fā)生時間及活動的最晚開始時間。（5）用Dijkstra算法計算源點到各頂點的最短路徑，（6）試寫出當計算出及的最短路徑時，（7）到其它各點路徑（中間結(jié)點）的值。 始點 1 2 3 3 2 1 2 1 3 1 5 終點 請在下列各題的 （N） 處，填寫適當?shù)腜ascal語句（或其它成份），完成各題的程序。題八（分）下列程序輸入一個正整數(shù)N(n10)，打印1,2,.,n各數(shù)字的全排列，例如輸入n=3,打印123,132,213,231,312,321program exam8(input,output); const maxn=9; var a:array1.maxn of integer;放全排序一個值 s:set of 1.maxn;放到各數(shù)字的集合 n:integer procedure load(j:integer);將中數(shù)字裝入到a中 var j,k integer; begin for j:=1 to n do if j in s then begin s:= (1) ai:=j; if in then (2) else for k:=1 to n do writen(ak); (3) endendload;begin main readln(n); s:=1.n; load(1)end.題九（分）下面的過程對二叉樹進行后序遍歷（非遞歸）。假設(shè)已有棧的一些操作過程說明。并說明樹的結(jié)點類型： type pointer= node; node=record data:integer ; left,right :pointer end; procedure post(p:pointer); var q:pointer; begin if p then begin create_stack(s);建立一個棧，并初始化為空棧 while (Pnil) or not empty_stack(s)s棧不空 do if pnil then begin push(s,p); 將進棧 push(s,p);P作為標記進棧 P:= （） end else begin pop(s,p);將標記退出棧退出到中 if pnil then begin push(s,nil)標記進棧 （） ； end else begin （3） ； write(q .data);訪問結(jié)點，打印結(jié)點數(shù)據(jù) end end endpost 題十（分）設(shè)結(jié)點的類型定義如下： type node=record data:integer; link:integer end; 在數(shù)組a中存放了個 結(jié)點： var a:array1.10 of node; 假定在主程序中已經(jīng)執(zhí)行了下列語句： for i:=1 to 10 do begin ai.data:=i, ai.link:=0 end; 最初將個結(jié)點看成分別屬于個集合，每個集合有且僅有一個結(jié)點，調(diào)用下面過程，判斷data=m和data=n的兩個結(jié)點是否在同一個集合中（最初肯定屬于不同集合，除非m=n），若不在同一集合中，則將這兩個結(jié)點合并到一個集合中。否則，已在同一個集合中，什么也不做。（此方法用于Kruskal求最小生成樹的算法中） procedure merge_set(m,n:integer); function find(k:integer):integer; var f:integer; begin f:=k; while ak.link0 do f:=ak.link; (1) ; end; begin m:=find(m); n:=frind(n); if mn then (2) endmerge_set題十一（分）設(shè)有數(shù)組變量說明： var a:array1.n of record key:integer; next:0.n end; 假設(shè)各元素的key已有值，并且假設(shè)最大值，再假定在主程序已執(zhí)行下面語句，已將各元素組成一個鏈；for i:= to n-1 do ai.next:=i+1; ai:= 下面是以10為基的基數(shù)排序法過程，將數(shù)組a按Key由小到大排序。Procedure bucket_sorting; Const maxkey=9999; Var bucket,tail :array0.9 of 0.n; P,last:0.n; i:=0.9; d:integer;begin d:=1; repeat for i:=0 to 9 do taili:= ; 分解 P：a0.next;a0.next是鏈的第一個結(jié)點 While P do Begin i:=ap.key div d mod 10; If (1) Then bucketi:=p Else a (2) .next:=p; Taili:=p; (3) end 收集 last:=0 for i:=0 to 9 do if (4) then begin alast.next:= (5) ; last:= (6) end; alast.next:= ; d:= (7) until dmaxkey endbucket_sorting題十二（12分）下面是一個判斷二叉樹是否是排序平衡樹的函數(shù)說明，若是排序平衡樹，則返回值為真，否則返回值假，另外，以參數(shù)的形式返回二叉樹的高度和最大最小結(jié)點值。結(jié)點的類型定義與題九的定義相同。 Function isbalance(p:pointer;var h,min,max:integer) Var hleft,hright,lmax,rmin:integer; Begin If pnil then begin if osbalance(p .left,hleft, (1) ) and isbalance(P .right,hright, (2) ) then begin if hleft=0 then begin min:=p .data; lmax:=p .data-1 end; if hright=0 then begin max:=p .data; rmin=p . data+1 end; if hlefthright then h:=hleft+1 else h:=hright+1; isbalanced:=(abs(h