11년 4월 9일 Subject 후기 > 시험문제 Q & A

본문 바로가기
사이트 내 전체검색


새창에서 채팅하기
시험문제 Q & A

11년 4월 9일 Subject 후기

페이지 정보

작성자 Ack 작성일11-04-10 00:04 조회4,677회 댓글1건

본문

안녕하세요. 방금 CS Subject을 보고 온 학생입니다. 준비하면서 csuhak에 올려주신 족보나 참고자료들이 큰 도움이

되었습니다. 특히 최근 후기들(07년)에서 확실히 많이 출제된 것 같네요. 혼자서 그냥 짜내자면 기억이 많이 안날 것

같고, 후기들을 한번 더 보면서 달라진 점이나 제가 고른 답들을 올려 보겠습니다. 확실히 몇몇 문제는 내용은 비슷하

되 문제 양식이나 주안점이 조금씩 달라진 것 같습니다.

일단 07후기부터 (자료실에 있는 2007_CS_SUBJECT.DOC 파일)

-----------------------------------------------------------------------------------------------

1) 그대로 나왔습니다.

2) What will be printed out if the following Java code has been executed?

class Base {
          public void Print(){
                System.out.print("base");
          }
          public void dosomething() {
                Print();
          }
}

class Sub extends Base {
          public void Print() {
                System.out.print("sub");
          }
}

class MainTest {

        public static void main(String[] args) {
                Sub sub = new Sub();
                sub.dosomething();
                doExtra(sub);

        }

        static void doExtra(Base b) {
                b.dosomething();
        }

}

07 후기와 코드가 약간 달라서 당황했습니다. 문제의 핵심은 Base에서 Override하지 않고 물려받은 함수 dosomething

이 Sub Class를 initiate해서 만들어진 sub Object에서 호출되었을 때, Base의 Print를 호출하느냐 아니면 Sub의

Print를 호출하느냐를 판별하는 것 같네요. (doExtra에서 Base 타입으로 선언되었을 때도 포함해서) 저 코드를 돌려보

면 답은 subsub이 나옵니다. 함수/변수명은 정확하지 않지만 문제의 의미는 저것이었던 것 같습니다.

3) While(i<3){ 이 당연히 for(i=0; i<3; i++) 로 바뀌어야 하겠습니다.
저는 (0 1 1 2 2 2 2), (0 1 2 1 2 2 2), (0 1 2 2 1 2 2) 세 개로 했습니다.
숫자 n을 찍은 Thread는 같은 Thread에서와 Fork를 해서 n+1을 두 번 찍을 수 있는데, 그러면 0은 두 1 앞에 와야 되

고, 1은 2개의 2 앞에 와야 된다고 생각했습니다.

4) 그대로 나왔습니다. 저는 Heap이라고 했습니다.

6) 문제에선 EF -> A 이었습니다. 저는 답을 6개로 했습니다.

7) Amdahl's Law가 숫자가 바뀌어 출제되었는데, 어떤 부분이 3.5배 성능 향상되어 전체가 1.8배 향상되었다면 향상된

부분은 전체의 몇% 인가 하는 문제였습니다. (62%로 기억합니다.)

8) Which value is not attainable from this if call by reference is used but the evaluation order is not pre-

defined ?


Int i=1;
Int j=10;
DoFunction(i++, i+3*j, j++);

Void doFunction(int a, int b, int c){
    Printf(a+b+c);
}

숫자와 식이 약간 바뀌었습니다. Call by Reference에 대한 언급도 있었는지 기억이 나지 않네요. 문제의 핵심은 b의

값이 계산될 때 i, j의 값이 먼저 바뀌느냐 입니다. 변수 두개 / (바뀐다, 안바뀐다) 합해서 네 가지 조합이 가능합니

다(1+10*3, 2+10*3, 1+11*3, 2+11*3). 저는 처음에 a와 c에는 바뀐 값(2과 11)이 넘어갔다고 가정했다가 보기에 맞지

않아서 안 바뀐 값(1과 10)으로 바꿔 생각했더니 유일한 답이 있어서 골랐습니다. 보기는 42 43 44 45 46 였고, 저는

b의 가능한 조합 4개에 11을 더해서 나올 수 없는 값 44를 골랐습니다.

9) Pre와 Post의 정의는 원래 문제와 같고, Pre(u) < Pre(v)에 l이 u와 v의 최소공통조상일때 맞는 것을 고르는 것 입

니다. 저는 Post(v) < Post(l) 이라고 했습니다.

10) 자료구조는 Binary Heap이 아니라 Binary Search Tree입니다. Inorder Traversal하면 정렬된 숫자들이 나오겠죠.

11) Job b and c must wait until job A finishes. Job D waits for job c. Job A should be done before any job.

choose the right way to use semaphore for this.

보기 하나가 Process 4개에 하나당 서너줄씩 나오는 바람에 문제가 한장을 꽉 채워서 intimidating 한데, 문제를 막상

보시면 별 거 없습니다. A만 봐도 처음에 아무 제약 없이 진입해서 끝날 때 Signal(Sem_B)와 Signal(Sem_C)를 하는 것

