[7급 국가직 자료구조론] 07년 1회차 기출문제 정답·해설 페이지
- 루트가 1인 트리는 작은 값이 위로 오는 최소 힙 형태라 이 정렬의 최초 힙이 아니다.
- 루트 13 아래 왼쪽 7(자식 1), 오른쪽 15(자식 19)인 트리는 이진 탐색 트리 형태로, 부모가 자식보다 작은 곳이 있어 힙이 아니다.
- 루트 7 아래 왼쪽 1, 오른쪽 15(자식 13·19)인 트리도 이진 탐색 트리 형태이며 완전이진트리 조건과 힙 조건을 모두 어긴다.
- <d,b>와 자기 루프 <b,b>를 포함한 집합: 두 칸 모두 False이고, d→a와 d→c가 빠져 있다.
- <a,b>를 포함한 집합: a행 b열이 False이므로 간선이 아니며, d→a도 빠져 있다.
- <d,b>와 <a,d>를 포함한 집합: 두 칸 모두 False이고, c→d와 d→c가 빠져 있다.
- 포항 ↔ 부산은 가중치 3으로 가장 가벼워 첫 번째로 선택된다.
- 서울 ↔ 인천은 가중치 4로 목포–진주와 함께 두 번째·세 번째로 선택된다.
- 진주 ↔ 부산은 가중치 14로 가장 무거워, 그 차례가 오기 전에 진주와 부산이 이미 같은 트리로 이어져 사이클이 생기므로 신장 트리에 포함되지 않는다.
- 61을 루트로 한 트리는 후속자도 선행자(47)도 아닌 노드를 올리고 전체를 재배치한 형태라 삭제 연산의 결과가 아니다.
- 58을 루트로 한 트리도 후속자가 아닌 노드를 올리고 서브트리를 재구성해 삭제 연산의 결과와 다르다.
- 84를 루트로 한 트리는 오른쪽 서브트리에 84보다 작은 63·54 등이 있어 이진 탐색 트리 조건을 어긴다.
- 쉘 정렬과 짝지은 나열: 쉘 정렬은 간격을 줄여 가며 삽입 정렬을 반복하는 방식으로 피봇을 쓰지 않는다.
- 피봇을 52로 둔 퀵 정렬 나열: 분할 구간의 첫 원소를 피봇으로 삼는 기본 방식과 맞지 않는다.
- A→C를 직접 간선 5로 두면 합이 15가 되어 E를 경유하는 더 짧은 경로를 놓친다.
- 오른쪽 부분 트리 개수에서 1만 빼는 식: 루트와 왼쪽 부분 트리를 모두 빠뜨린다.
- 왼쪽 재귀 결과에 1만 더하는 식: 오른쪽 부분 트리 전체를 빠뜨린다.
- 오른쪽 개수와 왼쪽 재귀 결과에서 1을 빼는 식: 루트 T를 더해야 할 자리에서 오히려 1을 뺀다.
- 루트 D, 왼쪽 B(A, C), 오른쪽 F(자식 E)인 트리는 균형은 맞지만 삽입·회전 과정에서 D가 루트로 오지 않는다.
- 루트 C, 왼쪽 A(오른쪽 자식 B)인 트리는 LR 회전 뒤에도 B가 왼쪽 자식 A를 유지한다는 점과 맞지 않는다.
- 루트 D, 오른쪽 E 아래 F만 있는 트리도 D가 루트가 되는 회전이 일어나지 않으므로 결과가 아니다.
- : 으로 가장 작다.
- : 이다.
- : 으로, 여기에 이 곱해진 것보다 작다.
- 2차원 배열에 전 원소를 저장하는 설명: 90%를 차지하는 0까지 모두 저장해 공간 낭비가 크다.
- 0이 아닌 원소에 1,000개 공간이 필요하다는 설명: 0이 아닌 원소는 100,000개이므로 맞지 않다.
- 연결 리스트가 전치에 더 효율적이라는 설명: 3원소쌍 배열도 열별 개수로 위치를 정하는 빠른 전치로 효율적으로 처리할 수 있어 연결 리스트가 낫다고 단정할 수 없다.
- S와 Q가 처음과 같은 상태: 삽입·삭제가 전혀 반영되지 않았다.
- S가 [3, 6, 7]에서 멈춘 상태: 마지막 push로 들어간 4가 빠졌다.
- Q에 7이 그대로 남은 상태: remove로 front의 7이 삭제된 것이 반영되지 않았다.
- 첫 노드를 가리키는 원형리스트는 삽입 위치인 마지막 노드를 찾으려면 리스트를 끝까지 순회해야 한다.
- 첫 노드(가장 최근 입력 D)를 가리키는 역원형리스트는 가장 먼저 들어온 A를 삭제하려면 A의 앞 노드를 찾아 순회해야 한다.
- 마지막 노드(A)를 가리키는 역원형리스트는 삽입은 쉽지만, A를 삭제하려면 앞 노드 B를 찾아 순회해야 한다.
- : 단계마다 병합 같은 선형 작업이 있어야 나오는데, 이 함수는 단계마다 상수 작업뿐이다.
- : 결과값에 2를 곱하는 것은 값 계산일 뿐 호출 횟수를 늘리지 않는다.
- : 재귀 깊이는 이므로 호출 수가 지수적으로 늘지 않는다.
- 4: 15 → 6 → 4로 3회 비교한다.
- 6: 15 → 6으로 2회 비교한다.
- 11: 15 → 6 → 11로 3회 비교한다.
- 2 → 1 → 0 → 5 → 4 → 3 → 6은 1에서 0, 0에서 5로 깊게 내려간 깊이우선탐색의 순서다.
- 2 → 1 → 3 → 0 → 4 → 5 → 6은 1의 이웃 6보다 3의 이웃 4를 먼저 방문해 큐 순서를 어겼다.
- 2 → 1 → 0 → 5 → 4 → 6 → 3은 시작 정점과 바로 인접한 3을 마지막에 방문해 너비우선 원칙에 맞지 않는다.
- 왼쪽 서브트리를 오른쪽으로 복사한다는 설명: 새 노드를 만들지 않고 포인터만 교환하므로 복사가 아니다.
- 왼쪽 서브트리를 오른쪽으로 이동한다는 설명: 한쪽만 옮기는 것이 아니라 양쪽을 서로 교환한다.
- 오른쪽 서브트리를 왼쪽으로 이동한다는 설명: 역시 양쪽이 동시에 바뀌고 하위 노드까지 모두 뒤집힌다.
힙정렬(heap sorting)로 다음 데이터를 내림차순으로 정렬할 때 만들어지는 최초의 힙구조는?7, 1, 15, 13, 19
최초의 힙은 루트 19 아래 왼쪽에 13(자식 7·1), 오른쪽에 15가 오는 최대 힙이다.
7, 1, 15, 13, 19를 완전이진트리로 배치한 뒤 마지막 비단말 노드부터 위로 heapify한다. 1은 자식 13·19 중 큰 19와 교환되고, 루트 7은 19와 교환된 뒤 다시 자식 13과 교환되어 배열 [19, 13, 15, 7, 1]이 된다. 이후 최댓값부터 차례로 꺼내면 내림차순으로 정렬된다.
오류나 개정된 내용이 보이면 알려주세요
다음의 인접행렬로 표시되는 그래프 G = (V, E)는?
(단, False는 from에서 to까지의 간선이 없고, True는 from에서 to까지의 간선이 있음을 의미한다)
| to from | a | b | c | d |
|---|---|---|---|---|
| a | False | False | True | False |
| b | True | False | False | False |
| c | False | False | False | True |
| d | True | False | True | False |
V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,b>,<b,b>,<c,d>}V = {a, b, c, d}, E = {<a,b>,<b,a>,<a,c>,<d,c>,<c,d>}V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,c>,<d,a>,<c,d>}V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,b>,<d,a>,<a,d>}이 인접행렬이 나타내는 그래프는 간선 집합이 E = {<b,a>, <a,c>, <d,c>, <d,a>, <c,d>}인 방향 그래프이다.
True인 칸 (from, to)마다 간선이 하나씩 생긴다. True 칸은 a→c, b→a, c→d, d→a, d→c의 5개뿐이다.
오류나 개정된 내용이 보이면 알려주세요
다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지도를 그래프로 표현한 것이다. 최소비용 신장 트리를 구하는 Kruskal 알고리즘을 이용하여 초고속철도를 건설하려고 한다. 4번째로 건설해야 할 구간은?
포항 ↔ 부산
진주 ↔ 부산
서울 ↔ 인천
인천 ↔ 목포
Kruskal 알고리즘에서 네 번째로 건설할 구간은 인천 ↔ 목포이다.
Kruskal은 간선을 가중치 오름차순으로 정렬해 사이클을 만들지 않는 가장 가벼운 간선부터 고른다. 순서는 포항–부산 3, 서울–인천 4, 목포–진주 4, 인천–목포 7, 인천–진주 8 … 이다.
앞의 세 간선을 고른 뒤 인천–목포(가중치 7)는 서울·인천 묶음과 목포·진주 묶음을 잇는 간선이라 사이클이 생기지 않으므로 네 번째로 채택된다.
오류나 개정된 내용이 보이면 알려주세요
크기가 10인 해시 테이블을 배열을 이용하여 만든다고 가정하자. 해시함수로 h(k) = k mod 10을 사용한다. 여기서 mod는 모듈로(modulo) 함수를 의미한다. 데이터가 다음과 같은 순서로 입력된다고 할 때 발생하는 충돌(collision) 횟수의 총 합으로 옳은 것은? (단, 배열의 인덱스는 [0]~[9]까지이고, 처음에 배열은 비어 있으며, 충돌을 해결하기 위해서는 배열의 다음 빈 공간에 데이터를 입력하는 선형 조사법(linear probe)을 사용한다고 가정한다)70, 17, 26, 69, 72, 53, 31, 27, 23, 13
3
4
5
6
선형 조사법으로 넣으면 충돌은 모두 4회 일어난다.
70, 17, 26, 69, 72, 53, 31은 각각 인덱스 [0], [7], [6], [9], [2], [3], [1]에 충돌 없이 들어간다.
27은 [7]에서 1회 충돌 후 [8]에, 23은 [3]에서 1회 충돌 후 [4]에 들어간다. 13은 [3]과 [4]에서 2회 충돌한 뒤 [5]에 들어간다.
합계: 1 + 1 + 2 = 4
오류나 개정된 내용이 보이면 알려주세요
다음 이진 탐색트리(binary search tree)에서 루트(root)노드가 삭제된 후의 상태는?
루트 52를 삭제하면 오른쪽 서브트리의 최솟값인 54(중위 후속자)가 루트 자리로 올라간 트리가 된다.
자식이 둘인 노드를 삭제할 때는 오른쪽 서브트리의 가장 왼쪽 노드로 대체한다. 84 → 63 → 54로 내려가 54가 후속자가 되고, 54의 오른쪽 자식 58은 54가 있던 자리인 63의 왼쪽 자식으로 붙는다.
오류나 개정된 내용이 보이면 알려주세요
최대힙(max heap)으로 우선순위큐를 구현하려 한다. 우선순위를 나타내는 9개의 데이터가 큐에 다음과 같은 순서대로 삽입되었다. 1개의 데이터가 큐에서 삭제된 후, 재 정렬된 힙에서 가장 마지막 원소는 무엇인가? (단, 숫자가 클수록 우선순위가 높다고 가정한다)24, 17, 29, 22, 20, 31, 27, 18, 21
17
18
20
21
삭제 후 재정렬된 힙의 마지막 원소는 17이다.
9개를 차례로 삽입하며 부모보다 크면 위로 올리면 힙 배열은 [31, 22, 29, 21, 20, 24, 27, 17, 18]이 된다.
루트 31을 삭제하고 마지막 원소 18을 루트로 옮긴 뒤 아래로 내리면 29, 27과 차례로 자리를 바꿔 [29, 22, 27, 21, 20, 24, 18, 17]이 된다. 따라서 마지막 자리는 17이다.
오류나 개정된 내용이 보이면 알려주세요
다음을 참조하여, 피봇(pivot)값을 이용하는 정렬 방법과 아래의 ㉠ ~ ㉤에 들어갈 값이 올바르게 나열된 것은?데이터 = {60, 50, 13, 92, 52, 2, 69, 30, 78, 42}
단계1) 피봇값 : ( ㉠ )
- 왼쪽으로부터 비교 : ( ㉡ )에서 비교 멈춤
- 오른쪽으로부터 비교 : ( ㉢ )에서 비교 멈춤
- ( ㉣ )과(와) ( ㉤ )의 저장 위치 교환
정렬 방법 ㉠ ㉡ ㉢ ㉣ ㉤
퀵 정렬 52 60 42 60 42
쉘 정렬 52 60 42 60 42
퀵 정렬 60 92 42 92 42
쉘 정렬 60 92 42 92 42
피봇을 쓰는 정렬은 퀵 정렬이고, 첫 원소 60을 피봇으로 잡으면 92와 42의 위치를 교환한다.
왼쪽부터는 피봇보다 큰 값을 찾아 50, 13을 지나 92에서 멈추고, 오른쪽부터는 피봇보다 작은 값을 찾아 바로 42에서 멈춘다. 이어 두 값의 저장 위치를 바꾼다.
오류나 개정된 내용이 보이면 알려주세요
다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그래프의 간선들 간의 거리를 나타낸다. 표에서 무한대 기호 ∞는 해당 간선이 없음을 나타낸다. 정점 A에서 나머지 네 개의 정점들에 도달하기 위한 최단경로들의 합은 얼마인가?
| to from | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 2 | 5 | ∞ | 3 |
| B | ∞ | 0 | ∞ | 4 | 10 |
| C | ∞ | ∞ | 0 | 6 | 2 |
| D | ∞ | ∞ | ∞ | 0 | ∞ |
| E | ∞ | ∞ | 1 | 2 | 0 |
12
14
15
16
A에서 나머지 정점까지의 최단경로 합은 14이다.
다익스트라 알고리즘으로 B = 2, E = 3이 먼저 확정된다. E를 거치면 C는 3 + 1 = 4로 직접 가는 5보다 짧고, D는 3 + 2 = 5로 B를 거치는 2 + 4 = 6보다 짧다.
합계: 2 + 4 + 5 + 3 = 14
오류나 개정된 내용이 보이면 알려주세요
이진 탐색트리(binary search tree) T에서 k보다 큰 키들의 개수를 찾는 클래스 함수 numGreaterThan(T, k)을 작성한다고 가정하자. 트리에 포함된 모든 키들은 상이하고, 각 노드 x는 링크 필드인 left 및 right와 데이터 필드인 data를 가지며, 추가적으로 하나의 데이터 필드 numDesc를 포함한다. numDesc는 x를 루트(root)로 하는 부분 트리에 포함된 모든 키들의 개수로 초기화되어 있다. 아래 코드에서 밑줄 친 부분에 해당되는 문장은 무엇인가?int numGreaterThan(T, k)
{
if (T == NULL) return 0;
else if (T.key <= k) return numGreaterThan(T.right, k);
else return _________________________________;
}
T.right.numDesc - 1
numGreaterThan(T.left, k) + 1
T.right.numDesc + numGreaterThan(T.left, k) - 1
T.right.numDesc + numGreaterThan(T.left, k) + 1
빈칸에는 T.right.numDesc + numGreaterThan(T.left, k) + 1이 들어간다.
T.key > k이면 오른쪽 부분 트리의 키는 모두 T.key보다 커서 그 개수 numDesc가 전부 포함되고, T 자신도 1개로 더해진다. 왼쪽 부분 트리는 k보다 큰 키가 일부만 있을 수 있어 재귀로 센다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 순서로 입력되는 데이터에 대해 올바르게 AVL-트리를 구성한 것은?
| A | F | E | C | B | D |
A, F, E, C, B, D를 차례로 넣으면 최종 AVL 트리는 루트 C, 왼쪽 B(자식 A), 오른쪽 E(자식 D·F)가 된다.
A, F, E 삽입 시 A에서 RL 불균형이 생겨 E가 루트(A, F)가 된다. C를 A의 오른쪽에 넣고 B를 넣으면 A에서 다시 RL 불균형이 생겨 B가 A·C의 부모가 된다.
마지막 D가 C의 오른쪽에 붙으면 루트 E의 왼쪽 높이가 3, 오른쪽이 1이 되어 LR 회전으로 C가 루트로 올라가고, D는 E의 왼쪽 자식이 된다.
오류나 개정된 내용이 보이면 알려주세요
입력 데이터의 개수 에 대한 시간 복잡도가 가장 큰 것은?시간 복잡도가 가장 큰 것은 이다.
빅오 표기에서는 상수 계수와 낮은 차수 항을 버리고 최고차 항만 남겨 비교한다.
오류나 개정된 내용이 보이면 알려주세요
3차원 배열 A(1:5, 2:4, 1:3)를 1차원 배열 B(1:45)에 행우선으로 저장하는 경우 A(2, 3, 2)가 저장되는 B의 인덱스는?
12
13
14
15
A(2, 3, 2)는 B(14)에 저장된다.
각 차원의 크기는 5, 3, 3이고, 행우선 저장에서는 마지막 첨자가 가장 빨리 변한다.
오프셋:
B는 1부터 시작하므로 인덱스는 1 + 13 = 14이다.
오류나 개정된 내용이 보이면 알려주세요
값이 0인 원소들의 비율이 90%인 1,000 × 1,000 희소 행렬 표현에 관한 설명 중 옳은 것은?
2차원 배열로 모든 원소들을 표현하는 것이 저장 관점에서 효율적이다.
2차원 배열로 0이 아닌 원소들만 표현하기 위해서 1,000개의 저장 공간이 필요하다.
0이 아닌 원소들만 연결 리스트로 표현하는 것이 배열로 표현하는 것보다 전치행렬 연산에 효율적이다.
0이 아닌 원소들만 3원소쌍(행의 인덱스, 열의 인덱스, 값)으로 배열에 저장하는 것이 저장 관점에서 효율적이다.
0이 아닌 원소만 3원소쌍 배열로 저장하는 방식이 저장 관점에서 효율적이다.
0이 아닌 원소는 개이므로, 3원소쌍으로 저장하면 약 칸으로 전체 칸보다 훨씬 적다.
오류나 개정된 내용이 보이면 알려주세요
스택(stack) S와 원형 큐(circular queue) Q의 초기 배열 상태가 다음과 같다고 가정하자. 여기서 T는 스택의 top을, R과 F는 큐의 rear와 front를 각각 나타낸다. 단, 스택에 관한 클래스 함수 push( )는 스택에 삽입, pop( )은 스택의 top이 가리키는 값을 삭제, top( )은 스택의 top이 가리키는 값을 반환한다. 큐에 관한 클래스 함수 front( )는 큐의 front가 가리키는 값의 반환, remove( )는 큐에서 front가 가리키는 값의 삭제를 나타낸다.
S :
| T | |||||
|---|---|---|---|---|---|
| 3 | 6 |
| R | F | ||||
|---|---|---|---|---|---|
| 2 | 7 | 4 |
다음 문장들이 순서대로 실행된 후 S와 Q의 상태는?
Q.remove(); S.push(Q.front());
S :
| 3 | 6 |
| 2 | 7 | 4 |
S :
| 3 | 6 | 7 |
| 2 | 4 |
S :
| 3 | 6 | 7 | 4 |
| 2 | 7 | 4 |
S :
| 3 | 6 | 7 | 4 |
| 2 | 4 |
실행 후 S = [3, 6, 7, 4]가 되고, Q에서는 7이 삭제되어 2와 4만 남는다.
Q의 front 값은 7이다. S.push(Q.front())로 7을 넣고, S.push(S.top())으로 7을 하나 더 넣었다가 S.pop()으로 꺼내 S = [3, 6, 7]이 된다.
Q.remove()로 7이 삭제되어 front가 4로 옮겨지고, S.push(Q.front())로 4가 S에 들어간다.
오류나 개정된 내용이 보이면 알려주세요
큐(queue)를 연결리스트로 구현하는 경우 일반적으로 front와 rear 등 2개의 포인터를 사용한다. 만약 리스트의 포인터를 하나밖에 사용할 수 없다면 가장 효율적인 구조는? (단, 큐에 A, B, C, D의 순서로 입력되었고, 역원형리스트는 데이터가 입력된 순서의 역순으로 만든 원형리스트를 의미한다고 가정한다)
포인터가 첫 노드를 가리키는 원형리스트 구조
포인터가 마지막 노드를 가리키는 원형리스트 구조
포인터가 첫 노드를 가리키는 역원형리스트 구조
포인터가 마지막 노드를 가리키는 역원형리스트 구조
포인터 하나로 큐를 구현할 때 가장 효율적인 것은 마지막 노드를 가리키는 원형리스트이다.
원형리스트에서 마지막 노드 D를 가리키면 그 다음 노드가 곧 첫 노드 A이다. 삽입은 ptr 뒤에 새 노드를 붙이고 ptr을 옮기면 되고, 삭제는 ptr의 다음 노드를 떼어내면 되므로 두 연산 모두 상수 시간에 끝난다.
오류나 개정된 내용이 보이면 알려주세요
다음 C 함수에 대하여 F(L, 0, n-1)를 수행할 경우 시간 복잡도는?int F(int L[], int p, int q)
{
if (p<q)
{ int r, f1, f2;
r = (p+q)/2;
f1 = 2*F(L, p, r);
f2 = 2*F(L, r+1, q);
return f1+f2;
}
else if (p == q)
return L[p]*L[p];
else
return 0;
}
F(L, 0, n-1)의 시간 복잡도는 이다.
함수는 구간을 반으로 나눠 두 번 재귀 호출하고, 나머지 곱셈·덧셈은 상수 시간이다. 따라서 이다.
마스터 정리에서 이 상수항보다 크므로 이다. 재귀 트리로 보아도 호출 수는 약 2n개이다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같이 정렬된 데이터에서 이진탐색(binary search)을 수행하는 경우 비교 횟수가 가장 많은 데이터는?
(단, 배열의 인덱스는 내림(floor)함수를 적용하여 구한다)4, 6, 11, 12, 15, 17, 18, 20, 21
4
6
11
12
비교 횟수가 가장 많은 데이터는 12이다.
9개(인덱스 0~8)에서 첫 중간값은 인덱스 4의 15이다. 12를 찾으면 15 → 6 → 11 → 12 순으로 4회 비교한다.
오류나 개정된 내용이 보이면 알려주세요
여러 명의 고객이 한 개의 창구를 이용하여 서비스를 받으려고 한다. 사용자들이 서비스를 받기 위해 대기하는 구조로서 큐를 사용한다. 이미 서비스를 받고 있는 고객이 있다면, 큐에서 기다려야 한다. 다음과 같은 순서로 다섯 개의 서비스 요청이 동시에 도착했을 때 이미 서비스를 받고 있던 고객은 없다고 가정한다. 다음 ㉠ ~ ㉢의 각 항목에 대한 값이 올바르게 짝지어진 것은? (단, 사각형 내의 숫자는 서비스 요청을 수행하는데 소요되는 시간을 의미한다)
| 10 | 5 | 8 | 50 | 1 |
㉡ 최소 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간
㉢ 최대 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간
㉠ ㉡ ㉢
64 73 200
74 74 74
121 45 251
131 46 301
㉠ 121, ㉡ 45, ㉢ 251이다.
각 고객의 대기 시간은 앞선 고객들의 서비스 시간 합이므로, 짧은 작업을 먼저 하면 최소, 긴 작업을 먼저 하면 최대가 된다.
㉠ 주어진 순서: 0 + 10 + 15 + 23 + 73 = 121
㉡ 짧은 순(1, 5, 8, 10, 50): 0 + 1 + 6 + 14 + 24 = 45
㉢ 긴 순(50, 10, 8, 5, 1): 0 + 50 + 60 + 68 + 73 = 251
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 인접리스트로 표현된 그래프에 대해 노드 2를 시작 정점으로 너비우선탐색(breadth first search)을 수행했을 때 노드들의 방문 순서를 올바르게 나열한 것은?
2 → 1 → 0 → 5 → 4 → 3 → 6
2 → 1 → 3 → 0 → 4 → 5 → 6
2 → 1 → 0 → 5 → 4 → 6 → 3
2 → 1 → 3 → 0 → 6 → 4 → 5
노드 2에서 너비우선탐색을 하면 방문 순서는 2 → 1 → 3 → 0 → 6 → 4 → 5이다.
BFS는 큐를 쓰며 인접리스트에 적힌 순서대로 미방문 노드를 넣는다. 2의 리스트에서 1·3, 1에서 0·6, 3에서 4(2·6은 이미 방문), 0에서 5를 추가하므로 큐에 들어간 순서가 곧 방문 순서다.
오류나 개정된 내용이 보이면 알려주세요
다음 재귀(recursion) 함수는 이진트리의 루트(root)를 가리키는 포인터를 사용하여 특정한 작업을 수행한다. 구체적으로 어떤 작업을 수행하는가?typedef struct node_struct {
int data;
struct node_struct *left, *right;
} node_t;
void JOB_Tree(node_t *root) {
node_t *temp;
if (root == NULL) return;
temp = root->right;
root->right = root->left; root->left = temp;
JOB_Tree(root->left); JOB_Tree(root->right);
}
트리의 루트를 중심으로 좌우 대칭 이동
트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 복사
트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 이동
트리의 루트를 중심으로 오른쪽 자식 트리를 왼쪽 자식 트리로 이동
이 함수는 트리를 좌우 대칭(미러)으로 바꾼다.
각 노드에서 왼쪽·오른쪽 자식 포인터를 맞바꾼 뒤, 두 서브트리에 같은 작업을 재귀로 반복한다. 결국 모든 노드의 좌우가 뒤집힌다.
오류나 개정된 내용이 보이면 알려주세요
[7급 국가직 자료구조론] 07년 1회차 시험지 PDF 다운로드·인쇄 →
전 회차를 한 권으로 — 7급 국가직 자료구조론 기출문제 PDF 전자책(문제집·정답해설집) →
[7급 국가직 자료구조론] 07년 1회차 정답과 해설은 무료인가요?
이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.
이 회차를 CBT 로 직접 풀어볼 수 있나요?
7급 국가직 자료구조론 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 국가직 자료구조론 기출문제 풀러 가기 →
시험지 PDF 나 전자책으로도 볼 수 있나요?
이 회차의 인쇄용 시험지 PDF 와, 전 회차를 문제집·정답해설집으로 묶은 PDF 전자책을 제공합니다. 7급 국가직 자료구조론 기출문제 PDF 전자책 보기 →


















