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 ​​​​​​​