카이스트전산학과대학원입시기출문제모음

카이스트전산학과대학원입시기출문제모음 2014.5

1. Programming Language / Compiler 자바에서 public, protected, private 키워드가있는데아무것도안쓸경우 default로적용되는범위는? Static typing과 dynamic typing의차이점은? C++/JAVA은어떤 typing을사용하는가? C++ 에서서로다른타입의오브젝트를가리키는포인터를사용할수있나? 전역변수사용의장단점은? 프로그램실행전컴파일시에타입과같은프로그램의정적성질을검사하는프로그래밍언어와그렇지않은프로그래밍언어를비교하시오. 파라미터패싱방식에는 eager evaluation 방식과 lazy evaluation 방식이있다. 두방식의차이점을비교설명하세요. call-by-value와 call-by-name 파라미터패싱방식은각각어느방식에속하는지구분하세요. 언어를분류하는데있어서는해당언어를생성하는 Production 룰의형태에가해지는제약사항을가지고분류하는것이일반적이다. Context Sensitive Language, Context Free Language, Regular Language를생성하는데사용되는 Production 룰의형태에대해서그차이점을비교설명하세요. Let L be a regular language. Prove that R(L), strings in L reversed, is also a regular language. LR 파싱이란? Parsing Table의역할은? 핸들이란? 핸들의가장중요한특징은? 파싱에서 bottom-up 방식과 top-down 방식의차이점은? Recursive-descent 방식에서백트래킹이일어나지않게하려면어떻게해야하는가? A grammar G generating language L is defined by: Consider the following grammar, with start symbol E: E -> E * E E / E E + E E E ( E ) a b c d e f..... x y z

The following strings are legal derivations from this grammar: I. a * b + c II. ( a b ) * c III. a / ( b c) Which of the above are rightmost sentential forms? A relation on the integer 0 through 4 is defined by: R = {(x,y) x+y 2x } Which of the properties listed below applies to this relation? Why? I. Transitivity II. Symmetry III. Reflexivity Grammar G is defined by: G = ({x,y,z}, {S,W,X,Y,Z}, P, S) Where the members of P are: S -> WZ W -> X Y X -> x xy Y -> y yy X -> x zz Which of the following regular expressions corresponds to this grammar? (A) xx* yy* zz* (B) (xx* yy*).zz*

(C) (D) (E) xx*.(yy* zz*) (xx yy)*.zz* x*.yy*.xx* A computer system stores floating-point numbers with a 16-bit mantissa and an 8-bit exponent, each in two s complement. The smallest and largest positive values which can be stored are (A) 1 x 10-128 and 2 15 x 10 128 (B) 1 x 10-256 and 2 15 x 10 255 (C) 1 x 10-128 and 2 15 x 10 127 (D) 1 x 10-128 and (2 15-1)x 10 127 (E) 1 x 10-256 and (2 15-1)x 10 255 A grammar G generating language L is defined by: G = ( {x,y}, {S,X,Y}, P, S) where the elements of P are: S -> xy S -> yx X -> xz X -> x Y -> y Z -> z Is the language L generated by G most accurately said to be: A. Chomsky type 0 B. Chomsky type 1 (context sensitive) C. Chomsky type 2 (context free) D. Chomsky type 3 (regular)

E. None of the above Consider the following program fragment: read(a, b) c := 3.0 * a + b ; if c = 0 then a :=1 else a := 1.0/c +1.0/b ; This program fragment will fault if given certain values for a and b. Which is the weakest of the supplied conditions (least restrictive or smallest) which, if applied to the data, will prevent failure? A. b > 0 B. a>0 and b>0 C. a -b/3 D. b 0 E. 3.0*a 0 and b 0 Grammar G is defined by: G = ({x,y,z}, {S,W,X,Y,Z}, P, S) Where the members of P are: S -> WZ W -> X Y X -> x xy Y -> y yy Z -> z zz A. Show some examples that are generated by this grammar. B. Write the regular expression corresponds to this grammar? A relation over the set s = {x,y,z} is defined by: {(x,x), (x,y), (y,x), (x,z), (y,z), (y,y), (z,z)}

What properties hold for this realtion? I. Symmetry II. III. IV. Reflexivity Antisymmetry Irreflexivity V. Transitivity Grammar G is defined by: G = ({a,b}, {S,A,B}, P, S) Where the members of P are: S -> AB AS A -> a aa B -> b A. Show some examples that are generated by this grammar. B. Write the regular expression corresponds to this grammar? A binary tree is to be used to sort positive integers. The partial tree shown below is formed.

