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

스택의 맨 위에 원소를 추가하는 연산의 이름은 무엇입니까?

1. APeek
2. BEnqueue
3. CPop
4. DPush

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

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

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

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

이진 트리의 루트는 1이고 왼쪽 자식은 2, 오른쪽 자식은 3입니다. 노드 2의 자식은 4(왼쪽)와 5(오른쪽)입니다. 후위 순회 결과는 무엇입니까?

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D1 2 4 5 3

원소가 n개인 배열의 중간에 원소를 삽입하는 비용은 얼마입니까?

1. A이진 탐색 때문에 O(log n)
2. B인덱스를 알고 있으므로 O(1)
3. C각 원소가 n번 이동하므로 O(n²)
4. D뒤의 원소들을 이동시켜야 하므로 O(n)

균형 이진 탐색 트리에서 키를 탐색하는 시간 복잡도는 무엇입니까?

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

O(1)의 추가 메모리로 단일 연결 리스트에 사이클이 있는지 어떻게 탐지할 수 있습니까?

1. A개수가 리스트 길이 필드를 넘을 때까지 노드를 센다
2. B포인터 하나는 한 칸씩, 다른 하나는 두 칸씩 움직여 만나는지 확인한다
3. C방문한 모든 노드를 해시 집합에 저장한다
4. D리스트를 정렬하고 중복을 찾는다

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

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