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

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

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

무방향 그래프에서 정점의 차수(degree)란 무엇입니까?

1. A그래프의 정점 수
2. B인접 리스트에서의 위치
3. C그 정점에 연결된 간선의 수
4. D그 정점에서 출발하는 가장 긴 경로의 길이

"후입선출"(LIFO) 원칙으로 동작하는 자료 구조는 무엇입니까?

1. A큐(Queue)
2. B해시 테이블(Hash table)
3. C연결 리스트(Linked list)
4. D스택(Stack)

알파벳이 고정된 트라이(trie)에서 길이 L인 단어를 탐색하는 데 얼마나 걸립니까?

1. An이 단어 수일 때 O(n)
2. B저장된 단어 수와 관계없이 O(L)
3. Cn이 단어 수일 때 O(log n)
4. DO(L × n)

높이를 간선 수로 셀 때, 높이가 h인 포화 이진 트리의 노드는 몇 개입니까?

1. A2^h
2. B2h + 1
3. Ch²
4. D2^h+1 − 1

큐를 스택 두 개로 구현합니다. "in" 스택에 push하고 "out" 스택에서 pop하며, "out"이 비면 "in"에서 다시 채웁니다. 연산당 분할 상환 비용은 얼마입니까?

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

기수 트리(radix tree, 압축 트라이)는 일반 트라이를 어떻게 개선합니까?

1. A자식이 하나인 노드들의 사슬을 문자열로 레이블된 간선 하나로 합친다
2. B각 단어를 개별 노드가 아니라 루트의 해시 테이블에 저장한다
3. C각 단어의 첫 글자만 유지한다
4. D각 노드의 자식을 빈도순으로 정렬한다

위상 정렬을 위한 칸(Kahn) 알고리즘은 진입 차수가 0인 정점을 반복해서 제거합니다. 그런 정점들은 어떤 구조에 보관됩니까?

1. A진출 차수로 정렬된 최대 힙
2. B방문한 모든 간선의 스택
3. C진입 차수가 0인 정점들의 큐(또는 아무 컬렉션)
4. D이미 제거된 정점이 어느 것인지 기록하는 인접 행렬