6장 연습문제

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

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

연결 자료구조에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위구조인 노드를 사용한다.

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

단순연결리스트

원형연결리스트

이중연결리스트

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

① p = p.link;

포인터p가 가리키는 노드의 다음노드로 포인터를 이동하라.

② p = q;

포인터q가 가리키는 노드를 포인터p도 가리키게 하여라.

③ p.link = q

포인터 q가 가리키는 노드를 포인터p가 가리키는 노드의 다음노드가 되도록 연결하여라.

④ p.link = q.link;

포인터q가 가리키는 노드의 다음노드를 포인터p가 가리키는 노드의 다음노드가 되도록 연결하여라.

4. 주소록 프로그램을 단순 연결 리스트를 이용하여 작성하여라.  [해답제공 x]

작성 조건1)

주소록은 이름, 전호번호, 메일주소를 저장할 수 있도록 노드를 구성하여라.

작성 조건2)

새로운 사람에 대한 주소록 삽입 연산을 작성하여라.

새로운 노드는 항상 주소록의 마지막에 삽입되도록 하여라.

작성 조건3)

지정한 이름에 대한 노드를 주소록에서 검색하여 삭제하는 연산을 작성하여라.

5. 다음 자료 중 성격이 다른 하나는? (2006년 5월 기출문제)

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

6. 연결리스트에 대한 설명으로 거리가 먼 것은? (2007년 기출문제)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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