[c로 배우는 쉬운 자료구조] 4장 연습문제

4장 연결 리스트 연습문제

01. 연결 리스트를 사용하기에 적합한 경우는?

1. 자료를 정렬하는 경우
2. 자료를 역순으로 처리하는 경우
3. 자료의 삽입과 삭제가 많은 경우
4. 자료를 탐색하는 경우

Ans: 3

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

1. 노드의 삽입과 삭제가 쉽다.
2. 노드들이 포인터로 연결되어 있어 탐색이 빠르다.
3. 연결해 주는 포인터를 위한 추가 공간이 필요하다.
4. 연결 리스트 중에서 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 어렵다.

Ans: 2

03. 다음과 같은 단순 연결 리스트에 대해, 아래와 같은 C 언어로 작성된 프로그램을 수행한 후 포인터 tmp가 가리키는 노드는?

1. 가
2. 나
3. 다
4. 라

Ans: 2

04. n개의 데이터로 구성된 선형 리스트를 단순 연결 리스트로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?

1. 포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제
2. 리스트 길이를 출력
3. 포인터값이 주어진 임의의 노드 앞에 새로운 노드 추가
4. 마지막 노드의 데이터

Ans: 1

05. 자료들이 단순 연결 리스트에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은?

1. A의 link → 2030
2. B의 link → 2010
3. B의 link → 2020
4. C의 link → 2030

Ans: 4

06. 다음의 왼쪽은 연결 리스트를 만들기 위한 코드의 일부분이다. 오른쪽 그림과 같이 두 노드 first와 second가 연결되었다고 가정하고 왼쪽 코드를 참조하여 노드 tmp를 노드 first와 노드 second 사이에 삽입할 때의 코드로 옳은 것은?

1. tmp.link = &first;
   first.link = &tmp;

2. tmp.link = first.link;
   first.link = &tmp;

3. tmp.link = &second;
   first.link = second.link;

4. tmp.link = NUL;
   second.link = &tmp;

Ans: 2

07. 다음 C 코드에서 foobar 함수가 하는 일을 바르게 설명한 것은?

1. 한 줄로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
2. 한 줄로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
3. 원형으로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
4. 원형으로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.

Ans: 3

08. 다음 알고리즘은 주어진 단순 연결 리스트를 역순으로 변환하는 알고리즘이다. 알고리즘의 ㉠에 들어갈 내용으로 옳은 것은? (단, 리스트의 시작 주소를 나타내는 포인터는 start이며 노드의 연결 포인터 필드는 link이다.)

1. q = q -> link; r = q;
2. r = q; q = p;
3. r = q; q = p -> link;
4. q = q -> link;

Ans: 2

09. 원형 연결 리스트 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도는?

	㉠	㉡
1.	Ο(1)	Ο(1)
2.	Ο(1)	Ο(n)
3.	Ο(n)	Ο(1)
4.	Ο(n)	Ο(n)

Ans: 3

10. 구조체 list를 이용한 단순 연결 리스트 x, y의 후위 노드(색칠된 부분)들을 서로 스왑하기 위한 코드는? (단, 후위 노드들의 next는 NULL이 아니다.)

1. tmp = x->next;
   x->next->next = y->next->next;
   y->next->next = tmp;
   tmp = y->next;
   x->next = y->next;
   y->next = tmp;

2. tmp = x->next->next;
   x->next->next = y->next->next;
   y->next->next = tmp;
   tmp = x->next;
   x->next = y->next;
   y->next = tmp;

3. tmp = x->next;
   x->next = y->next;
   y->next = tmp;
   tmp = x->next;
   x->next->next = y->next->next;
   y->next->next = tmp;

4. tmp = x->next->next;
   y->next->next = tmp;
   x->next->next = y->next->next;
   tmp = x->next;
   y->next = tmp;
   x->next = y->next;

Ans: 2

11. 희소행렬을 연결 리스트로 표현할 때 가장 큰 장점은?

