1. 해시 자료구조와 충돌 해결
해시 테이블에서 키 충돌을 처리하는 가장 일반적인 방법 두 가지는 무엇인가요?
A) 선형 탐색과 이진 탐색 B) 선형 조사와 이중 해싱 C) 체이닝과 개방 주소법 D) 재귀적 분할과 합병
2. 그래프 이론과 트리
다음 중 그래프와 트리의 차이점을 올바르게 설명한 것은 무엇인가요?
A) 그래프는 사이클을 포함할 수 있지만, 트리는 사이클이 없다. B) 그래프는 방향성이 있지만, 트리는 방향성이 없다. C) 트리는 항상 연결 그래프이지만, 그래프는 그렇지 않을 수 있다. D) 그래프는 루트 노드가 있지만, 트리에는 루트 노드가 없다.
3. 정렬 알고리즘의 효율성
다음 중 퀵정렬과 병합정렬의 주요 차이점을 설명한 것은 무엇인가요?
A) 퀵정렬은 항상 O(N log N)의 시간복잡도를 가지지만, 병합정렬은 그렇지 않다. B) 병합정렬은 안정 정렬이지만, 퀵정렬은 그렇지 않다. C) 퀵정렬은 추가 메모리가 필요하지 않지만, 병합정렬은 필요하다. D) 병합정렬은 최악의 경우에도 O(N log N)의 시간복잡도를 유지하지만, 퀵정렬은 그렇지 않다.
4. 이진탐색트리(BST)의 특성
이진탐색트리에서 중위 순회(inorder traversal)를 수행하면 얻을 수 있는 결과는 무엇인가요?
A) 트리의 모든 노드를 깊이 순으로 방문한다. B) 트리의 모든 노드를 너비 순으로 방문한다. C) 트리의 모든 노드를 오름차순으로 방문한다. D) 트리의 모든 노드를 내림차순으로 방문한다.
5. 다익스트라 알고리즘의 특징
다익스트라 알고리즘을 사용할 때, 힙(우선순위 큐)을 사용하지 않는다면 시간 복잡도는 어떻게 변할까요?
A) O(N^2)에서 O(N log N)으로 줄어든다. B) O(N log N)에서 O(N^2)으로 증가한다. C) O(N^2)를 유지한다. D) O(N log N)을 유지한다.
1. 해시 자료구조와 충돌 해결
정답: C) 체이닝과 개방 주소법
- 체이닝은 충돌이 발생할 경우 연결 리스트로 충돌하는 요소들을 관리합니다.
- 개방 주소법은 충돌이 발생하면, 다른 비어있는 해시 테이블의 주소를 찾아 그곳에 저장하는 방법입니다.
2. 그래프 이론과 트리
정답: A) 그래프는 사이클을 포함할 수 있지만, 트리는 사이클이 없다.
- 트리는 사이클이 없는 특수한 형태의 그래프입니다.
3. 정렬 알고리즘의 효율성
정답: D) 병합정렬은 최악의 경우에도 O(N log N)의 시간복잡도를 유지하지만, 퀵정렬은 그렇지 않다.
- 병합정렬은 모든 경우에 O(N log N)의 시간복잡도를 가집니다.
- 퀵정렬은 최악의 경우 O(N^2)의 시간복잡도를 가질 수 있습니다.
4. 이진탐색트리(BST)의 특성
정답: C) 트리의 모든 노드를 오름차순으로 방문한다.
- 이진탐색트리의 중위 순회는 노드를 오름차순으로 방문합니다.
5. 다익스트라 알고리즘의 특징
정답: B) O(N log N)에서 O(N^2)으로 증가한다.
- 힙을 사용하는 다익스트라 알고리즘의 시간 복잡도는 O(N log N)입니다.
- 힙을 사용하지 않을 경우, 각 노드에 대해 최소 거리를 찾는 데 O(N) 시간이 소요되므로 전체 시간 복잡도는 O(N^2)가 됩니다.
