자료구조 6장 연습문제 풀이

1. 순차 자료구조 방식과 연결 자료구조 방식을 비교 설명하시오.

 

답 : 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 연결 자료구조는 다음 원소의 주소에 의해 순서가 연결되는 방식이기 때문에 순차 자료구조와 달리 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

 

 

 

2. 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트의 특징을 설명하시오.

 

답 : 단순 연결 리스트는 단방향을 가리키고, 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킴, 이중 연결 리스트는 양방향을 가리키고 첫 번째, 마지막 노드가 서로를 가리키는 모습을 하고 있다.

 

 

 

3. 다음 참조 변수에 대한 연산의 의미를 설명하시오.

① p = p.link;

② p = q;

③ p.link = q;

④ p.link = q.link;

 

답 :

① p = p.link; → p가 가리키는 노드의 다음 노드로 포인터 이동

② p = q; → q가 가리키는 노드를 p도 가리킴

③ p.link = q; → q가 가리키는 노드를 p가 가리키는 노드의 다음 노드로

④ p.link = q.link; → q가 가리키는 노드의 다음 노드를 p가 가리키는 노드의 다음 노드로

 

 

 

5. 다음 자료 중 성격이 다른 하나는?

가. Stack    나. Queue    다. Linked List    라. Circular Queue

 

답 : 다. Linked List

 

 

 

6. 연결 리스트에 대한 설명으로 거리가 먼 것은?

가. 노드의 삽입이나 삭제가 쉽다.

나. 연결을 해주는 포인터를 위한 추가 공간이 필요하다.

다. 노드들이 포인터로 연결되어 검색이 빠르다.

라. 연결리스트 중에서 중간노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

 

답 : 다. 노드들이 포인터로 연결되어 검색이 빠르다.

? : 연결 리스트는 순차적으로 검색을 하기 때문에 많은 시간이 소요된다.

 

 

 

7. 연결 리스트에 대한 설명으로 옳지 않은 것은?

가. 단순 연결 리스트에서는 한쪽 방향으로만 이동이 가능하다.

나. 연결 리스트는 원형이 아닐 수도 있다.

다. 일반적으로 이중 연결 리스트의 노드는 적어도 3개의 필드를 가진다.

라. 이중 연결 리스트는 단순 연결 리스트보다 모든 면에서 우수하다.

마. 연결 리스트는 헤드 노드를 갖도록 구성할 수 있다.

 

답 : 라. 이중 연결 리스트는 단순 연결 리스트보다 모든 면에서 우수하다.

? : 포인터를 위한 공간이 많이 차지된다.

 

 

 

8. 단순 연결 원형 리스트에 대한 설명으로 가장 적절하지 않은 것은?

가. 단순 연결 리스트의 단점을 보완한 것이다.

나. 포인터 연결 방향의 반대 방향으로 직접 이동할 수 없다.

다. 삭제하고자 하는 노드에 대한 포인터만으로 그 노드를 삭제 할 수 없다.

라. 단점을 보완하기 위해 이중 연결 원형 리스트를 사용할 수 있다.

마. 마지막 노드의 링크 필드 값은 널(null)이다.

 

답 : 마. 마지막 노드의 링크 필드 값은 널(null)이다.

? : 마지막 노드의 링크 필드 값은 첫 번째 노드이다.

 

 

 

9. 이중 연결 리스트에 대한 설명으로 옳지 않은 것은?

가. 단순 연결 리스트의 노드에 비하여 링크 필드가 더 필요하다.

나. 특정 노드의 왼쪽과 오른쪽에 새로운 노드의 삽입과 삭제가 쉽다.

다. 원형으로 만들 경우 어떤 노드의 포인터 필드 값 1개를 잃어버려도 복구할 수 있다.

라. 같은 리스트를 단순 연결 리스트에 저장했을 때보다 시작 노드부터 n번째 노드를 찾는 시간이 더 빠르다.

마. 임의의 노드에 대한 포인터 값이 그 노드의 왼쪽 노드와 오른쪽 노드에 저장된다.

 

답 : 라. 같은 리스트를 단순 연결 리스트에 저장했을 때보다 시작 노드부터 n번째 노드를 찾는 시간이 더 빠르다.

? : 단순 연결 리스트보다 탐색 시간이 오래 걸린다.