- 1 -
중간고사 (데이터 구조 1)
2020. 5. 18
학번: 성명:
1. 다음 C 코드를 고려하라. (5*2 = 10) int i = 0, k = n;
while (k > 0) { i += k;
k /= 2;
}
a. 위 코드에 대한 시간복잡도 함수 T(n)을 구하라. 그 이유를 주라. (2) T(n) = 5log2n + 2 where
할당 연산: 2
while 문 반복 회수: log2n (왜냐면, 한번 반복시 k는 1/2이되고, k의 초기값이 n이고, k =1일 때까지 반복된 다. 반복 회수가 r이라고 하면, n/2^r = 1이 성립하고, 2^r = 1로부터 r = log2n. 즉 반복 회수는 log2n이 된다.)
while 문 몸체 내 연산: 비교 1번, 할당 2번, 덧셈 1번, 나눗셈 1번
b. a)의 T(n)에 대한 빅오 표기법을 주라. 그 이유를 주시오(2). 빅오 표기법 정의를 이용하라. O(logn) 이유: 빅오 표기법 정의: ∋ C, n0 s.t. |f(n)| <= |g(n)|, for n>= n0이면 f(n) = O(g(n))
문제에서, f(n) = 5log2n + 2, g(n) = log2n
5log2n + 2 <= 8log2n, n>=2이므로 C = 8, n0 = 2일 때 빅오 표기법 정의를 만족한다.
따라서 T(n) = O(log2n)
2. n개의 원판과 A, B, C의 3개의 막대가 주어져 있을 때, 막대 A에 쌓여 있는 n개의 모든 원판을 막대 B를 이용하 면서 막대 C로 옮기고자 한다. 단, 각 원판의 크기는 다르며, 크기가 작은 원판 위에 큰 원판을 쌓는 것은 허용되지 않으며, 한 번에 하나의 원판만 이동할 수 있다. 다음에 답하시오. (5*2 = 10)
a. 원판의 개수 n를 B를 이용하여 A에서 C로 이동할 때 최소 이동 회수를 구하는 순환 알고리즘 hanoi_count(n, A, B, C)를 작성하라. 단, 함수 매개변수 외에 다른 변수를 사용하면 안된다.
int hanoi(n, A, B, C) { if (n == 1) return 1; // 1) else {
return hanoi(n – 1, A, C, B) + 1 + hanoi(n-1, B, A, C); // 2) }
}
* 전역변수 사용: -2
b. 원판의 개수가 n일 때, 최소 이동 회수를 a)의 알고리즘을 이용하여 구하라. 그 과정을 기술해야 한다.
2^n – 1 (과정이 없으면 –3)
Hn이 n개의 원판에 대한 최소 이동회수라고 하면, a)의 알고리즘에서,
코드 1)로부터 H1 =1,
코드 2)로부터 Hn = 2H(n-1) + 1
= 2(2Hn-2 +1) +1 = 2^2Hn-2 + 2 + 1
= 2^2(2(Hn-3+1) + 2 + 1 = 2^3Hn-3 + 2^2 + 2 + 1
= ...
= 2^(n-1)H1 + 2^(n-2) + ... 2 + 1
= 2^(n-1) + 2^(n-2) + ... + 2 + 1 = 2^n - 1
3. 다음과 같이 2개의 노드로 연결된 동적 구조체를 생성하고자 한다. 다음에 답하시오. (10)
- 2 -
a. 노드는 (val, next)의 두 필드로 구성되며, val은 정수이며, next는 다른 노드를 가리키거나 NULL이다. 노드의 타 입 nodeType을 C 문장으로 정의하라. (2)
typedef struct node { int val;
struct node* next; // *가 없으면 0 } nodeType;
b. 변수 p를 선언하는 C 문장을 작성하라. (2)
nodeType *p; // a)가 정답이 아니어도 점수 부여
c. 위와 같은 동적 구조체를 생성하는 C 문장을 작성하라. 단, 변수는 p만 사용해야 한다. (6) p = (nodeType *) malloc(sizeof(nodeType)); // (2)
p->val = 10; p->next = NULL:
p->next = (nodeType *) malloc(sizeof(nodeType));
p->next->val = 20; p->next->next = NULL;
4. 다음 함수 reverse()는 정수 n을 매개변수로 전달받아서 스택을 이용하여 n의 역수를 구하여 반환하는 C 함수이 다. 이 함수는 n = 1234일 때, 그 역순인 4321을 반환한다. (15)
int reverse(int n) { stack_type s; // 스택 생성 init(&s); // 스택 초기화
// ① n에 포함된 숫자(digit)들을 뒤에서부터 순서대로 스택에 저장한다.
while (n != 0) { d = n % 10;
push(&s, d);
n = n / 10;
}
// ② 스택으로부터 숫자들을 가져와서 n의 역순을 만든다.
n = 0; fac = 1;
while (!is_empty(s)) { n = n + pop(&s) * fac;
fac *= 10;
}
return n; // 역순 n을 반환한다 }
a. ①의 코드를 작성하라. (7)
b. ②의 코드를 작성하라. (8)
5. 다음 수식을 고려하라(5*3 = 15): “2 * (9 - (2 + 3) + 1). 또한, 스택 S를 가정한다. 스택은 초기화되어 있으며, 이때 top의 값은 –1이다.
a. 위의 수식에 대한 후위식 표현은 무엇인가?
2 9 2 3 + - 1 + *
b. 위의 수식을 스택 s를 이용하여 후위 식으로 변환하는 과정을 보여라. 스택의 상태를 단계적으로, 즉 스택 상태가 변경될 때마다 그 상태를 보여주어야 한다. 스택 상태는 스택 내용과 top의 값으로 표현된다.
- 3 -
c. b)에서 변환된 후위 식을 스택을 이용하여 평가하라. 스택의 상태가 변경될 때마다 그 상태를 보여주면서 단계적 으로 그 변환과정을 보여라.