해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은?ㄱ… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은?
ㄱ. n개의 자료가 있을 때 자료의 탐색에 걸리는 시간은 O(logn)이다.
ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓(bucket)에 사상(mapping)시킨다.
ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다.
ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다.
ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다.
1
ㄴ, ㄷ
2
ㄴ, ㅁ
3
ㄱ, ㄹ
4
ㄹ, ㅁ
해설

옳은 것은 ㄹ, ㅁ이다.

해싱은 키의 대소 순서를 보존하지 않으므로 최대값을 찾으려면 모든 자료를 확인해야 해 O(n)이 걸린다. 좋은 해시함수는 충돌이 적고 주소에 고르게 분포해야 한다.

  • 탐색 시간 O(log n): 해싱의 평균 탐색 시간은 O(1)이며, O(log n)은 이진탐색이나 균형 탐색트리의 성능이다.
  • 서로 다른 자료가 항상 다른 버켓으로 간다는 설명: 키 공간이 주소 공간보다 커서 서로 다른 키가 같은 주소로 가는 충돌이 생긴다.
  • 적재 밀도가 높을수록 성능이 좋다는 설명: 적재 밀도가 높을수록 충돌이 늘어 탐색 성능이 나빠진다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 09년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기