• 검색 결과가 없습니다.

중간고사 (데이터 구조 1)

N/A
N/A
Protected

Academic year: 2021

Share "중간고사 (데이터 구조 1)"

Copied!
3
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

- 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)

- 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)

- 3 -

c. b)에서 변환된 후위 식을 스택을 이용하여 평가하라. 스택의 상태가 변경될 때마다 그 상태를 보여주면서 단계적 으로 그 변환과정을 보여라.

참조

관련 문서

허락 없이 복제하거나 다른 매체에 옮겨 실을 수 없으며, 상업적 용도로 사용할 수 없습니다.... 지금 당장 QR

허락 없이 복제하거나 다른 매체에 옮겨 실을 수 없으며, 상업적 용도로 사용할 수 없습니다.... 지금 당장 QR

모델 학습이 완료되면 [추가하기] 버튼을 눌러 엔트리 만들기 화면으로 이동합니다... 지금까지 완성된 코드를 시작하기를 눌러 마스크 감지 결과에 따라

종이컵의 개수에 따라 일정하게 늘어나는 탄소발자국의 양을 함수 의 그래프로 나타내보는 과정에서 그래프를 이해하고

– 즉 모든 네트워크 트래픽을 필터링하여 정확한 암호와 보안 코드를 가지고 있는 허가된 프로세스만을 통과시킴.

다음 단계는 흐름 시스템(하천 시스템 모형도), 횡단면 데이터, 그리고 수리 구조 데이터(교량, 암거, 위어 등등)에 대한 정보와 관련성을 구성하고 있는,

z 멱급수 해법으로 얻을 수 있는 유명한 특수함수 : 베셀 함수 ( Bessel function ), 르장드르 함수 ( Legendre function ), 가우스 ( Gauss ) 의 초기화함수(

예&gt; 발표에 대해 부정적 경험을 가지고 있는 경우 발표에 대한 부정적 정서를 극복하기 위해서 흥미 있는 주제에 대해 발표할 수 있는 기회를 제공하거나