[7급 국가직 자료구조론] 15년 1회차
7급 국가직 자료구조론 기출문제

15년 1회차

총 20문항 · 객관식 · A4 약 1장

1 / 1
A4정답 포함
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

15년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 함수를 이용하여 f1(4)를 수행한 결과 값은?
int f1(int n)
{
if (n <= 0)
return 0;
else if (n <= 2)
return n;
else
return f1(n-3) + f1(n-2) + f1(n-1);
}
13
24
35
46
정답 및 해설

f1(4)를 수행한 결과는 6이다.

n이 0 이하이면 0, 1~2이면 n을 그대로 반환하고, 3 이상이면 직전 세 값의 합을 반환한다. 따라서 f1(0)=0, f1(1)=1, f1(2)=2이다.

f1(3) = f1(0) + f1(1) + f1(2) = 0 + 1 + 2 = 3
f1(4) = f1(1) + f1(2) + f1(3) = 1 + 2 + 3 = 6

  • 값 3은 f1(3)의 결과로, f1(4)까지 전개하지 않은 값이다.
  • 값 5는 f1(n-3) 항을 빼고 두 항만 더했을 때(피보나치식) 나오는 값이다.
문제 2
다음 알고리즘의 시간 복잡도를 빅오(O) 표기법으로 표현한 것으로 옳은 것은?
Procedure calculate(int n)
{
int i, k, m, x = 0;
for (i = 0; i < (n - 5); i++)
for (k = 0; k < 100; k++)
for (m = 0; m < 1000; m++)
x++;
}
1O(logn)
2O(n)
3O(n2)
4O(n3)
정답 및 해설

시간 복잡도는 O(n)O(n)이다.

바깥 루프는 n−5회 돌고, 안쪽 두 루프는 n과 무관하게 100×1000회를 상수로 반복한다. 총 실행 횟수 100000(n−5)100000(n-5)에서 상수를 제거하면 n에 선형 비례한다.

  • O(log⁡n)O(\log n): 반복 변수가 배수로 늘거나 줄지 않으므로 로그 복잡도가 아니다.
  • O(n2)O(n^2): 안쪽 루프의 반복 횟수는 n이 아니라 고정값이다.
  • O(n3)O(n^3): 3중 루프이지만 n에 의존하는 루프는 바깥 하나뿐이다.
문제 3
다음 배열 데이터에서 첫 번째 원소 ‘66’을 피봇(pivot)으로 퀵정렬(Quick Sort)을 수행하는 경우, 순환 함수 quickSort()의 첫 번째 라운드가 완료되었을 때 생성된 배열 상태로 옳은 것은? (단, 퀵정렬 함수는 quickSort(int a[ ], int left, int right)이고, 매개변수 left와 right는 배열 a에서 정렬할 시작 위치와 끝 위치를 나타낸다)
int a[ ] = { 66, 51, 11, 98, 55, 1, 70, 35, 79, 41 };
111, 51, 35, 41, 55, 1, 66, 70, 79, 98
235, 51, 11, 41, 55, 1, 66, 70, 79, 98
355, 79, 70, 98, 66, 1, 11, 35, 51, 41
466, 79, 70, 98, 55, 1, 11, 35, 51, 41
정답 및 해설

첫 라운드 후 배열은 35, 51, 11, 41, 55, 1, 66, 70, 79, 98이다.

왼쪽에서는 피봇보다 큰 값, 오른쪽에서는 피봇보다 작은 값을 찾아 교환한다. 98과 41, 70과 35를 교환한 뒤 두 포인터가 교차하면 피봇 66을 교차 위치의 35와 맞바꾼다.

그 결과 66 왼쪽에는 작은 값, 오른쪽에는 큰 값만 남아 피봇이 최종 위치에 고정된다.

  • 11, 51, 35, 41, …로 시작하는 배열: 피봇과 맞바뀌는 값은 교차 위치의 35이므로 맨 앞이 11이 될 수 없다.
  • 55, 79, 70, 98, 66, …: 66 왼쪽에 79·70·98 같은 큰 값이 있어 분할 조건에 어긋난다.
  • 66, 79, 70, 98, 55, …: 피봇이 맨 앞에 그대로 있어 분할이 완료되지 않은 상태이다.
문제 4
행 우선(row major)으로 저장되는 3차원 배열 a[4][5][3]이 있을 때, 이 배열의 첫 번째 원소 a[0][0][0]의 주소를 α\alpha라고 하면, a[2][3][1]의 주소를 α+i\alpha + i로 표현했을 때 ii의 값은?
16
240
356
4168
정답 및 해설

i의 값은 40이다.

행 우선 3차원 배열 a[L][M][N]에서 a[i][j][k]의 위치(원소 단위)는 i×MN+j×N+ki \times MN + j \times N + k이다.

2×(5×3)+3×3+12 \times (5 \times 3) + 3 \times 3 + 1
=30+9+1=40= 30 + 9 + 1 = 40

  • 값 6은 첨자를 단순히 더한 값(2+3+1)으로 각 차원의 크기를 반영하지 않았다.
  • 값 56은 첫 첨자에 4×5, 둘째 첨자에 5를 곱해 가중치를 잘못 잡은 값(40+15+1)이다.
  • 값 168은 배열 전체 원소 수(4×5×3=60)보다 커서 이 배열의 위치가 될 수 없다.
문제 5
다음은 C 언어로 작성된 일차원 배열의 예제 프로그램이다. ㉠에 들어갈 수 있는 문장과 그 출력 결과로 옳게 짝지어진 것은?
int main()
{
int i, j, A[100];
for (i = 0; i < 100; i++)
A[i] = i;
j = i - 1;
printf("%d", ( ㉠ ));
}

㉠ 출력
1A[j] 100
2&A[0] + j 99
3*(A + j) 99
4*A + j 100
정답 및 해설

㉠에 *(A + j)를 넣으면 99가 출력된다.

for 문이 끝나면 i는 100이므로 j = 99이고, A[99]에는 99가 저장되어 있다. *(A + j)는 포인터 연산으로 A[j]와 같다.

  • A[j]: A[99]이므로 출력은 100이 아니라 99이다.
  • &A[0] + j: A[99]의 주소이므로 값 99가 출력되지 않는다.
  • *A + j: A[0] + j = 0 + 99 = 99이므로 100이 아니다.
문제 6
다항식을 표현하기 위하여 다음의 구조체를 정의하였다. 다항식 A(x)=∑i=0naixiA(x) = \sum_{i=0}^{n} a_i x^i에 대해 poly.degree = nn, poly.coef[ii] = an−ia_{n-i}로 표현되며, 구조체 멤버 중 degree는 다항식의 최고차수를 저장하고 배열 coef[MAX_DEGREE]는 다항식의 최고차수 항부터 최저 차수 항까지의 계수를 차례로 저장한다. 이때, 다항식 A(x)A(x)를 저장하기 위한 구조체 변수 poly의 선언 과정에서 다항식 ‘100×x5+60×x100 \times x^5 + 60 \times x’를 초기화하기 위한 ㉠의 내용으로 옳은 것은?
#define MAX_DEGREE 6
struct polynomial {
int degree;
int coef[MAX_DEGREE];
} poly = ( ㉠ ) ;
1{5, {100, 1, 60}}
2{5, {100, 60, 0, 0, 0, 1}}
3{5, {100, 0, 0, 0, 60, 0}}
4{5, {100, 0, 60}}
정답 및 해설

