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

트리의 루트는 무엇입니까?

1. A자식이 없는 노드
2. B가장 큰 값을 가진 노드
3. C중간에 있는 아무 노드
4. D부모가 없는 최상위 노드

트리의 높이는 일반적으로 어떻게 정의됩니까?

1. A루트와 모든 리프를 포함한 트리의 전체 노드 수
2. B루트에서 리프까지 가장 긴 경로의 간선 수
3. C루트의 자식 수
4. D트리의 리프 수

단일 연결 리스트에서 마지막 노드의 next 포인터에는 무엇이 들어 있습니까?

1. A이전 노드의 주소
2. B첫 번째 노드의 주소
3. CNull(노드 없음)
4. D리스트의 노드 수

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

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

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

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

충돌한 키들을 같은 버킷의 리스트에 저장하는 충돌 해결 방법은 무엇입니까?

1. A이중 해싱(Double hashing)
2. B분리 체이닝(Separate chaining)
3. C선형 탐사(Linear probing)
4. D이차 탐사(Quadratic probing)

n개의 수로 된 배열에 대한 펜윅 트리(Fenwick tree, 이진 인덱스 트리)는 어떤 연산을 O(log n)에 지원합니까?

1. A배열 정렬과 이진 탐색
2. B접두사 합 질의와 단일 원소 갱신
3. C임의 위치에 원소 삽입
4. DO(1)에 중앙값 찾기

개방 주소법을 사용하는 해시 테이블에서 삭제할 때 "툼스톤"(tombstone) 표시를 자주 사용하는 이유는 무엇입니까?

1. A테이블이 정렬된 상태가 되기 때문이다
2. B보안을 위해 삭제된 키를 영구히 보관해야 하므로 슬롯을 재사용할 수 없기 때문이다
3. C툼스톤이 해싱 속도를 높이기 때문이다
4. D슬롯을 비우면 다른 키의 탐사 순서가 끊길 수 있기 때문이다