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

맵(딕셔너리)은 무엇을 저장합니까?

1. A같은 키의 쌍
2. B삽입 순서대로 값만
3. C키가 유일한 키–값 쌍
4. D크기순으로 정렬된 값

단일 연결 리스트에서 마지막 노드의 next 포인터에는 무엇이 들어 있습니까?

1. A이전 노드의 주소
2. B리스트의 노드 수
3. C첫 번째 노드의 주소
4. DNull(노드 없음)

최대 힙 성질(max-heap property)이란 무엇입니까?

1. A모든 왼쪽 자식의 키가 오른쪽 형제의 키보다 크거나 같다
2. B모든 리프에 최대 키가 들어 있다
3. C키가 왼쪽에서 오른쪽으로 정렬되어 있다
4. D모든 부모의 키가 자식의 키보다 크거나 같다

정점 V개, 간선 E개인 그래프에서 인접 리스트는 메모리를 얼마나 사용합니까?

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E²)

이진 힙을 포인터 없이 배열에 저장할 수 있는 이유는 무엇입니까?

1. A배열이 키를 자동으로 정렬된 순서로 유지하므로 포인터가 필요 없기 때문에
2. B힙에는 원소가 100개를 넘지 않기 때문에
3. C힙의 모든 키가 같기 때문에
4. D완전 이진 트리이므로 위치가 간단한 인덱스 공식을 따르기 때문에

알파벳이 고정된 트라이(trie)에서 길이 L인 단어를 탐색하는 데 얼마나 걸립니까?

1. An이 단어 수일 때 O(log n)
2. B저장된 단어 수와 관계없이 O(L)
3. CO(L × n)
4. Dn이 단어 수일 때 O(n)

배열의 각 원소에 대해 그 오른쪽에서 다음으로 큰 원소를 전체 O(n) 시간에 구하려고 합니다. 도움이 되는 구조는 무엇입니까?

1. A원소마다 다시 만드는 이진 탐색 트리
2. B답을 기다리는 원소들을 유지하는 스택
3. C모든 원소 쌍을 담는 큐
4. D모든 원소의 해시 테이블

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

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