ICT 융합시대의 컴퓨터과학 연습문제 6장
데이터 구조와 알고리즘
객관식
1. 알고리즘의 처리를 위해 프로세서가 처리하는 데 소요되는 시간의 효율성을 비교하기 위하여 빅-O 표기법으로 나타낸다. 다음 중 N개의 데이터를 처리하는 평균시간으로 가장 효율적인 것은?
(d는 수학적인 결과 평균값이 가장 작은 수로 볼 수 있으나 번외의 경우)
(c) 100N log N
(d) 0.5N⅔
2. 다음에서 알고리즘의 조건을 설명한 것 중 가장 적절하지 않는 것은?
(e) 모든 문제 해결의 알고리즘은 항상 한 가지만 존재한다.
3. 다음 중 Polya의 문제해결 과정에 속하지 않는 것은?
(b) 기존의 문제해결 방법을 모두 찾아 비교한다.
4. 다음 중 NP-완전 문제에 속하는 것은?
(e) O(2N)
5. 다음 중 LIFO(Last-In-First-Out) 법칙을 따르는 데이터 구조는?
(a) 스택
6. 다음 중 스택(Stack)의 개념이나 작업과 가장 관련성이 적은 것은?
(d) Wait
7. 연결 리스트(Linked List)에서 필요하지 않은 정보는?
(c) 연결 리스트의 길이
8. 연결 리스트를 사용하는 이유와 가장 관련성이 적은 것은?
(b) 정보의 검색이 용이
9. 버블 정렬(Bubble Sorting) 알고리즘의 시간 복잡도는?
(a) 평균 O(N2), 최악 O(N2)
10. 순차탐색 알고리즘과 이진탐색 알고리즘의 시간 복잡도는?
(a) O(N), O(log N)
괄호 채우기
1. 최근에 메모리 공간은 거의 무제한으로 사용할 수 있으므로 알고리즘의 성능은 대체로 ( 시간복잡도 )를 이야기 한다.
2. 문제를 해결하는 방법으로 가장 잘 알려진 ( 폴야의 문제해결과정 )에서 제시하는 4단계가 있다.
3. ( 빅오표기법 )은 알고리즘의 상호 성능을 가장 일반적으로 평가하고 비교할 수 있는 일반적인 방법이다.
4. 데이터구조는 ( 추상데이터형 )으로 존재하여 외부에서 데이터구조와 데이터구조에 적용되는 연산에 대해 세부적인 작용과 절차를 알지 못해도 호출하여 사용할 수 있다.
5. ( 리스트 )는 순서로 나열된 데이터의 모임이다. 리스트의 맨 앞을 헤드(Head)라 부르고 맨 뒤를 테일(Tail)이라 부른다.
6. ( 스택 )은 일종의 리스트에 해당되나 데이터 접근방법이 특이하다. ( 스택 )은 Top과 Bottom이 존재하고 새로운 항목을 삽입할 경우 맨 위(측 Top)에다 쌓는다. 또한 ( Top )에서 한 항목을 가져갈 때도 맨 위에 있는 항목을 가져가게 된다.
7. ( 연결리스트 )는 리스트와 개념적으로 유사하나 항목의 연결 방식이 상이하다. 리스트나 스택, 큐의 경우는 각 항목들이 연속적인 저장되어 있다고 생각한다. 따라서 행렬과 같은 데이터구조를 이용하여 리스트를 구할 수 있다. 그러나 연결 리스트의 경우는 ( 포인터 ) 개념을 이용하여 각 항목을 연결한다.
8. 트리에는 여러 가지 형태의 트리가 존재한다. 그 중 ( 이진트리 )는 트리의 각 노드가 2개 이하의 자식을 갖는다. 즉 ( 이진트리 )는 노드의 데이터 필드 외에 왼쪽 포인터(Left Pointer)와 오른쪽 포인터(Right Pointer)를 가지고 있다.
9. ( 퀵 정렬 ) 알고리즘의 성능을 빅-O 표기법으로 나타내면 평균 경우 시간복잡도가 O(N log N)이고 최악 경우는 O(N2)이다. 일반적으로 지금까지 알려진 정렬 알고리즘들 중 ( 퀵 정렬 ) 알고리즘이 평균적으로 가장 속도가 빠른 알고리즘으로 알려져 있다.
10. ( 이진 탐색 ) 알고리즘의 성능을 빅-O 표기법으로 나타내면 평균 경우 시간복잡도가 O(log N)이고 최악 경우도 O(log N)이다. ( 이진 탐색 ) 알고리즘은 원시 데이터가 정렬되어 있다는 가정 하에 사용하는 알고리즘이다.