㉠에는 {5, {100, 0, 0, 0, 60, 0}}이 들어간다.

degree는 최고차수 5이고, coef에는 최고차수 항부터 x5x^5~x0x^0의 계수 6개를 차례로 넣는다. x4,x3,x2x^4, x^3, x^2 항과 상수항은 0, xx 항은 60이다.

  • {5, {100, 1, 60}}: 차수 1을 계수처럼 넣었고 빈 항의 0을 채우지 않았다.
  • {5, {100, 60, 0, 0, 0, 1}}: 60이 x4x^4 자리에 놓이고 상수항이 1이 된다.
  • {5, {100, 0, 60}}: 60이 x3x^3 자리에 놓여 다른 다항식이 된다.
문제 7
다음 중위 표현식(inorder expression)을 후위 표현식(postorder expression)으로 옳게 변환한 것은?
중위 표현식: Y = (1 + ((3 + 4 / 2) * 5 )) - 6
1Y 1 3 4 2 5 6 * / + + =
2Y = 1 3 4 2 / + 5 * + 6 -
3= Y 1 3 4 / 2 * 5 + + 6 -
4Y 1 3 4 2 / + 5 * + 6 - =
정답 및 해설

후위 표현식은 Y 1 3 4 2 / + 5 * + 6 - =이다.

대입 연산자 =는 우선순위가 가장 낮아 맨 마지막에 온다. 우변은 가장 안쪽부터 4 2 /, 3 4 2 / +, (…) 5 *, 1 (…) +, (…) 6 - 순으로 변환된다.

  • Y 1 3 4 2 5 6 * / + + =: 피연산자를 모두 앞에 몰아 연산 순서가 원식과 달라진다.
  • Y = 1 3 4 2 / + 5 * + 6 -: 대입 연산자가 피연산자 사이에 있어 후위 표기가 아니다.
  • = Y 1 3 4 / 2 * 5 + + 6 -: 대입 연산자가 앞에 오고, 4/2 대신 3/4를 먼저 계산해 순서가 틀렸다.
문제 8
다음은 연결리스트 스택의 삭제 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, 스택이 비었을 때 top은 NULL이고, top은 스택의 최상위 노드를 가리키는 포인터이다. 또한 스택이 빈 상태에서 맨 처음 삽입되는 노드의 next는 NULL이다)
typedef struct node{
int key;
struct node *next;
} NODE; // 스택의 노드 구조
NODE *top = NULL; // 스택의 최상위 노드를 가리키는 포인터
int pop(void) {
NODE *temp;
int ret;
if ( ( ㉠ ) ) {
printf("\n Stack underflow.");
return -1;
}
ret = top→key;
( ㉡ ) ;
( ㉢ ) ;
free(temp);
return ret;
}

㉠ ㉡ ㉢
1top→next == NULL temp = top→next top = top→next
2top→next == NULL temp = top top→next = temp→next
3top == NULL temp = top top = top→next
4top == NULL temp = top→next top→next = temp→next
정답 및 해설

㉠ top == NULL, ㉡ temp = top, ㉢ top = top→next 조합이 옳다.

스택이 비면 top이 NULL이므로 top == NULL로 공백을 검사한다. 이후 삭제할 최상위 노드를 temp에 보관하고 top을 다음 노드로 옮긴 뒤 temp를 해제한다.

  • top→next == NULL, temp = top→next, top = top→next: 노드가 하나일 때 언더플로로 오판하고, 최상위가 아닌 둘째 노드를 해제한다.
  • top→next == NULL, temp = top, top→next = temp→next: top이 바뀌지 않아 해제된 노드를 계속 가리킨다.
  • top == NULL, temp = top→next, top→next = temp→next: 최상위 노드가 아닌 둘째 노드를 삭제하게 된다.
문제 9
다음 그래프의 정점 A에서 시작하여 Prim 알고리즘을 적용하여 최소신장트리를 구축하고자 할 때, 설명으로 옳지 않은 것은?
1우선순위 큐를 활용하여 구현한다.
2탐욕(greedy) 기법을 이용한 알고리즘이다.
3마지막으로 선택되는 정점은 G이다.
4구축된 최소신장트리의 최소비용은 16이다.
정답 및 해설

A에서 Prim 알고리즘을 적용하면 최소신장트리의 총비용은 17이므로, 최소비용이 16이라는 설명이 옳지 않다.

트리에 붙은 정점과 붙지 않은 정점을 잇는 간선 중 가장 가벼운 것을 매번 고르면 C(3) → F(3) → H(1) → E(2) → B(1) → D(4) → G(3) 순으로 정점이 추가된다.
총비용 = 3 + 3 + 1 + 2 + 1 + 4 + 3 = 17

  • 우선순위 큐 활용: 후보 간선(또는 정점의 키 값) 중 최솟값을 반복해서 꺼내므로 우선순위 큐(힙)로 구현하는 것이 일반적이다.
  • 탐욕 기법: 매 단계 현재 가장 작은 비용의 간선을 선택하는 탐욕(greedy) 알고리즘이다.
  • 마지막 정점 G: 위 선택 순서에서 G는 D를 거쳐 비용 3으로 가장 마지막에 연결된다.
문제 10
다음은 이중연결리스트의 맨 앞에 새로운 키 값을 갖는 노드를 삽입하는 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, head는 이중연결리스트의 맨 앞 노드를 가리키는 포인터이며, 리스트는 초기에 비어있다고 가정한다)
struct node { // 이중연결리스트의 노드 구조
int key;
struct node *prev; // 이전 노드를 가리키는 포인터
struct node *next; // 다음 노드를 가리키는 포인터
};
struct node *head = NULL; // 맨 처음 노드를 가리키는 포인터
void insertDoubleList(int ikey)
{
struct node *temp;
temp = (struct node *) malloc(sizeof(struct node));
if (temp == NULL) {
printf("Memory allocation is failed. \n");
exit(1);
}
temp→key = ikey;
( ㉠ ) ;
if (head == NULL) // 리스트에 노드가 없는 경우
( ㉡ ) ;
else { // 리스트에 노드가 있는 경우
( ㉢ ) ;
head→prev = temp;
}
head = temp;
}

㉠ ㉡ ㉢
1temp→prev = NULL temp→prev = head temp→prev = head
2temp→prev = NULL temp→next = NULL temp→next = head
3head→next = temp temp→next = NULL temp→prev = head
4head→next = temp temp→prev = head temp→next = head
정답 및 해설

㉠ temp→prev = NULL, ㉡ temp→next = NULL, ㉢ temp→next = head 조합이 옳다.

맨 앞에 삽입되는 노드는 이전 노드가 없으므로 prev를 항상 NULL로 둔다. 리스트가 비어 있으면 다음 노드도 없어 next = NULL이고, 노드가 있으면 새 노드의 next가 기존 head를 가리킨 뒤 head→prev = temp로 양방향 연결을 완성한다.

  • temp→prev = NULL, temp→prev = head, temp→prev = head: prev만 덮어써 next가 초기화되지 않고 기존 노드와 연결되지 않는다.
  • head→next = temp, temp→next = NULL, temp→prev = head: 빈 리스트에서 NULL인 head의 next에 접근한다.
  • head→next = temp, temp→prev = head, temp→next = head: 빈 리스트에서 NULL 접근이 발생하고 연결 방향도 반대이다.
