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

이중 연결 리스트의 각 노드에는 무엇이 들어 있습니까?

1. A데이터 사본 두 개와 포인터 하나
2. B데이터, 다음 노드에 대한 포인터, 이전 노드에 대한 포인터
3. C데이터와 다음 노드에 대한 포인터만
4. D데이터와 포인터 두 개로, 하나는 다음 노드를, 다른 하나는 그 다음 다음 노드를 가리킨다

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

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

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

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

적재율이 임계값을 넘은 뒤 해시 테이블이 재해싱(rehash)하면 무슨 일이 일어납니까?

1. A기존 키를 제자리에서 정렬한다
2. B더 큰 테이블을 할당하고 모든 키를 다시 삽입한다
3. C자리를 만들기 위해 가장 오래된 키를 삭제한다
4. D충돌한 키만 테이블 끝의 새 오버플로 리스트로 옮긴다

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

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

이진 탐색 트리의 한 노드에 오른쪽 서브트리가 있습니다. 그 노드의 중위 후속자(in-order successor)는 어디에 있습니까?

1. A오른쪽 서브트리의 가장 왼쪽 노드
2. B항상 오른쪽 자식
3. C왼쪽 서브트리의 가장 오른쪽 노드
4. D항상 부모

원소가 n개인 이진 최소 힙에서 임의의 키를 탐색하는 데 얼마나 걸립니까?

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

배열에서 크기 k인 모든 윈도우의 최댓값을 전체 O(n)에 계산할 수 있게 하는 구조는 무엇입니까?

1. A이동으로 갱신하는 정렬된 배열
2. B윈도우마다 다시 만드는 최소 힙
3. C값의 내림차순으로 인덱스를 담는 덱
4. D윈도우 원소들의 단일 연결 리스트