The next number in the file is 13; where should this be placed such that in order traversal of the tree yields the sorted file? A grammar G generating language L is defined by: G = ( {x,y}, {S,A,B,C}, P, S) where the elements of P are: S -> ABA AB -> AC CB -> BBC CA -> BBA A -> a E B -> b Is the language L generated by G most accurately said to be: A. Chomsky type 0 B. Chomsky type 1 (context sensitive) C. Chomsky type 2 (context free) D. Chomsky type 3 (regular) E. None of the above Consider the following program fragment and its assertions: ASSERT INITIAL (B > 0) AND (C > 0) If B > C THEN A := B / C ELSE A := C / B ENDIF; ASSERT FINAL (A > 1) There are two paths through this code; which of the two is taken depends upon the predicate B > C. Which of the following statements is true?

A. The program fragment is consistent with its assertions along both path. B. The program fragment is inconsistent with its assertions along both path. C. The program fragment is consistent with its assertions along the predicate = false path only. D. The program fragment is consistent with its assertions along the predicate = true path only. E. The question of consistency is undecidable until the values of B and C are known. Grammar G is defined by: G = ({a,b}, {S,A,B}, P, S) where P is the set: S -> AB AS A -> a aa B -> b bb A. Draw a parse tree for the string aaabb. B. What type is the language L(G) most accurately? Is it regular, context free, or context sensitive? The binary tree below is traversed in postorder. In what order are the nodes visited? Write the program to visit a binary tree T in postorder and print the value of nodes in your favorite programming language.

2. Architecture 캐시가필요한이유는? Cache hit ratio 에대해설명하시오. 메모리접근하는데 x 사이클이걸리고캐시에접근하는데 y 사이클이걸리며캐시 hit rate 가 h % 일때 effective access time은? 페이지폴트는언제발생하는가? 페이지폴트비율과 cache miss 비율중큰것은? 그이유는? 캐쉬메모리와메인메모리의주소지정방식의차이점이무엇인가? 캐쉬를구성하는컴포넌트에무엇이있는가? 각컴포넌트는어떤역할을하는가? 캐쉬에서태그매칭이무엇이고왜필요한가? 캐쉬에서블록 ( 라인 ) 크기를크게했을때와작게했을때어떤장단점이있을까? Direct-mapped cache와 set-associative cache의장단점은무엇인가? Write-through cache와 write-back cache에대해서설명해보시오. Write-through cache는 write buffer를보통사용하는데이의역할은무엇인가? 코어가 10개있는 cpu에서프로세스하나를균등하게처리하면이상적인경우, 시간이얼마나줄어드는가? 그런데프로세스에서분할되지않는 20% 의작업이있다고하면, 시간이얼마나줄어드는가? 이제코어가수백개, 혹은무한개있다고하면얼마나줄어드는가? Cache에서사용하는 replacement policy에는어떤것이있는가?

3. OS Kernel을필요에의해어느정도수정했다고하자. 이 kernel이제대로작동하는지를알기위해서어떤 test를해야겠나? Sequential program과 multithread program에서 error detection에대한차이점에는어떤것이있나? 어떤 C program으로작성되어수행중인 process가있다고가정하자. C언어에서는직접적으로주소를변수에게지정해줄수있다. 만약주소 1, 2, 3, 4에변수를잡아서어떤일을수행하는 process라고하자. 이 process를한시스템에동시에두번수행시켰다. 그랬을때한프로세스가 1, 2, 3, 4 주소에있는변수를바꿨을때다른프로세스의변수들에도영향을끼치는가? Thread와 process의차이는무엇인가? IPC가무엇인가? Logical address와 physical address의차이는무엇인가? Logical address를 physical address로바꾸어주는 hw가무엇인가? Interrupt란무엇인가? interrupt를두종류로나눈다면어떻게되는가? (software interrupt/hardware interrupt) 두 interrupt의차이는무엇인가?-두 interrupt의 handler 를서로구분해서구현해야하는것이좋은가, 아니어도상관없는가? C로숫자로직접입력된주소를참조하는프로그램을짜서컴파일한후, 두개를실행시켰다고하자. 그러면이두프로세스는물리적으로같은곳을참조하나? 만약아니라면, 어떻게서로다른물리적공간을참조할수있나? 프로세스는가상메모리주소로어떻게실제메모리주소를찾아가죠? Paging이무엇인가? paging을할때어떻게실제메모리주소에데이터를전송하는가? page table에는어떤항목이저장되는가? page table은어디에저장되는가? page table이메모리에저장되면, paging을할떄메모리를두번참조해야되는데, 좀더빠르게하는방법은없는가? TLB에는어떤항목이저장되는가? Thread와 Process의차이는? Thread끼리 context switching 하는과정에대해설명하시오. 같은프로세스내부의 thread들끼리전환되는것과다른프로세스간의 thread 까리전환되는것이어떻게다른가? Virtual Address와 Virtual memory에대해설명하시오. 시스템콜과인터럽트의차이는? 인터럽트가걸리면어떤일이일어나고, 인터럽트

