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

우선순위 큐를 구현할 때 일반적으로 사용하는 구조는 무엇입니까?

1. A힙
2. B문자열
3. C스택
4. D정렬되지 않은 단일 연결 리스트

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

1. A노드, 왼쪽 서브트리, 오른쪽 서브트리
2. B왼쪽 서브트리, 노드, 오른쪽 서브트리
3. C위에서부터 레벨별로
4. D왼쪽 서브트리, 오른쪽 서브트리, 노드

트리에서 리프(leaf)란 무엇입니까?

1. A값이 가장 큰 노드
2. B자식이 정확히 하나인 노드
3. C부모가 없는 노드
4. D자식이 없는 노드

용량이 n인 배열에 저장된 원형 큐에서 인덱스 i 다음 위치는 어떻게 계산합니까?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

개방 주소법을 사용하는 해시 테이블에서 가능한 최대 적재율은 얼마입니까?

1. A1
2. B0.5
3. C최대값이 없다
4. D2

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

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

힙 정렬에 대한 진술 중 옳은 것은 무엇입니까?

1. A안정적이며 O(n)의 추가 메모리가 필요하다
2. B추가 저장소로 이진 탐색 트리가 필요하므로 O(n)의 추가 메모리를 쓴다
3. C최악의 경우 O(n log n) 시간에 제자리 정렬하지만 안정적이지 않다
4. D어떤 입력에서든 O(n) 시간에 실행된다

랭크 기반 합치기(union by rank)와 경로 압축(path compression)을 사용하는 union-find(서로소 집합) 구조의 연산당 분할 상환 비용은 얼마입니까?

1. AO(n)
2. BO(α(n)), 즉 역 아커만 함수로, 실질적으로 상수이다
3. CO(n²)
4. D정확히 O(log n)