[理工] [DS&Algo] [核對]-交大99-資訊聯招

[crazykk (JK)]

12.Consider the following program.
   void main()  {
      printf("%4d",f(95) ); }
   int f(int n)
      if(n>100) return (n-10);
      return (f(f(n+11)));  }
   (26).The output is an integer. How many digits are there?
        (A)1 (B)2 (C)3 (D)4 (E)5

   公佈答案:(B)  (我認為是D)

   原因:執行f(95)的結果是91
        但是"%4d" 不論是2位數或3位數甚至是5位數，都是印出4位數


14.Given a weighted graph and two vertices s and t, we want to find a longest
   path from s to t. Which of the following statements are WRONG aboout this
   problem? Select the correct answers from the following 2 questions.
   i.   This problem has a polynomail time algorithm.
   ii.  This prombel can be solved by transforming it into shortest path
        problem.
   iii. This problem can be solved by using Dynamic Programming.
   iv.  For a connected weighted graph the longest path has at least 3 edges.
   v.   For a graph with n vettices. if the longest path has n-1 edges, then
        it passes through each vertex exactly once.

   公佈答案:i,ii,iv   (我認為是i,ii,iii,iv)

   原因:longest path是NP-Complete Problem可用Dynamic Programming解?


18.Please finish the following implementation of circular queue.
   class Queue
   {  private:
         int orz,a,b;
         int data[3];
      public:
         Queue()
         {   orz=0;
             a=-1;
             b=0;   }
         void Enqueue(int x)
         {   if(IsFull())
             {   cout<<"Queue is full"<<endl;
                 reutrn;  }
             a=(a+1)%3;
             data[a]=x;
             if((a+1)%3==b) orz=1;  }
         int Dequeue(void)
         {   int x;
             if(IsEmpty())
             {    cout<<"Queue is empty"<<endl;
                  return -1;  }
             orz=0;
             x=data[ (42)  ];
             b%=3;
             return x;  }
         int IsEmpty(void)
         {   return (orz==0 && ((a+1)%3==b ?  (43);  }
         int IsFull(void)
         {   return (orz==1) ?  (44);  }
   };

   (42) (A)b  (B)b++  (C)++b  (D)b--  (E)--b

   公佈答案(B)  (我認為是C)

   原因:從Enqueue程式中的a=(a+1)%3;  data[a]=x;
        可以看出他是先把a指標(即Rear)前進,之後再放data
        因此在Dequeue時b指標(即Front)也要先前進，才能取出data
        否則b指標所指內容可能是空的，產生擷取到錯誤的資料情形發生


20. (48)Consider the case of inserting 10,8,12,6,4,2,11,1 into an empty min
        heap.Please show the first visited node when using LVR to traverse
        theresultant tree. (A)11 (B)10  (C)8  (D)12  (E)6

     公佈答案(B)  (我認為是C,B也沒錯,若用Top-down方式建立,答案是B)

     原因:從題組4可發現到採用Bottom-up方式建立max heap
          因此這題我也採用Bottom-up方式建立min heap,如下所示
                                      1
                                   /    \
                                  4      2
                                 / \    /  \
                                6  10  12  11
                               /
                              8
          LVR我想應該是inorder traversal
          因此第一個拜訪的點應該是8

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.36.162
※ 編輯: crazykk         來自: 60.244.36.162        (03/16 14:39)
※ 編輯: crazykk         來自: 60.244.36.162        (03/16 14:43)
→ Lukewind:12題應該是你誤會了 %md 是輸出寬度m的,不夠用空格補
→ Lukewind:18.也是a初始是-1 假如先++b第一輪應該就會錯了
→ Lukewind:最長路徑問題也確實可用DP解 GOOGLE有演算法
推 allenbody:20題他有強調一開始為空，用插入方式，這樣就是top down
→ crazykk:恩恩，感謝各位回答，讓我死心了...
→ allenbody:我沒帶考卷在身邊，有人可以PO一下或SCAN一下考題嗎?THX
→ EntHeEnd:請問哪邊有公佈答案呢 ?
推 willow02:有人要提出對OS的質疑嗎?XDD
→ crazykk:99交大選擇題解答  http://0rz.tw/x4ZH7
推 EntHeEnd:喔喔 感謝
推 assassin88:OS的第十六題的D FCFS那個選項對吧?
→ crazykk:回應樓上,SSTF(253) Look(253) SCAN(319)  C-Look(265)
→ crazykk:FIFO(300)  SCAN比FIFO更久
推 r5011057:請問OS第10.11題是怎麼算的?
→ keepoo:11.link要從頭讀起 所以┌422/128┐=3
→ keepoo:我錯了 XD 歹勢 腦袋糊塗
→ LATTICE:第12題答案沒錯,"%d"只是預留4個空間而已,不會補0
推 abcde1499:queue那題我也覺得是++b @@
推 sean721:我也寫++b.....〒△〒
推 fish0112:DS&Algo雖然考選擇，但是感覺很難 尤其對會懷疑自己的人
→ fish0112:小弟就是@rz
→ fish0112:不應該猜這麼多的...(哭哭)
推 Anthony53:LINK LIST那題為什麼不是三?
推 holik0123:資結6題 有人知道是什麼演算法嗎
→ holik0123:還是只是MAX-FLOW
推 haha31:OS拿幾分算高阿= =
推 RoddickJoe:80
推 lineageorc:我也寫++b說..
推 w8formePlz:80喔 那還好
推 pp393952:題組第20的(48) 我填C 這樣會算對嗎...
推 haha31:錯一個全錯吧.
推 tom21tom21:有沒有要寫去釋義
推 uthtdwp:請問資結第41題答案確定是(c)嗎  我算是(d)?
推 Lukewind:41題 前面係數要是4才會是d
推 sai31312:如果tree只有一個node那依據bipartite的定義，
→ sai31312:怎麼分成兩個subsets?
→ sai31312:所以22　23　我寫E耶
推 sai31312:還有我可以問一下第二題hash的答案是怎麼來的嗎？
推 sai31312:而且OS的第11題我也覺得很怪，他給的是logical address
推 sai31312:可是沒有說清楚logical physical之間的對應
→ sai31312:是怎麼知道必要讀取4個physical block才到的了