문제 11
다음 해시구조는 개방 주소법(open addressing) 중 선형 검색법(linear probing)을 사용하여 오버플로우를 처리하는 예제이다. 해시함수가 ‘입력되는 색인키의 첫 번째 문자에 대한 알파벳 순위’라고 가정할 때, 버킷 테이블의 ㉠, ㉡에 대한 접근 횟수로 옳게 짝지어진 것은? (예로, 해싱함수 h(alpha)=0, h(beta)=1, h(computer)=2, h(data)=3, h(email)=4, h(father)=5 등을 의미한다)
버킷색인키탐색에 필요한 버킷 접근 횟수
0ascii1
1atoi2
2char1
3define1
4equal1
5ceil㉠
6for㉡
…

㉠ ㉡
13 1
24 2
31 1
44 1
정답 및 해설

㉠은 4, ㉡은 2이다.

h(ceil)=2인데 버킷 2·3·4가 이미 차 있어 선형 검색으로 버킷 2, 3, 4, 5를 차례로 확인하므로 네 번 접근한다.

h(for)=5인데 버킷 5를 ceil이 차지하고 있어 버킷 5, 6을 확인하므로 두 번 접근한다.

  • ㉠ 3, ㉡ 1: ceil은 버킷 5까지 가야 하므로 세 번으로는 찾을 수 없다.
  • ㉠ 1, ㉡ 1: 두 키 모두 홈 버킷이 아닌 곳에 저장되어 한 번에 찾을 수 없다.
  • ㉠ 4, ㉡ 1: for의 홈 버킷 5는 ceil이 차지하고 있어 한 번에 찾을 수 없다.
문제 12
다음은 원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 추가하는 알고리즘의 의사코드이다. ㉠, ㉡에 들어갈 문장으로 옳은 것은? (단, 원형연결리스트에서 ‘last’는 리스트의 맨 마지막 노드를 가리키는 포인터이고 초기치는 NULL이며, 변수 ‘p’는 새로 삽입되는 노드를 나타낸다. 또한 리스트에 3개 이상의 노드를 추가할 수 있어야 한다)
struct node {
int key;
struct node *next;
} *last = NULL; //마지막 노드를 가리키는 포인터

Function insertFront(struct node *p)
if (last == NULL) then // 리스트가 빈 경우
last = p;
p→next = p;
else // 리스트에 하나 이상의 노드가 있는 경우
( ㉠ )
( ㉡ )
end if
return;

㉠ ㉡
1p→next = last→next; last→next = p;
2last→next = p; p→next = last→next;
3p→next = last; last→next = p;
4last→next = p; p→next = last;
정답 및 해설

㉠ p→next = last→next; 다음 ㉡ last→next = p; 순서가 옳다.

last→next가 맨 앞 노드이므로, 먼저 새 노드가 기존 맨 앞을 가리키게 한 뒤 last가 새 노드를 가리키게 해야 원형이 유지된다. 맨 앞 삽입이므로 last는 바꾸지 않는다.

  • last→next = p; 후 p→next = last→next;: 기존 맨 앞 주소를 먼저 덮어써 p가 자기 자신을 가리키게 된다.
  • p→next = last; last→next = p;: 새 노드가 마지막 노드를 가리켜 기존 맨 앞~중간 노드가 고리에서 끊긴다.
  • last→next = p; p→next = last;: last와 p 두 노드만의 고리가 되어 나머지 노드가 유실된다.
문제 13
다음 이진탐색트리(Binary Search Tree)에서 색인키 ‘20’을 삭제한 후, 트리를 재구성한 것으로 옳은 것은?
1
2
3
4
정답 및 해설

자식이 둘인 20을 삭제하면 오른쪽 서브트리의 최솟값(중위 후속자) 24가 그 자리로 올라가, 24의 왼쪽에 9(5, 14), 오른쪽에 28이 있고 28의 오른쪽 자식이 32인 트리가 된다.

20의 오른쪽 서브트리(28, 24, 32)에서 가장 작은 값은 단말 노드 24이므로, 24를 20 자리로 옮기고 원래 24 노드를 지운다. 그 결과 28은 왼쪽 자식을 잃고 오른쪽 자식 32만 남는다.

  • 20 자리에 28, 28의 오른쪽에 32, 32의 왼쪽에 24를 둔 트리: 24가 28보다 작은데 28의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.
  • 24의 오른쪽에 32, 32의 오른쪽에 28을 둔 트리: 28은 32보다 작으므로 32의 오른쪽 자식이 될 수 없다.
  • 20 자리에 32, 32의 오른쪽에 28, 28의 왼쪽에 24를 둔 트리: 28과 24가 32보다 작은데 32의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.
문제 14
calculate() 함수의 기능을 표현하는 수식으로 옳은 것은? (단, n은 양수만을 허용한다)
double calculate(float x, int n)
{
double t;
if (n < 0) exit(1);
if (n == 0) return 1.0;
else if (n % 2 == 0) {
t = calculate(x, n / 2);
return t * t;
}
else
return x * calculate(x, n - 1);
}
1xlog⁡2nx\log_2 n
2xlog⁡2nx^{\log_2 n}
3xnxn
4xnx^n
정답 및 해설

calculate(x, n)은 xnx^n을 계산한다.

n이 0이면 1, 짝수이면 (xn/2)2(x^{n/2})^2, 홀수이면 x⋅xn−1x \cdot x^{n-1}을 반환하는 분할 정복 거듭제곱이다.

예를 들어 n = 5이면 x⋅(x2)2=x5x \cdot (x^2)^2 = x^5이다.

  • xlog⁡2nx\log_2 n: 재귀 호출 횟수가 로그에 비례할 뿐, 반환값은 곱셈의 누적이다.
  • xlog⁡2nx^{\log_2 n}: 절반 지수의 결과를 다시 제곱하므로 지수가 줄지 않고 n이 된다.
  • xnxn: x를 n회 더하는 것이 아니라 곱한다.
문제 15
차수가 3인 B-트리에 G를 삽입한 후 모습은?
1
2
3
4
정답 및 해설

G를 넣으면 단말 노드가 넘쳐 중간 키 F가 부모로 올라가 루트가 [D, F], 자식이 [A, C]·[E]·[G]인 트리가 된다.

차수 3인 B-트리는 노드당 키를 최대 2개까지 가진다. G는 D보다 크므로 오른쪽 단말 [E, F]로 가서 [E, F, G]가 되어 넘치고, 분할로 E와 G가 나뉘며 F가 루트로 올라간다. 루트는 키가 1개뿐이었으므로 [D, F]로 수용된다.

  • 루트 [D, E], 단말 [A]·[C]·[F, G]인 트리: 삽입과 무관한 왼쪽 단말 [A, C]까지 쪼개져 있어 분할 결과가 아니다.
  • 루트 [C, F], 단말 [A, D]·[E]·[G]인 트리: 루트의 D가 아래로 내려가는 변화는 삽입 과정에서 일어나지 않는다.
  • 루트 [D, G], 단말 [A, C]·[E]·[F]인 트리: 분할 시에는 넘친 노드의 중간 키(F)가 올라가야 하며, G가 올라가면 F가 G보다 오른쪽 자리에 놓이는 모순도 생긴다.