처리후에어떻게이전상태로돌아가나? Non-preemptive scheduling이란? Critical section이란? OS의캐시메모리의사이즈를구하기위한프로그램을어떻게구현하면되는가? 세마포어의개념은? 주요연산 2가지는? 어떻게구현해야하는가? Virtual memory에서 page replacement policy에는어떤것이있는가? LRU의단점은? 운영체제에서 memory management 기법중하나로 paging이많이사용되고있습니다. Paging 기법의장단점들로는무엇이있으며, hierarchical paging 혹은 inverted page table은어떤환경에서유리할까요? 요즘많은사람들이각각자신만의스마트폰을사용하고있습니다. 이처럼각개인스마트폰을위하여 process system을 design하려고합니다. 스마트폰에서각 application이하나의 process로독립해서실행하는것이나을까요? 아니면, 하나의 thread로만들어져서실행하는것이나을까요? 어느쪽이나을지결정하고, 그이유를설명하세요. 캐쉬메모리와메인메모리의주소지정방식의차이점이무엇인가? s

4. DB Data inconsistency란무엇인가? Data normalization이무엇인가? 왜필요한가? Inner Join과 Outer Join의차이점은? Outer Join은언제사용하는가? DB와 file의차이점은? Data independence란?

5. 이산수학, 확률, 통계 Mathematical induction이란? Relation의정의는? a A, b B 일때 arb <-> (a, b) R 이뭔뜻인지설명하시오. 여기서왼쪽 R 과오른쪽의 R이같은것인가, 다른것인가? 다르다면어떻게다르나? Bijection의정의는? Equivalence relation이란? Partial order relation이란? Total order relation이란? Random variable이무엇인가? Sample space란무엇인가? Sample space가갖는조건이무엇인가? Exponential distribution이무엇인가? Poisson distribution이무엇인가?

6. 네트워크 TCP와같이 protocol을 reliable하게설계하려면무엇이필요한가? Flow control이란무엇인가? Congestion control과 flow control의차이점은? OSI 7계층에대해설명하시오. Transport, network, link 계층이모두연결에관한것인데, 무엇이차이가나나요? Network에서 checksum을위해사용하는 hash function과 security에서 data integrity 를위해사용하는 hash function이서로 interchangable해요? TCP와 UDP의차이점은? Congestion이발생했다는것을어떻게할수있는가? 3-way handshaking이란? CSMA/CD란? MAC address란? IP address가 MAC address에비해갖는장점은?

7. Software Engineering UML 에서시퀀스다이어그램이란무엇인가? SW에서모듈화란? 모듈화를잘하기위해중요한것은? CMMI 레벨이란? 요구공학에서는어떻게요구사항을수집하는가? 테스트기법으로화이트박스와블랙박스테스트가있는데, 그둘의차이점은? 화이트박스테스팅이에러가없는프로그램이라고보장해주지않는이유는?

8. AI / ML Show, using a proof or an example, that if P(A B,C) = P(A C), then P(A,B C) = P(A C)P(B C) An eigenvector of a square matrix A is a non-zero vector v that, when multiplied by A, yields the original vector multiplied by the corresponding eigenvalue λ. What is the 0 1 0 eigenvector of 0 2 0 corresponding to the eigenvalue 3? 0 0 3 In A* search, the evaluation function is defined as follows: f(n) = g(n) + h(n), where g(n) is the cost so far to reach n, and h(n) is the estimated cost from n to goal. We call h(n) the heuristic function. Under what condition is A* search guaranteed to find the optimal solution? If we want to design an admissible heuristic, what condition does h(n) need to satisfy?

