과목 구분 없음9급 국가직 공무원 컴퓨터일반 · 2011년04월09일 · 7/20
7.자료 구조 중 최악의 경우를 기준으로 했을 때 탐색(search) 성능이 가장 좋은 것은?
1
정렬되지 않은 배열
2
체인법을 이용하는 해쉬 테이블
3
이진 탐색 트리
4
AVL 트리정답
해설
- 정렬되지 않는 배열 : O(n) - 체인법을 이용하는 해쉬 테이블 : O(n) 체인법 사용시 연결리스트 모양의 해쉬 테이블로 구성,최악의 경우 => 모든 데이터에서 충돌이 발생하고 같은 주소에서 연결리스트 모양을 얻게 되는 경우 - 이진탐색 트리 : O(n) : 한쪽으로 치우쳐진 경우 - AVL 트리 : O(logn)