C언어로 쉽게 풀어쓴 자료구조 연습문제 EXERCISE 6 연결리스트

1. 다음중 NULL포인터가 존재하지 않는 구조는 어느 것인가?

1- 단순 연결 리스트 

[ h -> ㅁ -> ㅁ -> NULL ]

2- 원형 연결 리스트

[ h -> ㅁ(A) -> ㅁ -> ㅁ-> ㅁ(A) -> ... ]

3- 이중 연결 리스트

[ h <-> ㅁ <-> ㅁ <-> NULL ]

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

[1과 동일]

 

정답 - 2

 

 

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

1- 배열 = O(1)

2- 단순 연결 리스트 = O(n)

3- 원형 연결 리스트 = O(n)

4- 이중 연결 리스트 = O(n)

 

정답 - 1

 

 

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

1- last == NULL

2- last->data  == NULL

3- last->link == NULL

4- last->link->link == NULL

 

형태

last -> ㅁ -> NULL

1 = last는 노드가 있기에 NULL이 아님

2 = 모든 노드가 data를 가지고 있다는 가정 하에 last는 마지막 노드를 가르키고 있기에 NULL이 아님

3 = last의 link는 아무것도 없는 NULL을 가르키고 있기에 참

4 = 존재하지 않는 곳을 가르키고 있음

 

정답 - 3

 

 

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

(a)p++;

(b)p--;

(c)p=p->link;

(d)p=p->data;

 

정답 - 3

 

 

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

p -> 1ㅁ -> 2ㅁ-> r -> 3ㅁ -> NULL

을

p -> 2ㅁ -> r -> 3ㅁ -> NULL

로 변경

 

정답

Node *re;

re = p;

p = re->link;

free(re);

 

 

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

p -> 1ㅁ -> q ->2ㅁ -> r -> 3ㅁ -> NULL

을

p,q-> 1ㅁ -> 2ㅁ -> r -> 3ㅁ -> NULL

로 변경

 

정답

q = p;

 

 

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

list->head -> Aㅁ -> Bㅁ -> Cㅁ -> Dㅁ -> NULL

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

...

 

풀이

for 루프를 돌 경우 head를 가르키던 포인터 p는 1바퀴당 1칸씩 전진한다

이것을 p->link가 NULL일때 까지 한다는 것은 최후의 노드까지 전진하다 멈춘다는 것임

즉 p가 Dㅁ 노드에 도달 했을시 p->link가 NULL이기에 코드 실행후 p는 Dㅁ 노드를 가리킨다

 

정답

Dㅁ 노드

 

 

8. 덱은 삽입과 삭제가 양끝에서 임의로 수행되는 자료 구조이다. 다음 그림과 같이 단순 연결 리스트로 덱을 구현한다고 할 때 O(1) 시간내에 수행할 수 없는 연산은?

(단, fisrt와 last는 각각 덱의 첫번째 원소와 마지막 원소를 카리키며, 연산이 수행된 후에도 덱의 원형이 유지되어야 한다)

DQ,first -> x1ㅁ -> x2ㅁ -> ... -> last -> xnㅁ -> NULL

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

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

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

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

 

풀이

1 - o1

2 - on = 마지막 노드까지 n번 연산 필요

3 - o1

4 - on = 2번과 동일

 

정답 - 2, 4 

 

 

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

College/Data_structure/ListNode/EXERCISE_09 at main · NoNamed02/College

 

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

    int count = 0;
    Node* p = A;
    for(p;p!=NULL;p=p->link){
        count++;
    }
    free(p);
    printf("연결 리스트 노드의 개수 = %d", count);

College/Data_structure/ListNode/EXERCISE_10 at main · NoNamed02/College

 

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

    Node *p = A;
    int sum = 0;
    for(p; p != NULL ; p=p->link){
        sum += p->data;
    }
    printf("연결 리스트의 데이터 합: %d", sum);

College/Data_structure/ListNode/EXERCISE_11 at main · NoNamed02/College

 

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

    void find_num_to_node(Node *head){
    int find = 0;
    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &find);
    Node *p = head;
    int count = 0;
    for(p ; p != NULL ; p=p->link){
        if(p->data == find)
            count++;
    }
    printf("%d는 연결 리스트에서 %d번 나타납니다.", find, count);
    free(p);
}

College/Data_structure/ListNode/EXERCISE_12 at main · NoNamed02/College

 

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

Node* find_delete_node(Node *head){
    int find = 0;
    printf("삭제할 노드의값을 입력하시오: ");
    scanf("%d", &find);
    Node *p = head;
    for(p;p!=NULL;p=p->link){
        if(p->link->data == find)
            break;
    }
    head = _delete(head, p);
    return head;
}

College/Data_structure/ListNode/EXERCISE_13 at main · NoNamed02/College

 

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

Node* insert_last(Node* head, char N[], int a, float h){
    Node* p = head;
    while(p->link!=NULL){
        p=p->link;
    }
    Node* p2 = (Node*)malloc(sizeof(Node));
    strcpy(p2->name, N);
    p2->age = a;
    p2->heigh = h;
    p2->link = NULL;
    p->link = p2;
    return head;
}

College/Data_structure/ListNode at main · NoNamed02/College

 

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

void find_MM(Node* head){
    int min = head->data;
    int max = head->data;
    Node *p = head;
    while(p->link != NULL){
        if(p->data >= max )
            max = p->data;
        if(p->data <= min)
            min = p->data;
        p = p-> link;
    }
    printf("최솟값 %d\n", min);
    printf("최댓값 %d\n", max);
}

College/Data_structure/ListNode/EXERCISE_15 at main · NoNamed02/College

 

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