C언어로 쉽게 풀어 쓴 자료구조 개정 2판 4장 리스트 연습문제
1. 리스트에 대한 설명 중 틀린 것은?
(4) 리스트는 집합과 동일하다.
풀이 : 집합에는 각 항목 간에 순서의 개념이 없으나 리스트에는 항목들 간에 순서가 있다.
리스트의 예로는, 월~일요일, 가~하, ace~king ...
2. 다음은 순차적 표현과 연결된 표현을 비교한 것이다. 설명이 틀린 것을 모두 표시하여라.
-> 순차적 표현=배열, 연결된 표현=리스트
(1) 연결된 표현은 포인터를 가지고 있어 상대적으로 크기가 작아진다.
풀이 : link field때문에 크기가 더 커짐
(2) 연결된 표현은 삽입이 용이하다.
풀이 : link pointer를 사용하기 때문에 삽입, 삭제가 용이하다.
(3) 순차적 표현은 연결된 표현보다 접근 시간이 많이 걸린다.
풀이 : 배열은 리스트보다 접근 시간이 더 빠름
배열은 x[n]으로 공간을 먼저 확보하고 데이터를 접근하므로 '상수시간'이 걸림
리스트는 N번째 원소에 찾아가기 위해 1, 2, 3, 4, ... , N-1, N으로 찾아가기 때문에 시간이 걸림 -> 노드들은 메모리 순서대로 할당되지 않는 경우도 있어 0x0000 -> 0x0008 -> 0x0004 -> 0x0012 이런 식으로 접근
(4) 연결된 표현으로 작성된 리스트를 2개로 분리하기가 쉽다.
풀이 : link pointer만 변경해주면 간편
ref : https://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=65046222&qb=67Cw7Je06rO8IOumrOyKpO2KuCDsoJHqt7zsi5zqsIQ=&enc=utf8§ion=kin&rank=1&search_sort=0&spq=0&pid=Un5aVsp0J14ssiIugEwsssssty4-354237&sid=TI5et04RypqvBWHUSpWDDg%3D%3D
https://blog.naver.com/sasayakki/221402108050
3. 다음은 연결 리스트에서 있을 수 있는 여러 가지 경우를 설명한다. 잘못된 항목은?
(1) 정적인 데이터보다는 변화가 심한 데이터에서 효과적인 방법이다.
풀이 : 변화가 심한 데이터는 계속 수정을 해주어야 한다는 의미(?) -> 삽입과 삭제가 용이해야함 -> 리스트의 특성
(2) 모든 노드는 데이터와 링크(포인터)를 가지고 있어야 한다.
(3) 연결 리스트에서 사용한 기억 장소는 다시 사용할 수 없다.
풀이 : link pointer로 다시 가리키면 됨
(4) 데이터들이 메모리상에 흩어져서 존재할 수 있다.
풀이 : 배열과 다르게 데이터들이 순서 없이 흩어져서 존재 가능
4. 삽입과 삭제 작업이 자주 발생할 때 실행 시간이 가장 많이 소요되는 자료 구조는?
(1) 배열로 구현된 리스트
풀이 : 리스트류는 link pointer를 이용해 삽입, 삭제가 용이 but, 배열의 경우 삽입과 삭제 시 뒤의 데이터들을 shift해야하므로 오버헤드가 발생함에 따라 실행 시간이 많이 소요됨.
5. 다음 중 NULL 포인터(NULL pointer)가 존재하지 않은 구조는 어느 것인가?
(2) 원형 연결 리스트
ref : https://www.geeksforgeeks.org/circular-linked-list/
6. 원형 연결 리스트에 대한 설명 중 틀린 것은?
(4) 최종 노드 포인터가 NULL이다.
풀이 : 위 사진 참고
7. 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가?
(1) 배열
풀이 : 위에서 배열이 접근시간 빠름 설명
8. 단순 연결 리스트의 노드 포인터 p가 마지막 노드를 가리킨다고 할 때, 다음 수식 중 참인 것은?
(3) last -> link == NULL // 마지막 노드의 link pointer가 NULL을 가리킴
9. 단순 연결 리스트의 노드들을 노드 포인터 p로 탐색하고자 한다. p가 현재 가리키는 노드에서 다음 노드로 가려면 어떻게 하여야 하는가?
(3) p=p->link; // p의 link는 다음 노드를 가리키고 있으므로 p가 p->link가 된다면 p는 다음 노드를 가리키게 된다.
10. 단순 연결 리스트의 관련 함수 f가 헤드 포인터 head를 변경시켜야 한다면 함수 매개 변수로 무엇을 받아야 하는가?
(2) &head
11. A라는 공백 상태의 리스트가 있다고 가정하자. ~~
답 : first, sixth, fifth
풀이 : first -> first second-> first second third -> first second fourth third -> first second fourth third fifth -> first second third fifth -> first second fifth -> first sixth fifth
cf. index는 0부터
12.
13.
14.
15.
16.
17.
18.
...
(4) 리스트는 집합과 동일하다.
풀이 : 집합에는 각 항목 간에 순서의 개념이 없으나 리스트에는 항목들 간에 순서가 있다.
리스트의 예로는, 월~일요일, 가~하, ace~king ...
2. 다음은 순차적 표현과 연결된 표현을 비교한 것이다. 설명이 틀린 것을 모두 표시하여라.
-> 순차적 표현=배열, 연결된 표현=리스트
(1) 연결된 표현은 포인터를 가지고 있어 상대적으로 크기가 작아진다.
풀이 : link field때문에 크기가 더 커짐
(2) 연결된 표현은 삽입이 용이하다.
풀이 : link pointer를 사용하기 때문에 삽입, 삭제가 용이하다.
(3) 순차적 표현은 연결된 표현보다 접근 시간이 많이 걸린다.
풀이 : 배열은 리스트보다 접근 시간이 더 빠름
배열은 x[n]으로 공간을 먼저 확보하고 데이터를 접근하므로 '상수시간'이 걸림
리스트는 N번째 원소에 찾아가기 위해 1, 2, 3, 4, ... , N-1, N으로 찾아가기 때문에 시간이 걸림 -> 노드들은 메모리 순서대로 할당되지 않는 경우도 있어 0x0000 -> 0x0008 -> 0x0004 -> 0x0012 이런 식으로 접근
(4) 연결된 표현으로 작성된 리스트를 2개로 분리하기가 쉽다.
풀이 : link pointer만 변경해주면 간편
ref : https://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=65046222&qb=67Cw7Je06rO8IOumrOyKpO2KuCDsoJHqt7zsi5zqsIQ=&enc=utf8§ion=kin&rank=1&search_sort=0&spq=0&pid=Un5aVsp0J14ssiIugEwsssssty4-354237&sid=TI5et04RypqvBWHUSpWDDg%3D%3D
https://blog.naver.com/sasayakki/221402108050
3. 다음은 연결 리스트에서 있을 수 있는 여러 가지 경우를 설명한다. 잘못된 항목은?
(1) 정적인 데이터보다는 변화가 심한 데이터에서 효과적인 방법이다.
풀이 : 변화가 심한 데이터는 계속 수정을 해주어야 한다는 의미(?) -> 삽입과 삭제가 용이해야함 -> 리스트의 특성
(2) 모든 노드는 데이터와 링크(포인터)를 가지고 있어야 한다.
(3) 연결 리스트에서 사용한 기억 장소는 다시 사용할 수 없다.
풀이 : link pointer로 다시 가리키면 됨
(4) 데이터들이 메모리상에 흩어져서 존재할 수 있다.
풀이 : 배열과 다르게 데이터들이 순서 없이 흩어져서 존재 가능
4. 삽입과 삭제 작업이 자주 발생할 때 실행 시간이 가장 많이 소요되는 자료 구조는?
(1) 배열로 구현된 리스트
풀이 : 리스트류는 link pointer를 이용해 삽입, 삭제가 용이 but, 배열의 경우 삽입과 삭제 시 뒤의 데이터들을 shift해야하므로 오버헤드가 발생함에 따라 실행 시간이 많이 소요됨.
5. 다음 중 NULL 포인터(NULL pointer)가 존재하지 않은 구조는 어느 것인가?
(2) 원형 연결 리스트
6. 원형 연결 리스트에 대한 설명 중 틀린 것은?
(4) 최종 노드 포인터가 NULL이다.
풀이 : 위 사진 참고
7. 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가?
(1) 배열
풀이 : 위에서 배열이 접근시간 빠름 설명
8. 단순 연결 리스트의 노드 포인터 p가 마지막 노드를 가리킨다고 할 때, 다음 수식 중 참인 것은?
(3) last -> link == NULL // 마지막 노드의 link pointer가 NULL을 가리킴
9. 단순 연결 리스트의 노드들을 노드 포인터 p로 탐색하고자 한다. p가 현재 가리키는 노드에서 다음 노드로 가려면 어떻게 하여야 하는가?
(3) p=p->link; // p의 link는 다음 노드를 가리키고 있으므로 p가 p->link가 된다면 p는 다음 노드를 가리키게 된다.
10. 단순 연결 리스트의 관련 함수 f가 헤드 포인터 head를 변경시켜야 한다면 함수 매개 변수로 무엇을 받아야 하는가?
(2) &head
11. A라는 공백 상태의 리스트가 있다고 가정하자. ~~
답 : first, sixth, fifth
풀이 : first -> first second-> first second third -> first second fourth third -> first second fourth third fifth -> first second third fifth -> first second fifth -> first sixth fifth
cf. index는 0부터
12.
13.
14.
15.
16.
17.
18.
...
댓글
댓글 쓰기