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

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

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

가중 그래프란 무엇입니까?

1. A간선이 정점보다 많은 그래프
2. B각 간선에 비용이나 거리 같은 수치가 있는 그래프
3. C디스크에 저장된 그래프
4. D간선이 더 많은 일부 정점이 다른 정점보다 무거운 그래프

그래프에서 사이클이란 무엇입니까?

1. A가중치가 0인 간선
2. B간선이 없는 정점
3. C모든 정점을 방문하는 경로
4. D같은 정점에서 시작하고 끝나는 경로

키를 정렬된 순서로 삽입하면, n개의 노드를 가진 이진 탐색 트리의 최악의 높이는 얼마입니까?

1. An (연결 리스트처럼 됨)
2. B√n
3. C1
4. Dlog₂ n

어떤 애플리케이션은 빠른 조회가 필요하고, 키를 정렬된 순서로 나열하고 범위 질의에도 답해야 합니다. 가장 적합한 구조는 무엇입니까?

1. A정렬되지 않은 연결 리스트
2. B균형 이진 탐색 트리
3. C스택
4. D해시 테이블

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

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

데이터베이스가 인덱스에 일반 B-트리보다 B+ 트리를 자주 사용하는 이유는 무엇입니까?

1. AB+ 트리는 이진 내부 노드를 사용하여 디스크 읽기 횟수를 줄이기 때문에
2. BB+ 트리는 균형을 유지할 필요가 없기 때문에
3. C모든 레코드가 연결된 리프에 있어 범위 스캔이 효율적이기 때문에
4. DB+ 트리는 데이터를 루트에만 저장하기 때문에

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

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