[C언어로 쉽게 풀어쓴 자료구조] 6장

01 다음 중 NULL 포인터 (NULL pointer)가 존재하지 않는 구조는 어느 것인가?

(1) 단순 연결 리스트

(2) 원형 연결 리스트

(3) 이중 연결 리스트

(4) 헤더 노드를 가지는 단순 연결 리스트

 

02 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가?

(1) 배열

(2) 단순 연결 리스트

(3) 원형 연결 리스트

(4) 이중 연결 리스트

 

03 단순 연결 리스트에서 포인터 last가 마지막 노드를 가리킨다고 할 때 다음 수식 중 참인 것은?

(1) last==NULL

(2)last->data==NULL

(3)last->link==NULL

(4)last->link->link==NULL

 

04 단순 연결 리스트의 노드들을 포인터 p로 방문하고자 한다. 현재 p가 가리키는 노드에서 다음 노드로 가려면 어떤 코드를 사용해야 하는가?

(a)p++;

(b)p--;

(c)p=p->link;

(d)p=p->data;

 

05 다음과 같이 변수 p가 2를 저장한느 노드를 가리키도록 하는 문장을 작성하라.

 

06 다음과 같이 변수 q가 1을 저장하는 노드를 가리키도록 하는 문장을 작성하라.

07 다음과 같은 연결 리스트에 아래와 같은 코드를 실행한다고 하자. 실행이 끝난 후에 포인터 p가 가리키는 노드는 어떤 노드인가?

for (p=list->head; p->link!=NULL; p=p->link)

;

08 덱(deque: double-ended queue)은 삽입과 삭제가 양끝에서 임의로 수행되는 자료구조이다. 다음 그리미과 같이 단순 연결 리스트(singly linked list)로 덱을 구현한다고 할 때 O(1) 시간 내에 수행할 수 없는 연산은?(단, first 와 last는 각각 덱의 첫 번째 원소와 마지막 원소를 가리키며, 연산이 수행된 후에도 덱의 원형이 유지되어야한다.)

 

①insertFirst 연산: 덱의 첫 번째 원소로 삽입

②insertLast 연산: 덱의 마지막 원소로 삽입

③deleteFirst 연산: 덱의 첫 번째 원소를 삭제

④deleteLast 연산: 덱의 마지막 원소를 삭제

 

09 다음과 같이 단순 연결 리스트에 사용자가 입력하는 값을 저장했다가 출력하는 프로그램을 작성하라

노드의 개수 : 3 
노드 #1 데이터 : 5
노드 #2 데이터 : 6
노드 #3 데이터 : 7
생성된 연결 리스트: 5->6->7

10 다음과 같이 단순 연결 리스트의 노드들의 개수를 계산하는 프로그램을 작성해보자.

노드의 개수 : 3
노드 #1 데이터  : 5
노드 #2 데이터: 6
노드 #3 데이터 :7
연결 리스트 노드의 개수=3

11 단순 연결 리스트에 정수가 저장되어 있다. 연결 리스트에 있는 모든 노드의 데이터 값을 합한 결과를 출력하는 프로그램을 작성하시오.

노드의 개수: 3
노드 #1 데이터: 5
노드 #2 데이터: 6
노드 #3 데이터: 7
연결 리스트의 데이터 합: 18

12 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라.

노드의 개수: 3
노드 #1 데이터 :5
노드 #2데이터: 5
노드 #3 데이터: 7
탐색할 값을 입력하시오: 5
5는 연결리스트에서 2번 나타납니다.

13 단순연결 리스트에서의 탐색 함수를 참고하여 특정한 데이터 값을 갖는 노드를 삭제한느 함수를 작성하라.

 

14 다음 그림과 같은 데이터를 저장할 수 있는 단순 연결 리스트를 생성하는 프로그램을 작성해보자.

15 단순 연결 리스트가 정렬되지 않은 정수들의 리스트를 저장하고 있다. 리스트에서 최대값과 최소값을 찾는 프로그램을 작성하라.

 