은 하나밖에 없습니다. 다른 보기들은 모두 A에 Wait가 걸려 있네요. Semaphore 정의만 잘 이해하고 가셔도 충분할 것

같습니다.

12) 비슷한 문제가 PERT 그래프(선후 관계와 각 Job들의 시간 표시)로 도식화되어 나와 있습니다.

13) 똑같이 나왔습니다. 저는 C라고 했습니다.

14) public/private key encryption을 RSA로 대체해서 나왔습니다. 저는 B라고 했습니다.

15) 완전히 같은 문제는 아니고 {a, b}* 에서 (# a) mod s = 0이고 (# b) mod t = 0 인 Language를 Recognize하는 DFA

의 State의 개수는? 이라는 문제가 나왔습니다. 저는 Theta(st)라고 했습니다.

16) Master's Theorem 문제는 T(n) = 2T(n/2) + log n 으로 나왔습니다. Linear하다고 했습니다.

17) 완전히 똑같이 나왔습니다. 홀수 디그리를 가진 노드의 개수가 짝수겠죠.

18) 완전히 똑같은 문제에 Undirected란 조건이 붙었습니다. 저는 Back Edge는 있지만 Cross Edge는 없다고 했습니다.

19) 문제는 똑같은데 보기에 1이 있습니다. 저는 1개라고 했습니다.

20) 어떤 Logic Statement가 Contingent하다는 것은 그 Statement가 Variable들이 어떤 Universe Set에 속하는 지와

Predicate에 따라 참이 될 수도 거짓이 될 수도 있다는 것을 의미합니다.

I.  [ Forall x, Forall y, P(x, y) ] => [ Forall x, Forall y, P(x, y) ]
II. [ Forall x, Some y  , P(x, y) ] => [ Some y,  Forall x, P(x, y) ]

이 두 가지의 성질을 물었습니다. I은 Always True이고 II는 Contingent라고 했습니다.
(보기에 Always False도 있었는데 II에서 특수한 경우(Universe의 원소가 하나라던가 P(x, y)가 무조건 참이라던가)에

는 저 명제가 참이 될 수도 있기 때문에 Contingent라고 생각했습니다.)

21) Abstract Class와 Method Mapping Table에 관한 성질을 묻는 문제가 각각 나왔습니다.

Abstract 문제의 보기는

A. Instantiated될 수 없다
B. Concrete Method를 가질 수 있다.
C. Concrete Method는 Override할 수 없다.
D. Abstract Method는 Override할 수 있다?

등이었네요. 저는 C라고 골랐습니다.

Method Mapping Table의 보기는 07후기와 비슷합니다. 저는 각 Method마다 Mapping Table에서 Offset이 Compile Time

이 결정된다는 보기를 답으로 골랐습니다.

저 두 개념에 대한 확실한 이해가 필요할 듯 합니다.

22) Page Replacement 를 직접 시뮬레이션 해 보는 것은 안 나온 것 같고, 첫 문제가 혼란스러웠습니다. Two-level

Cache, 4-byte Page (Table?) Entry, 32-bit logical address, 8KB page size 등 다양한 정보를 해 놓고 Page offset

으로 쓸 Bit를 묻더군요. 처음에 혼란스러워하다가 Page size만 보고 13으로 골랐습니다.

24) Regular Language를 판별하는 문제는
A는 그대로인 것 같고,
B는 #a >= 10
C는 (#a - #b) mod 5 = 0 이었던 걸로 기억합니다. 저는 B, C로 했습니다.

25) Congestion Window Size가 4000이고 Segment Size가 1000일때 Slow Start 중에 Nonduplicated ACK를 한 번 받으면

얼마나 Congestion Window가 커지느냐 하는 문제입니다. 저는 1000이라고 했습니다. 다른 보기로는 250, 500, 2000,

4000 등이 있었던 듯.

26)
function F(int x)
{
        y = 1
        while(y < x) {
                y = y * 2
        }
        return y;
}
이런 함수에서 실행 시간 T와 결과 F를 x에 대해 표현하는 것입니다. T(Theta(log x)), F(Theta(x))를 골랐습니다.

27) 원문과 같이 배열에서 양수의 개수를 구하는 함수인데 P는 Tail Recursive로, Q는 Iterative하게 구현해 놓고
I. P와 Q는 같은 함수를 계산한다
II. P는 Recursive다
III. Q는 Recursive다

라는 문제가 나왔습니다. 저는 I, II를 골랐습니다.

28) 똑같이 나왔습니다.

-------------------------------------------------------------------------------------
서브젝트 QnA에 있는 "2009년 4월 cs subject 후기"에 있는 문제도 모두 나왔습니다. 그 문제들은 별로 바뀌지도 않아

서 제가 덧붙일 것도 없네요.


