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

트리에서 노드의 깊이(depth)란 무엇입니까?

1. A루트에서 그 노드까지의 간선 수
2. B그 노드에서 가장 깊은 리프까지의 간선 수
3. C그 서브트리의 노드 수
4. D그 노드의 자식 수

해시 테이블에서 해시 함수는 무엇을 합니까?

1. A테이블의 값을 암호화한다
2. B저장된 키의 개수를 센다
3. C키를 테이블의 인덱스에 대응시킨다
4. D테이블의 키를 정렬한다

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

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

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

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

이진 최소 힙에서 extract-min은 어떻게 동작합니까?

1. A루트를 제거하고 모든 원소를 왼쪽으로 한 칸씩 이동시킨다
2. B마지막 원소를 루트로 옮기고 아래로 내린다
3. C배열의 마지막 원소를 제거한다
4. D모든 리프에서 새로운 최솟값을 찾는다

인덱스 0부터 시작하는 배열에 저장된 이진 힙에서 인덱스 i인 노드의 부모는 어디에 있습니까?

1. A인덱스 ⌊i / 2⌋ + 1
2. B인덱스 i − 1
3. C인덱스 ⌊(i − 1) / 2⌋
4. D인덱스 2i + 1

키가 서로 다를 때 유일한 이진 트리를 항상 결정하는 순회 쌍은 무엇입니까?

1. A전위 순회만
2. B레벨 순서 순회만
3. C전위 순회와 후위 순회
4. D전위 순회와 중위 순회

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

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