16 단순 연결리스트의 헤드 포인터가 주어져있을 때 첫 번째 노드에서부터 하나씩 건너서 있는 노드를 전부 삭제하는 함수를 작성하라. 즉 홀수번째 있는 노드들이 전부 삭제된다.

 

17 두 개의 단순 연결 리스트 A,B가 주어져있을 경우, alternate 함수를 작성하라. alternate함수는 A와 B로부터 노드를 번갈아 가져와서 새로운 리스트 C를 만드는 연산이다. 만약 입력리스트 중에서 하나가 끝나게 되면 나머지 노드들을 전부 C로 옮긴다. 함수를 구현하여 올바르게 동작하는지 테스트하라. 작성된 함수의 시간 복잡도를 구하라.

18 2개의 단순 연결 리스트를 병합하는 함수를 조금 변경하여 보자. 두 개의 연결리스트 a=(a ₁,a₂...), b=(b₁,b₂...)가 데이터 값의 오름차순으로 노드들이 정렬되어 있는 경우, 이러한 정렬 상태를 유지하면서 합병을 하여 새로운 연결리스트를 만드는 알고리즘merge를 작성하라. a와 b에 있는 노드들은 전부 새로운 연결 리스트로 옮겨진다. 작성된 알고리즘의 시간 복잡도도 구하라. 

 

19 단순 연결리스트 C를 두 개의 단순 연결리스트 A와 B로 분리하는 함수 split를 작성하여 보자. C의 홀수 번째 노드들은 모두 A로 이동되고 C의 짝수 번째 노드들은 모두 B로 이동된다. 이 함수가 C를 변경하여서는 안 된다. 작성된 알고리즘의 시간 복잡도를 구하고 구현하여 수행하여 보라.

 

20 두 개의 다항식이 다음과 같이 주어졌다. 이들을 연결리스트를 이용하여 나타내고 본문의 프로그램을 이용하여 두 다항식의 합을 구해보시오. 

 

A(x)=3x⁶+7x³-2x²-9, B(x)=-2x⁶-4x⁴+6x²+6x+1

 

21 다항식을 연결 리스트로 표현할 수 있음을 보였다. 다항식이 연결 리스트로 표현되어 있고, p를 다항식을 가리키는 포인터라고 할 때, 어떤 실수 x에 대하여 이 다항식의 값을 계산하는 함수 poly_eval 을 작성하라. 즉 다항식이 x³+2x+6 이고 x=2이면 2³+2*2+6를 계산하는 함수를 작성하려보라.

 

22 배열을 이용하여 숫자들을 입력 받아 항상 오름차순으로 정렬된 상태로 유지하는 리스트 SortedList를 구현하여 보라. 다음의 연산들을 구현하면 된다.

ADT 6.2 SortedList
- 객체: n개의 element형으로 구성된 순서있는 모임
- 연산: 
add(list, item) ::= 정렬된 리스트에 요소를 추가한다.
delete(list, item)::=정렬된 리스트에서 item을 제거한다.
clear(list) ::= 리스트의 모든 요소를 제거한다.
is_in_list(list, item)::= item이 리스트안에 있는지를 검사한다.
get_length(list)::= 리스트의 길이를 구한다.
is_empty(list)::= 리스트가 비었는지 검사한다.
is_full(list)::= 리스트가 꽉찼는지를 검사한다.
display(list)::= 리스트의 모든 요소를 표시한다.

23 단순 연결 리스트를 이용하여 숫자들을 항상 오름차순으로 정렬된 상태로 유지하는 리스트 SortedList를 구현하여 보라. 앞의 문제의 연산들을 구현하면 된다. 

 

24 행렬 (matrix)은 숫자나 문자를 정사각형 또는 직사각형으로 배열하여 그 양끝을 괄호로 묶은 것으로 많은 문제를 수학적으로 해결하는 도구이다. 희소 행렬(sparse matrix)은 많은 항들이 0인 행렬이다. 연결 리스트를 이용하여 희소 행렬을 표현하는 방법을 생각하여 보고 구현하라.