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

단일 연결 리스트에서 각 노드에는 무엇이 들어 있습니까?

1. A데이터만
2. B데이터와 다른 모든 노드에 대한 참조
3. C데이터와 인덱스
4. D데이터와 다음 노드에 대한 참조

트리의 루트는 무엇입니까?

1. A자식이 없는 노드
2. B부모가 없는 최상위 노드
3. C중간에 있는 아무 노드
4. D가장 큰 값을 가진 노드

단일 연결 리스트에서 마지막 노드의 next 포인터에는 무엇이 들어 있습니까?

1. A리스트의 노드 수
2. BNull(노드 없음)
3. C첫 번째 노드의 주소
4. D이전 노드의 주소

리스트 중간에 있는 노드에 대한 참조가 있습니다. 어떤 리스트에서 그 노드를 O(1)에 제거할 수 있습니까?

1. A단일 연결 리스트
2. B동적 배열
3. C이중 연결 리스트
4. D정렬된 배열

인덱스 0부터 시작하는 배열에 저장된 이진 힙에서 인덱스 i인 노드의 부모는 어디에 있습니까?

1. A인덱스 2i + 1
2. B인덱스 ⌊(i − 1) / 2⌋
3. C인덱스 ⌊i / 2⌋ + 1
4. D인덱스 i − 1

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

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

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

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

어떤 객체를 해시 맵의 키로 저장한 뒤, 그 해시 함수가 사용하는 필드를 바꿉니다. 예상되는 결과는 무엇입니까?

1. A맵이 자동으로 키를 새 버킷으로 옮긴다
2. B키의 해시는 프로그램이 시작될 때 한 번만 계산되므로 아무것도 바뀌지 않는다
3. C객체가 이전 해시의 버킷에 있으므로 조회가 실패할 수 있다
4. D필드가 바뀌는 순간 맵이 오류를 던진다