문제 16
다음 최대힙(Max Heap) 트리를 일차원 배열에 표현할 경우, 배열에서 최댓값을 두 번 삭제한 후 남아있는 배열의 상태로 옳은 것은? (단, 최대힙 배열에서 첫 번째 요소는 비어있다)

최대힙의 배열 표현:
-978364512

1
-7364512
2
-7653412
3
-7653142
4
-7654321
정답 및 해설

최댓값을 두 번 삭제한 뒤의 배열은 7, 6, 5, 3, 1, 4, 2이다.

첫 번째 삭제: 루트 9를 빼고 마지막 원소 2를 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(2↔8, 2↔5).
결과: 8, 7, 5, 3, 6, 4, 2, 1

두 번째 삭제: 루트 8을 빼고 마지막 원소 1을 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(1↔7, 1↔6).
결과: 7, 6, 5, 3, 1, 4, 2

  • 7, 3, 6, 4, 5, 1, 2: 루트 7의 자식 3이 그 자식 4·5보다 작아 힙 조건을 어긴다.
  • 7, 6, 5, 3, 4, 1, 2: 1이 내려간 자리에 4가 와 있어 삭제 과정의 교환 결과와 다르다.
  • 7, 6, 5, 4, 3, 2, 1: 내림차순 정렬 상태로, 재힙화(sift-down) 결과가 아니다.
문제 17
다음 방향성 그래프에서 정점 ‘a’부터 시작하는 너비 우선 탐색(Breath First Search)을 수행하는 경우, 6번째로 방문될 수 있는 정점은? (단, 정점 ‘a’는 첫 번째 방문 노드라고 가정한다)
1e
2f
3g
4h
정답 및 해설

a에서 너비 우선 탐색을 하면 6번째로 방문될 수 있는 정점은 g이다.

BFS는 거리(간선 수) 순으로 방문한다. 거리 1은 a가 가리키는 b, h이고, 거리 2는 b가 가리키는 c, f이다(h는 나가는 간선이 없다). 따라서 둘째부터 다섯째까지는 b, h, c, f 순서 중 하나이며, 6번째는 거리 3인 d 또는 g가 된다.

  • e: d나 g를 거쳐야 도달하는 거리 4의 정점이라 마지막에 방문된다.
  • f: b에서 바로 도달하는 거리 2 정점이라 넷째 또는 다섯째에 방문된다.
  • h: a에서 바로 도달하는 거리 1 정점이라 둘째 또는 셋째에 방문된다.
문제 18
원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도 표현은?
㉠ 포인터 ptr이 원형연결리스트의 맨 앞 노드를 가리키는 경우

㉡ 포인터 ptr이 원형연결리스트의 맨 뒤 노드를 가리키는 경우
㉠ ㉡
1O(1)O(1) O(1)O(1)
2O(1)O(1) O(n)O(n)
3O(n)O(n) O(1)O(1)
4O(n)O(n) O(n)O(n)
정답 및 해설

맨 앞 삽입 시간은 ptr이 맨 앞을 가리키면 O(n)O(n), 맨 뒤를 가리키면 O(1)O(1)이다.

원형연결리스트에서 맨 앞에 노드를 넣으면 맨 뒤 노드의 링크를 새 노드로 바꿔야 원형이 유지된다. ㉠처럼 ptr이 맨 앞 노드를 가리키면 맨 뒤 노드를 찾기 위해 리스트를 한 바퀴 순회해야 하므로 O(n)O(n)이다. ㉡처럼 ptr이 맨 뒤 노드를 가리키면 맨 앞 노드는 ptr의 다음 노드로 바로 접근되므로 링크 두 개만 바꾸면 되어 O(1)O(1)이다.

  • O(1)O(1), O(1)O(1): ㉠에서 맨 뒤 노드를 찾는 순회 비용을 빠뜨렸다.
  • O(1)O(1), O(n)O(n): 두 경우의 복잡도를 거꾸로 짝지었다.
  • O(n)O(n), O(n)O(n): ㉡에서는 맨 뒤 노드가 이미 주어져 있어 순회가 필요 없다.
문제 19
다음 그래프는 각 정점들 사이의 거리를 간선에 나타낸 것이다. 정점 0에서 각 정점 1, 2, 3, 4, 5까지의 최단경로를 Dijkstra 최단경로 알고리즘으로 구할 때, 최단경로가 발견된 정점들의 순서로 옳은 것은?
10, 2, 3, 1, 5, 4
20, 2, 1, 3, 4, 5
30, 2, 4, 1, 3, 5
40, 1, 5, 2, 3, 4
정답 및 해설

Dijkstra 알고리즘으로 최단경로가 확정되는 순서는 0, 2, 1, 3, 4, 5이다.

매번 거리가 가장 짧은 미확정 정점을 확정하고 인접 정점의 거리를 갱신한다.
정점 2 확정(3) → 1은 3+6=9, 3은 3+15=18로 갱신
정점 1 확정(9) → 5는 9+30=39
정점 3 확정(18) → 4는 기존 20 유지
정점 4 확정(20) → 5는 20+3=23으로 갱신
정점 5 확정(23)

  • 0, 2, 3, 1, 5, 4: 2를 거친 경로로 1의 거리가 9가 되어 3(18)보다 먼저 확정된다.
  • 0, 2, 4, 1, 3, 5: 4의 거리 20은 1(9)·3(18)보다 크므로 먼저 확정될 수 없다.
  • 0, 1, 5, 2, 3, 4: 처음에는 거리 3인 2가 가장 가까워 먼저 확정되어야 한다.
문제 20
다음은 이진트리를 후위순회(postorder traversal)와 중위순회(inorder traversal)로 방문한 결과이다. 이 두 가지 순회 결과를 이용하여 이진트리를 구성한 것으로 옳은 것은?
Postorder 방문순서 : ADEBHGJKIFC
Inorder 방문순서 : ABDECGHFJIK
1
2
3
4
정답 및 해설

두 순회로 복원한 트리는 루트 C 아래 왼쪽 B(A, E), 오른쪽 F(G, I)이고, D는 E의 왼쪽 자식, H는 G의 오른쪽 자식, J·K는 I의 양쪽 자식인 트리이다.

후위순회의 마지막 C가 루트이고, 중위순회에서 C의 왼쪽 ABDE와 오른쪽 GHFJIK가 각 서브트리가 된다. 같은 방법을 반복하면 왼쪽은 후위 ADEB에서 B가 루트, 오른쪽은 후위 HGJKIF에서 F가 루트이며, 중위순회 위치로 각 자식의 좌우가 정해진다.

  • D를 A의 오른쪽 자식으로 둔 트리: 중위순회가 A, D, B, E…로 바뀌어 주어진 결과와 맞지 않는다.
  • H·J를 G의 양쪽 자식으로 둔 트리: J는 중위순회에서 F 뒤에 오므로 F의 오른쪽 서브트리(I 아래)에 있어야 한다.
  • H를 F의 왼쪽 자식으로 두고 G·J를 그 자식으로 둔 트리: 후위순회에서 H가 G보다 먼저 나오므로 G가 H의 부모여야 한다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
