출석체크하기
컴퓨터과학과
컴퓨터과학과 입학생, 재학생, 교수, 조교, 예비입학생분들을 위한 게시판입니다.
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 ​​​​​​​

 

  • ?
    해뇽이 2021.12.05 11:48

    비회원은 작성 1년 이내의 댓글을읽을 수 없습니다.

    로그인 후에 바로 열람 가능합니다
  • ?
    해뇽이 2021.12.05 11:49

    비회원은 작성 1년 이내의 댓글을읽을 수 없습니다.

    로그인 후에 바로 열람 가능합니다

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
Hot글 3학년 3-2 컴퓨터구조 기출문제 풀이 5년치(2010~2014) 33 file 서예지(국문과) 2021.09.09 121
공지 공부자료를 공유해주시면 다음 후배들에게 큰 도움이 됩니다. 10 file 방송대커뮤니티 2021.11.07 72
공지 포인트 코인을 얻는방법 (파일 다운로드 방법) 315 updatefile 방송대커뮤니티 2021.01.06 2043
251 3학년 2020년도 기출문제 구할 수 있을까요? 4 도련님 2021.12.03 41
250 3학년 3-2 컴파일러구성 (기말시험, 대체시험, 하계계절시험 기출문제) 2015~2019 26 updatefile 제로스 2021.11.29 43
249 3학년 3-2 컴퓨터구조 (기말시험, 대체시험, 하계계절시험 기출문제) 2015~2019 15 file 제로스 2021.11.29 40
248 2학년 2-2 선형대수 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 file 제로스 2021.11.29 13
247 2학년 2-2 자료구조 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 8 file 제로스 2021.11.29 33
246 2학년 2-2 프로그래밍언어론 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 7 file 제로스 2021.11.29 23
245 일반글 <C++프로그래밍> 교과목 기말대비 김남희 튜터님 온라인 특강 안내 제로스 2021.11.28 21
244 2학년 선형대수, 자료구조, 프로그래밍언어론(15~19 기말,대체 기출시험모음) 16 file 서예지(국문과) 2021.11.08 52
243 1학년 [컴과1] C++프로그래밍, 멀티미디어시스템, 컴퓨터과학개론(15~19 기말,대체 기출시험모음) 17 file 서예지(국문과) 2021.11.08 53
242 3학년 [컴과3] JSP프로그래밍, UNIX시스템, 데이터베이스설계 및 구현 (15~19 기말,대체 기출시험모음) 47 updatefile 서예지(국문과) 2021.11.08 82
241 3학년 [컴과3] 컴파일러구성, 컴퓨터구조 (15~19 기말,대체 기출시험모음) 14 updatefile 서예지(국문과) 2021.11.08 37
240 4학년 [컴과4] HTML5, 시뮬레이션, 인공지능(15~19 기말,대체 기출시험모음) 13 updatefile 서예지(국문과) 2021.11.08 27
239 4학년 [컴과4] 컴퓨터그래픽스, 컴퓨터보안 15~19 기말,대체 기출시험모음 1 file 서예지(국문과) 2021.11.08 8
238 4학년 [컴과4] 모바일앱프로그래밍, 소프트웨어공학, 정보통신망(15~19 기말,대체 기출시험모음) file 서예지(국문과) 2021.11.08 12
237 3학년 HTML 웹프로그래밍, 데이터베이스시스템, 디지털논리회로 (15~19기말, 대체 기출시험 자료모음) 3 file 서예지(국문과) 2021.11.08 14
» 3학년 [컴과3] (알고리즘, 운영체제 기말시험) 기출문제모음 기말,대체,계절시험 2 file 서예지(국문과) 2021.11.08 24
235 1학년 C프로그래밍, 유비쿼터스컴퓨팅개론 file 서예지(국문과) 2021.11.08 16
234 1학년 [컴과1] 인터넷과 정보사회 1 file 서예지(국문과) 2021.11.08 11
233 2학년 [컴과2] Java 프로그래밍, Visual C++ 프로그래밍, 이산수학 8 file 서예지(국문과) 2021.11.08 25
232 3학년 그래픽커뮤니케이션 기말대비입니다. 1 file 서예지(국문과) 2021.11.08 6
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 13 Next
/ 13