* 그래프 이론 하니까 Unweighted에서 DFS, BFS 비교하는 문제가 생각나네요.
A. DFS는 BFS보다 Asymptotically 빠르다
B. BFS는 DFS보다 Asymptotically 빠르다
C. DFS Search Tree는 루트에서의 Shortest Path Tree이다.
D. BFS Search Tree는 루트에서의 Shortest Path Tree이다.
E. DFS는 BFS보다 Search Tree의 Height가 작을 수 있다.

저는 D를 골랐습니다.

* Minimum Spanning Tree 직접 구하는 문제가 있었습니다. Node가 9개인 꽤 큰 그래프.

* 그리고 Cache 관한 진술 중 틀린 것을 고르는 문제가 있었는데,
D) Write-through policy는 Direct Mapped 에서만 구현된다.
E) Write-Back은 Direct Mapped와 Set-associative 모두에서 된다. 라는 보기가 있었습니다.
저는 D를 골랐는데, 한번 조사해 보심이.

* 실행시간이 O(n log n)가 아닌 문제
Sort를 비롯한 시시한 문제(n log n이 아니라 n인 것도 있습니다)가 나오다가 Vertex Cover가 등장합니다.

* RISC vs CISC??
문제에는 load-store architecture와 register memory architecture(??)라고 나왔는데 RISC vs CISC겠거니 지레짐작했

습니다.

I. 전자가 Instruction Count가 많다.
II. 전자가 언제나 같은 프로그램을 빠르게 수행한다.
III.

I은 맞다고 했고, II는 틀리다고 했는데, III은 기억이 잘 안나네요.

* Pipelining

I. Latency를 줄인다
II. Throughput을 올린다
III. Longest Stage를 맨 뒤에 배치하면 Throughput이 올라간다.

II라고 했습니다.


* 클럭 레이트를 무한정으로 올릴 수 없는 이유는?

I. Thermal problem(? 정확한 단어는 잘 기억이 안나네요)
II. Gate에서 Delay
III. Wire에서 Delay

* CDP (Compact Disk Packing)이란 문제를 정의하고 NPC임을 보이는 방법.

E) Polynomially Checkable하다는 것을 증명한 후에(NP), Subset Sum의 Instance들을 Polynomial Time에 CDP로

Mapping하는 Reduction을 찾는다.

* Propagation Speed가 2*10^8m/s이고 선길이가 200m일 때, 1G Ethernet(Transmission rate 10^9 bit/sec)의 Minimum

Packet Size는?

보기는 1000, 2000, 4000 등이 있었습니다.

* Class B, Subnet 255.255.255.128과 함께 한 네트워크 주소 X.Y.Z.100(X, Y, Z는 문제에서는 실제 숫자였음)을 주고

같은 Subnet에 있는 것을 고르는 문제

X, Y, Z 등이 하나 더 크거나 작은 보기들이 나오다가 마지막 두 보기가 X.Y.Z.50과 X.Y.Z.200입니다. X.Y.Z.50이라고
했습니다.

* Checked Exception에 관한 문제 나왔습니다.

I. Checked Exception이 Unchecked Exception보다 항상 효율적으로 Thrown된다.
II. Handling된 후에 Exception을 낸 Method로 Control을 돌려준다.
III. Compile Time에 체크 가능하다(정확히 기억 안남)

이었는데 잘 모르겠네요.

* 입력이 P, Q, R이고 출력이 Y, NAND와 OR로 이루어진 회로를 주고 (P, Q, R)이 어떤 값을 가져야 (don't care 포

함), Y 값이 정해지지 않는가 하는 문제도 있었습니다.
NAND게이트가 좀 많아서 짜증나실 수는 있겠지만 식 전체의 부정을 그때그때마다 De Morgan으로 풀지 마시고 계속 가

지고 최종 출력 Y를 그렇게 표현하면 바깥에서부터 De Morgan을 적용하는 과정에서 부정의 부정이 되어서 식들이 쉽게

간단해집니다. 최종 식이 Y = P + QR + PR + PQ 정도 되었던 듯.

-------------------------------------------------------------------------------------

이상입니다. 07 후기와 09 후기만 제대로 봐도 절반 이상의 Hint는 얻는군요. 이런 Resource가 없었으면 시험장에서

얼마나 고생했을까 생각해 보니-_-;;;

이상입니다. 같은 문제라도 조금씩 달라지는 것 같으니 후기 공부를 할 때 관련 개념들을 교과서나 인터넷에서 찾아보

시면서 정리하시면 지금까지 올라온 후기들만 봐도 짧은 시간 안에 좋은 성과를 올리지 않을까 생각해 봅니다. 앞으로

보시는 분들께 도움이 되었으면 좋겠습니다.

수고하세요~
추천 0

댓글목록

반찬털이님의 댓글

반찬털이 작성일

  저는 07후기만 살짝보고 들어갔는데 기출에서 거의 변하지 않는거 같아요 기출만 잘 보고 들어가도 될듯 ㅋ 답은 제가 못푼거 빼고는 거의 비슷한거 같아요 ㅋ


접속자집계

오늘
107
어제
104
최대
442
전체
320,085
Copyright © 2000-2015. csuhak.info. All rights reserved.
상단으로
모바일 버전으로 보기