[7급 국가직 자료구조론] 18년 1회차 기출문제 정답·해설 페이지
- 삽입 정렬: 새 원소를 이미 정렬된 앞부분의 알맞은 위치에 끼워 넣는 방식으로, 구간 끝까지 인접 교환을 되풀이하는 이 구조와 다르다.
- 선택 정렬: 한 바퀴에서 최솟값(또는 최댓값)의 위치를 찾은 뒤 한 번만 교환하므로, 비교할 때마다 교환하는 이 코드와 다르다.
- 힙 정렬: 배열을 힙으로 구성한 뒤 루트를 꺼내며 부모·자식 인덱스 관계로 재조정하는 방식이다.
- 1: 아홉 번째로 push 되는 피연산자이다.
- 2: 두 번째·다섯 번째·일곱 번째 등에 push 되는 값이다.
- 4: 첫 번째로 push 되는 피연산자이자 마지막 계산 결과이다.
- 43, (A, G): 마지막 간선은 맞지만 최소 비용은 42이다.
- 44, (F, G): (F, G)는 가중치 13으로 (A, G)의 11보다 커서 신장 트리에 포함되지 않고, 비용도 42가 아니다.
- 45, (F, G): 마지막 간선과 비용이 모두 계산 결과와 다르다.
- 6, 5, 7, 3, 8, 9, 1, 4, 0, 2: 시작 정점에서 가까운 정점부터 차례로 방문한 너비 우선 탐색(BFS)의 순서이다.
- 6, 5, 3, 4, 2, 1, 0, 7, 8, 9: 3의 인접 정점 중 1이 4보다 작으므로 1을 먼저 방문해야 한다.
- 6, 5, 7, 3, 1, 4, 0, 2, 8, 9: 5에서 3이 7보다 작은데 7을 먼저 방문해 오름차순 조건에 어긋난다.
- ㄱ(옳음): SWAP은 바깥 반복마다 조건 없이 한 번씩 수행되므로 회이다.
- ㄴ(옳음): 두 번째 SWAP 직후 배열은 3, 4, 8, 6, 9이다.
- ㄷ(틀림): 입력 상태와 관계없이 비교가 회 일어나므로 시간 복잡도는 이다.
- 5, 4, 7, 3, 6, 8: 회전 없이 바로 위 모양이 된다.
- 7, 5, 8, 6, 4, 3: 7(5(4, 6), 8)에서 3을 넣으면 루트 7에서 LL 불균형이 생기고, 오른쪽 회전으로 5가 루트가 된다.
- 8, 7, 5, 4, 6, 3: 8, 7, 5에서 LL 회전으로 7(5, 8)이 되고, 4, 6, 3을 넣은 뒤 다시 LL 회전으로 5가 루트가 된다.
- 루트 키가 4와 6 중 하나: 삭제 노드를 중위 선행자나 중위 후속자로 대체하므로 옳다.
- 중위 순회 순서 1, 2, 3, 4, 6, 7, 8, 9: 이진 탐색 트리의 중위 순회는 남은 키의 오름차순이므로 옳다.
- 차수의 합 7: 노드가 8개이면 간선은 7개이고, 각 간선이 부모의 차수를 1씩 늘리므로 옳다.
- 인천→서울→대구: 3 + 17 = 20 (최단)
- 인천→서울→대전→대구: 3 + 15 + 9 = 27
- 인천→대전→대구: 25 + 9 = 34
- 루트 2(자식 1, 3):
- 루트 1, 오른쪽 자식 3, 3의 왼쪽 자식 2:
- 루트 3인 트리: 확률이 가장 큰 키 1이 깊이 2 이상에 놓여 평균이 2를 넘는다.
- [0]에 13, [6]에 3을 둔 배치: 13은 [1], 3은 [0]에 들어가므로 틀리다.
- [0]에 16, [1]에 13을 둔 배치: 16은 첫 충돌 후 [6]에 들어가므로 틀리다.
- [1]에 11, [4]에 2, [5]에 3을 둔 배치: 11은 충돌 없이 [4], 2는 [5]에 들어가므로 틀리다.
- 9, 5, 7, 2, 9, 4, 6, 3: 먼저 넣은 값부터 꺼내는 큐(FIFO) 방식으로 처리한 순서이다.
- 2, 3, 6, 4, 9, 2, 7, 5: 첫 pop()의 결과가 9이어야 하므로 시작부터 맞지 않는다.
- 9, 5, 9, 4, 7, 6, 2, 2: 두 번째 pop()에서 맨 위의 2가 아닌 바닥 쪽 5를 꺼낸 것으로 틀리다.
- 17: G의 인덱스 값일 뿐이며 H의 위치 34를 담지 못한다.
- 18: G(인덱스 17)까지만 담는 크기로 H의 위치 34를 담지 못한다.
- 34: 최대 인덱스 34를 담으려면 인덱스 0을 포함해 원소가 35개 필요하므로 하나 부족하다.
- 2800: 원소 수 752에 원소 크기 4를 곱하지 않고 그대로 더한 값이다.
- 2804: 원소 크기 4를 곱하면 오프셋이 3008바이트이므로 3000 미만의 주소는 나올 수 없다.
- 5052: 앞선 원소 수를 751로 잘못 세어 원소 하나만큼 앞선 주소이다.
- current->next = current->next->next; 를 먼저 수행하는 순서: current의 오른쪽 노드를 삭제하는 연산이라 문제의 대상과 다르다.
- current->next->prev = current; 를 먼저 수행하는 순서: 역시 current의 오른쪽 노드를 다루며, 순서도 뒤바뀌어 오른쪽 노드 삭제로도 성립하지 않는다.
- current->prev->next = current; 를 먼저 수행하는 순서: 이때 current->prev는 아직 삭제할 노드이므로 삭제할 노드의 next만 바뀌고, 두 칸 왼쪽 노드의 next는 계속 삭제할 노드를 가리킨다.
- 13, 5: 호출 횟수와 반환값을 모두 작게 센 값이다.
- 13, 8: 반환값은 맞지만 호출 횟수를 15보다 적게 셌다.
- 15, 5: 호출 횟수는 맞지만 5는 R(4)의 값이고 R(5)는 8이다.
- 2: 계산값 3.03을 반올림한 결과보다 작다.
- 4: 키 24가 실제로 저장된 위치일 뿐, 첫 탐색 위치는 비례 계산으로 정해진다.
- 5: 계산값 3.03을 반올림한 결과보다 크다.
- last = new_node; 를 둘째로 수행하는 순서: 기존 마지막 노드가 new_node와 연결되지 않고, new_node가 자기 자신을 가리키게 된다.
- last->link = new_node; 를 먼저 수행하는 순서: 처음 노드의 주소를 잃어 new_node->link가 자기 자신을 가리키게 된다.
- last = new_node; 를 먼저 수행하는 순서: 기존 마지막 노드를 가리킬 방법이 없어져 리스트에 연결할 수 없다.
- {4, 4, 4}로 시작하고 행 순서로 나열한 것: 행·열 개수 자리에 최대 인덱스 4를 잘못 적었다.
- {4, 4, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 행·열 개수도 틀리고, 열 번호 기준으로 정렬해 규칙에도 어긋난다.
- {5, 5, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 첫 구조체는 맞지만 열 번호 기준으로 정렬해 행 번호 오름차순 규칙에 어긋난다.
- 12: 일렬 경로 모양(12개)만 세고 한 정점에 나머지 셋이 붙는 별 모양(4개)을 빠뜨린 값이다.
- 14: 사이클이 되는 조합은 삼각형 4가지뿐이므로 20에서 6을 뺀 이 값은 맞지 않는다.
- 18: 사이클 조합을 2가지만 제외한 셈이 되어 맞지 않는다.
- 1, 3, 6, 2, 9, 8, 7: 루트를 7로 본 순서로, 루트 2는 회전 없이 그대로 유지된다.
- 1, 6, 3, 2, 9, 8, 7: 루트를 7로 잘못 잡았고 6과 3의 부모·자식 관계도 뒤바뀌었다.
- 1, 6, 3, 7, 9, 8, 2: 회전 없이 6을 3의 오른쪽 자식으로 둔 것으로, 이중 회전 후에는 6이 3과 7의 부모가 된다.
다음 C 언어 함수에 의해 구현된 정렬 방식은?void whatsort(int a[ ], int size)
{
int i, j, temp;
for (i = (size-1); i > 0; i--) {
for (j = 1; j <= i; j++) {
if (a[j-1] > a[j]) {
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
삽입 정렬(insertion sort)
선택 정렬(selection sort)
힙 정렬(heap sort)
버블 정렬(bubble sort)
이 함수는 버블 정렬을 구현한 것이다.
안쪽 반복에서 인접한 두 원소 a[j-1]과 a[j]를 비교해 앞쪽이 크면 교환하므로, 한 바퀴가 끝날 때마다 가장 큰 값이 구간 맨 뒤(i 위치)로 밀려난다. 바깥 반복은 이 구간을 한 칸씩 줄여 간다.
오류나 개정된 내용이 보이면 알려주세요
다음 중위 표현식(infix expression)을 후위 표현식(postfix expression)으로 변환한 후, 스택을 이용하여 후위 표현식을 계산하고자 한다. 후위 표현식의 계산 과정에서 스택에 여덟 번째로 삽입(push)되는 값은?( 4 + 2 ) / 3 + ( 6 / 2 - 1 )
1
2
3
4
후위 표현식 계산 중 여덟 번째로 push 되는 값은 3이다.
중위식을 변환하면 4 2 + 3 / 6 2 / 1 - +가 된다. 피연산자는 그대로 push 하고, 연산자를 만나면 두 값을 pop 해 계산한 결과를 다시 push 한다.
push 순서: 4 → 2 → 6(4+2) → 3 → 2(6/3) → 6 → 2 → 3(6/2) → 1 → 2(3-1) → 4(2+2)
오류나 개정된 내용이 보이면 알려주세요
Prim 알고리즘을 사용하여 다음 가중 그래프(weighted graph)의 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선은? (단, 시작 정점은 A이다)
42, (A, G)
43, (A, G)
44, (F, G)
45, (F, G)
A에서 Prim 알고리즘을 적용하면 최소 비용은 42이고, 마지막으로 선택되는 간선은 (A, G)이다.
Prim 알고리즘은 이미 선택된 정점 집합과 나머지 정점을 잇는 간선 중 가중치가 가장 작은 간선을 하나씩 추가한다. 선택 순서는 (A, B) 10 → (B, C) 5 → (C, E) 3 → (E, F) 7 → (F, D) 6 → (A, G) 11 이다.
합계는 이다. G는 (A, G) 11과 (F, G) 13으로만 연결되므로 마지막에 더 가벼운 (A, G)가 선택된다.
오류나 개정된 내용이 보이면 알려주세요
시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: Depth First Search)의 방문 순서는? (단, 인접한 정점들은 오름차순으로 방문한다)
6, 5, 3, 1, 0, 2, 4, 7, 8, 9
6, 5, 7, 3, 8, 9, 1, 4, 0, 2
6, 5, 3, 4, 2, 1, 0, 7, 8, 9
6, 5, 7, 3, 1, 4, 0, 2, 8, 9
정점 6에서 인접 정점을 오름차순으로 방문하는 DFS의 방문 순서는 6, 5, 3, 1, 0, 2, 4, 7, 8, 9이다.
6의 인접 정점(5, 7) 중 작은 5로 가고, 5에서 3, 3에서 1, 1에서 0으로 내려간다. 0은 더 갈 곳이 없어 되돌아가(backtracking) 1의 다음 인접 정점 2, 이어서 4를 방문한다.
4의 인접 정점은 모두 방문했으므로 5까지 되돌아가 7을 방문하고, 7에서 8, 9 순으로 방문하면 탐색이 끝난다.
오류나 개정된 내용이 보이면 알려주세요
C 언어 함수로 구현된 <정렬 알고리즘>과 크기가 5인 배열 list를 이용하여 sort(list, 5)를 수행하였다. <설명>에서 옳은 것만을 모두 고르면? (단, sort(list, 5) 수행 전에 list 배열에 4, 9, 8, 6, 3이 순서대로 저장되어 있다)<정렬 알고리즘>#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[ ], int n)
{
int i, j, least, temp;
for (i = 0; i < n - 1; i++) {
least = i;
for (j = i + 1; j < n; j++)
if (list[j] < list[least]) least = j;
SWAP(list[i], list[least], temp);
}
}<설 명>
ㄱ. sort(list, 5)의 수행이 완료될 때까지 SWAP은 4회 수행된다.
ㄴ. SWAP이 두 번째 수행된 후 배열 list에는 3, 4, 8, 6, 9가 순서대로 저장되어 있다.
ㄷ. 정렬 알고리즘의 시간 복잡도를 빅세타(Θ) 표기법으로 표현한 것은 Θ(nlogn)이다.
ㄱ
ㄱ, ㄴ
ㄱ, ㄷ
ㄴ, ㄷ
옳은 것은 ㄱ, ㄴ이다. 이 코드는 매 단계 최솟값을 골라 앞자리와 교환하는 선택 정렬이다.
4, 9, 8, 6, 3 → (i=0, 최솟값 3) 3, 9, 8, 6, 4 → (i=1, 최솟값 4) 3, 4, 8, 6, 9 → (i=2, 최솟값 6) 3, 4, 6, 8, 9 → (i=3, 최솟값 8, 자기 자신과 교환) 3, 4, 6, 8, 9
오류나 개정된 내용이 보이면 알려주세요
공백 AVL 트리에 데이터를 순서대로 삽입하여 AVL 트리를 구성할 때, 나머지와 다른 모습의 AVL 트리가 구성되는 데이터 키(key)들의 순서는?
3, 4, 6, 5, 7, 8
5, 4, 7, 3, 6, 8
7, 5, 8, 6, 4, 3
8, 7, 5, 4, 6, 3
나머지와 다른 AVL 트리가 만들어지는 순서는 3, 4, 6, 5, 7, 8이다.
3, 4, 6 삽입 시 RR 회전으로 4가 루트가 되고, 5와 7을 넣은 뒤 8을 넣으면 루트 4에서 다시 불균형이 생겨 RR 회전이 일어난다. 결과는 루트 6, 왼쪽 4(자식 3, 5), 오른쪽 7(오른쪽 자식 8)이다.
나머지 세 순서는 모두 루트 5, 왼쪽 4(왼쪽 자식 3), 오른쪽 7(자식 6, 8)인 같은 트리가 된다.
오류나 개정된 내용이 보이면 알려주세요
다음 키(key) 값을 갖는 9개의 데이터를 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 루트 노드를 삭제한 후 구성되는 이진 탐색 트리에 대한 설명으로 옳지 않은 것은?5, 6, 2, 8, 4, 1, 9, 3, 7
루트 노드의 키는 4와 6 중 한 개의 값을 가진다.
중위 순회(inorder traversal)할 경우 키 값이 1, 2, 3, 4, 6, 7, 8, 9인 노드들을 순서대로 방문한다.
모든 단말 노드들의 키 값들의 합은 21이다.
모든 노드들의 차수(degree)들의 합은 7이다.
옳지 않은 설명은 단말 노드 키 값의 합이 21이라는 것으로, 실제 합은 20이다.
원래 트리는 루트 5, 왼쪽 2(자식 1, 4), 4의 왼쪽 자식 3, 오른쪽 6, 6의 오른쪽 자식 8(자식 7, 9)이다. 루트를 삭제하면 왼쪽 서브트리 최댓값 4 또는 오른쪽 서브트리 최솟값 6이 루트 자리로 올라온다.
어느 쪽으로 대체해도 단말 노드는 1, 3, 7, 9로 같아 합은 20이다.
오류나 개정된 내용이 보이면 알려주세요
다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구간 최단 경로 거리와 광주-대구 구간 최단 경로 거리 사이의 차이 값은? (단, ∞는 두 도시 간에 직접적인 연결이 없음을 의미한다)
| 대전 | 광주 | 서울 | 인천 | 대구 | |
|---|---|---|---|---|---|
| 대전 | 0 | 10 | 15 | 25 | 9 |
| 광주 | 10 | 0 | 18 | 20 | ∞ |
| 서울 | 15 | 18 | 0 | 3 | 17 |
| 인천 | 25 | 20 | 3 | 0 | ∞ |
| 대구 | 9 | ∞ | 17 | ∞ | 0 |
1
2
3
4
두 최단 경로 거리의 차이는 1이다.
인천-대구는 직접 연결이 없으므로 경유 경로를 비교한다.
광주-대구도 직접 연결이 없으며, 광주→대전→대구 = 10 + 9 = 19가 광주→서울→대구(35) 등보다 짧다.
따라서 차이는 20 − 19 = 1이다.
오류나 개정된 내용이 보이면 알려주세요
키(key) 집합에 속하는 각 키에 대해 탐색이 일어날 확률이 알려져 있을 때, 최적 이진 탐색 트리(optimal binary search tree)를 구성함으로써 한 번의 탐색에 대한 평균 비교 횟수를 최소화할 수 있다. 를 키 에 대한 탐색 확률이라고 할 때, 키 집합 {1, 2, 3}에 속하는 각 키에 대한 탐색 확률은 다음과 같다. 키 값이 각각 1, 2, 3인 3개의 데이터를 사용하여 구성한 최적 이진 탐색 트리에서 탐색 1회당 평균 비교 횟수는? (단, 이므로, 1, 2, 3 외의 키를 탐색하는 경우는 없다)
1.4
1.5
1.6
1.7
최적 이진 탐색 트리의 평균 비교 횟수는 1.5이다.
평균 비교 횟수는 각 키의 (깊이 × 탐색 확률)의 합이다. 확률이 큰 키를 루트 가까이 두어야 하므로 1을 루트로, 2를 그 오른쪽 자식, 3을 2의 오른쪽 자식으로 둔다.
오류나 개정된 내용이 보이면 알려주세요
다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에서 해시 테이블의 크기는 7이며 0부터 6까지의 인덱스를 가진다. 는 첫 번째 조사 위치를 결정하는 기본적인 해시 함수이고 는 충돌 발생 시 조사 위치 간격을 결정하는 추가 해시 함수로서, 번째 충돌 발생 시 다음 조사 위치를 결정하는 해시 함수는 가 된다. 공백 해시 테이블에 일련의 키(key) 값 9, 10, 2, 3, 16, 13, 11을 가지는 레코드들을 순서대로 삽입한 후, 해시 테이블의 위치별 키 값을 보여주는 것은? (단, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|
| 13 | 16 | 9 | 10 | 11 | 2 | 3 |
| 16 | 13 | 9 | 10 | 11 | 2 | 3 |
| 3 | 13 | 9 | 10 | 11 | 2 | 16 |
| 13 | 11 | 9 | 10 | 2 | 3 | 16 |
삽입 후 해시 테이블은 [0]부터 3, 13, 9, 10, 11, 2, 16이다.
충돌이 없으면 위치에 넣고, 충돌하면 간격으로 다음 위치를 조사한다.
9: h=2 → [2]
10: h=3 → [3]
2: h=2 충돌, f=3 → (2+3) mod 7 = 5 → [5]
3: h=3 충돌, f=2 → [5] 충돌 → (3+4) mod 7 = 0 → [0]
16: h=2 충돌, f=4 → (2+4) mod 7 = 6 → [6]
13: h=6 충돌, f=2 → (6+2) mod 7 = 1 → [1]
11: h=4 → [4]
오류나 개정된 내용이 보이면 알려주세요
다음 일련의 스택 연산에 의해 스택에서 삭제되는 자료를 순서대로 바르게 나열한 것은? (단, push()는 스택에 자료 를 삽입하는 연산이고, pop()은 스택에서 자료 한 개를 삭제하는 연산이다)push(9), pop(), push(5), push(7), push(2), pop(), push(9), pop(), push(4), pop(), pop(), push(6), push(3), pop(), push(2), pop(), pop()
9, 5, 7, 2, 9, 4, 6, 3
9, 2, 9, 4, 7, 3, 2, 6
2, 3, 6, 4, 9, 2, 7, 5
9, 5, 9, 4, 7, 6, 2, 2
삭제되는 자료의 순서는 9, 2, 9, 4, 7, 3, 2, 6이다.
스택은 후입선출(LIFO)이므로 pop()은 항상 가장 최근에 push 된 값을 꺼낸다.
push(9)·pop() → 9
push(5, 7, 2)·pop() → 2 (남은 스택 5, 7)
push(9)·pop() → 9
push(4)·pop() → 4
pop() → 7 (남은 스택 5)
push(6, 3)·pop() → 3
push(2)·pop() → 2
pop() → 6 (남은 스택 5)
오류나 개정된 내용이 보이면 알려주세요
다음 이진 트리(binary tree)를 <보기>에서 제시한 방법을 사용하여 1차원 배열로 표현할 때, 필요한 배열의 최소 크기는? (단, 배열의 인덱스(index)는 0부터 시작하며 배열의 크기는 배열 원소의 개수이다)<보 기>
○ 루트 노드는 배열의 인덱스가 1인 위치에 저장된다.
○ 배열 인덱스가 인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 인 위치에 있으며 오른쪽 자식 노드는 인덱스가 인 위치에 있다.
17
18
34
35
가장 큰 인덱스가 34이고 인덱스가 0부터 시작하므로 필요한 배열의 최소 크기는 35이다.
루트 A가 1이면 B는 2, C는 3, D는 , E는 C의 왼쪽 자식이므로 이다.
F는 D의 왼쪽 자식으로 8, G는 F의 오른쪽 자식으로 , H는 G의 왼쪽 자식으로 가 된다. 사용하지 않는 인덱스 0 자리를 포함해 0~34까지 칸이 있어야 한다.
오류나 개정된 내용이 보이면 알려주세요
행 우선(row major) 순서로 저장되는 3차원 배열 a[3][30][10]이 있을 때, 첫 번째 원소인 a[0][0][0]의 메모리 주소가 2048이면 a[2][15][2]의 메모리 주소는? (단, 배열 a에서 각 원소의 크기는 4바이트이다)
2800
2804
5052
5056
a[2][15][2]의 메모리 주소는 5056이다.
행 우선 순서에서 a[i][j][k]까지 앞선 원소 수는 이다.
오류나 개정된 내용이 보이면 알려주세요
다음은 C 언어 구조체와 이를 이용한 이중 연결 리스트(doubly linked list)이다. 포인터 current가 가리키는 노드의 왼쪽 노드를 삭제할 때 수행할 C 언어 문장을 순서대로 바르게 나열한 것은? (단, 삭제 전에 포인터 current가 가리키는 노드의 왼쪽에 최소 2개의 노드가 있다고 가정하며, 삭제 노드에 대한 메모리 할당 해제는 생략한다)struct Dnode {
int key;
struct Dnode *prev;
struct Dnode *next;
};
current->next = current->next->next;
current->next->prev = current;
current->next->prev = current;
current->next = current->next->next;
current->prev = current->prev->prev;
current->prev->next = current;
current->prev->next = current;
current->prev = current->prev->prev;
current의 왼쪽 노드를 삭제하려면 먼저 current->prev = current->prev->prev;로 current가 두 칸 왼쪽 노드를 가리키게 하고, 이어서 current->prev->next = current;로 그 노드가 current를 가리키게 한다.
첫 문장 뒤 current->prev는 삭제할 노드의 왼쪽 노드이므로, 두 번째 문장은 그 노드의 next를 current로 바꿔 삭제할 노드를 양방향 모두에서 건너뛰게 한다.
오류나 개정된 내용이 보이면 알려주세요
다음 C 언어 프로그램의 출력 결과는?#include <stdio.h>
int i;
int RecFunc(int n)
{
i++;
if (n <= 1)
return 1;
else
return RecFunc(n-1) + RecFunc(n-2);
}
int main()
{
int result;
i = 0;
result = RecFunc(5);
printf("%d, %d\n", i, result);
}
13, 5
13, 8
15, 5
15, 8
출력 결과는 15, 8이다.
RecFunc의 반환값은 , 이다. 따라서 R(2)=2, R(3)=3, R(4)=5, R(5)=8이다.
i는 호출될 때마다 1 증가하므로 호출 횟수는 , 이다. C(2)=3, C(3)=5, C(4)=9, C(5)=15이다.
오류나 개정된 내용이 보이면 알려주세요
다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 대한 보간 탐색(interpolation search)을 수행할 때, 첫 번째 탐색 위치는? (단, 배열에서 크기가 가장 작은 키와 가장 큰 키의 값은 미리 주어지고, 위치의 차이는 키 값의 차이에 비례한다는 가정 하에 탐색 위치를 계산하며, 소수점 이하는 반올림한다)
| 위치 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 키 | 3 | 10 | 15 | 19 | 24 | 30 | 40 | 65 | 70 | 74 | 80 | 82 | 87 | 93 |
2
3
4
5
보간 탐색의 첫 번째 탐색 위치는 3이다.
보간 탐색은 키 값의 비율로 위치를 추정한다.
소수점 이하를 반올림하면 3이다.
오류나 개정된 내용이 보이면 알려주세요
다음은 C 언어 구조체와 이를 이용한 원형 연결 리스트(circular linked list)이다. 원형 연결 리스트의 맨 마지막에 포인터 new_node가 가리키는 노드를 삽입할 때 수행할 C 언어 문장을 순서대로 바르게 나열한 것은? (단, new_node의 삽입 전에 원형 연결 리스트는 공백 리스트가 아니고, last는 원형 연결 리스트의 마지막 노드를 가리키는 포인터다)struct Cnode {
int key;
struct Cnode *link;
};
new_node->link = last->link;
last = new_node;
last->link = new_node;
new_node->link = last->link;
last->link = new_node;
last = new_node;
last->link = new_node;
new_node->link = last->link;
last = new_node;
last = new_node;
last->link = new_node;
new_node->link = last->link;
원형 연결 리스트의 끝에 삽입하려면 new_node->link = last->link; → last->link = new_node; → last = new_node; 순서로 수행한다.
last->link는 처음 노드를 가리키므로, 이 값을 먼저 new_node->link에 보관해야 처음 노드를 잃지 않는다. 그다음 기존 마지막 노드를 new_node에 연결하고, 마지막으로 last를 new_node로 옮긴다.
오류나 개정된 내용이 보이면 알려주세요
다음 5×5 희소 행렬(sparse matrix)을 구조체 배열로 표현하기 위해 <규칙>의 표현 규칙을 사용하여 <코드>의 C 언어 코드를 작성하였다. <코드>의 ㉠에 들어갈 내용은? (단, 행렬의 행 번호와 열 번호는 0부터 시작한다)<코 드>typedef struct {
int row;
int col;
int val;
} term;
term A[ ] = ㉠ ;<규 칙>
○ 첫 번째 구조체인 A[0]의 row, col, val에는 희소 행렬의 행 개수, 열 개수, 값이 0이 아닌 원소 개수를 순서대로 저장한다.
○ 두 번째부터의 나머지 구조체는 값이 0이 아닌 희소 행렬 원소를 표현하기 위해 사용되며, 각 구조체의 row, col, val에 해당 원소의 행 번호, 열 번호, 값을 순서대로 저장한다.
○ 값이 0이 아닌 희소 행렬 원소 정보는 행 번호의 오름차순으로 구조체 배열 A에 저장되며, 행 번호가 같은 경우에는 열 번호의 오름차순으로 저장된다.
{{4, 4, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}{{4, 4, 4}, {3, 0, 3}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}}{{5, 5, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}{{5, 5, 4}, {3, 0, 3}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}}㉠에 들어갈 내용은 {{5, 5, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}이다.
A[0]에는 행 수 5, 열 수 5, 0이 아닌 원소 수 4를 저장한다. 나머지는 행 번호 오름차순(같으면 열 번호 오름차순)으로 (0, 1, 5), (0, 2, 2), (1, 3, 1), (3, 0, 3)을 저장한다.
오류나 개정된 내용이 보이면 알려주세요
정점이 4개인 무방향(undirected) 완전 그래프(complete graph)에서 만들어질 수 있는 신장 트리(spanning tree)의 총 개수는?
12
14
16
18
만들 수 있는 신장 트리의 총 개수는 16이다.
케일리 공식에 따르면 정점이 n개인 완전 그래프의 서로 다른 신장 트리 수는 이다.
검산: 간선 6개 중 3개를 고르는 20가지에서 사이클(삼각형)이 되는 4가지를 빼면 16이다.
오류나 개정된 내용이 보이면 알려주세요
일련의 키(key) 값 2, 1, 8, 9, 7, 3, 6을 가지는 7개의 데이터를 순서대로 삽입하여 레드-블랙 트리(red-black tree)를 구성하였다. 구성된 레드-블랙 트리를 후위 순회(postorder traversal)할 경우 방문 노드들의 키 값을 방문 순서대로 바르게 나열한 것은?
1, 3, 6, 2, 9, 8, 7
1, 3, 7, 6, 9, 8, 2
1, 6, 3, 2, 9, 8, 7
1, 6, 3, 7, 9, 8, 2
후위 순회 결과는 1, 3, 7, 6, 9, 8, 2이다.
2(흑, 루트)에 1, 8을 적색으로 삽입한다. 9 삽입 시 부모 8과 삼촌 1이 모두 적색이라 색 변경(1, 8 흑)하고, 7은 8의 왼쪽 적색 자식이 된다.
3 삽입 시 부모 7과 삼촌 9가 적색이라 색 변경(7, 9 흑, 8 적)한다. 6 삽입 시 부모 3은 적색, 삼촌(7의 오른쪽)은 흑색이고 꺾인 모양이므로 이중 회전을 하여 6(흑)이 3, 7(적)을 자식으로 갖는다.
최종 트리: 2(1, 8(6(3, 7), 9))
오류나 개정된 내용이 보이면 알려주세요
[7급 국가직 자료구조론] 18년 1회차 시험지 PDF 다운로드·인쇄 →
전 회차를 한 권으로 — 7급 국가직 자료구조론 기출문제 PDF 전자책(문제집·정답해설집) →
[7급 국가직 자료구조론] 18년 1회차 정답과 해설은 무료인가요?
이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.
이 회차를 CBT 로 직접 풀어볼 수 있나요?
7급 국가직 자료구조론 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 국가직 자료구조론 기출문제 풀러 가기 →
시험지 PDF 나 전자책으로도 볼 수 있나요?
이 회차의 인쇄용 시험지 PDF 와, 전 회차를 문제집·정답해설집으로 묶은 PDF 전자책을 제공합니다. 7급 국가직 자료구조론 기출문제 PDF 전자책 보기 →