15년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 함수를 이용하여 f1(4)를 수행한 결과 값은?
int f1(int n)
{
if (n <= 0)
return 0;
else if (n <= 2)
return n;
else
return f1(n-3) + f1(n-2) + f1(n-1);
}
13
24
35
46
정답 및 해설

f1(4)를 수행한 결과는 6이다.

n이 0 이하이면 0, 1~2이면 n을 그대로 반환하고, 3 이상이면 직전 세 값의 합을 반환한다. 따라서 f1(0)=0, f1(1)=1, f1(2)=2이다.

f1(3) = f1(0) + f1(1) + f1(2) = 0 + 1 + 2 = 3
f1(4) = f1(1) + f1(2) + f1(3) = 1 + 2 + 3 = 6

  • 값 3은 f1(3)의 결과로, f1(4)까지 전개하지 않은 값이다.
  • 값 5는 f1(n-3) 항을 빼고 두 항만 더했을 때(피보나치식) 나오는 값이다.
문제 2
다음 알고리즘의 시간 복잡도를 빅오(O) 표기법으로 표현한 것으로 옳은 것은?
Procedure calculate(int n)
{
int i, k, m, x = 0;
for (i = 0; i < (n - 5); i++)
for (k = 0; k < 100; k++)
for (m = 0; m < 1000; m++)
x++;
}
1O(logn)
2O(n)
3O(n2)
4O(n3)
정답 및 해설

시간 복잡도는 O(n)O(n)이다.

바깥 루프는 n−5회 돌고, 안쪽 두 루프는 n과 무관하게 100×1000회를 상수로 반복한다. 총 실행 횟수 100000(n−5)100000(n-5)에서 상수를 제거하면 n에 선형 비례한다.

  • O(log⁡n)O(\log n): 반복 변수가 배수로 늘거나 줄지 않으므로 로그 복잡도가 아니다.
  • O(n2)O(n^2): 안쪽 루프의 반복 횟수는 n이 아니라 고정값이다.
  • O(n3)O(n^3): 3중 루프이지만 n에 의존하는 루프는 바깥 하나뿐이다.
문제 3
다음 배열 데이터에서 첫 번째 원소 ‘66’을 피봇(pivot)으로 퀵정렬(Quick Sort)을 수행하는 경우, 순환 함수 quickSort()의 첫 번째 라운드가 완료되었을 때 생성된 배열 상태로 옳은 것은? (단, 퀵정렬 함수는 quickSort(int a[ ], int left, int right)이고, 매개변수 left와 right는 배열 a에서 정렬할 시작 위치와 끝 위치를 나타낸다)
int a[ ] = { 66, 51, 11, 98, 55, 1, 70, 35, 79, 41 };
111, 51, 35, 41, 55, 1, 66, 70, 79, 98
235, 51, 11, 41, 55, 1, 66, 70, 79, 98
355, 79, 70, 98, 66, 1, 11, 35, 51, 41
466, 79, 70, 98, 55, 1, 11, 35, 51, 41
정답 및 해설

첫 라운드 후 배열은 35, 51, 11, 41, 55, 1, 66, 70, 79, 98이다.

왼쪽에서는 피봇보다 큰 값, 오른쪽에서는 피봇보다 작은 값을 찾아 교환한다. 98과 41, 70과 35를 교환한 뒤 두 포인터가 교차하면 피봇 66을 교차 위치의 35와 맞바꾼다.

그 결과 66 왼쪽에는 작은 값, 오른쪽에는 큰 값만 남아 피봇이 최종 위치에 고정된다.

  • 11, 51, 35, 41, …로 시작하는 배열: 피봇과 맞바뀌는 값은 교차 위치의 35이므로 맨 앞이 11이 될 수 없다.
  • 55, 79, 70, 98, 66, …: 66 왼쪽에 79·70·98 같은 큰 값이 있어 분할 조건에 어긋난다.
  • 66, 79, 70, 98, 55, …: 피봇이 맨 앞에 그대로 있어 분할이 완료되지 않은 상태이다.
문제 4
행 우선(row major)으로 저장되는 3차원 배열 a[4][5][3]이 있을 때, 이 배열의 첫 번째 원소 a[0][0][0]의 주소를 α\alpha라고 하면, a[2][3][1]의 주소를 α+i\alpha + i로 표현했을 때 ii의 값은?
16
240
356
4168
정답 및 해설

i의 값은 40이다.

행 우선 3차원 배열 a[L][M][N]에서 a[i][j][k]의 위치(원소 단위)는 i×MN+j×N+ki \times MN + j \times N + k이다.

2×(5×3)+3×3+12 \times (5 \times 3) + 3 \times 3 + 1
=30+9+1=40= 30 + 9 + 1 = 40

  • 값 6은 첨자를 단순히 더한 값(2+3+1)으로 각 차원의 크기를 반영하지 않았다.
  • 값 56은 첫 첨자에 4×5, 둘째 첨자에 5를 곱해 가중치를 잘못 잡은 값(40+15+1)이다.
  • 값 168은 배열 전체 원소 수(4×5×3=60)보다 커서 이 배열의 위치가 될 수 없다.
문제 5
다음은 C 언어로 작성된 일차원 배열의 예제 프로그램이다. ㉠에 들어갈 수 있는 문장과 그 출력 결과로 옳게 짝지어진 것은?
int main()
{
int i, j, A[100];
for (i = 0; i < 100; i++)
A[i] = i;
j = i - 1;
printf("%d", ( ㉠ ));
}

㉠ 출력
1A[j] 100
2&A[0] + j 99
3*(A + j) 99
4*A + j 100
정답 및 해설

㉠에 *(A + j)를 넣으면 99가 출력된다.

for 문이 끝나면 i는 100이므로 j = 99이고, A[99]에는 99가 저장되어 있다. *(A + j)는 포인터 연산으로 A[j]와 같다.

  • A[j]: A[99]이므로 출력은 100이 아니라 99이다.
  • &A[0] + j: A[99]의 주소이므로 값 99가 출력되지 않는다.
  • *A + j: A[0] + j = 0 + 99 = 99이므로 100이 아니다.
문제 6
다항식을 표현하기 위하여 다음의 구조체를 정의하였다. 다항식 A(x)=∑i=0naixiA(x) = \sum_{i=0}^{n} a_i x^i에 대해 poly.degree = nn, poly.coef[ii] = an−ia_{n-i}로 표현되며, 구조체 멤버 중 degree는 다항식의 최고차수를 저장하고 배열 coef[MAX_DEGREE]는 다항식의 최고차수 항부터 최저 차수 항까지의 계수를 차례로 저장한다. 이때, 다항식 A(x)A(x)를 저장하기 위한 구조체 변수 poly의 선언 과정에서 다항식 ‘100×x5+60×x100 \times x^5 + 60 \times x’를 초기화하기 위한 ㉠의 내용으로 옳은 것은?
#define MAX_DEGREE 6
struct polynomial {
int degree;
int coef[MAX_DEGREE];
} poly = ( ㉠ ) ;
1{5, {100, 1, 60}}
2{5, {100, 60, 0, 0, 0, 1}}
3{5, {100, 0, 0, 0, 60, 0}}
4{5, {100, 0, 60}}
정답 및 해설

