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

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

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

무방향 그래프에서 정점의 차수(degree)란 무엇입니까?

1. A그 정점에 연결된 간선의 수
2. B인접 리스트에서의 위치
3. C그 정점에서 출발하는 가장 긴 경로의 길이
4. D그래프의 정점 수

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

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

연결 리스트에서 센티넬(더미) 노드의 목적은 무엇입니까?

1. Ahead나 tail의 특수한 경우를 없애 코드를 단순하게 하기 위해
2. B리스트를 정렬된 상태로 만들기 위해
3. C리스트가 정해진 최대 노드 수를 넘어 커지는 것을 막기 위해
4. D원소의 개수를 저장하기 위해

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

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

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

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

정점이 V개이고 인접 행렬로 저장된 그래프에서 너비 우선 탐색의 실행 시간은 얼마입니까?

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

랭크에 의한 합집합(union by rank)이나 경로 압축 없이, 원소가 n개인 union-find 구조에서 find 한 번의 최악의 경우 비용은 얼마입니까?

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