자료구조 9장 연습문제

소개글

"자료구조 9장 연습문제"에 대한 내용입니다.

목차

없음

본문내용

1. 히프트리에서 노드가 삭제되는 위치는 어디인가?

1) 루트 2) 마지막 노드
3) 가장 최근에 삽입된 노드 4) 가장 먼저 삽입된 노드

1) 루트이다.

2. 히프를 배열로 표현할 수 있는 이유는 무엇인가?

1) 완전 이진트리이기 때문에 2) 어느 정도 정렬되기 때문에
3) 이진 트리이기 때문에 4) 히프 조건을 만족하기 때문에

1) 완전 이진트리이기 때문이다. 완전 이진 트리는 빈 공간이 없으므로,
배열으로 구현할 시 메모리가 낭비되지 않기 때문이다.

3. 히프 연산 중에서 하나의 노드가 삽입되거나 삭제되는 시간은 무엇에 비례하는가?
1) 노드의 개수 2) 트리의 높이 3) 항상 일정하다. 4) 예측 불가능하다.

4. 다음 중 히프 정렬이 특히 유용하게 사용될 수 있는 경우는?
1) 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할 때
2) 비교적 데이터의 개수가 적을 때
3) 정렬의 대상이 되는 레코드의 크기가 클 때
4) 데이터가 역순으로 정렬되어 있을 때

1) 오름차순으로 20개를 뽑고자 할 때이다. 힙 정렬의 성질은 부모 노드가 자식 노드보다 커야한다는 성질을 가지고 있으므로 힙 정렬은 내림차순으로 정렬되어있다. 그러므로 1)번의 경우 가장 유용하다.

5. 최소 히프에서 가장 작은 데이터가 있는 노드는?
1) 마지막 노드 2) 첫 번째 노드
3) 간 노드 4) 알 수 없다.

최소 힙은 오름차순 정렬이므로 가장 작은 데이터는 루트노드에 위치해있다. 그러므로 2) 첫 번째 노드이다.

6. 최소 히프에서 2번째로 작은 데이터가 있는 노드는?

2번의 위치에 있는 노드이다.

7. 10개의 데이터를 저장하고 있는 히프트리의 높이는?

히프트리는 완전 이진 트리이므로 이진 트리의 높이는 log2n+1의 식을 따른다. 그러므로 히프트리의 높이는 4이다.

8. 최소 히프를 구현한 배열의 내용이 다음과 같을 때 해당하는 히프트리를 그려라.

참고 자료

없음