C로 배우는 쉬운 자료구조
C로 배우는 쉬운 자료구조 개정 3판 Chapter 04 연습문제
가속 ・ 2020. 6. 8. 19:32
URL 복사 이웃추가
본문 기타 기능
신고하기
| 01. 연결 리스트를 사용하기에 적합한 경우는? | ||
| ① 자료를 정렬하는 경우 ② 자료를 역순으로 처리하는 경우 ③ 자료의 삽입과 삭제가 많은 경우 ④ 자료를 탐색하는 경우 | ||
| 연결 리스트는 데이터 이외에 다른 노드를 가리키는 주솟값을 가지기 때문에 배열에 비해 삽입과 삭제가 간단하다 |
| 02. 성격이 다른 자료구조는? | ||
| ① Stack ② Queue ③ Linked List ④ Circular Queue | ||
| 4번 원형 큐는 배열을 이용한 순차 자료구조임 |
| 03. 연결 리스트에 대한 설명으로 거리가 먼 것은? | ||
| ① 노드의 삽입과 삭제가 쉽다. ② 노드들이 포인터로 연결되어 있어 탐색이 빠르다. ③ 연결해 주는 포인터를 위한 추가 공간이 필요하다. ④ 연결 리스트 중에서 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 어렵다. | ||
| 연결 리스트는 배열에 비해 탐색 속도가 떨어진다. 연결 리스트의 장점은 삽입과 삭제가 용이한 것이다. |
| 04. 다음과 같은 단순 연결 리스트에 대해, 아래와 같은 C언어로 작성된 프로그램을 수행한 후 포인터 tmp가 가리키는 노드는? | ||
| L P ↓ ↓ data link → . . . . . →data link → data link → data NULL 가 나 다 라 for (tmp = L; tmp->link != p; tmp = tmp -> link); tmp -> link = p -> link; | ||
| ① 가 ② 나 ③ 다 ④ 라 | ||
| 초기식 tmp = L 조건식 tmp의 link(temp 의 다음 노드)가 P가 아닐때 까지 반복 변화식 tmp = temp -> link 반복문을 마치면 tmp는 P 노드의 이전 노드인 '나' 노드를 가리키게 된다. 이후 tmp -> link = p -> link tmp 의 link가 p의 link(라) 를 가리키게 되어 연결 순서는 가 . . . . 나 라 가 된다. 이 코드는 '다' 노드를 삭제하기 위한 코드인 걸 알 수 있다. |
| 05. n개의 데이터로 구성된 선형 리스트를 단순 연결 리스트로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은? | ||
| ① 포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제 ② 리스트 길이를 출력 ③ 포인터 값이 주어진 임의의 노드 앞에 새로운 노드 추가 ④ 마지막 노드의 데이터 | ||
| ① 삭제할 이전 노드의 주솟값이 주어졌기 때문에 바로 삭제 연산을 진행할 수 있다. ② ④ n번의 탐색이 필요하다. ③ 임의의 노드 앞의 노드를 찾기 위한 탐색 과정이 필요하다. |
| Index | Name | Pointer |
| 1 | KIM | 6 |
| 2 | PARK | 1 |
| 3 | CHOI | 4 |
| 4 | BAEK | 2 |
| 5 | LEE | 7 |
| 6 | MIN | 5 |
| 7 | ANN | 8 |
| 8 | JUNG | - |
| 06. 다음 선형 연결 리스트리스트에서 LEE를 찾기 위한 비교 횟수는? (단, HEADER는 3이다.) | ||
| 위 표 참고 | ||
| ① 4 ② 5 ③ 6 ④ 7 | ||
| 3 → 4 → 2 → 1 → 6 → 5(LEE) 6회 |
| 07. C 언어를 사용해 연결 리스트를 구현할 때, 관련이 없는 것은? | ||
| ① 비트 단위 논리곱 ② 자기 참조 구조체 ③ 동적 메모리 할당 ④ 포인터 | ||
| |
| 메모리 주소 | data | link |
| 2000 | A | 2020 |
| 2010 | B | 2030 |
| 2020 | C | 2010 |
| 2030 | D |
| 08. 자료들이 단순 연결 리스트에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은? | ||
| 위 표 참고 | ||
| ① A의 link → 2030 ② B의 link → 2010 ③ B의 link → 2020 ④ C의 link → 2030 | ||
| 자료의 연결 순서는 A (2000) → C (2020) → B (2010) → D(2030) 이다. B를 삭제할 경우 A (2000) → C (2020) → D(2030)가 되는데 C의 link가 D로 바뀌었다. |
| 09. 다음 포인터 연산의 의미를 설명하시오. | ||
| (가) p = p.link; (나) p = q; (다) p.link = q; (라) p.link = q.link | ||
| (가) p를 p의 다음 노드로 설정한다. (나) p가 가리키는 값은 q가 된다. (다) p의 다음 노드는 q 노드이다. (라) p의 다음 노드는 q의 다음 노드이다. |
| 10. 단순 연결 리스트 L에서 특정 노드 p 바로 뒤에 새로운 노드 new를 삽입하기 위한 연산 insertAfter의 가상코드가 다음과 같다. ㉠에 들어갈 내용으로 옳은 것은? | ||
| Algorithm insertAfter(L, p, new) if L = NULL then L ← new; else ㉠ end if return | ||
| ① p.next ← new; new. next ← p.next; ② new.next ← p.next; p.next ← new; ③ new.next ← p; p.next ← new; ④ p.next ← new; new.next ← p; | ||
| L이 NULL이 아닐 때 new 노드를 삽입하는 연산이 필요하다. new의 다음 노드를 p의 다음 노드로 설정하고 p의 다음 노드를 new노드로 설정한다. 순서가 바뀌면 원래 p의 다음 노드값을 찾을 수 없게 된다. |
| 11. 다음 C코드에서 foobar 함수가 하는 일을 바르게 설명한 것은? | ||
| struct list_t{ int data; struct list_t *link; }; typedef struct list_t *list_p; void foobar(list_p *ptr, struct list_t *node){ if (*ptr == NULL){ *ptr = node; node -> link = node; } else{ node -> link = (*ptr) -> link; (*ptr) -> link = node; } } | ||
| ① 한 줄로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다. ② 한 줄로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다. ③ 원형으로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다. ④ 원형으로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다. | ||
| foobar 함수는 *ptr이 NULL일 경우에는 node로 원형 리스트를 만든다. NULL아닐 경우에는 *ptr의 뒤에 node를 삽입한다. |
| 12. 다음 알고리즘은 주어진 단순 연결 리스트를 역순으로 변환하는 알고리즘이다. 알고리즘의 ㉠에 들어갈 내용으로 옳은 것은? (단, 리스트의 시작 주소를 나타내는 포인터는 start이며 노드의 연결 포인터 필드는 link이다.) | ||
| p = start; q = NULL; while (p != NULL){ ㉠ p = p -> link; q -> link = r; } start = q; | ||
| ① q = q -> link; r = q; ② r = q; q = p; ③ r = q; p -> link; ④ q = q -> link; | ||
| 역순으로 변환하려면 연결 리스트가 3개 필요하다. |
| 13. 구조체 list를 이용한 단순 연결 리스트 x, y의 후위 노드(색칠된 부분)들을 서로 스왑(Swap)하기 위한 코드는? (단, 후위 노드들의 next는 NULL이 아니다.) | ||
| x → data next → (색칠된 부분) → data next → . . . y → data next → (색칠된 부분) → data next → . . . struct list{ int data; struct list *next; }*x, *y, *tmp | ||
| ① ② ③ ④ 보기 생략 | ||
| 임의로 각 노드의 데이터를 x1, x2, x3 , y1, y2, y3라고 한다. tmp = x -> next -> next; x -> next -> next = y -> next -> next; y -> next -> next = tmp; tmp = x -> next; x -> next = y -> next; y -> next = tmp; 임의로 각 노드의 데이터를 x1, x2, x3 , y1, y2, y3라고 한다. ① tmp는 x3 노드를 가리킨다 ② x2의 다음 노드를 y3 노드로 설정 ③ y2의 다음 노드를 tmp노드로 설정(현재 tmp 노드는 x3을 가리킴) ④ tmp는 x2 노드를 가리킨다 ⑤ x1의 다음 노드를 y2 노드로 설정 ⑥ y1의 다음 노드를 tmp노드로 설정(현재 tmp노드는 x2를 가리킴) 아래 그림 처럼 연결하고 데이터를 순서대로 읽으면 x1 → y2 → x3 → . . . . . y1 → x2 → y3 → . . . . .이 된다. |
문제 13의 답
| 14. 희소행렬은 연결 리스트로 표현할 때 가장 큰 장점은? | ||
| ① 기억 장소가 절약된다. ② 임의의 위치로 액세스가 가능하다. ③ 이진 탐색이 가능하다. ④ 행렬 사이의 연산 시간을 줄일 수 있다. | ||
| 희소행렬을 이차원 배열로 표현할 경우 배열에 행 번호, 열 번호, 값인 3가지 데이터가 필요하다. 연결 리스트를 이용할 경우 값, 다음 노드의 주소 2가지 데이터만 있으면 된다. |
| 15. 다음은 원형 연결 리스트의 길이를 구하는 함수이다. 원형 연결 리스트의 마지막 노드를 last가 가리키고 있을 때, ㉠에 들어갈 문장으로 옳은 것은? | ||
| int length(listPointer last){ listPointer temp = last; int count = 0; if (last){ for (count = 1; ㉠; count++) temp = temp -> link; } return count; } | ||
| ① temp -> link != last ② temp == last -> link ③ temp != last -> link ④ temp -> link == NULL | ||
| last는 원형 연결 리스트의 마지막 노드를 가리킨다. temp의 다음 노드가 last를 가리킨다면 한 바퀴를 탐색한 것이다. |
| 16. 원형 연결 리스트 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도는? | ||
| ㉠ 포인터 ptr이 원형 연결 리스트의 맨 앞 노드를 가리키는 경우 ㉡ 포인터 ptr이 원형 연결 리스트의 맨 뒤 노드를 가리키는 경우 | ||
| ㉠ ㉡ ① O(1) O(1) ② O(1) O(n) ③ O(n) O(1) ④ O(n) O(n) | ||
| 연결 리스트에 새로운 노드를 삽입하려면 삽입하고자 하는 위치 이전의 노드의 주소를 알아야한다. ㉠ 포인터 ptr이 맨 앞 노드를 가리킬 경우 그 앞 노드(마지막 노드)를 탐색하기 위한 연산이 추가로 필요하다. ㉡ 포인터 ptr이 마지막 노드를 가리킨다면 삽입하고자 하는 위치의 이전 노드의 주소를 알고 있는 것이니 바로 새로운 노드를 삽입할 수 있다. |
| 17. 원형 연결 리스트 길이를 계산하기 위한 C 함수를 작성하고자 한다. ㉠과 ㉡에 들어갈 알맞은 명령은? (단, 원형 연결 리스트의 길이는 노드 개수로 정의하고, 원형 연결 리스트의 시작 포인터는 ptr이라고 가정한다.) | ||
| struct list_node{ char data; struct list_node* link; } typedef struct list_node* list_pointer; int CListLength(list_pointer ptr){ list_pointer temp; int count = 0; if ( ㉠ ){ temp = ptr; do{ count++; }while ( ㉡ ); } return count; } | ||
| ㉠ ㉡ ① !ptr temp -> link != ptr ② ptr temp = temp -> link, temp != ptr ③ !ptr temp = temp -> link, temp == ptr ④ ptr temp -> link == ptr | ||
| 15번과 비슷한 문제지만 이 문제는 count가 0부터 시작한다. temp와 ptr이 같아질 때까지 link를 타고 이동한다. 처음에 temp 를 ptr로 초기화 하기 때문에 do while문을 사용. |
| 18. 이중 연결 리스트에서 노드 p 다음(next) 노드가 q이고 이전(prev) 노드가 p인 경우, 인접한 p, q 노드의 위치를 서로 바꾸는 연산 순서로 옳은 것은? (단, p, q 노드는 모두 연결 리스트의 처음 노드나 마지막 노드가 아니라고 가정한다.) | ||
| ㄱ. p -> preve -> next = q; ㄴ. q -> next -> prev = p; ㄷ. p -> prev = q; ㄹ. q -> next = p; ㅁ. q -> prev = p -> prev; ㅂ. p -> next = q -> next; | ||
| ① ㄱ → ㄴ → ㄷ → ㄹ → ㅁ → ㅂ ② ㄱ → ㄴ → ㅁ → ㅂ → ㄷ → ㄹ ③ ㄱ → ㄴ → ㅂ → ㄹ → ㄷ → ㅁ ④ ㄷ → ㄹ → ㅁ → ㅂ → ㄱ → ㄴ | ||
| |
| 19. 다음은 원형 연결 리스트의 맨 앞에 새로운 노드를 추가하는 알고리즘의 가상코드이다. ㉠, ㉡에 들어갈 문장으로 옳은 것은? (단, 원형 연결 리스트에서 last는 리스트의 맨 마지막 노드를 가리키는 포인터이고 초기치는 NULL 가상코드이며, 변수 p는 새로 삽입되는 노드를 나타낸다. 또한 리스트에 노드를 세 개 이상 추가할 수 있어야 한다.) | ||
| struct node{ int key; struct node *next; }*last = NULL; // 마지막 노드를 가리키는 포인터 Function insertFront(struct node *p) if (last == NULL) then // 리스트가 빈 경우 last = p; p -> next = p; else // 리스트에 하나 이상의 노드가 있는 경우 ㉠ ㉡ end if return; end | ||
| ㉠ ㉡ ① p -> next = last -> next last -> next = p; ② last -> next = p; p -> next = last -> next; ③ p -> next = last; last -> next = p; ④ last -> next = p; p -> next = last; | ||
| 원형 연결 리스트인 것에 주의 |
| 20. 이중 연결 리스트에서 포인터 p가 가리키는 노드의 오른쪽에 포인터 newNode가 가리키는 노드를 삽입할 때, 연산 순서가 바르게 나열된 것은? (단, llink는 왼쪽 노드를 가리키는 포인터이고 rlink는 오른쪽 노드를 가리키는 포인터이다.) | ||
| ㄱ. p -> rlink = newNode; ㄴ. newNode -> llink = p; ㄷ. newNode -> rlink = p -> rlink; ㄹ. p -> rlink -> llink = newNode; | ||
| ① ㄱ - ㄴ - ㄷ- ㄹ ② ㄴ - ㄱ - ㄹ- ㄷ ③ ㄴ - ㄷ- ㄱ - ㄹ ④ ㄴ - ㄷ - ㄹ - ㄱ | ||
| ㄴ - ㄷ - ㄱ - ㄹ의 순으로 하면 ㄹ이 p -> rlink -> rlink -> llink가 되어야함. |
| 21. 다음 코드는 가용 공간 리스트로부터 노드를 할당받아 이중 연결 리스트에 새로운 값 x를 삽입하기 위한 함수의 일부이다. 할당받은 노드에 대한 포인터는 new이고, 이중 연결 리스트에서 삽입 위치는 pre가 가리키는 노드 뒤라고 하자. ㉠, ㉡에 알맞은 문장은? | ||
| new ← getNode(); new.data ← x; ㉠ ㉡ pre.rlink ← new; new.llink ← pre; | ||
| ㉠ ㉡ ① new.rlink ← pre.rlink; new.rlink.llink ← new.llink; ② new.llink ← pre.rlink; new.rlink.rlink ← new; ③ new.llink ← pre.rlink; new.rlink.rlink ← new.llink; ④ new.rlink ← pre.rlink; new.rlink.llink ← new; | ||
| ㉠ ㉡ 뒤에서 pre의 오른쪽 link와 new의 왼쪽 link를 서로 연결하고 있다. ㉠과 ㉡에서는 new의 오른쪽 link를 연결하는 과정이 필요하다. |
| 22. 이중 연결 리스트가 적당한 자료구조는? | ||
| ① 스택 ② 큐 ③ 원형 큐 ④ 데크 | ||
| 데크는 이중 연결 리스트를 사용해 큐의 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있도록 확장된 큐 자료구조이다. |
| 23. 다음 구조체를 갖는 이중 연결 리스트에서 A, B, C는 각각 노드를 가리키는 포인터 변수이다. 노드 B를 삭제하기 위한 명령으로 옳지 않은 것은? | ||
| struct Dlist{ int data; struct Dlist *left; struct Dlist *right; }; 그림 생략 | ||
| ① B -> right -> left = B -> left; B -> left -> right = B -> right; ② A -> right = C; C -> left = A; ③ A -> right = A -> right -> right; B -> right -> left = B -> left; ④ C -> left -> right = B -> right; C -> left = B -> left; | ||
| C -> left -> right == B -> right 이므로 의미 없는 문장이다. |
| 24. 다음은 이중 연결 리스트의 맨 앞에 새로운 키값을 갖는 노드를 삽입하는 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 바르게 짝지어진 것은? (단, head는 이중 연결 리스트의 맨 앞 노드를 가리키는 포인터이며, 리스트는 초기에 비어 있다고 가정한다. | ||
| 코드 생략 | ||
| ㉠ ㉡ ㉢ ① temp -> prev = NULL temp -> prev = head temp -> prev = head ② temp -> prev = NULL temp -> next = NULL temp -> next = head ③ temp -> next = temp temp -> next = NULL temp -> prev = head ④ temp -> next = temp temp -> prev = head temp -> next = head | ||
| ㉠ 우선 temp 의 이전 노드를 NULL로 설정한다. (맨 앞에 삽입할 거니까) ㉡ 리스트에 NULL이면 연결할 노드가 없으므로 temp의 다음 노드도 NULL로 설정한다. ㉢ temp는 맨 앞에 삽입할 노드이므로 next를 head와 연결해준다. |
| 25. 순차 자료구조와 연결 자료구조를 비교하여 설명하시오. | ||
| 순차 자료구조는 빈자리 없이 값을 저장하기 때문에 메모리를 적게 잡아먹는데 연결 자료구조는 값 이외에 다음 자료의 주소를 저장하여야 하기 때문에 순차 자료구조에 비해 메모리를 많이 잡아먹는다. 순차 자료구조는 데이터를 삽입하거나 삭제할 때 모든 원소를 이동시켜야 하는 반면 연결 자료구조는 다음 자료의 주소값만 바꾸어 주면 되기 때문에 삽입과 삭제가 쉽다. 순차 자료구조는 연결 자료구조에 비해 탐색이 빠르다. |
| 26. 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트의 특징을 비교하여 설명하시오. | ||
| 단순 연결 리스트는 각 노드가 다음 노드를 가리키는 주솟값을 갖기 때문에 배열과 비교해 값의 삽입과 삭제가 쉽다. 원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 첫 번째 노드를 가리키는 것으로 한 노드에서 모든 노드로 접근할 수 있다. 이중 연결 리스트는 이전 노드를 가리키는 주솟값과 다음 노드를 가리키는 주솟값을 둘다 저장한다. 그래서 값을 삽입하거나 삭제할 때 이전 노드의 주솟값을 따로 구하는 연산을 하지 않아도 된다. |
| 27. 이중 연결 리스트가 필요한 경우를 예를 들어 설명하시오. | ||
| 이중 연결 리스트는 이전 노드와 이후 노드의 주솟값을 둘 다 가지고 있다. 이는 인터넷 브라우저에서 이전 방문 / 이후 방문 기능에 사용된다. 인터넷을 사용하다가 이전에 방문했던 페이지를 방문할 때 이전 버튼을 누르면 방금 전의 페이지가 나오고 그 상태에서 또 이전 버튼이나 이후 버튼을 이용해 페이지를 방문할 수 있다. 한글이나 엑셀, 포토샵 등 편집 프로그램에도 사용된다. 해당 프로그램들에는 되돌리기(Ctrl+Z)와 다시 실행(Ctrl+Shift+Z or Ctrl + Y) 기능이 있다. 되돌리기 버튼을 누르면 방금 전에 수행한 동작을 원래대로 되돌린다. 그 상태에서 다시 실행을 누르면 되돌리기를 실행하여 취소했던 명령이나 동작을 다시 실행한다. 저장된 메모리가 허용하는 한 되돌리기 버튼을 계속 누를 수도 있다. |
| 28. 다음과 같이 구조체 자료형인 _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는 삭제하려는 정수이다.) | ||
| tail이 무슨 용도인지는 모르겠는데 쓰레기값이 저장되어서 값이 100,000 이상일 때 쓰레기값으로 판단 후 NULL처리 이후는 교재에 나오는 연결 리스트와 비슷함 |
#include <stdio.h>#include <stdlib.h>typedef struct _node{ int data; struct _node *next;}node;node *head, *tail;void init_list(){ head = (node*)malloc(sizeof(node)); tail = (node*)malloc(sizeof(node)); head -> next = tail; tail -> next = tail;}node *ordered_insert(int k){ node* newNode = (node*)malloc(sizeof(node)); newNode -> data = k; if (head -> next -> data >= 100000){ newNode -> next = NULL; head -> next = newNode; tail -> next = newNode; } else{ node* temp = head -> next; node* pre = NULL; while(k > temp -> data){ pre = temp; temp = temp -> next; } if (pre == NULL){ newNode -> next = temp; head -> next = newNode; } else{ newNode -> next = temp; pre -> next = newNode; } }}node* print_list(node* t){ int count = 0; printf("{"); while (t != NULL){ printf("%d", t -> data); t = t -> next; count++; if (count >= 10) break; if (t != NULL) printf(", "); } printf("} \n");}int delete_node(int k){ node* pre = head -> next; node* old; while (pre -> next -> data != k) pre = pre -> next; old = pre -> next; pre -> next = pre -> next -> 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); delete_node(8); print_list(head -> next); return 0;}
직접 푼 거라 틀린 문제가 있을 수 있습니다.
댓글23 이 글에 댓글 단 블로거 열고 닫기
인쇄
