2021년 군무원 7급자료구조론기출문제상세해설

소개

2021년 군무원 7급자료구조론기출문제에 대한 상세해설을 여러 아래 대학교재들을 참고하여 자작 해설한 내용입니다.도움 되시길 바랍니다.

목차

없음

본문내용

002 재귀(recursion) 알고리즘과 for 문 또는 while 문을 사용하는 반복(iteration) 알고리즘에 대한설명중 가장 적절한 것은?
① 반복 알고리즘은 대체로 재귀 알고리즘에 비해 시간적으로나 공간적으로 매우 비효율적이다.
② 재귀 알고리즘은 반드시 큐(queue)의 개념이 필요하다.
③ 이진 탐색을 하는 반복 알고리즘의 최악의 경우 수행 시간은 O(logn)이고, 재귀 알고리즘의 최악의 경우 수행 시간은 O(n)이다.
④ 재귀 알고리즘은 재귀 호출(recursive call)을 사용한 알고리즘으로서 오버헤드(overhead), 즉 부가적인 기억 공간이 필요할 수 있다.
[해설]
④ 재귀 알고리즘은 반복적으로 자기 자신인 함수를 호출하므로 각 함수마다 시스템 스택 상에 복귀 주소, 지역 변수, 매개 변수 등의 관련 정보(스택 프레임)를 유지해야 하므로 부가적인 기억공간을 필요로 한다.
∎ 스택 프레임(stack frame): 실행 시에 함수 호출이 수행되면 시스템 스택 상에는 활성 레코드(activation record) 또는 스택 프레임이라는 구조를 만들어 함수 호출을 관리한다. 스택 프레임에는 이전 스택 프레임에 대한 포인터, 반환 주소, 지역 변수, 매개변수 등이 포함된다. 함수 호출시 시스템 상의 top에 만들어진 스택 프레임은 해당 함수 종료시 제거되어 시스템 스택의 top에는 이전 함수 호출에 대한 스택 프레임이 남게 되고 이전 함수를 처리하는 상태로 복귀한다.

참고자료

· C로 쓴 자료구조로 ( 이석호 역, 교보문고)
· C, C++ 로 배우는 자료구조론 (주우석 저, 한빛미디어)
· C 언어로 쉽게 풀어쓴 자료구조 (천인국 외 3인 공저, 한빛미디어)
· 예제로 배우는 자료구조론( 주낙근 외 3인 공저, 정익사)
· 자료구조와 JAVA (이석호 저, 정익사)
· 쉽게 배우는 알고리즘 (문병로 저, 한빛미디어)
· A BOOK ON C (김명호 역, 홍릉 출판사)
· 기타 알고리즘 교재 및 인터넷 구글 검색 정보 등