1. 기억 장소가 절약된다.
2. 임의의 위치로 액세스가 가능하다.
3. 이진 탐색이 가능하다.
4. 행렬 사이의 연산 시간을 줄일 수 있다.

Ans: 1

12. 이중 연결 리스트에서 노드 p 다음(next) 노드가 q이고 노드 q 이전(prev) 노드가 p인 경우, 인접한 p, q 노드의 위치를 서로 바꾸는 연산 순서로 옳은 것은? (단, p, q 노드는 모두 연결 리스트의 처음 노드나 마지막 노드가 아니라고 가정한다.)

1. ㄱ－ㄴ－ㄷ－ㄹ－ㅁ－ㅂ
2. ㄱ－ㄴ－ㅁ－ㅂ－ㄷ－ㄹ
3. ㄱ－ㄴ－ㅂ－ㄹ－ㄷ－ㅁ
4. ㄷ－ㄹ－ㅁ－ㅂ－ㄱ－ㄴ

Ans: 2

13. 원형 연결 리스트 길이를 계산하기 위한 C 함수를 작성하려고 한다. ㉠과 ㉡에 들어갈 알맞은 명령은? (단, 원형 연결 리스트의 길이는 노드 개수로 정의하고, 원형 연결 리스트의 시작 포인터는 ptr이라고 가정한다.)

	㉠	㉡
1.	!ptr	temp -> link != ptr
2.	ptr	temp=temp -> link, temp != ptr
3.	!ptr	temp=temp -> link, temp == ptr
4.	ptr	temp -> link == ptr

Ans: 2

14. 이중 연결 리스트에서 포인터 p가 가리키는 노드의 오른쪽에 포인터 newNode가 가리키는 노드를 삽입할 때, 연산 순서가 바르게 나열된 것은? (단, llink는 왼쪽 노드를 가리키는 포인터이고 rlink는 오른쪽 노드를 가리키는 포인터이다.)

1. ㄱ－ㄴ－ㄷ－ㄹ
2. ㄴ－ㄱ－ㄹ－ㄷ
3. ㄴ－ㄷ－ㄱ－ㄹ
4. ㄴ－ㄷ－ㄹ－ㄱ

Ans: 4

15. 순차 자료구조와 연결 자료구조를 비교하여 설명하시오.

순차 자료구조는 논리적 순서와 물리적 순서가 같은 반면, 연결 자료구조는 논리적 순서와 물리적 순서가 반드시 같아야 하는 것은 아니다. 순차 자료구조는 배열을 이용하여 구현되고, 삽입 - 삭제 연산 이후 연속적인 물리적 위치를 유지하기 위해 원소를 이동하는 추가적인 작업이 필요하기 때문에 오버헤드가 발생할 수 있다. 연결 자료구조는 주소를 이용해 접근하기 때문에 포인터를 사용하고, 순차 자료구조처럼 물리적인 순서를 만들기 위한 추가 작업이 필요하지 않다.

16. 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트의 특징을 비교하여 설명하시오.

단순 연결 리스트는 노드와 노드 사이가 주솟값으로 연결되어 있는 형태기 때문에 배열과 같이 물리적인 공간을 만들고 값들을 이동하지 않아도 되므로 값의 삽입과 삭제가 쉽다.

원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 첫번째 노드와 연결되어있으므로 다른 노드로의 접근이 쉽다.

이중연결리스트는 값의 삽입과 삭제 시 이전 노드의 주솟값을 구하지 않아도 된다. 이전 노드와 다음 노드의 주솟값을 저장해둔 상태이기 때문이다.

17. 다음은 원형 연결 리스트의 맨 앞에 새로운 노드를 추가하는 알고리즘의 가상코드이다. ㉠, ㉡에 들어갈 문장으로 옳은 것은? (단, 원형 연결 리스트에서 last는 리스트의 맨 마지막 노드를 가리키는 포인터이고 초깃값은 NULL 가상코드이며, 변수 p는 새로 삽입되는 노드를 나타낸다. 또한 리스트에 노드를 세 개 이상 추가할 수 있어야 한다.)

	㉠	㉡
