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

해시 테이블은 데이터를 어떤 형태로 저장합니까?

1. A정렬된 리스트로만
2. B키가 정렬된 트리
3. C고정 길이 문자열
4. D해시 함수로 위치가 정해지는 키–값 쌍

배열에서는 느리지만 연결 리스트의 head에서는 빠른 연산은 무엇입니까?

1. A5번째 원소에 접근하기
2. B맨 앞에 삽입하기
3. C인덱스로 마지막 원소 읽기
4. D고정 배열의 길이 구하기

그래프의 인접 리스트 표현에서 각 정점마다 무엇이 저장됩니까?

1. A다른 모든 정점까지의 최단 경로
2. B그래프의 전체 간선 수
3. CV개의 불리언 값으로 된 행
4. D이웃한 정점들의 리스트

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

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

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

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

균형 이진 탐색 트리에서 키를 탐색하는 시간 복잡도는 무엇입니까?

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

이진 탐색 트리에서 자식이 두 개인 노드를 삭제할 때는 보통 어떻게 합니까?

1. A중위 후속자(또는 선행자)로 대체한 다음 그 노드를 삭제한다
2. B루트와 맞바꾼다
3. C그 아래 서브트리를 처음부터 다시 만들어 그 안에 있던 모든 키를 다시 삽입한다
4. D서브트리 전체를 삭제한다

단순 균등 해싱 가정에서, 키가 n개이고 버킷이 m개인 체이닝 해시 테이블의 탐색 기대 시간은 얼마입니까?

1. AO(m)
2. Bα = n / m일 때 O(1 + α)
3. CO(n)
4. DO(log n)