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

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

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

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

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

트리의 레벨 순서 순회(level-order)에 사용하는 자료 구조는 무엇입니까?

1. A스택
2. B큐
3. C해시 테이블
4. D우선순위 큐

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

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

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

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

이진 힙에 새 원소는 어떻게 삽입됩니까?

1. A배열의 끝에 놓고 힙 성질을 위반하는 동안 위로 올린다(sift up)
2. B더 큰 원소들을 모두 오른쪽으로 한 칸씩 밀어 정렬된 위치에 삽입한다
3. C힙 전체를 처음부터 다시 만든다
4. D루트에 놓고 아래로 내린다(sift down)

크러스컬의 최소 신장 트리 알고리즘에서 union-find 구조는 무엇에 사용됩니까?

1. A시작 정점을 고르는 것
2. B탐색 중 각 정점의 출발점으로부터의 현재 거리를 저장하는 것
3. C간선을 가중치순으로 정렬하는 것
4. D간선의 두 끝점이 이미 연결되어 있는지 확인하는 것

루트가 50이고, 왼쪽 서브트리는 30(자식 20, 40), 오른쪽 서브트리는 70(자식 60, 80)인 BST에서 중위 후속자를 사용하여 루트를 삭제합니다. 어떤 키가 새 루트가 됩니까?

1. A60
2. B40
3. C80
4. D70