[7급 서울시 자료구조론] 26년 1회차 기출문제 정답·해설 페이지
- A: B 다음, 여섯 번째로 push된다.
- D: 두 번째로 push된다.
- E: 가장 먼저(첫 번째로) push된다.
- 연속된 메모리 공간에 저장되는 것은 배열(순차 리스트)의 특징이다.
- 링크가 하나뿐인 것은 단순(단일) 연결 리스트이다.
- 인덱스로 직접 접근하는 임의 접근은 배열의 특징이며, 연결 리스트는 순차적으로 따라가야 한다.
- 7회: 중복 호출을 대부분 빠뜨린 값이다.
- 12회: 재귀 트리의 일부 호출을 누락한 값이다.
- 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.
- 순차 탐색은 원소를 처음부터 하나씩 비교하므로 이다.
- 인덱스 테이블이 작아지면 인덱스 간격이 커져 배열에서 탐색할 구간이 넓어진다.
- 11개 원소의 이진 탐색은 중간값 11과 비교한 뒤 오른쪽 구간의 중간값 17과 비교하므로 비교는 2회이다.
- [1, 2, 3, 4, 5, 6]은 회전하지 않은 원래 상태이다.
- [2, 3, 4, 5, 6, 1]은 왼쪽으로 1칸 회전한 결과이다.
- [5, 6, 1, 2, 3, 4]는 오른쪽으로 2칸 회전한 결과이다.
- 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 개이다.
- 인접 행렬의 행 는 정점 에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
- 인접 리스트에서 헤드 에 연결된 노드는 에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.
- ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
- ㄹ: 이진 탐색 트리의 평균 검색 시간은 이며, 은 한쪽으로 치우친 최악의 경우이다.
- : k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
- : k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
- : n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.
- 3: C까지 삽입한 시점의 rear이다.
- 4: D까지 삽입한 시점의 rear이다.
- 5: E까지 삽입한 시점의 rear로, F 삽입 시 원형으로 되돌아가는 것을 반영하지 않은 값이다.
- [3, 12, 27, 17, 80, 42, 91, 95]: 17과 27의 자리가 바뀌어 부분 리스트가 정렬되지 않았다.
- [80, 42, 3, 12, 91, 95, 17, 27]: 단계까지만 수행한 상태이다.
- [80, 42, 3, 12, 95, 91, 17, 27]: 단계 결과와도 91, 95의 순서가 다르다.
- 삽입 시 완전 이진 트리를 유지하려면 마지막 노드 다음 자리( 위치)에 원소를 임시로 두고 부모와 비교하며 올라간다.
- 힙의 삭제는 루트 원소를 꺼낸 뒤 마지막 노드를 루트로 옮겨 재정렬한다.
- 배열로 구현하면 노드 의 부모는 처럼 인덱스 계산으로 바로 찾는다.
- (A, B): 두 번째로 포함되는 간선이다.
- (A, C): 사이클을 만들어 제외된다.
- (B, D): 정점 4개의 신장 트리는 간선 3개로 이미 완성되어 선택되지 않는다.
- G가 C의 왼쪽 자식인 구조는 중위 순회가 G−C 순서가 되어 맞지 않는다.
- F가 E의 오른쪽 자식인 구조는 중위 순회가 E−F 순서가 되어 맞지 않는다.
- E가 B의 왼쪽, D가 B의 오른쪽에 있는 구조는 전위 순회가 A−B−E−F−D… 가 되어 맞지 않는다.
- old->link = pre->link: 삭제할 노드의 링크만 바뀌고 pre는 여전히 old를 가리켜 연결이 끊기지 않는다.
- (나)에서 head를 pre로 바꾸는 경우: 마지막 노드가 첫 노드가 되어 기존 순서가 바뀐다.
- pre = old->link: 지역 변수만 바뀔 뿐 리스트의 링크는 그대로이다.
- 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
- 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
- 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.
- RR 회전은 불균형 노드의 오른쪽-오른쪽에 삽입된 경우에 쓴다.
- LR 회전은 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우에 쓴다.
- RL 회전은 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우에 쓴다.
- 3가지는 C로 시작하는 경우만 센 값이다.
- 4가지는 C−E−B−D처럼 E가 B보다 먼저 오는 순서를 빠뜨린 값이다.
- 6가지는 가능한 5가지보다 많아, 간선 제약을 어기는 순서를 포함해야만 나오는 값이다.
- [3, 17, 124, 227, 423, 80, 691, 95]: 십의 자리가 2인 원소를 백의 자리 기준으로 미리 정렬해 앞 단계 순서를 지키지 않았다.
- [17, 3, 227, 423, 124, 80, 95, 691]: 십의 자리가 0인 3보다 1인 17을 앞에 두어 십의 자리 기준 정렬이 아니다.
- [17, 3, 423, 227, 124, 80, 95, 691]: 역시 17이 3보다 앞서 있어 2단계 결과가 될 수 없다.
- order[2]: 2, order[3]: 4 — 정점 2는 1→4를 거친 뒤 마지막에 방문되므로 두 번째가 될 수 없다.
- order[2]: 3, order[3]: 4 — 0과 가까운 정점부터 차례로 방문하는 너비 우선 탐색의 순서이다.
- order[2]: 5, order[3]: 4 — 정점 1에서 인덱스가 작은 3을 4보다 먼저 방문하므로 order[3]은 3이다.
- 인덱스 0, 길이 2: 버킷 0에는 8 하나만 저장된다.
- 인덱스 5, 길이 4: 버킷 5의 키는 3개뿐이다.
- 인덱스 6, 길이 2: 6·14의 2개로 가장 긴 체인이 아니다.
<보기> 수식을 전위 표기법(prefix notation)으로 변환한 후, 스택을 이용하여 계산하려고 한다. 계산 과정에서 스택에 다섯 번째로 삽입(push)하는 값은? (단, 전위표기법을 스택으로 계산할 때, 오른쪽에서 왼쪽으로 읽으며 진행한다.)(A-B)*C+D/E
A
B
D
E
스택에 다섯 번째로 push되는 값은 B이다.
수식을 전위 표기로 바꾸면 + * - A B C / D E이다. 오른쪽부터 읽으며 피연산자는 push하고, 연산자를 만나면 두 값을 pop해 계산한 결과를 다시 push한다.
push 순서: E → D → (D/E) → C → B → A …
오류나 개정된 내용이 보이면 알려주세요
이중 연결 리스트(doubly linked list)의 특징에 대한 설명으로 가장 옳은 것은?
각 노드가 이전 노드와 다음 노드의 정보를 가진다.
노드들이 메모리의 연속된 공간에 저장된다.
모든 노드는 하나의 링크만 가진다.
인덱스를 이용하여 원하는 노드에 직접 접근할 수 있다.
이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 링크를 가진다.
그래서 양방향 순회가 가능하지만, 노드는 메모리에 흩어져 있고 특정 노드에 가려면 링크를 따라가야 한다.
오류나 개정된 내용이 보이면 알려주세요
<보기>는 피보나치 수열을 계산하는 C 프로그램이다. fib(5)을 호출했을 때, 함수 fib( )가 호출되는 총 횟수는? (단, 첫 호출도 1회로 계산한다.)int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return (fib(n-1) + fib(n-2));
}
7
12
15
17
fib(5)를 호출하면 함수는 총 15회 호출된다.
호출 횟수를 이라 하면 , 이다.
오류나 개정된 내용이 보이면 알려주세요
탐색 알고리즘의 설명으로 가장 옳지 않은 것은?
순차 탐색의 시간 복잡도는 이다.색인 순차 탐색에서 인덱스 테이블의 크기가 줄어들면, 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 탐색해야 하는 범위도 커진다.
색인 순차 탐색의 시간 복잡도는 이다. (단, : 배열의 크기, : 인덱스 테이블의 크기)
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21과 같이 정렬되었을 때 이진 탐색으로 찾고자 하는 수가 17일 경우, 비교 횟수는 2번이다.
색인 순차 탐색의 시간 복잡도는 이므로, 이라는 설명이 옳지 않다.
크기 인 인덱스 테이블을 먼저 탐색한 뒤, 찾은 구간(크기 약 )을 배열에서 순차 탐색하기 때문이다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 C 프로그램 함수 func에 대해서 배열 arr[] = {1, 2, 3, 4, 5, 6}일 때, func(arr, 6, 2)를 실행한 후 배열 arr[]의 상태는?void func(int arr[], int n, int k) {
int temp[100];
for (int i = 0; i < n; i++)
temp[i] = arr[(i + k) % n];
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}[1, 2, 3, 4, 5, 6]
[2, 3, 4, 5, 6, 1]
[3, 4, 5, 6, 1, 2]
[5, 6, 1, 2, 3, 4]
실행 후 배열은 [3, 4, 5, 6, 1, 2]가 된다.
temp[i]에 arr[(i+2)%6]을 담으므로 배열이 왼쪽으로 2칸 회전한다. temp[0]=arr[2]=3, temp[1]=arr[3]=4, …, temp[4]=arr[0]=1, temp[5]=arr[1]=2이다.
오류나 개정된 내용이 보이면 알려주세요
그래프에 대한 설명으로 가장 옳지 않은 것은?
완전 그래프에서 정점이 개인 방향 그래프의 최대 간선 수는 개이다.
방향 그래프의 인접 행렬에서 행 의 합은 정점 의 진출 차수이다.
방향 그래프의 인접 리스트에서 각 정점의 헤드에 연결된 노드의 수는 정점의 진출 차수이다.
개의 간선을 가진 무방향 그래프의 인접 리스트에 저장되는 연결 노드의 총 수는 개이다.
무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 개이다. 따라서 개라는 설명이 옳지 않다.
방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 개가 된다.
오류나 개정된 내용이 보이면 알려주세요
<보기>에서 이진 트리(binary tree)의 성질에 대한 설명으로 옳은 것을 모두 고른 것은? (단, 트리의 높이는 루트 노드의 레벨을 1로 하여 계산한다.)ㄱ. 총 개의 노드를 가진 이진 트리의 높이()는 적어도 이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. 개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 이다.
ㄱ
ㄱ, ㄷ
ㄴ, ㄹ
ㄱ, ㄷ, ㄹ
옳은 것은 ㄱ, ㄷ이다.
높이 인 이진 트리의 최대 노드 수는 이므로 , 즉 이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?Algorithm(int n) {
int i, j, k, l;
int sum = 0;
for (i = 0; i < 500; i++)
for (j = 0; j < 100; j++)
for (k = 1; k < n; k = k * 2)
for (l = 0; l < 10; l++)
sum = sum + i + j + k + l;
}시간 복잡도는 이다.
i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 회 반복한다.
총 실행 횟수는 이고, 상수를 제거하면 이다.
오류나 개정된 내용이 보이면 알려주세요
크기가 6인 원형 큐(circular queue)가 있다. <보기 1>의 설명을 참고하여 <보기 2>의 연산을 모두 수행한 후, rear가 가리키는 배열의 인덱스는?• 배열의 인덱스는 0부터 5까지 사용한다.
• 초기 상태에서 front와 rear은 모두 0을 가리키며, 큐는 공백 상태이다.
• 공백 상태와 포화 상태를 구분하기 위해 항상 한 칸을 비워 두는 방식으로 구현한다.
• enqueue는 데이터를 삽입하는 연산이며, rear을 먼저 한 칸 이동시킨 후 해당 위치에 저장한다.
• dequeue는 데이터를 삭제하는 연산이며, front를 먼저 한 칸 이동시킨 후 해당 데이터를 삭제한다.enqueue(A) ⇒ enqueue(B) ⇒ enqueue(C) ⇒
dequeue() ⇒ enqueue(D) ⇒ enqueue(E) ⇒ enqueue(F)
0
3
4
5
모든 연산을 마친 뒤 rear는 인덱스 0을 가리킨다.
enqueue는 , dequeue는 로 이동한다.
A는 1, B는 2, C는 3에 저장되고 dequeue로 front가 1이 된다. D는 4, E는 5, F는 에 저장되며, 이때 다음 칸이 front가 되어 포화 상태가 된다.
오류나 개정된 내용이 보이면 알려주세요
[91, 42, 17, 12, 80, 95, 3, 27] 배열을 셸(shell) 정렬로 오름차순 정렬할 때, 간격을 에 저장하는데, 인 단계가 완료된 직후의 배열 상태는? (단, 최초 간격 는 배열 원소 개수 에 대하여 이고 이후 각 단계에서 절반으로 감소한다.)
[3, 12, 17, 27, 80, 42, 91, 95]
[3, 12, 27, 17, 80, 42, 91, 95]
[80, 42, 3, 12, 91, 95, 17, 27]
[80, 42, 3, 12, 95, 91, 17, 27]
단계 직후 배열은 [3, 12, 17, 27, 80, 42, 91, 95]이다.
단계: (91, 80), (42, 95), (17, 3), (12, 27) 부분 리스트를 각각 정렬하면 [80, 42, 3, 12, 91, 95, 17, 27]이다.
단계: 짝수 위치 (80, 3, 91, 17)은 (3, 17, 80, 91)로, 홀수 위치 (42, 12, 95, 27)은 (12, 27, 42, 95)로 정렬해 합친다.
오류나 개정된 내용이 보이면 알려주세요
힙(heap)에 대한 설명으로 가장 옳지 않은 것은?
최대 힙은 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같고, 최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작다.
삽입 연산 시 노드가 개인 완전 이진 트리에서 다음 노드의 확장 자리는 번의 노드이며 그 자리에 삽입할 원소를 임시 저장한다.
일반적인 힙의 삭제 연산 시 루트 노드에 있는 원소를 삭제한다.
힙을 구현할 때 1차원 배열의 순차 자료구조를 이용하면 인덱스 관계를 이용하여 부모 노드를 찾기가 쉽다.
최소 힙은 부모 키값이 자식 키값보다 작거나 같으면 되므로, "항상 작다"고 한 설명이 옳지 않다.
힙은 같은 키값을 허용하므로 최대 힙(부모 ≥ 자식)과 마찬가지로 최소 힙도 등호를 포함한 부모 ≤ 자식 관계를 만족한다.
오류나 개정된 내용이 보이면 알려주세요
가중치 무방향 그래프에서 크루스칼(Kruskal) 알고리즘을 이용해 최소 비용 신장 트리를 구성하려고 한다. 간선의 가중치는 <보기>와 같다. 크루스칼 알고리즘으로 간선을 선택하는 과정에서, 세 번째로 신장 트리에 포함되는 간선은?(A, B): 2, (A, C): 3, (B, C): 1, (B, D): 5, (C, D): 4
(A, B)
(A, C)
(B, D)
(C, D)
세 번째로 신장 트리에 포함되는 간선은 (C, D)이다.
크루스칼 알고리즘은 가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 제외한다.
(B, C) 1 선택 → (A, B) 2 선택 → (A, C) 3은 A-B-C 사이클을 만들어 제외 → (C, D) 4 선택.
오류나 개정된 내용이 보이면 알려주세요
<보기>와 같은 순회 결과들을 모두 만족하는 7개의 노드로 이루어진 이진 트리의 구조로 옳은 것은?전위 순회: A − B − D − E − F − C − G
중위 순회: D − B − F − E − A − C − G
후위 순회: D − F − E − B − G − C − A
세 순회를 모두 만족하는 트리는 E의 왼쪽 자식이 F, C의 오른쪽 자식이 G인 구조이다.
전위 순회의 첫 노드 A가 루트이고, 중위 순회에서 A의 왼쪽(D B F E)이 왼쪽 서브트리, 오른쪽(C G)이 오른쪽 서브트리가 된다. 왼쪽 서브트리는 전위상 B가 루트로 D가 왼쪽, F·E가 오른쪽에 오며, 전위 E−F·중위 F−E이므로 F는 E의 왼쪽 자식이다.
오른쪽 서브트리는 전위 C−G, 중위 C−G이므로 G는 C의 오른쪽 자식이고, 후위 순회 D−F−E−B−G−C−A로도 확인된다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 코드는 원형 연결 리스트(circular linked list)에서 특정 노드 old를 삭제하는 C언어 함수이다. 빈칸 (가), (나)에 들어갈 내용으로 가장 옳은 것은? (단, head는 첫 번째 노드를 가리키며, 삭제 후에도 기존 노드들의 순서는 유지된다.)void deleteNode(linkedList_h* CL, listNode* old) {
listNode* pre;
if (CL->head == NULL) return;
if (CL->head->link == CL->head) {
free(CL->head);
CL->head = NULL;
return;
}
else if (old == NULL) return;
else {
pre = CL->head;
while (pre->link != old) {
pre = pre->link;
}
( (가) )
if (old == CL->head) {
( (나) )
}
free(old);
}
}(가) old->link = pre->link; (나) CL->head = old->link;
(가) pre->link = old->link; (나) CL->head = old->link;
(가) pre->link = old->link; (나) CL->head = pre;
(가) pre = old->link; (나) CL->head = old->link;
(가)는 pre->link = old->link;, (나)는 CL->head = old->link;이다.
pre는 old의 바로 앞 노드이므로 pre의 링크를 old의 다음 노드로 바꿔 old를 리스트에서 떼어낸다. old가 head였다면 순서를 유지하도록 old의 다음 노드를 새 head로 지정한다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. 이때 실제 자식 노드를 가리키는 링크 수를 , 중위 선행자 또는 중위 후속자를 가리키는 스레드 수를 , 스레드 구성 후에도 NULL로 남는 포인터 수를 라고 할 때, , , 의 값으로 가장 옳은 것은? (단, 중위 선행자나 중위 후속자가 없는 경우 해당 스레드 포인터에는 NULL을 저장한다.)
중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.
그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 개이고, 전체 포인터 개 중 빈 포인터는 개이다.
중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 개이다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 AVL 트리에 5를 삽입한 후, AVL 트리의 균형을 유지하기 위해 수행해야 하는 회전으로 가장 옳은 것은?
LL 회전
RR 회전
LR 회전
RL 회전
5를 삽입하면 루트 30에서 왼쪽-왼쪽 방향으로 불균형이 생기므로 LL 회전을 수행한다.
그림의 트리는 루트 30의 왼쪽에 20(자식 10, 25), 오른쪽에 40이 있다. 5는 30→20→10을 거쳐 10의 왼쪽 자식으로 삽입된다.
삽입 후 30의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 균형 인수가 +2이고, 불균형 노드 30에서 삽입 위치까지 왼쪽→왼쪽으로 내려가므로 20을 축으로 오른쪽 회전하는 LL 유형이다. 회전 후 20이 루트가 되고 왼쪽에 10(자식 5), 오른쪽에 30(자식 25, 40)이 온다.
오류나 개정된 내용이 보이면 알려주세요
<보기>의 방향 그래프에 대해 위상 정렬(topological sort)을 수행할 때, 가능한 서로 다른 위상 순서의 총 개수는?
3
4
5
6
가능한 위상 순서는 모두 5가지이다.
그래프의 간선은 A→B, A→C, B→D, C→D, C→E, D→F, E→F이다. 진입 차수가 0인 정점은 A뿐이므로 A가 맨 앞, 모든 경로가 끝나는 F가 맨 뒤에 고정된다.
가운데 B, C, D, E는 D가 B·C 뒤에, E가 C 뒤에 와야 한다. B로 시작하면 B−C−D−E, B−C−E−D의 2가지, C로 시작하면 C−B−D−E, C−B−E−D, C−E−B−D의 3가지가 있어 합은 5가지이다.
오류나 개정된 내용이 보이면 알려주세요
[691, 423, 17, 124, 80, 95, 3, 227] 배열을 LSD(least significant digit) 기수 정렬로 오름차순 정렬할 때, 2단계가 완료된 직후 배열 상태로 가장 옳은 것은?
[3, 17, 124, 227, 423, 80, 691, 95]
[3, 17, 423, 124, 227, 80, 691, 95]
[17, 3, 227, 423, 124, 80, 95, 691]
[17, 3, 423, 227, 124, 80, 95, 691]
2단계 직후 배열은 [3, 17, 423, 124, 227, 80, 691, 95]이다.
1단계(일의 자리): 0→80, 1→691, 3→423·3, 4→124, 5→95, 7→17·227 순으로 모아 [80, 691, 423, 3, 124, 95, 17, 227]이 된다.
2단계(십의 자리, 같은 자릿값은 앞 단계 순서 유지): 0→3, 1→17, 2→423·124·227, 8→80, 9→691·95 순으로 모은다.
오류나 개정된 내용이 보이면 알려주세요
<보기>는 무방향 그래프에서 깊이 우선 탐색(DFS, depth first search)을 수행하는 C 프로그램이다. dfs(0)을 호출했을 때, order[2]와 order[3]의 값으로 가장 옳은 것은?int adj[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
int visited[5] = { 0, };
int order[5];
int cnt = 0;
void dfs(int v) {
visited[v] = 1;
order[v] = ++cnt;
for (int i = 0; i < 5; i++) {
if (adj[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}order[2]: 2, order[3]: 4
order[2]: 3, order[3]: 4
order[2]: 5, order[3]: 3
order[2]: 5, order[3]: 4
order[2]는 5, order[3]은 3이다.
인접 행렬을 인덱스 순서로 검사하며 방문하지 않은 정점이 있으면 즉시 재귀한다.
dfs(0): order[0]=1 → dfs(1): order[1]=2 → dfs(3): order[3]=3, 더 갈 곳이 없어 복귀 → dfs(4): order[4]=4 → dfs(2): order[2]=5.
오류나 개정된 내용이 보이면 알려주세요
크기가 8인 해시 테이블에서 해시 함수 을 사용하고, 충돌은 체이닝(chaining)으로 처리한다. <보기>의 키를 순서대로 삽입할 때, 가장 긴 체인이 형성된 버킷의 인덱스와 해당 체인의 길이를 옳게 짝지은 것은? (단, 버킷의 인덱스는 0부터 시작한다.)13, 25, 6, 21, 14, 29, 8
인덱스 0, 길이 2
인덱스 5, 길이 3
인덱스 5, 길이 4
인덱스 6, 길이 2
가장 긴 체인은 인덱스 5, 길이 3이다.
13→5, 25→1, 6→6, 21→5, 14→6, 29→5, 8→0이므로 버킷 5에 13·21·29의 3개가 연결된다.
오류나 개정된 내용이 보이면 알려주세요
[7급 서울시 자료구조론] 26년 1회차 시험지 PDF 다운로드·인쇄 →
[7급 서울시 자료구조론] 26년 1회차 정답과 해설은 무료인가요?
이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.
이 회차를 CBT 로 직접 풀어볼 수 있나요?
7급 서울시 자료구조론 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 서울시 자료구조론 기출문제 풀러 가기 →
시험지 PDF 나 전자책으로도 볼 수 있나요?
이 회차의 인쇄용 시험지 PDF 페이지에서 시험지를 받을 수 있습니다. 시험지 PDF 받기 →