㉠에는 {5, {100, 0, 0, 0, 60, 0}}이 들어간다.

degree는 최고차수 5이고, coef에는 최고차수 항부터 x5x^5~x0x^0의 계수 6개를 차례로 넣는다. x4,x3,x2x^4, x^3, x^2 항과 상수항은 0, xx 항은 60이다.

  • {5, {100, 1, 60}}: 차수 1을 계수처럼 넣었고 빈 항의 0을 채우지 않았다.
  • {5, {100, 60, 0, 0, 0, 1}}: 60이 x4x^4 자리에 놓이고 상수항이 1이 된다.
  • {5, {100, 0, 60}}: 60이 x3x^3 자리에 놓여 다른 다항식이 된다.
문제 7
다음 중위 표현식(inorder expression)을 후위 표현식(postorder expression)으로 옳게 변환한 것은?
중위 표현식: Y = (1 + ((3 + 4 / 2) * 5 )) - 6
1Y 1 3 4 2 5 6 * / + + =
2Y = 1 3 4 2 / + 5 * + 6 -
3= Y 1 3 4 / 2 * 5 + + 6 -
4Y 1 3 4 2 / + 5 * + 6 - =
정답 및 해설

후위 표현식은 Y 1 3 4 2 / + 5 * + 6 - =이다.

대입 연산자 =는 우선순위가 가장 낮아 맨 마지막에 온다. 우변은 가장 안쪽부터 4 2 /, 3 4 2 / +, (…) 5 *, 1 (…) +, (…) 6 - 순으로 변환된다.

  • Y 1 3 4 2 5 6 * / + + =: 피연산자를 모두 앞에 몰아 연산 순서가 원식과 달라진다.
  • Y = 1 3 4 2 / + 5 * + 6 -: 대입 연산자가 피연산자 사이에 있어 후위 표기가 아니다.
  • = Y 1 3 4 / 2 * 5 + + 6 -: 대입 연산자가 앞에 오고, 4/2 대신 3/4를 먼저 계산해 순서가 틀렸다.
문제 8
다음은 연결리스트 스택의 삭제 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, 스택이 비었을 때 top은 NULL이고, top은 스택의 최상위 노드를 가리키는 포인터이다. 또한 스택이 빈 상태에서 맨 처음 삽입되는 노드의 next는 NULL이다)
typedef struct node{
int key;
struct node *next;
} NODE; // 스택의 노드 구조
NODE *top = NULL; // 스택의 최상위 노드를 가리키는 포인터
int pop(void) {
NODE *temp;
int ret;
if ( ( ㉠ ) ) {
printf("\n Stack underflow.");
return -1;
}
ret = top→key;
( ㉡ ) ;
( ㉢ ) ;
free(temp);
return ret;
}

㉠ ㉡ ㉢
1top→next == NULL temp = top→next top = top→next
2top→next == NULL temp = top top→next = temp→next
3top == NULL temp = top top = top→next
4top == NULL temp = top→next top→next = temp→next
정답 및 해설

㉠ top == NULL, ㉡ temp = top, ㉢ top = top→next 조합이 옳다.

스택이 비면 top이 NULL이므로 top == NULL로 공백을 검사한다. 이후 삭제할 최상위 노드를 temp에 보관하고 top을 다음 노드로 옮긴 뒤 temp를 해제한다.

  • top→next == NULL, temp = top→next, top = top→next: 노드가 하나일 때 언더플로로 오판하고, 최상위가 아닌 둘째 노드를 해제한다.
  • top→next == NULL, temp = top, top→next = temp→next: top이 바뀌지 않아 해제된 노드를 계속 가리킨다.
  • top == NULL, temp = top→next, top→next = temp→next: 최상위 노드가 아닌 둘째 노드를 삭제하게 된다.
문제 9
다음 그래프의 정점 A에서 시작하여 Prim 알고리즘을 적용하여 최소신장트리를 구축하고자 할 때, 설명으로 옳지 않은 것은?
1우선순위 큐를 활용하여 구현한다.
2탐욕(greedy) 기법을 이용한 알고리즘이다.
3마지막으로 선택되는 정점은 G이다.
4구축된 최소신장트리의 최소비용은 16이다.
정답 및 해설

A에서 Prim 알고리즘을 적용하면 최소신장트리의 총비용은 17이므로, 최소비용이 16이라는 설명이 옳지 않다.

트리에 붙은 정점과 붙지 않은 정점을 잇는 간선 중 가장 가벼운 것을 매번 고르면 C(3) → F(3) → H(1) → E(2) → B(1) → D(4) → G(3) 순으로 정점이 추가된다.
총비용 = 3 + 3 + 1 + 2 + 1 + 4 + 3 = 17

  • 우선순위 큐 활용: 후보 간선(또는 정점의 키 값) 중 최솟값을 반복해서 꺼내므로 우선순위 큐(힙)로 구현하는 것이 일반적이다.
  • 탐욕 기법: 매 단계 현재 가장 작은 비용의 간선을 선택하는 탐욕(greedy) 알고리즘이다.
  • 마지막 정점 G: 위 선택 순서에서 G는 D를 거쳐 비용 3으로 가장 마지막에 연결된다.
문제 10
다음은 이중연결리스트의 맨 앞에 새로운 키 값을 갖는 노드를 삽입하는 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, head는 이중연결리스트의 맨 앞 노드를 가리키는 포인터이며, 리스트는 초기에 비어있다고 가정한다)
struct node { // 이중연결리스트의 노드 구조
int key;
struct node *prev; // 이전 노드를 가리키는 포인터
struct node *next; // 다음 노드를 가리키는 포인터
};
struct node *head = NULL; // 맨 처음 노드를 가리키는 포인터
void insertDoubleList(int ikey)
{
struct node *temp;
temp = (struct node *) malloc(sizeof(struct node));
if (temp == NULL) {
printf("Memory allocation is failed. \n");
exit(1);
}
temp→key = ikey;
( ㉠ ) ;
if (head == NULL) // 리스트에 노드가 없는 경우
( ㉡ ) ;
else { // 리스트에 노드가 있는 경우
( ㉢ ) ;
head→prev = temp;
}
head = temp;
}

㉠ ㉡ ㉢
1temp→prev = NULL temp→prev = head temp→prev = head
2temp→prev = NULL temp→next = NULL temp→next = head
3head→next = temp temp→next = NULL temp→prev = head
4head→next = temp temp→prev = head temp→next = head
정답 및 해설

㉠ temp→prev = NULL, ㉡ temp→next = NULL, ㉢ temp→next = head 조합이 옳다.

맨 앞에 삽입되는 노드는 이전 노드가 없으므로 prev를 항상 NULL로 둔다. 리스트가 비어 있으면 다음 노드도 없어 next = NULL이고, 노드가 있으면 새 노드의 next가 기존 head를 가리킨 뒤 head→prev = temp로 양방향 연결을 완성한다.

  • temp→prev = NULL, temp→prev = head, temp→prev = head: prev만 덮어써 next가 초기화되지 않고 기존 노드와 연결되지 않는다.
  • head→next = temp, temp→next = NULL, temp→prev = head: 빈 리스트에서 NULL인 head의 next에 접근한다.
  • head→next = temp, temp→prev = head, temp→next = head: 빈 리스트에서 NULL 접근이 발생하고 연결 방향도 반대이다.