9. 알고리즘 Sorting algorithm 들에는어떤것들이있는가? Insertion sort, heap sort, selection sort, quick sort 중 optimal 한것과 optimal 하지않은알고리즘은? 그이유는? 그래프의정의는? 트리의정의는? 트리와그래프의관계는? Topological Sorting을설명하시오. Partially ordered set이란? NP Complete의정의는? Dynamic Programming이란? Priority queue란? Heap 이란? 오일러사이클이란? Tree traversal의 3 가지방식을설명하시오. Quick sort 에대해설명하시오. Transitive closure란? Finite state automata란? Binary tree란? binary tree에서각 node는두개의 children을갖거나혹은 leaf node 이거나둘중에하나라고할때, non-leaf node와 leaf node 개수의관계식은어떻게되는가? Minimum spanning tree를구하는알고리즘과, 그알고리즘의복잡도는? Suppose we have a straightforward Θ(n 2 ) algorithm for a problem. Suppose we devise a divide-and-conquer algorithm that divides an input into two inputs half as big, and takes nlgn time to divide the problem and nlgn time to combine the solutions. Is the divide-and-conquer algorithm faster or slower than the straightforward algorithm? Justify your answer. Let P be a problem. The worst-case time complexity of P is O(n 2 ). The worst-case complexity of P is also Θ(n lg n). Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P. (a) A has worst-case time complexity O(n2) (b) A has worst-case time complexity O(n)

(c) A has worst-case time complexity Θ(n 2 ) (d) A has worst-case time complexity Θ(n 3 ) Show how you can make Quicksort to have O(n lg n) worst-case running time. Consider the following divide-and-conquer algorithm. Given a graph G = (V, E), we partition the set V into two sets V1 and V2 s.t. V1 and V2 differ by at most 1. Let E1 be the set of edges that are incident only on vertices in V1, and let E2 be the set of edges that are incident only on vertices in V2. Recursively solve a minimum-spanningtree problem on each of the two subgraphs G1 = (V1, E1) and G2 = (V2, E2). Finally, select the minimum-weight edge in E that crosses the cut (V1, V2), and use this edge to unite the resulting two minimum spanning trees into a single spanning tree. Either argue that the algorithm correctly computes a minimum spanning tree of G, or provide an example for which the algorithm fails. Let T be a minimum spanning tree of G. Then for any pair of vertices s and t, is the shortest path from s to t in G the path from s to t in T? Justify your answer. Describe Dijkstra s algorithm and analyze its running time. Describe Floyd-Warshall algorithm and analyze its running time. Optimal한정렬알고리즘의예를들어보세요. 그알고리즘의 complexity를분석하고 optimal하다는것을증명해보세요. Dynamic programming과 Greedy algorithm에대하여각각이무엇인지설명하고, 공통점과차이점을이야기하세요. 구체적으로 Dynamic programming으로풀수있는데 Greedy algorithm으로는풀수없는문제의예를들어보세요. 그문제가 dynamic programming으로풀수있다는것을증명해보세요. n개의숫자가 array로주어졌습니다. 이중에 Median을찾는알고리즘을설명해보세요. 설명한알고리즘의 complexity는무엇입니까? Median을찾는 optimal한알고리즘의 complexity는무엇입니까? optimal하다는것을어떻게증명할수있나요? Median을찾는알고리즘을이용하여 n개의숫자를정렬해보세요. 이정렬알고리즘의 complexity는무엇입니까? 두가지문제를통해 Reduction이라는개념을설명해보세요.

10. 그래픽 여러 shading 모델들과, 차이점을설명하시오 Edge detection에대해설명하시오. Massive한데이터를그래픽으로출력하려면, 어떻게해야하는가? 3차원의가상공간에놓여있는 3차원물체들이 2차원의그림으로렌더링되어우리의화면에보여진다. 이를우리는 2차원윈도우를통해서상호작용을하게되는데이때간단하게는마우스를이용하여 3차원공간에있는물체를선택하게된다. 이때마우스 input은 (x,y) 2차원좌표인데어떻게 3차원공간에있는물체를선택 (selection) 할수있을까? 이를가능하게할수있는 Object Selection 방법을제시하라. 물체의빠른충동감지를위해서물체를감싸는간단한도형인 bounding volume 을 hierarchical 하게구성하여사용한다. 이의간단한예를만들어얼마나빠르게처리를할수있는지설명하라

11. 정보보호 네트워크에서정보를전송할때데이터를보호하기위해암호화하는방법에는어떤 것이있는가?