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

本文檔由標(biāo)準(zhǔn)美女（標(biāo)準(zhǔn)王國）整理，僅作學(xué)習(xí)交流使用。如文檔存在缺頁、字跡模糊、亂碼等情況，請(qǐng)大家通過論壇消息與我聯(lián)系。 上海交通大學(xué)一九九七年碩士研究生入學(xué)考試試題 試題名稱：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)技術(shù) 試題編號(hào)：題一（分）有五個(gè)數(shù)依次進(jìn)棧：1,2,3,4,5.在各種出棧的序列中，以3,4先出的序列有哪幾個(gè)。（在之前出棧）題二（分）試寫出進(jìn)棧操作，出棧操作算法的時(shí)間復(fù)雜性。題三（分）已知串匹配算法的模式串是AABBAAB,試寫出改進(jìn)后的NEXT信息幀。題四（分）設(shè)某通信電文由、六個(gè)字符組成，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)分別是16,5,9,3,20,1。試畫出編碼用的哈夫曼樹。題五（分）已知某排序平衡二叉樹具有下列特點(diǎn)：（）結(jié)點(diǎn)的關(guān)鍵字均在1到9范圍內(nèi)；（）在中存在一個(gè)關(guān)鍵字為n1的葉結(jié)點(diǎn)，若刪去該結(jié)點(diǎn)，立即插入一個(gè)關(guān)鍵字為n1的結(jié)點(diǎn)，得到的平衡樹與原不相同；（）在中存在另一個(gè)關(guān)鍵字為n2的非葉結(jié)點(diǎn)，刪去它，并立即插入n2結(jié)點(diǎn)，得到與原相同的平衡樹；（）在中插入某n3結(jié)點(diǎn)后立即刪除它，得到的平衡樹與原不相同。試畫出具有上述特點(diǎn)的最簡單（結(jié)點(diǎn)個(gè)數(shù)最少）的平衡樹，并寫明n1,n2,n3分別等于幾？題六（分）某整型數(shù)組的個(gè)元素值依次為6,2,9,7,3,8,4,5,0,1,用下列各排序方法，將中元素由小到大排序。（1）取第一個(gè)元素值作為分割數(shù)，（2）試寫出快速排序第一次分隔后中的結(jié)果。（3）用堆排序，（4）試寫出將第一個(gè)選出的數(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ā)生時(shí)間及活動(dòng)的最晚開始時(shí)間。（5）用Dijkstra算法計(jì)算源點(diǎn)到各頂點(diǎn)的最短路徑，（6）試寫出當(dāng)計(jì)算出及的最短路徑時(shí)，（7）到其它各點(diǎn)路徑（中間結(jié)點(diǎn)）的值。 始點(diǎn) 1 2 3 3 2 1 2 1 3 1 5 終點(diǎn) 請(qǐng)?jiān)谙铝懈黝}的 （N） 處，填寫適當(dāng)?shù)腜ascal語句（或其它成份），完成各題的程序。題八（分）下列程序輸入一個(gè)正整數(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;放全排序一個(gè)值 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.題九（分）下面的過程對(duì)二叉樹進(jìn)行后序遍歷（非遞歸）。假設(shè)已有棧的一些操作過程說明。并說明樹的結(jié)點(diǎn)類型： 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);建立一個(gè)棧，并初始化為空棧 while (Pnil) or not empty_stack(s)s棧不空 do if pnil then begin push(s,p); 將進(jìn)棧 push(s,p);P作為標(biāo)記進(jìn)棧 P:= （） end else begin pop(s,p);將標(biāo)記退出棧退出到中 if pnil then begin push(s,nil)標(biāo)記進(jìn)棧 （） ； end else begin （3） ； write(q .data);訪問結(jié)點(diǎn)，打印結(jié)點(diǎn)數(shù)據(jù) end end endpost 題十（分）設(shè)結(jié)點(diǎn)的類型定義如下： type node=record data:integer; link:integer end; 在數(shù)組a中存放了個(gè) 結(jié)點(diǎn)： var a:array1.10 of node; 假定在主程序中已經(jīng)執(zhí)行了下列語句： for i:=1 to 10 do begin ai.data:=i, ai.link:=0 end; 最初將個(gè)結(jié)點(diǎn)看成分別屬于個(gè)集合，每個(gè)集合有且僅有一個(gè)結(jié)點(diǎn)，調(diào)用下面過程，判斷data=m和data=n的兩個(gè)結(jié)點(diǎn)是否在同一個(gè)集合中（最初肯定屬于不同集合，除非m=n），若不在同一集合中，則將這兩個(gè)結(jié)點(diǎn)合并到一個(gè)集合中。否則，已在同一個(gè)集合中，什么也不做。（此方法用于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í)行下面語句，已將各元素組成一個(gè)鏈；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是鏈的第一個(gè)結(jié)點(diǎn) 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分）下面是一個(gè)判斷二叉樹是否是排序平衡樹的函數(shù)說明，若是排序平衡樹，則返回值為真，否則返回值假，另外，以參數(shù)的形式返回二叉樹的高度和最大最小結(jié)點(diǎn)值。結(jié)點(diǎn)的類型定義與題九的定義相同。 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