문제 11
다음 해시구조는 개방 주소법(open addressing) 중 선형 검색법(linear probing)을 사용하여 오버플로우를 처리하는 예제이다. 해시함수가 ‘입력되는 색인키의 첫 번째 문자에 대한 알파벳 순위’라고 가정할 때, 버킷 테이블의 ㉠, ㉡에 대한 접근 횟수로 옳게 짝지어진 것은? (예로, 해싱함수 h(alpha)=0, h(beta)=1, h(computer)=2, h(data)=3, h(email)=4, h(father)=5 등을 의미한다)
버킷색인키탐색에 필요한 버킷 접근 횟수
0ascii1
1atoi2
2char1
3define1
4equal1
5ceil㉠
6for㉡
…

㉠ ㉡
13 1
24 2
31 1
44 1
정답 및 해설

㉠은 4, ㉡은 2이다.

h(ceil)=2인데 버킷 2·3·4가 이미 차 있어 선형 검색으로 버킷 2, 3, 4, 5를 차례로 확인하므로 네 번 접근한다.

h(for)=5인데 버킷 5를 ceil이 차지하고 있어 버킷 5, 6을 확인하므로 두 번 접근한다.

  • ㉠ 3, ㉡ 1: ceil은 버킷 5까지 가야 하므로 세 번으로는 찾을 수 없다.
  • ㉠ 1, ㉡ 1: 두 키 모두 홈 버킷이 아닌 곳에 저장되어 한 번에 찾을 수 없다.
  • ㉠ 4, ㉡ 1: for의 홈 버킷 5는 ceil이 차지하고 있어 한 번에 찾을 수 없다.
문제 12
다음은 원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 추가하는 알고리즘의 의사코드이다. ㉠, ㉡에 들어갈 문장으로 옳은 것은? (단, 원형연결리스트에서 ‘last’는 리스트의 맨 마지막 노드를 가리키는 포인터이고 초기치는 NULL이며, 변수 ‘p’는 새로 삽입되는 노드를 나타낸다. 또한 리스트에 3개 이상의 노드를 추가할 수 있어야 한다)
struct node {
int key;
struct node *next;
} *last = NULL; //마지막 노드를 가리키는 포인터

Function insertFront(struct node *p)
if (last == NULL) then // 리스트가 빈 경우
last = p;
p→next = p;
else // 리스트에 하나 이상의 노드가 있는 경우
( ㉠ )
( ㉡ )
end if
return;

㉠ ㉡
1p→next = last→next; last→next = p;
2last→next = p; p→next = last→next;
3p→next = last; last→next = p;
4last→next = p; p→next = last;
정답 및 해설

㉠ p→next = last→next; 다음 ㉡ last→next = p; 순서가 옳다.

last→next가 맨 앞 노드이므로, 먼저 새 노드가 기존 맨 앞을 가리키게 한 뒤 last가 새 노드를 가리키게 해야 원형이 유지된다. 맨 앞 삽입이므로 last는 바꾸지 않는다.

  • last→next = p; 후 p→next = last→next;: 기존 맨 앞 주소를 먼저 덮어써 p가 자기 자신을 가리키게 된다.
  • p→next = last; last→next = p;: 새 노드가 마지막 노드를 가리켜 기존 맨 앞~중간 노드가 고리에서 끊긴다.
  • last→next = p; p→next = last;: last와 p 두 노드만의 고리가 되어 나머지 노드가 유실된다.
문제 13
다음 이진탐색트리(Binary Search Tree)에서 색인키 ‘20’을 삭제한 후, 트리를 재구성한 것으로 옳은 것은?
1
2
3
4
정답 및 해설

자식이 둘인 20을 삭제하면 오른쪽 서브트리의 최솟값(중위 후속자) 24가 그 자리로 올라가, 24의 왼쪽에 9(5, 14), 오른쪽에 28이 있고 28의 오른쪽 자식이 32인 트리가 된다.

20의 오른쪽 서브트리(28, 24, 32)에서 가장 작은 값은 단말 노드 24이므로, 24를 20 자리로 옮기고 원래 24 노드를 지운다. 그 결과 28은 왼쪽 자식을 잃고 오른쪽 자식 32만 남는다.

  • 20 자리에 28, 28의 오른쪽에 32, 32의 왼쪽에 24를 둔 트리: 24가 28보다 작은데 28의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.
  • 24의 오른쪽에 32, 32의 오른쪽에 28을 둔 트리: 28은 32보다 작으므로 32의 오른쪽 자식이 될 수 없다.
  • 20 자리에 32, 32의 오른쪽에 28, 28의 왼쪽에 24를 둔 트리: 28과 24가 32보다 작은데 32의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.
문제 14
calculate() 함수의 기능을 표현하는 수식으로 옳은 것은? (단, n은 양수만을 허용한다)
double calculate(float x, int n)
{
double t;
if (n < 0) exit(1);
if (n == 0) return 1.0;
else if (n % 2 == 0) {
t = calculate(x, n / 2);
return t * t;
}
else
return x * calculate(x, n - 1);
}
1xlog⁡2nx\log_2 n
2xlog⁡2nx^{\log_2 n}
3xnxn
4xnx^n
정답 및 해설

calculate(x, n)은 xnx^n을 계산한다.

n이 0이면 1, 짝수이면 (xn/2)2(x^{n/2})^2, 홀수이면 x⋅xn−1x \cdot x^{n-1}을 반환하는 분할 정복 거듭제곱이다.

예를 들어 n = 5이면 x⋅(x2)2=x5x \cdot (x^2)^2 = x^5이다.

  • xlog⁡2nx\log_2 n: 재귀 호출 횟수가 로그에 비례할 뿐, 반환값은 곱셈의 누적이다.
  • xlog⁡2nx^{\log_2 n}: 절반 지수의 결과를 다시 제곱하므로 지수가 줄지 않고 n이 된다.
  • xnxn: x를 n회 더하는 것이 아니라 곱한다.
문제 15
차수가 3인 B-트리에 G를 삽입한 후 모습은?
1
2
3
4
정답 및 해설

G를 넣으면 단말 노드가 넘쳐 중간 키 F가 부모로 올라가 루트가 [D, F], 자식이 [A, C]·[E]·[G]인 트리가 된다.

차수 3인 B-트리는 노드당 키를 최대 2개까지 가진다. G는 D보다 크므로 오른쪽 단말 [E, F]로 가서 [E, F, G]가 되어 넘치고, 분할로 E와 G가 나뉘며 F가 루트로 올라간다. 루트는 키가 1개뿐이었으므로 [D, F]로 수용된다.

  • 루트 [D, E], 단말 [A]·[C]·[F, G]인 트리: 삽입과 무관한 왼쪽 단말 [A, C]까지 쪼개져 있어 분할 결과가 아니다.
  • 루트 [C, F], 단말 [A, D]·[E]·[G]인 트리: 루트의 D가 아래로 내려가는 변화는 삽입 과정에서 일어나지 않는다.
  • 루트 [D, G], 단말 [A, C]·[E]·[F]인 트리: 분할 시에는 넘친 노드의 중간 키(F)가 올라가야 하며, G가 올라가면 F가 G보다 오른쪽 자리에 놓이는 모순도 생긴다.
