포인터 변수 L이 단순 연결 리스트의 첫 번째 노드를 가리킬 때, (가… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 26년 1회차

포인터 변수 L이 단순 연결 리스트의 첫 번째 노드를 가리킬 때, (가)～(다)를 수행하는 각 알고리즘의 시간 복잡도를 바르게 연결한 것은? (단,  $n$ 은 리스트의 노드 개수를 나타낸다)(가) L이 가리키는 리스트의 노드 순서를 역순으로 변환
(나) 새로운 노드를 L이 가리키는 리스트의 첫 번째 노드가 되도록 삽입
(다) L이 가리키는 리스트의 마지막 노드 삭제
(가) (나) (다)

 $O(1)$   $O(1)$   $O(1)$

 $O(1)$   $O(n)$   $O(n)$

 $O(n)$   $O(1)$   $O(n)$

 $O(n)$   $O(n)$   $O(1)$

해설

역순 변환은 $O(n)$ , 첫 노드 삽입은 $O(1)$ , 마지막 노드 삭제는 $O(n)$ 이다.

역순 변환은 모든 노드의 링크를 한 번씩 뒤집어야 하므로 노드 수에 비례한다. 맨 앞 삽입은 새 노드의 link를 L로 두고 L을 새 노드로 바꾸면 끝난다.

마지막 노드를 지우려면 그 직전 노드의 link를 NULL로 바꿔야 하는데, 단순 연결 리스트는 뒤로 갈 수 없어 처음부터 끝까지 순회해야 한다.

세 연산 모두 상수 시간이라는 연결은 역순 변환과 마지막 노드 삭제가 전체 순회를 요구하므로 틀리다.
역순 변환을 상수 시간으로, 맨 앞 삽입을 선형 시간으로 본 연결은 두 연산의 비용을 뒤바꾼 것이다.
마지막 노드 삭제를 상수 시간으로 본 연결은 직전 노드를 찾는 순회를 빠뜨린 것이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 26년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→