1.	p → next = last → next	last → next = p
2.	last → next = p	p → next = last → next
3.	p → next = last	last → next = p
4.	last → next = p	p → next = last

Ans: 1

18. 다음 구조체를 갖는 이중 연결 리스트에서 A, B, C는 각각 노드를 가리키는 포인터 변수이다. 노드 B를 삭제하기 위한 명령으로 옳지 않은 것은?

1. B -> right -> left = B -> left;
   B -> left -> right = B -> right;

2. A -> right = C;
   C -> left = A;

3. A -> right = A -> right -> right;
   B -> right -> left = B -> left;

4. C -> left -> right = B -> right;
   C -> left = B -> left;

Ans: 4

19. 다음은 이중 연결 리스트의 맨 앞에 새로운 키값을 갖는 노드를 삽입하는 알고리즘이다. ㉠~㉢에 들어갈 문장으로 바르게 짝지어진 것은? (단, head는 이중 연결 리스트의 맨 앞 노드를 가리키는 포인터이며, 리스트는 초기에 비어 있다고 가정한다.)

	㉠	㉡	㉢
1.	temp → prev = NULL	temp → prev = head	temp → prev = head
2.	temp → prev = NULL	temp → next = NULL	temp → next = head
3.	head → next = temp	temp → next = NULL	temp → prev = head
4.	head → next = temp	temp → prev = head	temp → next = head

Ans: 2

20. 다음과 같이 구조체 자료형인 _node를 선언하고 이를 이용해 연결 리스트를 만들었다. 다음 코드를 보고 물음에 답하시오(단 시작 함수는 _tmain( )이다).

(가) 숫자 10, 5, 8, 3, 1, 7을 삽입하되 작은 수부터 연결 리스트가 유지되도록 함수 ordered_insert(int k)를 작성하시오(단, k는 삽입하려는 정수이다).

(나) 연결 리스트를 구성하는 각 node의 변수 data를 모두 출력하는 함수 print_list(node* t)를 작성하시오(단, t는 node에 대한 시작 포인터이고, 화면에 출력할 함수는 printf()를 사용한다).

(다) 삭제하려는 숫자를 인수로 받아 그 노드를 삭제하는 함수 delete_node(int k)를 작성하시오(단, k는 삭제하려는 정수이다).

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    int data;
    struct _node* next;
}node;

node* head, * tail;

void init_list(void) {
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
    tail->data = -1;
} 
node* ordered_insert(int k) {
    node* newNode = (node*)malloc(sizeof(node));
    newNode->data = k;

    node* prev = head;
    node* current = head->next;

    int current_data;

    if (head->next->data == -1) {
        head->next = newNode;
        newNode->next = tail;
    }


    while (1) {
        if (current->next == current) {
            prev->next = newNode;
            newNode->next = current;
            break;
        }

        if (newNode->data < current->data) {
            prev->next = newNode;
            newNode->next = current;
            break;
        }

        prev = current;
        current = current->next;
    }
    return 0;
}

void print_list(node* current) {
    while (current->next != current) {
        printf("current data: %d\n", current->data);
        current = current->next;
    }
}

void delete_node(int data) {
    node* prev = head;
    node* current = head->next;
    while (current->next != current) {
        if (current->data == data) {
            prev->next = current->next;
        }

        prev = current;
        current = current->next;
    }
}



int main() {
    node* t;

    init_list();
    ordered_insert(10);
    ordered_insert(5);
    ordered_insert(8);
    ordered_insert(3);
    ordered_insert(1);
    ordered_insert(7);

    printf("\nInitial Linked list is ");
    print_list(head->next);

    printf("---- 삭제 연산 진행 ----\n");

    delete_node(8);
    print_list(head->next);

    return 0;
}

기존 함수 수정

void init_list(void) {
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
    tail->data = -1;
} // 노드들을 탐색할 때 어떤 노드가 tail인지 구분하기 위해서 코드 추가