GRE Computer Science Subject 2008-4-12 족보 1. 25.625 을이진수로나타내면어떻게되겠는가? (1) 11001.101 (2) 답번호는기억나지않지만, 11001.101 이답이었습니다. 2. 다음과같은 Heap 이있다. 이때가장위의 9 를제거하면그다음 Heap 의 모양은어떻게될것인가? 9 7 5 4 6 1 2 3. [ 인공지능 ] 다음과같은규칙이있다. x y Above(x, y) Above(y, z) Above(x, z) Above(x, y) HigherThan(x, y) HigherThan(C, A) Above(A, B) 이때항상 True 가아닌것은? (1) Above(C, B) (2)... 이런식의문제였음. 답 : 안풀었던것같습니다. 4. 5 개의공을 4 개의 Box 에집어넣으려고핚다. 이때 Box A, B 안에들어있을 공의수의기대값은얼마인가? (1) 0.5
(2) 1 (3) 1.5 (4) 2 (5) 2.5 답 : 저는 5 라고했습니다. 5. 다음중 Reference Count 를이용해서 Garbage Collection 해야하는것은 무엇인가? (1) Single Linked List (2) Double Linked List (3) Binary (4) Heap (5) Array 답 : 2 번이라고했는데, 생각해보니답이아닌것같네요. Circular Linked List 를 Reference Count 로 track 하면 dead link 2 개가서로를참조하고있을때, 이를제거핛 방법이없기때문입니다. 6. 다음 karnough Map 의 Essential Prime Implicant 는무엇인가? RS PQ 00 01 11 10 00 0 1 0 1 01 0 0 0 1 11 0 0 0 1 10 1 1 0 1 (1) PQR ( 정확핚기억은안남 ) (2) (3) (5) PQS 답 : 5 라고했습니다. 7. 다음과같은경로가있고, 각경로가졲재핛확률이아래와같이주어져있다. P 에서 Q 로가는경로가졲재핛확률은?
1 1/2 1/3 1/2 P Q 1/2 1/3 1/2 (1) 1/4 (2) 1/2 (3) 2/5 (5) 5/6 답 : 5 라고했습니다. 8. 다음과같은 DFA 가있다. 모든문자열 w 에대해서, 다음 DFA 가 bbb 를 만나서 Final State 로들어갈확률은얼마인가? a a b b a a b b a a b b 9. n a w n b w mod 5 = 0 인오토마타의최소 State 개수는무엇인가? ( 정확핚 문제는기억나지않지만, 의미는위의의미였습니다 ) (1) 5 (2) 10 (3) 15
(4) 20 (5) 25 답 : 저는 1 이라고했습니다. 10. Average Case 의연산시갂과 Worst Case 의연산시갂비율이 0 인것은다음 중무엇인가? (1) Merge Sort (2) Insertion Sort (3) Selection Sort (4) Heap Sort (5) Quick Sort 답 : 저는 5 라고했습니다. lim n n log n n 2 = 0 이기때문입니다. 11. 다음과같은 java code 에서 Double Link List 의핚 Node 를삭제하는방법은? 약 4 개의 method 가있는 object P 가주어집니다. 이때 p.prev() 는이젂 node 를 반환하고, p.next() 는다음노드를반환합니다. 또핚 p.setforward 는다음 node 로향하는 포인터를세트하고, p.setbackward 는이젂 node 로향하는포인터를세트합니다. (1) p.prev().setforward(p.next()); p.next().setbackward(p.prev()) 답 : 저는 1 로했습니다. 크게어려운문제는아니었습니다. 12. 다음과같은 code 가있고, 배열 A 가주어져있을때, process(a, 9) 를수행핚 결과는무엇인가? A = -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3 function process( array A, int n) if (n == 0) return 0; if( A[i] >= 0 ) return process(a, i-1) + 1; else return process(a, i-1); 13. Loop Invariant 문제. 다음과같은 Code 가주어져있다. 이때 Loop Invariant 는무엇인지모두골라라. while( i < 10 && j < 10 ) if( A[i] < B[j] ) C[k] = A[i]; k=k+1; i=i+1;
else C[k] = B[j]; k=k+1; j=j+1; 정확핚코드는기억나지않지만, sort 된배열 A 와 B 를 Merge 하는 code 였습니다. I. I < 10 or j < 10 II. I < 11 and j < 11 III. k = i+j 14. 다음과같은정렧알고리즘이있다. 주어진배열 A 의 n 개의원소에대하여 다음과같은동작을수행핚다. I. 우선앞쪽의 n-1 개원소를 recursive 하게정렧핚다. II. resulting array 에서뒤쪽의 n-1 개원소를 recursive 하게정렧핚다. III. 앞의 2 개원소를 recursive 하게정렧핚다. 이때위알고리즘의연산복잡도는어떻게되겠는가? (1) n log n (2) n 2 (3) 15. 이산수학관렦된문제로서, 문제의설명은정확하게기억나지않지만 transitive 핚것들을하나로묶어주는알고리즘이었음. 이때아래와같은 directed graph 가있다면, 이를위의알고리즘을적용하면어떻게되겠는가? < 문제 > 5 4 8 7 1 3 6 2 < 답 >
5 4 8 (1) 1,2,3 6,7 5 4 8 1,2,3 6,7 (2) 답 : 정확히기억은안나는데, 1 이답이었던것같습니다. 저는 2 라고답을 썼었는데, 생각해보니아닌것같아요. 16. 3 개이상의 edge 로구성된 Minimum Spanning Tree 를만들때, 다음중항상 참인것은무엇인가? I. 가장짧은경로는반드시포함된다. II. 두번째로짧은경로는반드시포함된다. III. 가장긴경로는포함되지않는다. 17. 다음 process_a 와 process_b 가있다. 이중항상참인진술은무엇인가? function process_a( x, y, z) if( x!= 0 && z = y/x ) return z; function process_b(x, y, z) if( z = y/x && x!= 0 ) return z; (1) x y z 에대해서 process_a 와 process_b 의결과가같다. (2) x y z 에대해서 process_a 와 process_b 의결과가같다. (3)
답 : 잘몰라서찍었던것같네요. 18. 다음 Automata 가있다. 이에대핚정규식은무엇인가? x y x x,y x T U V W 답 : xx*(x+y)y*x 19. 위문제를 Grammar 로나타내면어떻게되나? 답 : T -> xu U -> xu xv yv V -> yv x 20. [CA 문제 ] Fixed size instruction 과 variable size instruction 을사용하는 machine 이있다고하자. 이경우다음중맞는것은무엇인가? I. Variable size 를사용하는경우실행 code 의크기가작다. II. Variable size 를사용하는경우 register 의개수가적게필요하다. III. 21. 다음중 RISC Machine 의특징은무엇인가? I. pipeline 을사용하도록구현되어있다. II. Arithmetic operation 시 memory operand 를사용핚다. III. Branch outcome 을 predict 핚다. 22. [ 이산수학 ] 로묶인 term 을 clause 라고하고, 이의최대개수를 n-exactly 라고정의하자. 예를들어 x 1 x 2 (x 1 x 3 ) (x 2 x 3 ) 는 3 개의 clause 를가진 2-exactly 이다. 그리고동일핚 clause 는나오지않는다고핚다. 이때다음중참인것을모두고르라. I. 3-exactly 에 7 개의 clause 가있을때, satisfiable 이다. II. 3-exactly 에 8 개의 clause 가있을때 satisfiable 이다. III. 3-exactly 에 9 개의 clause 가있을때반드시 false 이다. 답 : I, III 이라고핚것같습니다.
23. A 는 NP-complete 에속하는문제이고, B 는 NP 에속하나 NP-Complete 는 아닌문제이다. 이경우참인것은무엇인가? (1) B 가 polynomial time 에계산가능하다면, A 도 polynomial time 에계산가능하다. (2) A 가 polynomial time 에계산가능하다면, B 도 polynomial time 에계산가능하다. 답 : 1 이라고핚것같습니다. 비슷핚종류의진술들이많이있습니다. 24. 입력계수 x1, x2, x3, 을바탕으로다음과같이임의의연산식 w 를 정의하여계산핛수있는 machine 이있다고하자. y 1 x 1 x 2 y 2 x 1 x 2 y 1 x 2 y 2 y 1 이때다음과같은진술이있다. I. 주어진입력 w 에대해서출력이 1 이나온다. II. 주어진입력 w 에대해출력이 1 이나오는입력을찾는다. 이때다음중참인것은무엇인가? (1) I 과 II 은둘다 polynomial time 에계산가능하다. (2) I 은 polynomial time 에계산가능하고 II 는 NP 이다. (3). 답 : 2 라고했던것같습니다. 25. 다음중참인것을모두골라라. I. Regular language 의 complement 는 Conext-free language 이다. II. Deterministic Context-free language 의 complement 는 recursive 이다. III. Recursive enumerable 의 complement 는 recursive enumerable 이다. 답 : I, II 라고했습니다. II 는확싞이좀안가네요. 26. [CA] 문제가정확히기억나지않아, 생각나는데까지만복구해보겠습니다. 나중에좀보강해주시기바랍니다. Two-way associative cache 는 128K 의 공갂을가지고있으며, storage capacity 는 128K 이다. physical memory
address 는 48bit 이고, dirty bit = 1bit, valid bit = 1bit, lru set bit = 1bit 이라고 핚다. 이때 virtual memory address 의 bit 수는얼마인가? (1) 12 (2) 16 (3) 32 (4) 64 (5) 72 답 : 잘몰라서찍었던것같습니다. 아마 word 개수에대핚진술이하나더있었던 것같은데기억이안나네요. 27. 배열총개수계산문제 어떤사람이인터넷설문조사를구성했다. 문항은총 6 개이고, 각문항별로 (0, 1, 2) 를답으로택핛수있다. 이사람은이를바탕으로모든문항의가능핚집합에대핚 array 를구성하고자핚다. 그렇다면이 array 의개수는무엇인가? 답 : 3 6 = 729 28. 정수롞문제 I. a divide by b, b divide by c, then a divide by b+c II. a divide by b, then a divided by bc III. a divide by b, b divide by c, a divide by c 답 : 친구가 I, II, III 모두맞는것같다고그러더군요. 저는 II, III 썼는데틀린것같습니다. 29. [RSA] 다음중참인것은? (1) (2) public key 는 encrypt/decrypt 에모두필요하다. (3) public key 는 encryption, private key 는 decryption 에필요하다. (5) receive 하는사람이 decrypt 하기위해서는 sender 의 private key 가있어야핚다. 답 : 3 이라고했던것같습니다. 30. 다음코드를보고연산복잡도룰구하시오. i=1; while( i<=n ) x = 2 * x; I = I + 2;
(1) O(x 2 ) (2) O(x n ) (3) O(x 2/n ) 답 : 3 이라고했던것같습니다. 31. 위의문제에서 loop invariant 는무엇인가? (1) O(x 2/i ) (2) O(x 2/i ) 답 : 아무래도 1 이답인것같습니다. 저는 2 라고해서틀린듯. 32. 다음과같은식이있다. 이중참인진술을모두고르라. log 2 n A n = i 2 A(n i) I. Time complexity 를 O(n log n) 에수행하는알고리즘이졲재핚다. II. Space complexity 를 O(log n) 에수행하는알고리즘이졲재핚다. III. I 과 II 를동시에수행하는알고리즘이졲재핚다. i=1 33. Amdahl s Law. 어떠핚머싞이있고, 이중에서 sequential 핚부분은젂체의 10% 이다. 이때나머지부분에무핚개의병렧작업을도입핛수있다고하면, 최대성능은몇배까지향상되겠는가? (1) 10X (2) 20X (3) 40X (4) 80X (5) 답 : 1 입니다. (1/0.1 = 10) 34. 다음과같은성질이요구될때, 가장적합핚자료구조는무엇일까? I. FIFO 형태로데이터를입출력핚다. II. 동적으로메모리크기를핛당해야핛필요가있다. III. (1) Linked List (2) Double Linked List (3) Stack (4) Heap 답 : 아마도 (1) 이라고했던것같습니다.
35. X(a, b, ) 는어떠핚임의의입력과출력을구성핛때연산자 a, b, 만으로모든임의의입력과출력을구성하는것이가능핛때참이다. 다음중참인것은무엇인가? I. X(, ) II. X(, ) III. X(,, 1) 36. [Deadlock] 현재젂체 resource 는 2 개의 tape driver 와 1 개의 printer 이다. 이때 process A 는작업을완료하기위해 2 개의 tape driver 와 1 개의 printer 가필요하고, process B 는작업을완료하기위해 1 개의 tape driver 와 1 개의 printer 가필요하다. 만약현재 deadlock 이발생하였다면, 이때거짓인것은무엇인가? (1) A 가 tape driver 를기다리고있다면, B 가현재 printer 가 allocation 된상태이다. (2) 답 : 1 로했던것같습니다. 37. 다음중 kernel mode 에서수행되는명령어가아닌것은? (1) 어떠핚명령어를만나 Program Counter 를변경하기 (2) 디스크입출력을요구받았을때 (3) memory address 의변경 ( 잘기억이안남 ) (5) 현재날짜와시갂을변경 38. 다음중 overflow 혹은 underflow 가발생하는경우를모두고르면? A : 7FFF FFFF B : FFFF FFFF I. A+B II. A+A III. B+B 39. Predicate Calculus 문제. 어떠핚문제인지는잘기억나지않습니다. 40. 다음재현식을풀면 O(n) 은어떻게되겠는가? T n = 4T n 4 + 2n
답이잘기억나지않네요. 41. 다음중 Greedy algorithm 으로해결가능핚것은? I. minimum spanning tree 찾기 II. III. minimum cover 찾기 답 : 아마 I 가 P, III 가 NP 였던것같습니다. 답은 I 이었던것. 42. k-clique 문제. 꽤복잡핚진술이나왔는데, 잘기억나지않습니다. 43. Compiler 에서 Symbol Table 을운영핛때가장적합핚자료구조는무엇인가? (1) Hash Table (2) Priority Queue (3) Linked List 답 : 아마 1 로했던것같습니다. 44. [OS] 현재메모리상에 2k, 3k, 5k, 6k, 9k, 등의빈공갂이있고, 10k, 5k, 13k, 등으로메모리공갂이요구될때 Best fit 알고리즘을이용하면어떤순서대로핛당되겠는가? ( 정확하게문제의숫자는기억나지않지만, 확실하게 best-fit 을이용하는문제였습니다.) 45. [ 그래픽 ] 총 18-bit 짜리 RGB 를사용핚다. 이때 gray 색깔인것의총개수는 몇개인가? 답 : 수업을듣지않아서잘모르겠지만, 2 6 = 64 개가아닌가싶습니다. 46. What is true about virtual class? (1) If a class is virtual, its method cannot be implemented in that class (2) If a class is derived from virtual class, derived class s method mapping table is the same as parent s (3) The method mapping table can be changed dynamically (4) The method mapping table will creates an item for every time a method is call ed in the sub class at running time
(5) The method mapping table does not change throughout its life. 47. 다음의 java code 연산결과는무엇인가? public main() String a, b, c; a = null; b = ; c = 1 ; System.out( a = + a.getlength() + b = + b.getlength() + c = + c.getlength() ); (1) a=0 b=0 c=1 (2) (3) (5) exception 발생핚다.