문제 16
다음 최대힙(Max Heap) 트리를 일차원 배열에 표현할 경우, 배열에서 최댓값을 두 번 삭제한 후 남아있는 배열의 상태로 옳은 것은? (단, 최대힙 배열에서 첫 번째 요소는 비어있다)

최대힙의 배열 표현:
-978364512

1
-7364512
2
-7653412
3
-7653142
4
-7654321
정답 및 해설

최댓값을 두 번 삭제한 뒤의 배열은 7, 6, 5, 3, 1, 4, 2이다.

첫 번째 삭제: 루트 9를 빼고 마지막 원소 2를 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(2↔8, 2↔5).
결과: 8, 7, 5, 3, 6, 4, 2, 1

두 번째 삭제: 루트 8을 빼고 마지막 원소 1을 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(1↔7, 1↔6).
결과: 7, 6, 5, 3, 1, 4, 2

  • 7, 3, 6, 4, 5, 1, 2: 루트 7의 자식 3이 그 자식 4·5보다 작아 힙 조건을 어긴다.
  • 7, 6, 5, 3, 4, 1, 2: 1이 내려간 자리에 4가 와 있어 삭제 과정의 교환 결과와 다르다.
  • 7, 6, 5, 4, 3, 2, 1: 내림차순 정렬 상태로, 재힙화(sift-down) 결과가 아니다.
문제 17
다음 방향성 그래프에서 정점 ‘a’부터 시작하는 너비 우선 탐색(Breath First Search)을 수행하는 경우, 6번째로 방문될 수 있는 정점은? (단, 정점 ‘a’는 첫 번째 방문 노드라고 가정한다)
1e
2f
3g
4h
정답 및 해설

a에서 너비 우선 탐색을 하면 6번째로 방문될 수 있는 정점은 g이다.

BFS는 거리(간선 수) 순으로 방문한다. 거리 1은 a가 가리키는 b, h이고, 거리 2는 b가 가리키는 c, f이다(h는 나가는 간선이 없다). 따라서 둘째부터 다섯째까지는 b, h, c, f 순서 중 하나이며, 6번째는 거리 3인 d 또는 g가 된다.

  • e: d나 g를 거쳐야 도달하는 거리 4의 정점이라 마지막에 방문된다.
  • f: b에서 바로 도달하는 거리 2 정점이라 넷째 또는 다섯째에 방문된다.
  • h: a에서 바로 도달하는 거리 1 정점이라 둘째 또는 셋째에 방문된다.
문제 18
원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도 표현은?
㉠ 포인터 ptr이 원형연결리스트의 맨 앞 노드를 가리키는 경우

㉡ 포인터 ptr이 원형연결리스트의 맨 뒤 노드를 가리키는 경우
㉠ ㉡
1O(1)O(1) O(1)O(1)
2O(1)O(1) O(n)O(n)
3O(n)O(n) O(1)O(1)
4O(n)O(n) O(n)O(n)
정답 및 해설

맨 앞 삽입 시간은 ptr이 맨 앞을 가리키면 O(n)O(n), 맨 뒤를 가리키면 O(1)O(1)이다.

원형연결리스트에서 맨 앞에 노드를 넣으면 맨 뒤 노드의 링크를 새 노드로 바꿔야 원형이 유지된다. ㉠처럼 ptr이 맨 앞 노드를 가리키면 맨 뒤 노드를 찾기 위해 리스트를 한 바퀴 순회해야 하므로 O(n)O(n)이다. ㉡처럼 ptr이 맨 뒤 노드를 가리키면 맨 앞 노드는 ptr의 다음 노드로 바로 접근되므로 링크 두 개만 바꾸면 되어 O(1)O(1)이다.

  • O(1)O(1), O(1)O(1): ㉠에서 맨 뒤 노드를 찾는 순회 비용을 빠뜨렸다.
  • O(1)O(1), O(n)O(n): 두 경우의 복잡도를 거꾸로 짝지었다.
  • O(n)O(n), O(n)O(n): ㉡에서는 맨 뒤 노드가 이미 주어져 있어 순회가 필요 없다.
문제 19
다음 그래프는 각 정점들 사이의 거리를 간선에 나타낸 것이다. 정점 0에서 각 정점 1, 2, 3, 4, 5까지의 최단경로를 Dijkstra 최단경로 알고리즘으로 구할 때, 최단경로가 발견된 정점들의 순서로 옳은 것은?
10, 2, 3, 1, 5, 4
20, 2, 1, 3, 4, 5
30, 2, 4, 1, 3, 5
40, 1, 5, 2, 3, 4
정답 및 해설

Dijkstra 알고리즘으로 최단경로가 확정되는 순서는 0, 2, 1, 3, 4, 5이다.

매번 거리가 가장 짧은 미확정 정점을 확정하고 인접 정점의 거리를 갱신한다.
정점 2 확정(3) → 1은 3+6=9, 3은 3+15=18로 갱신
정점 1 확정(9) → 5는 9+30=39
정점 3 확정(18) → 4는 기존 20 유지
정점 4 확정(20) → 5는 20+3=23으로 갱신
정점 5 확정(23)

  • 0, 2, 3, 1, 5, 4: 2를 거친 경로로 1의 거리가 9가 되어 3(18)보다 먼저 확정된다.
  • 0, 2, 4, 1, 3, 5: 4의 거리 20은 1(9)·3(18)보다 크므로 먼저 확정될 수 없다.
  • 0, 1, 5, 2, 3, 4: 처음에는 거리 3인 2가 가장 가까워 먼저 확정되어야 한다.
문제 20
다음은 이진트리를 후위순회(postorder traversal)와 중위순회(inorder traversal)로 방문한 결과이다. 이 두 가지 순회 결과를 이용하여 이진트리를 구성한 것으로 옳은 것은?
Postorder 방문순서 : ADEBHGJKIFC
Inorder 방문순서 : ABDECGHFJIK
1
2
3
4
정답 및 해설

두 순회로 복원한 트리는 루트 C 아래 왼쪽 B(A, E), 오른쪽 F(G, I)이고, D는 E의 왼쪽 자식, H는 G의 오른쪽 자식, J·K는 I의 양쪽 자식인 트리이다.

후위순회의 마지막 C가 루트이고, 중위순회에서 C의 왼쪽 ABDE와 오른쪽 GHFJIK가 각 서브트리가 된다. 같은 방법을 반복하면 왼쪽은 후위 ADEB에서 B가 루트, 오른쪽은 후위 HGJKIF에서 F가 루트이며, 중위순회 위치로 각 자식의 좌우가 정해진다.

  • D를 A의 오른쪽 자식으로 둔 트리: 중위순회가 A, D, B, E…로 바뀌어 주어진 결과와 맞지 않는다.
  • H·J를 G의 양쪽 자식으로 둔 트리: J는 중위순회에서 F 뒤에 오므로 F의 오른쪽 서브트리(I 아래)에 있어야 한다.
  • H를 F의 왼쪽 자식으로 두고 G·J를 그 자식으로 둔 트리: 후위순회에서 H가 G보다 먼저 나오므로 G가 H의 부모여야 한다.