1과목
알고리즘
(1～35)
출제위원：방송대 이관용
출제범위：교재 전체(해당 멀티미디어 강의 포함)
1. 이론적으로 문제 해결이라는 관점에서 반드시 만족하지 않아도 되는 알고리즘의 조건은?
① 유효성 ② 명확성
③ 효율성 ④ 유한성
2. 연결 리스트의 특정 노드에서 선행 노드와 후행 노드에 대한 접근이 모두 가능한 것은?
① 단일 원형 연결 리스트
② 이중 연결 리스트
③ 단일 연결 리스트
④ 순차 연결 리스트
3. 다음 빈 칸에 알맞은 용어는?
그래프 에서 정점 으로부터 정점 까지의 ( )(이)란 간선 으로 연결된 정점의 순서 리스트 을 의미한다.
① 경로 ② 차수
③ 연결 ④ 사이클
4. 알고리즘의 대표적인 설계 기법으로 거리가 먼 것은?
① 동적 프로그래밍 방법 ② 욕심쟁이 방법
③ 상각분석 방법 ④ 분할정복 방법
5. 입력 크기 에 대한 알고리즘 수행시간 을 점근 성능으로 올바르게 나타낸 것은?
① ②
③ ④
6. 단위 연산의 수행시간이 ( 초)인 컴퓨터에서 개의 데이터를 처리하는 데 가장 오랜 시간이 걸리는 알고리즘의 성능을 나타내는 점화식은?
① ,
② ,
③ ,
④ ,
7. 분할정복 방법을 적용한 알고리즘 중에서 입력 크기 에 대한 성능이 가장 우수한 것은?
① 퀵 정렬 ② 이진 탐색
③ 배낭 문제 ④ 합병 정렬
8. 분할정복 방법에서 각 순환 호출시마다 거치는 작업 단계가 아닌 것은?
① 정렬 ② 정복
③ 분할 ④ 결합
9. 다음과 같은 데이터에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후 왼쪽 부분배열에 존재하는 데이터의 개수는?(단, 피벗은 맨 왼쪽 원소이고, 오름차순으로 정렬한다.)
30 45 20 15 40 25 35 10
① 2 ② 4
③ 6 ④ 8
알고리즘, 운영체제 4－1
3 학년 3 교시
10. 퀵 정렬에서 최악의 성능이 발생하지 않는 경우는? (단, 피벗은 맨 왼쪽 원소이다.)
① 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
② 피벗이 항상 부분배열에서 최솟값이 되는 경우
③ 입력 데이터가 정렬되어 있는 경우
④ 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우
11. 다음은 입력 크기 38인 배열의 원소를 7개의 그룹(G1∼G7)으로 구성한 모습이다. 최악 으로 i 번째로 작은 원소를 찾기 위한 선택 문제에서 피벗(“중간값들의 중간값”)으로 선택되는 원소는?
그림입니다. 원본 그림의 이름: CLP00005abc0001.bmp 원본 그림의 크기: 가로 361pixel, 세로 240pixel
① 27 ② 36
③ 43 ④ 50
12. 동적 프로그래밍 방법에 대한 설명으로 적당하지 못한 것은?
① 모든 정점 간의 최단 경로 문제와 스트링 편집 거리 문제에 적용된다.
② 상향식 접근 방법이다.
③ 최적성의 원리가 만족되는 문제에만 적용할 수 있다.
④ 소문제들은 서로 독립적이다.
13. 피보나치 수열 에서 은 얼마인가? (단, , 이다.)
① 8 ② 11
③ 13 ④ 21
14. 동적 프로그래밍 방법을 적용하여 n개의 행렬에 대한 연쇄적 곱셈 문제를 해결하는 알고리즘의 시간 복잡도는?
① ②
③ ④
15. 다음은 플로이드 알고리즘을 간략히 정리한 것이다. 이 알고리즘의 성능 표현으로 올바른 것은?
Floyd (G=(V,E) ) { // |V|=n
D[][] ← 입력 간선의 인접 행렬로 초기화
for (k=1부터 n까지)
for (i=1부터 n까지)
for (j=1부터 n까지)
if ( D[i][j] > D[i][k] + D[k][j] )
D[i][j] = D[i][k] + D[k][j];
return D[][];
}
① ②
③ ④
알고리즘, 운영체제 4－2
3 학년 3 교시
16. 다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하였을 때 얻게 되는 최대 이익은? (단, 물체를 쪼갤 수 있다.)
• 배낭의 용량 10
• 물체1 → 무게 3, 이익 9
• 물체2 → 무게 3, 이익 15
• 물체3 → 무게 4, 이익 14
• 물체4 → 무게 5, 이익 20
① 35 ② 38
③ 42 ④ 49
17. 욕심쟁이 방법을 적용하여 최소 신장 트리를 구하는 알고리즘으로만 나열된 것은?
① 크루스칼 알고리즘, 플로이드 알고리즘
② 프림 알고리즘, 크루스칼 알고리즘
③ 데이크스트라 알고리즘, 프림 알고리즘
④ 플로이드 알고리즘, 데이크스트라 알고리즘
알고리즘 기말시험(2015).hwp 알고리즘 기말시험(2016).hwp 알고리즘 기말시험(2017).hwp 알고리즘 기말시험(2018).hwp 알고리즘 기말시험(2019).hwp 알고리즘 대체시험(2015).hwp 알고리즘 대체시험(2016).hwp 알고리즘 대체시험(2017).hwp 알고리즘 대체시험(2018).hwp 알고리즘 대체시험(2019).hwp 알고리즘 동계계절시험(2019).hwp 운영체제 기말시험(2015).hwp 운영체제 기말시험(2016).hwp 운영체제 기말시험(2017).hwp 운영체제 기말시험(2018).hwp 운영체제 기말시험(2019).hwp 운영체제 동계계절시험(2019).hwp
