크기가 10인 해시 테이블을 배열을 이용하여 만든다고 가정하자. 해시함… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
크기가 10인 해시 테이블을 배열을 이용하여 만든다고 가정하자. 해시함수로 h(k) = k mod 10을 사용한다. 여기서 mod는 모듈로(modulo) 함수를 의미한다. 데이터가 다음과 같은 순서로 입력된다고 할 때 발생하는 충돌(collision) 횟수의 총 합으로 옳은 것은? (단, 배열의 인덱스는 [0]~[9]까지이고, 처음에 배열은 비어 있으며, 충돌을 해결하기 위해서는 배열의 다음 빈 공간에 데이터를 입력하는 선형 조사법(linear probe)을 사용한다고 가정한다)
70, 17, 26, 69, 72, 53, 31, 27, 23, 13
1
3
2
4
3
5
4
6
해설

선형 조사법으로 넣으면 충돌은 모두 4회 일어난다.

70, 17, 26, 69, 72, 53, 31은 각각 인덱스 [0], [7], [6], [9], [2], [3], [1]에 충돌 없이 들어간다.

27은 [7]에서 1회 충돌 후 [8]에, 23은 [3]에서 1회 충돌 후 [4]에 들어간다. 13은 [3]과 [4]에서 2회 충돌한 뒤 [5]에 들어간다.
합계: 1 + 1 + 2 = 4

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

이어서 풀어보기

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