2004학년도 연세대학교 편입학 기출문제

 

1.그래프에 관한 문제였습니다. 다음 그림을 보고서....   (1) 인접리스트(adjacency list) 표현을 이용하여 저장할때에 어떻게 될것인가? (2) 깊이우선탐색(Depth First Search) 방식으로 방문하면서 신장트리(spaning tree)를 보이시오. (3) 너비우선탐색(Breath First Search) 방식으로 방문할때에 신장트리를 보이시오. 2. 컴퓨터 구조에 관한 문제였습니다. 16개의 메모리 셀을 가진 컴퓨터에서 덧셈과 저장만이 가능할 때에 (1) 컴퓨터 구조를 나타내고 기계어를 설계하시오. (2) 이 컴퓨터의 0번지에 'a'가 저장되어 있고, 1번지에 'b'가 저장되어 있을 때에 0번지에 2a+b가 저장되도록 프로그래밍 하시오. 3. 해슁에 관한 문제입니다.해슁에 대한 설명이 나온후에... (1) 해슁작업전에 문자열을 정수화하여야 한다. 문자열을 정수화 하는 함수를 구하시오. (2) 해슁에서 충돌이 생기는 이유를 설명하고 충돌을 없애기 위한 방법이 무엇이 있는지 설명하시오. (3) (2)에서 설명한 방법을 이용하여....각각 xx,xx,xx,xx,xx,xx(숫자 6개가 주어졌습니다. 정확한 숫자들은 기억이 나질 않아서^^xx처리 했습니다.) 를 키값으로 갖는 O-1,O-2,O-3......,O-6(영문 O에 숫자가 아랫첨자인것인데...여기선 표현 불가능해서 데쉬(-)를 썼습니다.) 를 해슁하는 과정을 설명하라. 해슁하게 되면 HT[n]에 각각 남겨지게 되는데 각 HT[]안에 무엇이 남겨지게 될지도 보이시오. 4.정렬과 최대값, 최소값을 구하는 알고리즘에 관한 문제였습니다. 배열 A[0:n-1]이 있다. (1) 최대값, 최소값을 구하는 알고리즘을 재귀적인 방법을 쓰지 않고 함수를 작성하시오. 또한 총 n개의 비교연산횟수가 어떻게 되는지 n에 관련하여 보이시오. (2) 비교연산횟수를 줄이는 방향으로 최대값, 최소값을 재귀적방법을 써서 분할 후 정복(devide and conquer)을 이용하여 최대값, 최소값을 구하는 알고리즘 함수를 보이시오. 또한 비교연산횟수는 n=2^k 일 때, n에 관하여 어떻게 나타나는지 보이시오.

[출처] 2004년 연세대 컴퓨터과학과 편입기출문제|작성자 백승지