2005年軟件設計師考試題目預測(zz)

          Posted on 2005-05-24 19:19 蝸牛 閱讀(153) 評論(0)  編輯  收藏 所屬分類: pages(zz)
            1 一筆畫問題 

              2 迷宮問題 

              3 最短路徑問題(就是給出一個交通示意圖,邊上的數字為路的長度,求每個結點到某個固定點的最短路程) 

              4 N個球稱重問題吧 

              荷蘭國旗問題????四色定理 

              3種顏色(0,1,2)在一個數組里,每次只可交換一次,掃描一邊后,三種顏色自然分開,應為顏色為:紅,白,藍,(荷蘭國旗的顏色)所以叫它荷蘭國旗問題(也是他老人家的國籍)! 

          #include "stdio.h" 
          #include "stdlib.h" 
          #include "time.h" 

          #define N 15 

          int main(int argc, char* argv[]) 

          char array[N]; 
          char t,*p_red_end,*p_write_end,*p_blue_head; //分別為紅色的尾指針、白色的尾指 

              針、藍色的首指針 

          int i; 

          srand( (unsigned)time( NULL ) ); 
          for(i=0;i<N;i++) 

          switch (rand()%3) 

          case 0:  
          array=’r’; 
          break; 
          case 1: 
          array=’w’; 
          break; 
          default: 
          array=’b’; 

          printf("%c ",array); 

          printf("\n"; 

          for(p_red_end=p_write_end=array,p_blue_head=array+14;p_write_end<=p_blue_head 
          switch (*p_write_end) 

          case ’r’: 
          t=*p_red_end; 
          *p_red_end=*p_write_end; 
          *p_write_end=t; 
          p_red_end++; 
          p_write_end++; 
          break; 
          case ’b’: 
          t=*p_write_end; 
          *p_write_end=*p_blue_head; 
          *p_blue_head=t; 
          p_blue_head--; 
          break; 
          default: 
          p_write_end++; 

          for(i=0;i<N;i++) 
          printf("%c ",array); 

          運行結果是: 
          rrrwwrwwrwbbbbb 

              這個結果是荷蘭國旗算法的結果嗎?(我不清楚荷蘭國旗算法) 

              題目最終要求的結果應該是:紅,白,蘭,紅,白,蘭,紅,白,蘭……還是:紅,紅,紅,紅,紅,白,白,白,白,藍,藍,藍,藍,藍……? 

          #include "stdio.h" 
          #define k 15 /*假定數組有15個數*/ 
          char a[k]={’r’,’w’,’b’,’r’,’r’,’b’,’w’,’w’,’b’,’b’,’b’,’w’,’r’,’r’,’w’}; /*r,b,w代表紅, 

              藍,白*/ 

          main() 
          {int i,ii; 
          char t; 
          int m,n,p; 
          m=0; /*m為紅色末尾指針*/ 
          n=0; /*n為白色末尾指針*/ 
          p=14;/*p為藍紅色頭指針*/ 
          for (ii=0;ii<15;ii++) 
          printf("%c",a[ii]); 
          while(n<=p) 

          if (a[n]==’r’) {t=a[n];a[n]=a[m];a[m]=t;m++;n++;} 
          else if (a[n]==’w’) n++; 
          else { 
          t=a[n];a[n]=a[p];a[p]=t;p--;n++; 
          if (a[n-1]==’r’) {t=a[n-1];a[n-1]=a[m];a[m]=t;m++;} 


          for (i=0;i<15;i++) 
          prinrf("%s",a[n]); 



            貨郎問題???? 

              一筆畫問題 

          const max=6;{頂點數為6} 
          type shuzu=array[1..max,1..max]of 0..max; 
          const a:shuzu {圖的描述與定義 1:連通;0:不通} 
          =((0,1,0,1,1,1), 
          (1,0,1,0,1,0), 
          (0,1,0,1,1,1), 
          (1,0,1,0,1,1), 
          (1,1,1,1,0,0), 
          (1,0,1,1,0,0)); 
          var 
          bianshu:array[1..max]of 0..max; {與每一條邊相連的邊數} 
          path:array[0..1000]of integer; {記錄畫法,只記錄頂點} 
          zongbianshu,ii,first,i,total:integer;  

          procedure output(dep:integer); {輸出各個頂點的畫法順序} 
          var sum,i,j:integer; 
          begin 
          inc(total); 
          writeln(’total:’,total); 
          for i:=0 to dep do write(Path);writeln; 
          end; 


          function ok(now,i:integer;var next:integer):boolean;{判斷第I條連接邊是否已行過} 
          var j,jj:integer; 
          begin 
          j:=0; jj:=0; 
          while jj<>i do begin inc(j);if a[now,j]<>0 then inc(jj);end; 
          next:=j; 
          {判斷當前頂點的第I條連接邊的另一端是哪個頂點,找出后賦給NEXT傳回} 
          ok:=true; 
          if (a[now,j]<>1) then ok:=false; {A[I,J]=0:原本不通} 
          end; { =2:曾走過} 

          procedure init; {初始化} 
          var i,j :integer; 
          begin 
          total:=0; {方案總數} 
          zongbianshu:=0; {總邊數} 
          for i:=1 to max do 
          for j:=1 to max do 
          if a[i,j]<>0 then begin inc(bianshu);inc(zongbianshu);end; 
          {求與每一邊連接的邊數bianshu} 
          zongbianshu:=zongbianshu div 2; {圖中的總邊數} 
          end; 

          procedure find(dep,nowpoint:integer); {dep:畫第幾條邊;nowpoint:現在所處的頂點} 
          var i,next,j:integer; 
          begin 
          for i:=1 to bianshu[nowpoint] do {與當前頂點有多少條相接,則有多少種走法} 
          if ok(nowpoint,i,next) then begin {與當前頂點相接的第I條邊可行嗎?} 
          {如果可行,其求出另一端點是NEXT} 
          a[nowpoint,next]:=2; a[next,nowpoint]:=2; {置成已走過標志} 
          path[dep]:=next; {記錄頂點,方便輸出} 
          if dep < zongbianshu then find(dep+1,next) {未搜索完每一條邊} 
          else output(dep); 
          path[dep]:=0; {回溯} 
          a[nowpoint,next]:=1; a[next,nowpoint]:=1; 
          end; 

          begin 
          init; {初始化,求邊數等} 
          for first:=1 to max do {分別從各個頂點出發,嘗試一筆畫} 
          fillchar(path,sizeof(path),0); 
          path[0]:=first; {記錄其起始的頂點} 
          writeln(’from point ’,first,’:’);readln; 
          find(1,first); {從起始點first,一條邊一條邊地畫下去} 
          end. 

              銀行家算法其實是很普通的但是比較經典的算法,每本OS的書上都講的,主要用來防止產生死鎖的, 

              形象的講:銀行發放貸款(對不同的客戶,有分期貸的)不能使有限可用資金匱乏而導致整個銀行無法運轉,也就是說每次請求貸款時,銀行要考慮他能否憑著貸款完成項目還清貸款使銀行運轉正常, 

              (借用flyingcoolhwak寫的步驟) 

              令Request(i)是進程P(i)請求向量,如果Request(i)[j]=k,則進程P(i)希望請求j類資源k個。 

              算法步驟如下: 

              1、如果Request(i)>Need(i)則出錯(請求量超過申報的最大量),否則轉2、 

              2、如果Requdst(i)>Available則P(i)等待,否則轉3、 

              3、系統對P(i)所請求的資源實施試探分配,更改數據結構中的數值 

              4、Available<-Available-Request(i) 
                 Allocation(i)<-Allocation(i)+Request(i) 
                 Need(i)<-Need(i)-Request(i) 

              5、執行安全性算法(如下),如果是安全的則承認試分配,否則廢除試分配,讓進程P(i)等待 

              貨郎擔問題 

              問題描述 

              歐幾里德貨郎擔問題是對平面給定的n個點確定一條連結各點的、閉合的游歷路線問題。圖1(a)給出了七個點問題的解。Bitonic旅行路線問題是歐幾里德貨郎擔問題的簡化,這種旅行路線先從最左邊開始,嚴格地由左至右到最右邊的點,然后再嚴格地由右至左到出發點,求路程最短的路徑長度。圖1(b)給出了七個點問題的解。 

              請設計一種多項式時間的算法,解決Bitonic旅行路線問題 

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 汪清县| 白水县| 武夷山市| 七台河市| 黎川县| 准格尔旗| 三穗县| 基隆市| 上虞市| 会宁县| 云和县| 来凤县| 吴堡县| 宁晋县| 清河县| 临江市| 郯城县| 惠安县| 多伦县| 乐亭县| 漾濞| 通海县| 宁阳县| 蛟河市| 土默特左旗| 无为县| 乌鲁木齐县| 柯坪县| 崇仁县| 景洪市| 永安市| 皋兰县| 丰城市| 道孚县| 东乌| 大庆市| 湘阴县| 南木林县| 长丰县| 清流县| 博罗县|