1、PAGE PAGE 4四、完善程序(每空3分，共30分)1.存儲空間的回收算法。設在內存中已經存放了若干個作業A，B，C，D。其余的空間為可用的(如圖一中(a)。此時，可用空間可用一個二維數組dk1.100，1.2 表示，(如下表一中(a)，其中：dki，1對應第i個可用空間首址，dki，2對應第i個可用空間長度如上圖中，dk：1005030010050100 0 0100 50 300100 500 10010000 0 表一(a)表一(b)現某個作業釋放一個區域，其首址為d，長度為L，此時將釋放區域加入到可用空間表中。要求在加入時，若可用空間相鄰時，則必須進行合并。因此出現下面的4種情況(

2、如上圖一(b)所示)。(1)下靠，即回收區域和下面可用空間相鄰，例如，d=80，L=20，此時成為表二中的(a)。(2)上靠，例如，d=600，L=50，此時表成為表二中的(b)。(3)上、下靠，例如，d=150，L=150，此時表成為表二中的(c)。(4)上、下不靠，例如，d=430，L=20，此時表成為表二中的(d)。807030010050100100503001005001501003005001001005030010043020500100表二(a)(下靠)表二(b)(上靠)表二(c)(上，下靠)表二(d)(上，下不靠)程序說明：對數組dk預置2個標志，即頭和尾標志，成為表二中(b

3、)，這樣可使算法簡單，sp為dk表末地址。程序清單：var i,j,sp,d,l:integer; dk:array0.100,1.2of integer;begin readln(sp); for i:=1 to sp do readln(dki,1,dki,2); dk0,1:=0;dk0,2:=0; _; dksp,1:=10000;dksp,2:=0; readln(d,l); i:=1; while dki,1d do i:=i+1; _; if (dki,1+dki,2=d) then if (d+l=dki+1,1) then begin dki,2:=_; for j:=i+1

4、 to sp-1 do dkj:=dkj+1; sp:=sp-1; end else dki,2:=dki,2+l /l 不是1 else if (d+l=dki+1,1) then begin dki+1,1:=_; dki+1,2:=dki+1,2+l end else begin for j:=sp downto i+1 do dkj+1:=dkj; _:=d; dki+1,2:=l; sp:=sp+1; end; for i:=1 to sp-1 do writeln( dki,1:4, dki,2:4); readln;end.2.求關鍵路徑 設有一個工程網絡如下圖表示(無環路的有向

5、圖)： 其中，頂點表示活動，表示工程開始，表示工程結束(可變，用N表示)，邊上的數字表示活動延續的時間。 如上圖中，活動開始5天后活動才能開始工作，而活動則要等、完成之后才能開始，即最早也要7天后才能工作。 在工程網絡中，延續時間最長的路徑稱為關鍵路徑。上圖中的關鍵路徑為：共18天完成。關鍵路徑的算法如下：1.數據結構： R1.N，1.NOF INTEGER；表示活動的延續時間，若無連線，則用-1表示； EET1.N表示活動最早可以開始的時間 ET1.N 表示活動最遲應該開始的時間 關鍵路徑通過點J，具有如下的性質：EETJ=ETJ2.約定： 結點的排列已經過拓撲排序，即序號前面的結點會影響序

6、號后面結點的活動。程序清單：var i,j,n,max,min,w,x,y:integer; r:array1.20,1.20of integer; eet,et:array1.20of integer;begin readln(n); for i:=1 to n do for j:=1 to n do ri,j:=-1; readln(x,y,w); while x0 do begin rx,y:=w; _; end; eet1:=0; for i:=2 to n do begin max:=0; for j:=1 to n do if rj,i-1 then if _ then max:=rj,i+eetj; eeti:=max; end; _ for i:=n-1 downto 1 do begin min:=1000; for j:=1 to n do if ri,j-1 then if _ then min:=etj