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

방향 그래프란 무엇입니까?

1. A간선이 한 정점에서 다른 정점으로 향하는 방향을 가진 그래프
2. B사이클이 없는 그래프
3. C서로 다른 모든 정점 쌍이 간선으로 연결된 그래프
4. D모든 간선에 가중치가 있는 그래프

트리의 높이는 일반적으로 어떻게 정의됩니까?

1. A루트와 모든 리프를 포함한 트리의 전체 노드 수
2. B루트에서 리프까지 가장 긴 경로의 간선 수
3. C루트의 자식 수
4. D트리의 리프 수

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

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

이진 최소 힙에서 extract-min은 어떻게 동작합니까?

1. A루트를 제거하고 모든 원소를 왼쪽으로 한 칸씩 이동시킨다
2. B배열의 마지막 원소를 제거한다
3. C모든 리프에서 새로운 최솟값을 찾는다
4. D마지막 원소를 루트로 옮기고 아래로 내린다

실제로 배열 순회가 같은 길이의 연결 리스트 순회보다 훨씬 빠른 경우가 많은 이유는 무엇입니까?

1. A배열 원소는 연속되어 있어 CPU 캐시를 잘 활용하기 때문에
2. B배열은 값 비교에 더 적은 명령어를 쓰기 때문에
3. C배열 순회는 전체가 O(1)이고 연결 리스트 순회는 O(n)이기 때문에
4. D연결 리스트는 항상 원소를 디스크에 저장하기 때문에

실행 중인 프로그램이 활성 함수 호출과 그 지역 변수를 추적하는 데 사용하는 자료 구조는 무엇입니까?

1. A호출 스택(call stack)
2. B프레임들의 이진 탐색 트리
3. C함수들의 해시 테이블
4. D힙 메모리 큐

랭크에 의한 합집합(union by rank)이나 경로 압축 없이, 원소가 n개인 union-find 구조에서 find 한 번의 최악의 경우 비용은 얼마입니까?

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

세그먼트 트리는 일반적으로 무엇에 사용됩니까?

1. A구간 질의(구간 합 등)와 갱신을 O(log n)에 처리하는 데
2. B각 접두사를 별도의 트리 노드에 저장하여 문자열을 알파벳순으로 정렬하는 데
3. C그래프의 간선을 저장하는 데
4. D스택을 구현하는 데