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

배열에서는 O(1)이지만 단일 연결 리스트에서는 O(n)인 연산은 무엇입니까?

1. A인덱스 i의 원소에 접근하기
2. B첫 번째 원소 읽기
3. Chead 원소 제거하기
4. Dhead에 삽입하기

덱(deque, double-ended queue)이란 무엇입니까?

1. A뒤쪽에서만 제거할 수 있는 큐
2. B양쪽 끝에서 삽입과 제거를 할 수 있는 구조
3. C하나의 배열을 공유하는 별개의 큐 두 개
4. D우선순위로 정렬된 큐

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

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

AVL 트리와 레드-블랙 트리가 보장하는 것은 무엇입니까?

1. A키가 삽입 순서대로 저장됨
2. B재균형을 통한 O(log n) 높이
3. C자식이 두 개인 노드가 없음
4. D모든 경우의 상수 시간 탐색

키를 정렬된 순서로 삽입하면, n개의 노드를 가진 이진 탐색 트리의 최악의 높이는 얼마입니까?

1. A√n
2. B1
3. Clog₂ n
4. Dn (연결 리스트처럼 됨)

리스트 중간에 있는 노드에 대한 참조가 있습니다. 어떤 리스트에서 그 노드를 O(1)에 제거할 수 있습니까?

1. A정렬된 배열
2. B동적 배열
3. C이중 연결 리스트
4. D단일 연결 리스트

레드-블랙 트리 규칙은 키가 n개인 트리의 높이에 대해 무엇을 보장합니까?

1. A높이는 정확히 log₂ n이다
2. B높이는 최대 log₂ n + 1이다
3. C높이는 최대 n / 2이다
4. D높이는 최대 2 log₂(n + 1)이다

get과 put이 O(1)인 LRU(least recently used) 캐시를 지원하는 자료 구조는 무엇입니까?

1. A하나의 정렬된 배열
2. B해시 맵과 이중 연결 리스트의 조합
3. C이진 탐색 트리만
4. D스택만