정답이 있는 자료구조 학습지

"선입선출"(FIFO) 원칙으로 동작하는 자료 구조는 무엇입니까?

1. A큐(Queue)
2. B힙(Heap)
3. C스택(Stack)
4. D이진 트리(Binary tree)

텍스트 편집기의 "실행 취소"(undo) 기능에 가장 적합한 자료 구조는 무엇입니까?

1. A해시 셋
2. B스택
3. C그래프
4. D큐

트리의 레벨 순서 순회(level-order)에 사용하는 자료 구조는 무엇입니까?

1. A큐
2. B해시 테이블
3. C우선순위 큐
4. D스택

AVL 트리는 모든 노드에서 어떤 균형 조건을 유지합니까?

1. A모든 리프가 정확히 같은 깊이에 있다
2. B왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다
3. C모든 노드의 두 서브트리가 정확히 같은 수의 노드를 포함한다
4. D모든 노드가 빨간색 또는 검은색으로 칠해져 있다

배열에 저장된 이진 최소 힙(인덱스는 0부터 시작)에서 인덱스 i인 노드의 자식은 어디에 있습니까?

1. Ai/2와 i/2 + 1
2. Bi + 1과 i + 2
3. C2i와 2i + 1
4. D2i + 1과 2i + 2

큐를 스택 두 개로 구현합니다. "in" 스택에 push하고 "out" 스택에서 pop하며, "out"이 비면 "in"에서 다시 채웁니다. 연산당 분할 상환 비용은 얼마입니까?

1. AO(log n)
2. BO(1)
3. CO(n)
4. DO(n²)

레드-블랙 트리가 반드시 만족해야 하는 성질은 무엇입니까?

1. A루트는 빨간색이어야 한다
2. B모든 빨간 노드의 자식은 빨간색이어야 하므로 빨간 노드가 리프까지 끊기지 않는 사슬을 이룬다
3. C모든 노드는 빨간색이어야 한다
4. D한 노드에서 그 자손 리프까지의 모든 경로에 있는 검은 노드의 수가 같다

n개의 수로 된 배열에 대한 펜윅 트리(Fenwick tree, 이진 인덱스 트리)는 어떤 연산을 O(log n)에 지원합니까?

1. A임의 위치에 원소 삽입
2. B접두사 합 질의와 단일 원소 갱신
3. C배열 정렬과 이진 탐색
4. DO(1)에 중앙값 찾기