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

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

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

덱(deque, double-ended queue)이란 무엇입니까?

1. A우선순위로 정렬된 큐
2. B뒤쪽에서만 제거할 수 있는 큐
3. C양쪽 끝에서 삽입과 제거를 할 수 있는 구조
4. D하나의 배열을 공유하는 별개의 큐 두 개

이진 트리의 후위 순회(postorder)는 노드를 어떤 순서로 방문합니까?

1. A오른쪽 서브트리, 노드, 왼쪽 서브트리
2. B왼쪽 서브트리, 오른쪽 서브트리, 노드
3. C왼쪽 서브트리, 노드, 오른쪽 서브트리
4. D노드, 왼쪽 서브트리, 오른쪽 서브트리

크기가 7인 해시 테이블이 h(k) = k mod 7과 선형 탐사를 사용합니다. 10을 삽입한 뒤 17은 어디에 저장됩니까?

1. A인덱스 0
2. B인덱스 6
3. C인덱스 3
4. D인덱스 4

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

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

키 50, 30, 70, 20, 40을 이 순서로 빈 이진 탐색 트리에 삽입합니다. 30의 왼쪽 자식은 무엇입니까?

1. A50
2. B70
3. C40
4. D20

이진 힙에서 decrease-key(원소의 위치를 알고 있는 경우)의 시간 복잡도는 무엇입니까?

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

이중 해싱은 주로 선형 탐사의 어떤 문제를 줄입니까?

1. A차 있는 칸들이 길게 이어지는 1차 군집(primary clustering)
2. B해시 함수가 필요하다는 것
3. C키를 테이블에 저장해야 한다는 것
4. D키의 값을 읽는 O(n) 비용