[7급 국가직 자료구조론] 08년 1회차 기출문제 정답·해설 페이지
- A[9][4] = 15: 10행 5열을 첨자로 직접 지정한 올바른 방법이다.
- *(A[0] + 454) = 15: A[0]은 첫 행 시작 주소(int 포인터)이므로 454칸 뒤가 10행 5열이다.
- *(&A[9][0] + 4) = 15: 10행 첫 원소 주소에서 4칸 뒤이므로 10행 5열이다.
- 508 - 706 - 155 - 133 - 379 - 984 - 193: 앞 단계 순서상 706이 508보다 앞서야 하고, 십의 자리 3인 133이 5인 155보다 앞서야 한다.
- 706 - 508 - 155 - 133 - 379 - 193 - 984: 133과 155의 순서가 뒤바뀌었고, 십의 자리 8인 984가 9인 193보다 뒤에 있다.
- 508 - 706 - 133 - 155 - 379 - 193 - 984: 십의 자리가 같은 706과 508의 앞 단계 순서가 깨졌고, 984와 193의 순서도 틀렸다.
- 노드 가: L이 가리키는 첫 노드일 뿐, 그 link가 p가 아니므로 반복이 계속된다.
- 노드 다: p 자신이며 tmp→link가 p가 되는 조건을 만족하지 않는다.
- 노드 라: p 뒤의 노드로, tmp는 p를 지나쳐 이동하지 않는다.
- 3: 22 쪽 서브트리만 본 값으로, 10 쪽 서브트리가 더 깊다.
- 4: 13까지만 센 값으로, 그 아래 11과 14가 한 레벨 더 있다.
- 6: 레벨 6에 해당하는 노드는 없다.
- (가) - (나) - (다) - (라): p→llink가 먼저 newNode로 바뀌어 기존 왼쪽 노드 주소를 잃는다.
- (나) - (가) - (라) - (다): (라) 시점에 p→llink가 이미 newNode라서 newNode→llink가 자기 자신을 가리킨다.
- (다) - (라) - (가) - (나): (나) 시점의 p→llink가 newNode라서 기존 왼쪽 노드의 rlink는 갱신되지 않고 newNode→rlink가 자기 자신이 된다.
- : 안쪽 반복 횟수가 i에 비례해 늘어날 때의 값이다.
- : 바깥 반복 n회를 빠뜨린 값이다.
- : 안쪽 반복이 상수 횟수일 때의 값이다.
- [0] F, [3] C, [4] D, [5] E인 상태: 하나의 원소 삭제로 C가 빠져야 하는데 남아 있다.
- [1] A, [2] B, [3] F인 상태: A와 B가 삭제되지 않았고 C, D, E도 없다.
- [3] F, [4] D, [5] E인 상태: rear가 원형으로 돌아가므로 F는 [0]에 들어가야 하며, C 삭제 후 [3]은 비어 있다.
- A * B + C / D: (A*B)+(C/D)이므로 A B * C D / + 로 맞다.
- A + (B + C) / D - E: (A+((B+C)/D))-E이므로 A B C + D / + E - 로 맞다.
- A / B - C + D * E: ((A/B)-C)+(D*E)이므로 A B / C - D E * + 로 맞다.
- 루트가 57이고 오른쪽 자식이 45인 트리: 마지막 원소 4만 빠진 형태로, 루트(최댓값)를 꺼내는 힙 삭제가 반영되지 않았다.
- 루트가 57이고 오른쪽 자식이 20인 트리: 최댓값 57이 아니라 45가 삭제된 형태이다.
- 20의 자식이 4, 16 순서인 트리: 4는 마지막 위치에서 내려온 원소이므로 20의 오른쪽 자식이어야 하고, 왼쪽 자식은 16이다.
- : 한쪽 절반만 재귀하는 식으로 합병 정렬과 다르며, 풀면 이다.
- : 이진 탐색의 비교 횟수 식이다.
- : 합병 비용을 상수로 본 식이며, 풀면 이 되어 짝지은 복잡도와도 맞지 않는다.
- b: (b, c)에 head를 한 번 더 적용해야 나오는 값이다.
- c: (b, c)의 마지막 원소로, 주어진 연산 결과가 아니다.
- (d, e): L의 두 번째 원소로 head(tail(L))의 값이다.
- 3이 2의 왼쪽 자식이고 8 아래에 9가 달린 트리: 중위 순회가 3, 2로 시작해 주어진 2, 3과 어긋난다.
- 3이 2의 오른쪽 자식이고 9가 7의 자식, 8이 6의 오른쪽 자식인 트리: 전위 순회가 6, 7, 9, 8 순이 되어 주어진 6, 7, 8, 9와 다르다.
- 3이 2의 왼쪽 자식이고 9가 7의 자식인 트리: 중위 순회가 3, 2로 시작하고 9, 8의 위치도 주어진 순서와 맞지 않는다.
- 대각 원소 (0, 0)과 (4, 4)가 0인 행렬: 길이 0 경로를 포함하지 않은 이행적 폐쇄이다.
- 대각 원소가 0이고 직접 간선 일부만 1인 행렬: 반사성도 없고 경로를 통한 도달도 반영되지 않았다.
- 대각 원소는 1이지만 직접 간선 일부만 1인 행렬: 반사성은 있으나 경로를 통한 도달(이행성)이 반영되지 않았다.
- 루트 15, 왼쪽 10(2, 14), 오른쪽 25(20)인 트리: 모든 노드의 높이 차가 1 이하이다.
- 루트 15에서 10의 오른쪽 자식 12 아래에 14가 붙은 트리: 10에서 높이 차 1, 루트에서 높이 차 1로 균형을 만족한다.
- 루트 14, 왼쪽 4(2, 10(8, 12)), 오른쪽 20(15, 25)인 트리: 4에서 높이 차 1, 루트에서 높이 차 1이다.
- 힙 정렬과 퀵 정렬: 힙 정렬은 입력 분포와 무관하게 이라 갑처럼 급격히 느려지지 않는다.
- 합병 정렬과 퀵 정렬: 합병 정렬도 최악이 이라 갑의 큰 편차를 설명하지 못한다.
- 합병 정렬과 힙 정렬: 둘 다 분포에 둔감해 갑의 큰 편차가 나올 수 없다.
- (A, B): A와 B 모두의 최소 비용 간선(5)이다.
- (C, F): C와 F 모두의 최소 비용 간선(15)이다.
- (D, E): D와 E 모두의 최소 비용 간선(10)이다.
- 1-2-3-4-6-7-5-8: 6에서 막혀 4로 돌아가 7을 방문하고, 7에서 5, 5에서 8로 가는 정상 순서이다.
- 1-2-3-4-6-5-7-8: 6에서 4로 되돌아가 5, 5에서 7, 다시 5로 돌아가 8을 방문한다.
- 1-2-3-4-5-7-8-6: 5에서 7, 막혀 5로 돌아가 8, 다시 4로 돌아가 6을 방문한다.
- [2]에 15, [4]에 10, [6]에 6인 상태: 충돌 시 한 칸씩 옮기는 선형 탐사의 결과다.
- [0]에 6, [5]에 10, [6]에 15인 상태: 10은 [1], [6]을 거쳐 [4]에 들어가야 한다.
- [2]에 15, [5]에 10, [6]에 6인 상태: 15부터 두 번째 해시 함수를 올바로 적용하지 않은 결과다.
- return T; 와 return T→Left; 조합: 왼쪽으로 한 단계만 내려가 더 깊은 곳의 최솟값을 놓친다.
- return T→Right; 와 return T→Left; 조합: 왼쪽 자식이 없을 때 최소는 현재 노드인데 더 큰 값인 오른쪽 자식을 반환한다.
- return FindMin(T→Right); 와 return FindMin(T→Left); 조합: 오른쪽 서브트리에는 현재 노드보다 큰 값만 있어 최솟값이 될 수 없다.
- early(5) = 10, late(5) = 10: a5는 <3, 6>, 시간 4로 earliest[3] = 10, latest[6] − 4 = 10이다.
- early(7) = 7, late(7) = 12: a7은 <4, 7>, 시간 4로 earliest[4] = 7, latest[7] − 4 = 12이다.
- early(9) = 14, late(9) = 14: a9는 <6, 8>, 시간 5로 earliest[6] = 14, latest[8] − 5 = 14이다.
C 언어를 사용하여 100행 50열로 이루어진 행렬을 2차원 배열 A[100][50]에 저장하려고 한다. 10행 5열에 정수 값 15를 저장하는 방법으로 옳지 않은 것은?
A[9][4] = 15
*(A[0] + 454) = 15
*(&A[9][0] + 4) = 15
*(&A[0][0] + 904) = 15
10행 5열은 0부터 세는 C 배열에서 A[9][4]이므로 *(&A[0][0] + 904) = 15가 옳지 않다.
행 우선 저장이므로 시작 주소로부터의 오프셋은 행 첨자 × 열 개수 + 열 첨자이다.
오프셋 904는 에 해당해 19행 5열 위치를 가리킨다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 7개의 십진수를 입력받아 3단계(three passes)의 기수 정렬(Radix Sort)을 수행하여 오름차순으로 정렬하려고 한다.379 - 508 - 706 - 193 - 984 - 155 - 133두 번째 단계를 수행한 후 부분 정렬되어진 결과는?
508 - 706 - 155 - 133 - 379 - 984 - 193
706 - 508 - 155 - 133 - 379 - 193 - 984
508 - 706 - 133 - 155 - 379 - 193 - 984
706 - 508 - 133 - 155 - 379 - 984 - 193
일의 자리부터 정렬하는 기수 정렬에서 두 번째 단계 후 결과는 706 - 508 - 133 - 155 - 379 - 984 - 193이다.
1단계(일의 자리)는 자리값이 같으면 입력 순서를 유지해 193 - 133 - 984 - 155 - 706 - 508 - 379가 된다.
2단계(십의 자리)는 이 순서에서 십의 자리 0(706, 508), 3(133), 5(155), 7(379), 8(984), 9(193) 순으로 모으며, 같은 버킷 안에서는 안정성에 따라 앞 단계 순서가 유지된다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 단순 연결 리스트(singly linked list)에 대해, 아래와 같은 C 언어로 작성된 프로그램을 수행한 후 포인터 tmp가 가리키는 노드는?for (tmp = L; tmp→link != p; tmp = tmp→link);
tmp→link = p→link;
가
나
다
라
반복문이 끝났을 때 tmp는 p가 가리키는 노드의 바로 앞 노드인 나를 가리킨다.
for 문은 tmp를 L에서 출발시켜 tmp→link가 p와 같아지는 순간 멈추므로, tmp는 p 직전 노드에 머문다. 이어지는 tmp→link = p→link는 p가 가리키는 노드 다를 리스트에서 떼어 내는 삭제 연산이다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 9개의 데이터를 순서대로 입력하여 생성한 이진 탐색 트리(binary search tree)의 높이는?
(단, 루트(root)의 레벨은 1이다)17, 10, 22, 15, 13, 24, 20, 11, 14
3
4
5
6
생성된 이진 탐색 트리의 높이는 5이다.
17이 루트, 10은 왼쪽, 22는 오른쪽 자식이 된다. 15는 10의 오른쪽, 13은 15의 왼쪽, 11과 14는 각각 13의 왼쪽·오른쪽 자식이 된다. 24와 20은 22의 자식으로 레벨 3이다.
가장 긴 경로는 17 → 10 → 15 → 13 → 11(또는 14)로 레벨 5까지 내려간다.
오류나 개정된 내용이 보이면 알려주세요
이중 연결 리스트(doubly linked list)에서 포인터 p가 가리키는 노드의 왼쪽으로 포인터 newNode가 가리키는 노드를 삽입한다고 할 때, 연산의 순서가 바르게 나열된 것은?
(단, llink는 왼쪽 노드를 가리키는 포인터이고, rlink는 오른쪽 노드를 가리키는 포인터이다)(가) p→llink = newNode;
(나) p→llink→rlink = newNode;
(다) newNode→rlink = p;
(라) newNode→llink = p→llink;
(가) - (나) - (다) - (라)
(나) - (가) - (라) - (다)
(다) - (라) - (가) - (나)
(라) - (다) - (나) - (가)
올바른 순서는 (라) - (다) - (나) - (가)이다.
p→llink를 바꾸기 전에 기존 왼쪽 노드 주소가 필요하므로, 먼저 newNode의 두 링크를 채우고(라, 다) 기존 왼쪽 노드의 rlink를 newNode로 바꾼 뒤(나) 마지막에 p→llink를 갱신한다(가).
오류나 개정된 내용이 보이면 알려주세요
다음은 C 언어로 작성된 프로그램의 일부이다. 이 프로그램의 시간 복잡도는?for (i = 1; i < n; i++) {
m = 1;
while (m < i) m = m * 2;
}이 프로그램의 시간 복잡도는 이다.
안쪽 while은 m을 2배씩 키우므로 i마다 약 회 반복하고, 바깥 for는 n-1회 돈다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 원형 큐(circular queue)에 대해 ‘가’에서 ‘바’까지의 연산들을 차례대로 수행했을 때, 수행이 완료된 후 큐의 상태는?
(단, 현재 상태에서 front = 0, rear = 2이며, front에서는 삭제, rear에서는 삽입이 일어난다)
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| A | B |
다. 두 개의 원소 삭제 라. 원소 E 삽입
마. 하나의 원소 삭제 바. 원소 F 삽입
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | D | E |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | C | D | E |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| A | B | F |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | D | E |
수행 후 큐는 [0]에 F, [4]에 D, [5]에 E가 들어 있는 상태이다.
front는 첫 원소 바로 앞 칸을 가리키며, 삽입은 rear를, 삭제는 front를 으로 한 칸씩 옮긴다.
C, D 삽입 → rear = 4
두 개 삭제(A, B) → front = 2
E 삽입 → rear = 5
하나 삭제(C) → front = 3
F 삽입 → rear = 0
오류나 개정된 내용이 보이면 알려주세요
다음 중 중위(infix) 표기식과 그에 대응하는 후위(postfix) 표기식이 일치하지 않는 것은?
중위표기식 후위표기식
A * B + C / D A B * C D / +
A + (B + C) / D - E A B C + D / + E -
A * B / (C - D) + E A B * C D - E / +
A / B - C + D * E A B / C - D E * +
일치하지 않는 것은 A * B / (C - D) + E와 그 후위식이다.
* 와 / 는 같은 우선순위로 왼쪽부터 결합하므로 ((A*B)/(C-D))+E이고, 후위식은 A B * C D - / E +가 되어야 한다. 제시된 A B * C D - E / + 는 (A*B)+((C-D)/E)를 뜻한다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 차례대로 삽입하여 최대 힙(max heap)을 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?4, 16, 57, 9, 32, 45, 20, 19
삭제 후의 최대 힙은 레벨 순서로 45 / 32, 20 / 19, 9, 16, 4이다.
차례로 삽입하며 부모와 교환(up-heap)하면 힙 배열은 57, 32, 45, 19, 9, 16, 20, 4가 된다. 삭제는 루트 57을 꺼내고 마지막 원소 4를 루트로 올린 뒤, 더 큰 자식과 교환하며 내려간다(4↔45, 4↔20).
그 결과 배열은 45, 32, 20, 19, 9, 16, 4가 된다.
오류나 개정된 내용이 보이면 알려주세요
개의 원소를 가지는 배열을 합병 정렬(Merge Sort) 알고리즘으로 정렬하고자 한다. 이 알고리즘에서 값을 비교하는 횟수를 이라고 할 때, 순환식(recurrence equation)으로 표현된 과 시간복잡도는?
(단, 이고, 이라고 가정한다)
시간복잡도
합병 정렬의 비교 횟수는 , 시간복잡도는 이다.
크기 N/2인 두 부분을 각각 정렬하고(), 정렬된 두 리스트를 합병할 때 최악 번 비교한다.
이를 풀면 이다.
오류나 개정된 내용이 보이면 알려주세요
일반 리스트 L = (, , …, )에서 head(L)은 첫 번째 원소인 이고, tail(L)은 첫 번째 원소를 제외한 나머지 리스트 (, …, )으로 정의된다고 할 때, 일반 리스트 L = ((a, (b, c)), (d, e), ((f, g), h))에서 head(tail(head(L)))의 값은?
b
c
(b, c)
(d, e)
head(tail(head(L)))의 값은 (b, c)이다.
head(L)은 첫 원소 (a, (b, c))이고, 그 tail은 a를 뺀 리스트 ((b, c))이다. 이 리스트의 head는 유일한 원소인 (b, c)이다.
tail의 결과는 항상 리스트이므로 괄호 한 겹이 더 씌워진다는 점에 주의한다.
오류나 개정된 내용이 보이면 알려주세요
어떤 이진 트리(binary tree)를 전위 순회(preorder traversal)한 결과는 1, 2, 3, 4, 5, 6, 7, 8, 9이고, 중위 순회(inorder traversal)한 결과는 2, 3, 1, 5, 4, 7, 8, 6, 9라고 할 때, 이 이진 트리는?
복원한 트리는 루트 1의 왼쪽에 2와 그 오른쪽 자식 3, 오른쪽에 4(왼쪽 5, 오른쪽 6)가 있고, 6의 왼쪽 자식 7의 오른쪽 자식이 8, 6의 오른쪽 자식이 9인 형태이다.
전위 순회의 첫 원소가 루트이고, 중위 순회에서 루트의 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리이다. 1을 기준으로 {2, 3}과 {5, 4, 7, 8, 6, 9}로 나누고, 같은 방식으로 4와 6을 서브트리의 루트로 재귀 분할한다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive transitive closure) 행렬 D*를 인접 행렬로 바르게 표현한 것은?
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 |
반사 이행적 폐쇄는 자기 자신을 포함해 경로로 도달 가능한 모든 정점을 1로 표시한 행렬이다.
그래프는 0→1→2→3 경로와 3→1 역방향 간선, 3→4 간선으로 이루어져 있어 1, 2, 3은 서로 순환하며 4로도 갈 수 있다. 따라서 0행은 모두 1, 1~3행은 0열만 0, 4행은 대각 원소만 1이다.
오류나 개정된 내용이 보이면 알려주세요
다음 중 AVL 트리가 아닌 것은?
루트가 20이고 왼쪽 서브트리가 10-15-14로 깊어진 트리는 AVL 트리가 아니다.
AVL 트리는 모든 노드에서 왼쪽·오른쪽 서브트리 높이 차(균형 인수)가 1 이하여야 한다. 이 트리는 루트의 왼쪽 높이가 3, 오른쪽(25) 높이가 1이라 균형 인수가 2이다.
오류나 개정된 내용이 보이면 알려주세요
각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 대해 ‘갑’과 ‘을’의 두 가지 정렬 기법으로 정렬을 수행했을 때 다음과 같은 시간이 소요되었다.
| 정렬 기법 데이터 세트 | 갑 | 을 |
|---|---|---|
| A | 0.21초 | 0.40초 |
| B | 6.71초 | 0.39초 |
갑 을
퀵 정렬 합병 정렬
힙 정렬 퀵 정렬
합병 정렬 퀵 정렬
합병 정렬 힙 정렬
갑은 퀵 정렬, 을은 합병 정렬이다.
갑은 데이터 세트 B에서 시간이 30배 이상 늘었다. 데이터 분포(이미 정렬된 경우 등)에 따라 최악 로 떨어지는 기법은 퀵 정렬뿐이다.
을은 두 세트에서 시간이 거의 같으므로 분포와 무관하게 인 기법이며, 갑이 퀵 정렬인 조합은 을이 합병 정렬인 경우뿐이다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 그래프에서 Sollin 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구하려고 한다. Sollin 알고리즘의 시작 단계에서는 하나의 정점으로 이루어진 트리들로 구성된 포리스트(forest)에서 각 트리의 최소 비용 간선(edge)을 선택하게 된다. 하나의 정점으로 이루어진 트리에 대한 최소 비용 간선을 선택할 때, 선택되는 간선이 아닌 것은?
(A, B)
(B, E)
(C, F)
(D, E)
단일 정점 트리들이 고르는 최소 간선은 (A, B), (C, F), (D, E)뿐이므로 (B, E)는 선택되지 않는다.
Sollin 알고리즘 첫 단계에서는 각 정점마다 연결된 간선 중 가중치가 가장 작은 것을 고른다. A와 B는 가중치 5인 (A, B), C와 F는 15인 (C, F), D와 E는 10인 (D, E)를 고른다.
(B, E)의 가중치 20은 B 입장에서는 (A, B)보다, E 입장에서는 (D, E)보다 크므로 어느 쪽에서도 최소가 아니다.
오류나 개정된 내용이 보이면 알려주세요
다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색(Depth First Search)을 수행할 경우 나타날 수 없는 순서는?
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
1 - 2 - 3 - 4 - 6 - 7 - 5 - 8
1 - 2 - 3 - 4 - 6 - 5 - 7 - 8
1 - 2 - 3 - 4 - 5 - 7 - 8 - 6
1-2-3-4-5-6-7-8은 깊이 우선 탐색으로 나올 수 없다.
깊이 우선 탐색은 현재 정점에 방문하지 않은 인접 정점이 남아 있으면 반드시 그쪽으로 내려가고, 없을 때만 되돌아간다. 정점 5는 7, 8과 인접하고 6과는 연결되지 않으므로, 5 다음에는 7이나 8이 와야 한다.
오류나 개정된 내용이 보이면 알려주세요
크기가 7()인 해시 테이블(hash table)에 이중 해싱(double hashing) 기법을 사용하여 데이터를 삽입한다고 하자. 첫 번째 해시 함수(hash function)는 이고, 충돌이 발생할 경우 사용하는 두 번째 해시 함수는 이다. 이러한 해시 함수를 사용하여 다음과 같은 탐색 키들을 차례대로 삽입한다고 할 때, 삽입이 완료된 후 해시 테이블의 상태는?1, 15, 3, 6, 10
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
삽입 완료 후 테이블은 [0]=6, [1]=1, [3]=3, [4]=10, [6]=15이다.
이중 해싱은 충돌 시 위치를 차례로 탐사한다.
1 → [1], 3 → [3]은 충돌 없이 들어간다.
15: 충돌, →
6: 충돌, → 충돌 →
10: 충돌, → [1], [6] 충돌 →
오류나 개정된 내용이 보이면 알려주세요
다음은 이진 탐색 트리(binary search tree)에서 최소 키 값을 가지는 노드에 대한 포인터를 반환하는 함수를 C 언어로 구현한 프로그램의 일부이다. ( 가 )와 ( 나 )부분에 해당되는 문장이 바르게 나열된 것은?struct TreeNode {
int data;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;
SearchTree FindMin(SearchTree T)
{
if (T == NULL) return NULL;
else if (T→Left == NULL) ( 가 )
else ( 나 )
}( 가 ) ( 나 )return T; return T→Left;
return T→Right; return T→Left;
return T; return FindMin(T→Left);
return FindMin(T→Right); return FindMin(T→Left);
(가)는 return T;, (나)는 return FindMin(T→Left);이다.
이진 탐색 트리의 최솟값은 왼쪽 자식을 끝까지 따라간 노드에 있다. 왼쪽 자식이 없으면 현재 노드가 최소이므로 T를 반환하고, 있으면 왼쪽 서브트리에서 재귀적으로 찾는다.
오류나 개정된 내용이 보이면 알려주세요
AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 이른 시간(earliest time)과 가장 늦은 시간(latest time)을 각각 나타내는 early(i)와 late(i)를 구하고자 한다. 가장 이른 사건 발생 시간(earliest event occurrence time)을 earliest라고 하고, 가장 늦은 사건 발생 시간(latest event occurrence time)을 latest라고 할 때, 작업 ai가 간선 <k, l>로 표현된다면, 다음 식으로부터 early(i)와 late(i)를 구할 수 있다.early(i) = earliest[k]다음과 같은 AOE 네트워크에서 early(i)와 late(i)를 구한 결과 중 옳지 않은 것은?
late(i) = latest[l] - 작업 ai의 작업 시간(duration)
early(3) = 6, late(3) = 10
early(5) = 10, late(5) = 10
early(7) = 7, late(7) = 12
early(9) = 14, late(9) = 14
작업 a3은 early(3) = 6이지만 late(3) = 11이므로, late(3)을 10으로 제시한 결과가 옳지 않다.
전진 계산으로 earliest를 구하면 V1 = 6, V3 = 10, V4 = 7, V6 = 14, V7 = 11, V8 = 19이다. 후진 계산으로 latest를 구하면 V6 = 14, V7 = 16, V4 = min(14 − 2, 16 − 4) = 12이다.
a3은 간선 <1, 4>, 작업 시간 1이므로 late(3) = latest[4] − 1 = 11이다.
오류나 개정된 내용이 보이면 알려주세요
[7급 국가직 자료구조론] 08년 1회차 시험지 PDF 다운로드·인쇄 →
전 회차를 한 권으로 — 7급 국가직 자료구조론 기출문제 PDF 전자책(문제집·정답해설집) →
[7급 국가직 자료구조론] 08년 1회차 정답과 해설은 무료인가요?
이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.
이 회차를 CBT 로 직접 풀어볼 수 있나요?
7급 국가직 자료구조론 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 국가직 자료구조론 기출문제 풀러 가기 →
시험지 PDF 나 전자책으로도 볼 수 있나요?
이 회차의 인쇄용 시험지 PDF 와, 전 회차를 문제집·정답해설집으로 묶은 PDF 전자책을 제공합니다. 7급 국가직 자료구조론 기출문제 PDF 전자책 보기 →
















