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

트리에서 리프(leaf)란 무엇입니까?

1. A값이 가장 큰 노드
2. B자식이 정확히 하나인 노드
3. C부모가 없는 노드
4. D자식이 없는 노드

해시 테이블에서 충돌(collision)이란 무엇입니까?

1. A키를 전혀 해시할 수 없는 것
2. B테이블의 메모리가 바닥나는 것
3. C같은 두 키가 두 번 저장되는 것
4. D서로 다른 두 키가 같은 인덱스에 대응되는 것

트리에서 형제(sibling) 노드란 무엇입니까?

1. A서로 다른 서브트리에서 같은 깊이에 있는 노드들
2. B한 노드와 그 부모
3. C같은 부모를 공유하는 노드들
4. D자식이 없는 노드들

도로망에 교차로가 100,000개 있고, 각 교차로는 다른 교차로 약 4개와 연결됩니다. 가장 적합한 표현은 무엇입니까?

1. A간선들의 이진 힙
2. B정점들의 정렬된 배열 하나
3. C인접 리스트
4. D인접 행렬

실제로 배열 순회가 같은 길이의 연결 리스트 순회보다 훨씬 빠른 경우가 많은 이유는 무엇입니까?

1. A배열 원소는 연속되어 있어 CPU 캐시를 잘 활용하기 때문에
2. B연결 리스트는 항상 원소를 디스크에 저장하기 때문에
3. C배열 순회는 전체가 O(1)이고 연결 리스트 순회는 O(n)이기 때문에
4. D배열은 값 비교에 더 적은 명령어를 쓰기 때문에

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

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

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

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

힙 정렬에 대한 진술 중 옳은 것은 무엇입니까?

1. A안정적이며 O(n)의 추가 메모리가 필요하다
2. B어떤 입력에서든 O(n) 시간에 실행된다
3. C최악의 경우 O(n log n) 시간에 제자리 정렬하지만 안정적이지 않다
4. D추가 저장소로 이진 탐색 트리가 필요하므로 O(n)의 추가 메모리를 쓴다