100 문제 였는데 별로 추천하는 과목은 아니다. 원래 시간이 있으면 깊게 공부하고 싶었으나 이거저거 병행하느라고 별로 공부하지 못했지만 꼭 다시 공부해야할 과목중에 하나인거같다.
* 1장 – 알고리즘 소개
1장 1절 – 알고리즘의 개념
1. 다음 중 교재 및 강의에서 다루어지지 않은 부류의 알고리즘은? (2018. 기말)(교재 목차)
① 기하 알고리즘
② 정렬 알고리즘
③ 유전 알고리즘
④ 욕심쟁이 알고리즘
정답 : 1번
설명 : 교재 목차에 기하 알고리즘을 제외한
나머지 항목만이 있었습니다.
2.이론적으로 문제 해결이라는 관점에서 반드시 만족하지 않아도 되는 알고리즘의 조건은? (2019. 기말)(교재 6p)
① 유효성 ② 명확성
③ 효율성 ④ 유한성
정답 : 3번
설명 : 알고리즘의 조건은 입출력, 명확성, 유한성, 유효성을 만족해야합니다. 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 단단하며 컴퓨터가 수행
가능한 유한개의 일련의 명령들을 순서적으로 구성한 것입니다. 하지만
실용적인 관점에서는 효율적이어야 한다는 것도 고려되야 합니다.
3.주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은? (2018. 기말)(교재
6p)
①모든 명령은 컴퓨터에서 수행 가능해야 한다.
② 각 명령은 단순하고 명확해야 한다.
③ 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다.
④외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다.
정답 : 4번
설명 : 입출력의 조건을 만족하기 위해서는 외부
입력이 반드시 존재할 필요는 없지만 하나 이상의 출력이 필요한 것은 사실입니다.
4.다음 그래프에 대해서 오일러 경로를 찾으려고 한다. 이때 출발점이 되어야 하는 정점은? (2018. 출석 대체)(교재
4p)
① (a) ② (b)
③ (c) ④ (d)
정답 : 1번
설명 : 그래프의 모든 간선을 오직 한 번씩만
지나가는 경로를 찾으려면 각 정점의 차수가 홀수인 점이 없거나 두 개여야 합니다. 현재 보기의 정점의 차수가 홀수인 점은 두 개 이므로 오일러의 경로를 찾을 수 있으며 정점의 차수가 홀수 점이 두 개 이기
때문에 그 중 보기에 있는 a로 고르게 되었습니다.
1장 2절 – 기본 자료구조
5.연결 리스트의 특정 노드에서 선행 노드와 후행 노드에 대한 접근이 모두 가능한 것은? (2019. 기말)(교재 10p)
① 단일 원형 연결
리스트
② 이중 연결 리스트
③ 단일 연결 리스트
④ 순차 연결 리스트
정답 : 2번
설명 : 2번을 제외한 연결 리스트의 종류들은
링크필드가 하나씩 있기 때문에 선행 노드나 후행 노드 모두를 이동할 수 있는 것이 아니라 한 방향으로만 이동이 가능합니다.
6. 다음 빈 칸에 알맞은 용어는? (2019. 기말)(교재 18p)
그래프
에서 정점
으로부터 정점
까지의 (
)(이)란 간선
으로 연결된 정점의
순서 리스트
을 의미한다.
|
① 경로 ② 차수
③ 연결 ④ 사이클
정답 : 1번
설명 : 그래프 G에서 정점으로부터 다른 정점까지의 간선으로 연결된 정점의 순서리스트를 말하는
것으로는 경로인 1번입니다.
차수는 해당 정점에 부수된 간선의 수를 의미합니다.
연결이란 무방향 그래프에서 서로 다른 정점의 모든 쌍에 대해서 경로가 있을때를 이야기합니다.
사이클이란 처음과 마지막 정점이 같은 단순 경로를 말합니다.
7.선형 자료구조 중에서 데이터에 대한 임의 접근을 제공하는 것은? (2019. 출석대체)(교재 9p)
① 큐
② 배열
③ 연결 리스트
④ 그래프
정답 : 2번
설명 : 배열의 가장 큰 특징은 원소의 논리적
순서와 저장된 물리적 순서가 같다는 것으로 인덱스를 이용하여 빠른 임의 접근이 가능합니다.
8. 다음 트리에 대한 설명 중 틀린 것은? (2019. 출석대체)(교재 12p)
① 트리의 차수는 3이다.
② 노드의 차수가 0인 노드의 개수는 7이다.
③노드 D의 후손 노드의 개수는 노드 L의 조상 노드의 개수보다 많다.
④ 트리의 레벨은 4이다.
정답 : 3번
설명 : 1번은 D의 차수가 3이며 2번은 자식노드가 없는 노드가 총 7개가 존재하며 4번의 트리는 루트노드에서부터의 거리가1 + 3 이므로
4가 맞습니다.
3번은 D의 후손노드는 3개이고 L의 조상 노드는 3개이므로 오답입니다.
9.전 이진트리(full binary tree)에서 루트 노드를 포함한 비단말 노드가 3개인 경우 단말 노드의 개수는?
(2019. 출석대체)(교재 16p)
① 2
② 3
③ 4
④ 6
정답 : 3번
설명 : 비단말 노드의 개수는 공식에 대입하면 n0-1=3이며 n0=4이므로 단말 노드의 개수는 4개입니다.
10. 최대 개수의 노드를 갖는 높이 4인 이진 트리에서 단말 노드의 개수는? (2018. 기말)(교재 14p)
① 7 ② 8
③ 15 ④ 16
정답 : 2번
설명 : 이진 트리의 최대 노드의 수는 2h-1 이므로 2의 4승인 16의 -1 이므로 최대 노드의 개수는 15이며 단말노드의
수는 n0=n2+1이므로 n0= 7.5+1 이므로 총 8개의 단말 노드를 가지고 있습니다.
11. 자료구조에 대한 설명으로 적절한 것은? (2018. 출석 대체)(교재 9p)
①연결 리스트는 데이터의 삽입 시 데이터의 추가적인 이동이 발생한다.
② 배열은 각 데이터에 대한 접근 시간이 동일하다.
③ 배열은 데이터의 논리적 순서와 물리적 순서가 다르다.
④ 연결 리스트의 노드는 반드시 하나의 링크 필드만을 갖는다.
정답 : 2번
설명 : 1번의 특징은 배열의 특징으로
연결리스트는 뒤에 새로운 노드만 추가하면 됩니다. 3번의 경우
배열은 논리적 순서와 물리적 순서가 같습니다. 4번의 경우는
연결리스트의 노드는 여러개의 링크 필드를 가질 수 있습니다.
12.다음 중 완전(complete) 이진 트리이면서 전(full) 이진 트리가 되는 것은? (2018. 출석 대체)(교재
15p)
①
|
②
|
③
|
④
|
정답 : 3번
설명 : 전 이진 트리란 모든 노드의 차수가 0이거나 2인 이진 트리를 말하며 완전 이진 트리는 레벨 l-1까지 모두 포화 이진 트리를 형성하고 있는 것을 말합니다. 두 개의 조건을 모두 갖춘 트리는 3번입니다.
1장 3절 – 알고리즘의 설계
13. 알고리즘의 대표적인 설계 기법으로 거리가 먼 것은? (2019. 기말)(교재 22p)
① 동적 프로그래밍 방법
② 욕심쟁이 방법
③ 상각분석 방법 ④ 분할정복 방법
정답 : 3번
설명 : 대표적인 기법으로는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법이 있습니다.
1장 4절 – 알고리즘의 분석
14.알고리즘 생성 단계 중에서 시간 복잡도 및 공간 복잡도를 계산하는 단계는? (2019. 출석대체)(교재 23p)
① 정확성 분석
② 알고리즘 기술
③ 효율성 분석
④ 알고리즘 설계
정답 : 3번
설명 : 정확성 분석은 수학적 기법을 사용하여
알고리즘을 증명하는 과정을 이야기합니다. 효율성 분석을 통해
시간 복잡도와 공간 복잡도를 계산합니다.
15. 알고리즘의 시간 복잡도에 대한 설명으로 틀린 것은? (2019. 출석대체)(교재 23p)
① 입력 데이터의 상태에 따라 달라진다.
② 입력 크기에 대한 함수로 표현한다.
③ 알고리즘에서 기본 명령의 수행 횟수의 합으로 나타낸다.
④ 일반적으로 평균 수행시간을 평가 척도로 사용한다.
정답 : 4번
설명 : 시간 복잡도의 수행시간은 모든
입력상태와 그에 대한 각각의 수행 시간을 알기 어렵다는 문제를 가지고 잇기 때문에 최악의 수행 시간을 알고리즘의 시간복잡도를 평가하는 일반적인
척도로 사용합니다.
16. 알고리즘의 시간 복잡도는 무엇의 함수로 표현하는가? (2018. 기말)(교재 24p)
① 입력 데이터의 값
② 프로그램에 사용된 동적 변수의 개수
③ 프로그램 코드의 길이
④ 입력 데이터의 크기
정답 : 4번
설명 : 입력으로 제공되는 데이터의 크기에 따라
수행시간도 증가하기 때문에 입력 크기를 n에 대한 함수로
표현합니다.
17. 다음 알고리즘의 성능을 빅오 표기로 올바르게 나타낸 것은? (2018. 출석 대체)(교재 25p)
SumAverage( A[], n ) {
sum = 0;
i = 0;
while ( i < n ) {
sum = sum + A[i];
i = i + 1;
}
average = sum / n;
print sum, average;
}
|
① O(logn) ② O(n2)
③ O(nlogn)
④ O(n)
정답 : 4번
설명 : 수행횟수를 모두 더하면 T(n)=3n+5가 되는데 이를 시간 복잡도로 표현하면 가장 높은 차수가 n이므로 O(n)이 됩니다.
1장 5절 - 점근성능
18.입력 크기
에 대한
알고리즘 수행시간
을 점근 성능으로 올바르게 나타낸 것은? (2019. 기말)(교재 28p)
①
②
③
④
정답 : 4번
설명 : 최고 차항이 n의 3승이기에 점근 성능은
입니다.
19.점근 성능의 표기법 중에서 최악의 수행시간만을 나타낼 때 적합한 것은? (2019. 출석대체)(교재 26p)
① O
(“big-oh”)
② Ω (“big-omega”)
③ Θ (“big-theta”)
④ Φ (“big-phi”)
정답 : 1번
설명 : 빅 오메가는 최선의 수행 시간을
나타내며 빅 세타는 최선과 최악의 수행시간을 나타냅니다. 빅파이는
해당 교재에 나오지 않고 1번인 빅오는 최악의 수행시간만
나타내므로 1번입니다.
20. 다음 O-표기 중에서 가장 효율적인 성능을 나타내는 것은? (2018. 기말)(교재 28p)
① O(logn) ② O(nlogn)
③ O(n2) ④ O(2n)
정답 : 1번
설명 : 성능은 O(logn) > O(nlogn) > (n2) > O(2n) 순으로 빠릅니다.
1장 6절 – 순환 알고리즘의 성능
21.단위 연산의 수행시간이
(
초)인 컴퓨터에서
개의 데이터를 처리하는 데 가장 오랜 시간이 걸리는 알고리즘의 성능을 나타내는 점화식은? (2019. 기말)(교재 31p)
①
,
②
,
③
,
④
,
정답 : 4번
설명 : 가장 오래 걸리는 점화식으로는 일단
세타(1)은 세타(n)보다 빠르므로 제외합니다. 1번과 4번을 비교하면 T(n)과 T(n-1)이기 때문에 시간 소요가 적은 4번이 정답입니다.
* 2장 – 분할정복 알고리즘
2장 1절 – 분할정복 방법의 원리
22.분할정복 방법에서 각 순환 호출시마다 거치는 작업 단계가 아닌 것은? (2019. 기말)(교재 37p)
① 정렬 ② 정복
③ 분할 ④ 결합
정답 : 1번
설명 : 분할정복 방법은 분할, 정복, 결합의 단계를 거치는 도중에 정렬 단계는 제외하고 진행됩니다. 간혹 결합 단계 없이 해가 구해지기도 합니다.
23. 분할정복에 대한 설명으로 거리가 먼 것은? (2018. 기말)(교재 37p)
① 분할된 작은 문제는 서로 독립적이다.
② 하향식 접근 방법을 사용한다.
③ 분할, 정복, 결합의 처리 과정을 거친다.
④ 점화식을 이용해서 보다 큰 문제의 해를 구한다.
정답 : 4번
설명 : 최대한 해를 나눠 결합 하기 때문에 큰
문제를 해결할 필요가 없습니다.
2장 2절 – 이진 탐색
24.분할정복 방법을 적용한 알고리즘 중에서 입력 크기
에 대한 성능이 가장 우수한 것은? (2019. 기말)(교재 65p)
① 퀵 정렬 ② 이진 탐색
③ 배낭 문제 ④ 합병 정렬
정답 : 2번
설명 : 퀵 정렬의 성능은 O(n2), 이진 탐색의 성능은 O(logn), 배낭 문제의 성능은 O(nlogn) , 합병
정렬의 성능은 O(nlogn) 이므로 가장 빠른 것은 이진
탐색입니다.
25.다음과 같이 주어진 데이터에 대해 적절한 처리를 거친 후 이진 탐색을 적용하였을 때 접근 시간이 가장 빠른 데이터는?
(2019. 출석대체)(교재 40p)
60 25 40 35 50 55 20 45 30
|
① 20
② 30
③ 40
④ 50
정답 : 3번
설명 : 탐색키에 대한 이야기를 물어보는 것으로
모든 값의 가운데 값을 지정했을 경우가 제일 빠릅니다. 정확하게
가운데로 나눠지기 때문에 루프를 도는 횟수가 현저히 줄어듭니다. 20, 25, 30, 35, 40,
45, 50, 55, 60 이렇게 나열했을 때 가장 가운데 있는 40이 가장 적합합니다.
26. 이진 탐색의 최악의 시간 복잡도에 해당하는 점화식은? (2018. 출석 대체)(교재 41p)
① T(n)=2T(n/2)+Θ(n), T(1)=Θ(1)
② T(n)=T(n-1)+Θ(1), T(1)=Θ(1)
③ T(n)=T(n/2)+Θ(1), T(1)=Θ(1)
④ T(n)=T(n-1)+Θ(n), T(1)=Θ(1)
정답 : 3번
설명 : 이진 탐색의 점화식은 T(n)=T(n/2)+1 (n>1), T(1)=1 이므로 해당 점화식과 같은
점화식입니다.
27. 다음과 같이 주어진 데이터에 대해서 이진 탐색을 적용할 때 가장 빨리 찾을 수 있는 데이터는? (2018. 출석
대체)(교재 40p)
10 15 20 25 30 35 40 45 50
|
① 10 ② 20
③ 30 ④ 40
정답 : 3번
설명 : 주어진 값이 정렬 되어 있을 때 가장
가운데 있는 25 혹은 30이 가장 적은 루프를 돌며 찾게 되는데 해당 보기에는 25 없으므로 3번의 30이 정답입니다.
28.최악의 경우의 성능이 가장 효율적인 것은? (단, 입력의 크기는 n이다) (2018. 출석 대체)(교재 66p)
① 합병 정렬의 합병 함수 Merge()
② 주어진 데이터에 대한 최솟값 찾기
③ 정렬된 데이터에 대한 이진 탐색
④ 퀵 정렬의 분할 함수 Partition()
정답 : 3번
설명 : 합병 정렬의 성능은 O(nlogn), 최솟값 찾기의 성능은 O(n),
이진 탐색의 성능은 O(logn), 합병 정렬의 성능은 O(nlogn) 이므로 가장
빠른 것은 이진 탐색입니다.
2장 3절 – 합병 정렬
29.분할정복 방법을 적용한 알고리즘 중에서 결합 단계를 거쳐야만 하는 것은? (2019. 출석대체)(교재 42p)
① 퀵 정렬
② 합병 정렬
③ 이진 탐색
④ 분할함수를 이용한 선택 문제
정답 : 2번
설명 : 분할 했던 배열들을 하나의 배열로
합치기 위해 결합 단계를 거치는 것은 합병 정렬입니다.
2장 4절 – 퀵 정렬
30.다음과 같은 데이터에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후 왼쪽 부분배열에 존재하는
데이터의 개수는?(단, 피벗은 맨 왼쪽 원소이고, 오름차순으로 정렬한다.) (2019. 기말)(교재 49p)
30 45 20 15 40 25 35 10
|
① 2 ② 4
③ 6 ④ 8
정답 : 2번
설명 : 맨 왼쪽 원소인 30을 피벗으로 사용하고 오름차순이라면 30보다 적은 값들은 피벗의 왼쪽으로 오게 됩니다. 총 4개의 원소가 왼쪽의 부분배열에 존재함으로 2번입니다.
31.퀵 정렬에서 최악의 성능이 발생하지 않는 경우는? (단, 피벗은 맨 왼쪽 원소이다.) (2019. 기말)(교재 53p)
①피벗을 중심으로 항상
동일한 크기의 두 부분배열로 분할되는 경우
② 피벗이 항상 부분배열에서 최솟값이 되는 경우
③ 입력 데이터가 정렬되어 있는 경우
④피벗만 제자리를 잡고
나머지 모든 원소가 하나의 부분배열이 되는 경우
정답 : 1번
설명 : 2번의 경우 항상 최악의 성능이
발생하는 경우이며, 3번과 4번은 최악의 성능이 발생할 가능성은 미세하게라도 존재합니다. 하지만 1번의 경우는 항상 최선의 성능이 발생하는 경우입니다.
32.분할정복 방법의 분할 과정에서 입력 크기 n인 문제가 일정하지 않은 크기의 두 개의 작은 문제로 분할되는 알고리즘은?
(2019. 출석대체)(교재 48p)
① 합병 정렬
② 이진 탐색
③ 퀵 정렬
④ 동전 거스름돈 문제
정답 : 3번
설명 : 퀵 정렬은 분할되는 두 부분배열의
크기가 일정하지 않지만 합병 정렬은 항상 동일한 크기의 부분배열로 분할합니다.
33다음과 같은 데이터에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후 왼쪽 부분배열의 첫 번째
원소는? (단, 피벗은 맨 왼쪽 원소이고, 오름차순으로 정렬한다.) (2018. 기말)(교재 49p)
30 45 20 15 40 25 35 10
|
① 10 ② 15
③ 20 ④ 25
정답 : 4번
설명 : 30을 피벗으로 사용한다면 45와 10이 스왑하여 자리를 바꾸고 20과 35는 해당 자리를 지킵니다. 15 역시 자리를 지키고 40과 25 가 자리를 바꾼 후 right와 left 포인터가 엇갈린 상태에서 마지막인 25와 30의 자리를 바꿔주기 때문에 왼쪽 부분배열은 4번이
되게 됩니다.
34. 퀵 정렬의 최악의 시간 복잡도에 해당하는 점화식은? (2018. 기말)(교재 54p)
① T(n)
2T(n/2)+Θ(n), T(1)
Θ(1)
② T(n)
T(n-1)+Θ(1), T(1)
Θ(1)
③ T(n)
T(n/2)+Θ(1), T(1)
Θ(1)
④ T(n)
T(n-1)+Θ(n), T(1)
Θ(1)
정답 : 4번
설명 : 세타(1) 인 2,3번은 제외하고 1번과 4번의 비교를 하였을 때 1번은 T(n) 이고 4번은 T(n-1)이므로 4번이 더 적은 값을 가져 4번입니다.
35.퀵 정렬에서 최악의 성능이 발생하는 경우는? (단, 피벗은 맨 왼쪽 원소이다.) (2018. 출석 대체)(교재
53p)
①피벗을 중심으로 항상
동일한 크기의 두 부분배열로 분할되는 경우
② 피벗이 항상 부분배열에서 최댓값이 되는 경우
③ 부분배열의 임의의 위치에서 피벗을 선택하는 경우
④ 임의의 순서로 데이터가 주어지는 경우
정답 : 2번
설명 : 1번은 최선의 성능을 보여주며 3,4 번은 어떠한 성능을 보여줄지 모르지만 2번은 항상 최악의 성능을 보여줍니다.
2장 5절 – 선택 문제
36.다음은 입력 크기 38인 배열의 원소를 7개의 그룹(G1∼G7)으로 구성한 모습이다. 최악
으로 i번째로 작은 원소를 찾기 위한 선택
문제에서 피벗(“중간값들의 중간값”)으로 선택되는 원소는? (2019. 기말)(교재 62p)
① 27 ② 36
③ 43 ④ 50
정답 : 2번
설명 : 총 38개 이므로 5개씩 7개로 나누고 나머지 3개는 피벗 선정에 사용하지 않습니다. 각 그룹내 중간값을 찾은 뒤에 정렬을 수행합니다. 각 중간값으로 15, 50, 77, 27, 34, 60, 36이 나오게 되며 이를 정렬하게 되면 15, 27, 34, 36, 50, 60, 77이 됩니다. 이 중 가장 가운데 있는 값은 36이므로 2번입니다.
37. 중간값들의 중간값을 사용하는 선택 문제에서 각 그룹은 몇 개의 원소로 구성되는가? (2018. 기말)(교재 61p)
① 3 ② 5
③ 7 ④ 9
정답 : 2번
설명 : 피벗을 이용하는 선택 문제 알고리즘을
말하는 것으로 5개씩 나누므로 2번입니다.
* 3장 동적 프로그래밍 알고리즘
3장 1절 – 동적 프로그래밍 방법의 원리
38. 동적 프로그래밍 방법에 대한 설명으로 적당하지 못한 것은? (2019. 기말)(교재 69p)
①모든 정점 간의 최단 경로 문제와 스트링 편집 거리 문제에 적용된다.
② 상향식 접근 방법이다.
③ 최적성의 원리가 만족되는 문제에만 적용할 수 있다.
④ 소문제들은 서로 독립적이다.
정답 : 4번
설명 : 소문제들이 서로 독립적인 것은 분할
정복 알고리즘의 해당사항이므로 4번입니다.
3장 2절 – 피보나치 수열 문제
39. 피보나치 수열
에서
은 얼마인가? (단,
,
이다.) (2019. 기말)(교재 71p)
① 8 ② 11
③ 13 ④ 21
정답 : 3번
설명 : n이 2 이상이기에 f(n-1)+f(n-2) 점화식에 대입하면 f(5)+f(6)의 값을 더해
5+8이므로 3번입니다.
3장 3절 – 연쇄 행렬 곱셈 문제
40.동적 프로그래밍 방법을 적용하여 n개의 행렬에 대한 연쇄적 곱셈 문제를 해결하는 알고리즘의 시간 복잡도는?
(2019. 기말)(교재 80p)
①
②
③
④
정답 : 4번
설명 : 연쇄 행렬 곱셈문제의 시간 복잡도는 4번에 해당합니다.
41.차원이 각각 3×2, 2×4, 4×1인 세 개의 행렬 M1,
M2, M3을
연쇄적으로 곱하는 데 필요한 최소의 기본 곱셈 횟수는? (2019. 출석대체)(교재 74p)
① 14
② 20
③ 24
④ 36
정답 : 1번
설명 : (M1M2)M3인 3x2x4 + 4x1x3 = 36 의 최대 곱셈 횟수가 존재하고 M1(M2M3)인 2x4x1 + 2x1x3
= 14 의 최소 곱셈 횟수이므로 1번이 정답입니다.
42.연쇄 행렬 곱셈 문제에서 다음과 같이 6개의 행렬을 곱한다고 하자. 이때 C(1,2)의 값은? (2018.
기말)(교재 74p)
① 24 ② 30
③ 72 ④ 168
정답 : 2번
설명 : c(1,2)란 M1부터 M2까지 곱하는 것을 의미합니다. M1 * M2 는
5*2*3이 곱셈횟수이므로 2번이 정답입니다.
43. 연쇄 행렬 곱셈 알고리즘에서 구한 배열 P[1][4]=3이라는 사실로부터 얻어지는 최적의 곱셈 순서는 무엇인가?
(2018. 출석 대체)(교재 74p)
① (M1M2)(M3M4) ② M1(M2M3)M4
③ (M1M2M3M4) ④ (M1M2M3)M4
정답 : 4번
설명 : 최적의 곱셈순서를 찾기 위한 식으로 P[1][4]=3 란 점화식의 k가 3이라는 이야기입니다. 그렇다면 1부터 4까지의 행렬 곱셈을 할 때 최적으로
갈라지는 곳은 3번째라는 것입니다. 보기에 해당 하는 식은 (M1M2M3)M4 인 정답은 4번입니다.
3장 4절 – 스트링 편집 거리 문제
44.두 문자열 X와 Y에 대한 스트링 편집거리 알고리즘의 시간 복잡도는? (단, X의 길이는 n, Y의 길이는 m이다)
(2018. 출석 대체)(교재 87p)
① O(n+m) ② O(nm)
③ O(n2m) ④ O(nm2)
정답 : 2번
설명 : 스트링 편집거리 알고리즘의 시간
복잡도는 O(nm)이므로 정답은 2번입니다.
3장 5절 – 모든 정점 간의 최단 경로
45.다음은 플로이드 알고리즘을 간략히 정리한 것이다. 이 알고리즘의 성능 표현으로 올바른 것은? (2019. 기말)(교재
92p)
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번
설명 : for문이 3번 중복되었으므로 n의 3승인 4번이 정답입니다.
46. 다음 중 동적 프로그래밍을 적용한 알고리즘은? (2019. 출석대체)(교재 88p)
① 데이크스트라 알고리즘
② 프림 알고리즘
③ 플로이드 알고리즘
④ 크루스칼 알고리즘
정답 : 3번
설명 : 플로이드 알고리즘은 동적 프로그래밍을
적용한 알고리즘중 모든 정점 간의 최단 경로를 찾아주는 알고리즘이므로 정답은 3번입니다.
1번은 욕심쟁이 프로그래밍이므로 오답입니다.
47.그래프 G=(V,E)에 대한 플로이드 알고리즘의 설명으로 적절하지 못한 것은? (2019. 출석대체)(교재 88p)
① 시간 복잡도는 O(|V|3)이다.
② 단일 출발점에서 다른 모든 정점으로의 최단 경로를 구한다.
③ 간선의 인접 행렬 표현을 활용한다.
④ 점화식을 이용하여 주어진 문제의 해를 구한다.
정답 : 2번
설명 : 플로이드 알고리즘은 모든 정점에서 모든
정점으로의 최단 경로를 구하기 때문에 내용이 맞지 않으므로 2번입니다.
48. 다음 중 동적 프로그래밍 방법을 적용한 알고리즘은? (2018. 기말)(교재 88p)
① 모든 정점 간의 최단 경로 구하는 알고리즘
② 합병 정렬
③ 최솟값과 최댓값을 모두 찾는 알고리즘
④ 작업 선택 문제
정답 : 1번
설명 : 합병 정렬, 최솟값과 최대값값을 찾는 알고리즘, 작업 선택문제 알고리즘은 모두 분할 정복 알고리즘에 속하며 1번인 모든 정점 간의 최단 경로를 구하는 알고리즘은 동적 프로그래밍 방법중 플로이드 알고리즘에 속합니다.
49.다음 그래프에 대해서 모든 정점 간의 최단 경로를 구하려고 한다.
의 값은? (2018. 기말)(교재 90p)
① ∞ ② 7
③ 5 ④ 4
정답 : 4번
설명 : d는 3이라는 정점을 거쳐서 4부터 2까지 가는 것을 뜻합니다. 제일 적은 값은 1의 정점을 거쳐 3+2-1=4이므로 정답은 4번입니다.
50. 다음 중 플로이드 알고리즘에 대한 설명은? (2018. 출석 대체)(교재 88p)
①두 문자열 간의 변환 과정에서 필요한 최소의 편집 비용을 구한다.
② 최소 신장 트리를 구한다.
③ 모든 정점 간의 최단 경로를 구한다.
④하나의 출발점에서 다른 모든 정점으로의 최단 경로를 구한다.
정답 : 3번
설명 : 1번은 스트링 편집 거리 알고리즘이며 2번인 최소 신장 트리는 욕심쟁이 프로그래밍을 말하는 것입니다.
3번은 플로이드 알고리즘을 의미하는 것이므로 정답은 3번입니다.
3장 6절 – 저울 문제
51. 동적 프로그래밍 방법으로 해결 가능한 저울 문제에 대한 설명으로 올바른 것은? (2018. 기말)(교재 96p)
① 추의 무게는 정수이어야 한다.
② 최적화 문제이다.
③ 양팔 저울의 어느 쪽에나 추를 올릴 수 있다.
④ 저울로 달려는 무게에는 아무런 제약이 없다.
정답 : 1번
설명 : 2번은 저울문제는 최적성의 원리를
따기지 때문에 틀렸고 3번은 어느쪽이든 상관 없지만 물건의
반대쪽이여야 합니다. 또한, 4번은 음수이면 안됩니다. 정답은 1번인 추의 무게는 정수여야한다입니다.
* 4장 욕심쟁이 알고리즘
4장 1절 – 욕심쟁이 방법의 원리
52. 욕심쟁이 방법에 대한 설명으로 적절하지 못한 것은? (2019. 출석대체)(교재 109p)
①각 단계에서 여러 최적해를 고려한 후 다음 단계로 넘어간다.
② 최적화 문제 해결에 주로 사용된다.
③동전의 액면가가 임의로 주어지는 동전 거스름돈 문제에는 적용할 수 없다.
④ 전체적인 최적해를 구하지 못할 수도 있다.
정답 : 1번
설명 : 욕심쟁이 방법은 여러 최적해를 고려하지
않습니다. 1번의 특징은 동적 프로그래밍 방법의 특징으로 답은
1번입니다.
53. 욕심쟁이 방법에 대한 설명으로 적절한 것은? (2018. 출석 대체)(교재 109p)
① 주어진 문제를 여러 개의 작은 문제로 나눠서 처리한다.
② 전체적인 최적해를 구할 수 있다는 것을 보장하지 못한다.
③최적성의 원리를 만족시키지 못하는 문제를 대상으로 처리한다.
④점화식을 이용해서 보다 큰 문제의 해를 점진적으로 만들어간다.
정답 : 2번
설명 : 1번은 동적 프로그래밍 방법의 특징, 3번은 욕심쟁이 방법이 아닙니다. 4번은 동적프로그래밍 방법입니다. 정답인 2번은 각 단계마다 최적해를 고려하기 때문에 전체적인 최적해를 구하지 못하는 방법이
정답입니다.
4장 2절 – 동전 거스름돈 문제
54. 동전 거스름돈 문제에 대한 설명으로 올바른 것은? (2018. 기말)(교재 110p)
①동전의 액면가가 임의로 주어지는 경우에도 욕심쟁이 방법으로 해결할 수 있다.
② 동전의 종류가 n개이면 시간 복잡도는 O(n2)이다.
③동전의 액면가가 큰 것부터 욕심을 부려 최대한 사용해서 거스름돈을 만든다.
④동전의 종류가 500원, 100원, 50원, 10원이면 거스름돈 750원에 대한 최적해는 3개이다.
정답 : 3번
설명 : 1번처럼 임의로 주어지는 경우는 동적
프로그래밍 방법으로 해결할 수 있기에 오답입니다. 2번의 시간
복잡도는 동전의 개수만큼이므로 O(n)이므로 잘못된 답입니다. 4번은 500원 1개, 100원 2개, 50원 1개 총 4개이기 때문에 틀린답입니다.
3번이 동전 거스름돈 문제에 대한 정의이므로 정답입니다.
4장 3절 – 배낭 문제
55.다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하였을 때 얻게 되는 최대 이익은? (단, 물체를 쪼갤 수
있다.) (2019. 기말)(교재 112p)
•배낭의 용량 10
•물체1 → 무게 3, 이익 9
•물체2 → 무게 3, 이익 15
•물체3 → 무게 4, 이익 14
•물체4 → 무게 5, 이익 20
|
① 35 ② 38
③ 42 ④ 49
정답 : 3번
설명 : 무게가 적게 나가고 이익이 많이 나가는
물체부터 넣으면 됩니다. 1은 무게당 3의 이익, 2는 무게당 5의 이익, 3은 무게당 3.5의 이익, 4는 무게당 4의 이익이므로 물체 2 와 물체 4를 넣고 물체 3을 반으로 쪼개 넣으면 총 이익은 20+15+7=42이므로 정답은 3번입니다.
56.다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하려고 한다. 배낭에 전혀 들어가지 않는 물체는? (단, 물체를
쪼개서 배낭에 넣을 수 있다.) (2018. 출석 대체)(교재 113p)
배낭의 용량 10
|
① 물체1 ② 물체2
③ 물체3 ④ 물체4
정답 : 4번
설명 : 물체 1은 무게당 3.5 이익, 물체 2는 무게당 5 이익, 물체 3은 무게당 4 이익, 물체 4는 무게당 3이익이므로 무게당 이익이 가장 큰 순으로 물체2, 물체3을 넣고 물체1을 절반으로 쪼개 넣는다면 들어가지 않는 물체는 4번입니다.
4장 4절 – 최소 신장 트리
57.욕심쟁이 방법을 적용하여 최소 신장 트리를 구하는 알고리즘으로만 나열된 것은? (2019. 기말)(교재 116p)
① 크루스칼 알고리즘, 플로이드 알고리즘
② 프림 알고리즘, 크루스칼 알고리즘
③ 데이크스트라 알고리즘, 프림 알고리즘
④ 플로이드 알고리즘, 데이크스트라 알고리즘
정답 : 2번
설명 : 1번과 4번의 플로이드 알고리즘은 동적 프로그래밍 방법입니다. 데이크스트라 알고리즘은 최단 경로 이므로 3번은 오답입니다. 프림 알고리즘과 크루스칼 알고리즘을 포함하는 2번이
정답입니다.
58. 주어진 그래프에 대한 최소 신장 트리의 가중치의 합은? (2019. 기말)(교재 116p)
① 15 ② 16
③ 17 ④ 18
정답 : 2번
설명 : 사이클을 형성하지 않고 최소의 가중치를
갖는 간선을 이용하여 계산하였을 때 크루스칼 알고리즘을 사용하엿을 때는 1 + 2 + 3 + 6 +
4 = 16이고 프림 알고리즘을 사용하여 계산하였을땐 1 +
3 + 2 + 6 + 4 = 16이므로 정답은 2번입니다.
59. 다음 중 최소 신장 트리를 구하는 알고리즘은? (2018. 기말)(교재 116p)
① 크루스칼 알고리즘
② 플로이드 알고리즘
③ 데이크스트라 알고리즘
④ KMP 알고리즘
정답 : 1번
설명 : 2번은 동적 프로그래밍 방법입니다. 3번 데이크스트라 알고리즘은 최단 경로를 구하는 알고리즘입니다. 최소 신장 트리에 해당되는 알고리즘은 1번인 크루스칼 알고리즘입니다.
4장 5절 – 최단 경로
60. 다음 중 욕심쟁이 방법으로 해결 가능한 문제는? (2019. 출석대체)(교재 124p)
① 음의 가중치를 갖는 간선이 없는 데이크스트라 알고리즘
② 오름차순으로 정렬하는 퀵 정렬 알고리즘
③ 추의 무게와 물체의 무게가 모두 정수인 저울 문제
④가중치의 합이 음수인 사이클이 존재하지 않는 플로이드 알고리즘
정답 : 1번
설명 : 2번은 분할정복 알고리즘, 3번은 동적 프로그래밍 알고리즘입니다.
1번이 데이스크트라 알고리즘으로 욕심쟁이 방법으로 해결이 가능합니다.
61. 다음과 같은 처리 방법이 적용되는 알고리즘은? (2018. 출석 대체)(교재 124p)
미선택 정점 집합에서 거리가 가장 작은 정점 u를 선택한 후, u의 인접 정점에 대해서 u를
경유하는 거리와 기존 거리 중에서 작은 것을 새로운 값으로 조정한다.
|
① 크루스칼 알고리즘 ② 플로이드 알고리즘
③ 데이크스트라 알고리즘
④ 프림 알고리즘
정답 : 3번
설명 : 해당 내용의 알고리즘은 데이크스트라
알고리즘이므로 3번이 정답에 해당됩니다.
4장 6절 – 작업 스케줄링 문제
62.다음 작업에 대한 작업 스케줄링 문제의 최적해를 구하려고 한다. 가장 먼저 기계에 할당하는 작업은? (2018.
기말)(교재 131p)
t1=(2, 5) t2=(6, 9) t3=(4,
9) t4=(1, 4)
t5=(0, 7) t6=(9, 10) t7=(7, 10) t8=(5, 8)
|
① t1 ② t4
③ t5 ④ t8
정답 : 3번
설명 : 작업의 시작시간이 제일 빠른것부터
시작함으로 3번이 0부터 시작할 수 있으므로 정답입니다.
4장 7절 – 작업 선택 문제
63.욕심쟁이 방법을 적용한 작업 선택 문제에서 기계에 가장 먼저 할당되는 작업은? (2019. 기말)(교재 135p)
,
,
,
,
,
,
,
|
①
②
③
④
정답 : 3번
설명 : 완료시간이 제일 빠른 것을 먼저
선택하기 때문에 3번이 제일 적은 2를 할당되면 되므로 3번이 답입니다.
4장 8절 – 허프만 코딩
64. 허프만 코딩에 대한 설명으로 적절하지 못한 것은? (2019. 출석대체)(교재 138p)
① 가변 길이 변환 코드를 사용한다.
② 특정 텍스트에 대한 허프만 트리는 유일하다.
③ 허프만 코딩은 접두부 코드이다.
④ 허프만 트리는 전 이진트리이다.
정답 : 2번
설명 : 허프만 코딩은 가변 길이 변환 코드를
사용하고 인코딩과 디코딩을 하기 위해 접두부 코드를 사용하고 전 이진 트리입니다. 해당 사항이 없는 2번이 정답입니다.
65.텍스트 abcdbcdcdd를 허프만 코딩으로 인코딩하였을 때 가장 짧은 코드가 부여되는 문자는? (2018.
기말)(교재 140p)
① a ② b
③ c ④ d
정답 : 4번
설명 : d가 가장 많이 나오기 때문에 가변
길이 변환 코드로 변환시 제일 짧은 코드로 변환합니다. 정답은
4번
66. 허프만 트리와 관련이 없는
것은? (2018. 출석 대체)(교재 139p)
① 완전 이진 트리 ② 욕심쟁이 방법
③ 접두부 코드 ④ 최적 코드
정답 : 1번
설명 : 허프만 트리는 전 이진 트리이기 때문에
정답은 1번입니다.
* 5장 – 정렬 알고리즘
5장 1절 – 정렬의 개념
67. 정렬 방식의 관점에서 나머지와 다른 하나의 정렬 알고리즘은? (2019. 기말)(교재 154p)
① 버블 정렬 ② 셸 정렬
③ 힙 정렬 ④ 계수 정렬
정답 : 4번
설명 : 비교 기반 정렬 알고리즘인 버블 정렬, 합병 절렬, 셸 정렬이 있고 데이터 분포 기반 알고리즘인 기수 정렬, 계수 정렬이 있는데 해당되는 답은 4번입니다.
68. 비교 기반의 정렬 알고리즘이 아닌 것은? (2018. 기말)(교재 154p)
① 버블 정렬 ② 기수 정렬
③ 합병 정렬 ④ 셸 정렬
정답 : 2번
설명 : 비교 기반 정렬 알고리즘인 버블 정렬, 합병 절렬, 셸 정렬이 있고 데이터 분포 기반 알고리즘인 기수 정렬, 계수 정렬이 있는데 해당되는 답은 2번입니다.
5장 2절 – 버블 정렬
69. 안정적인 정렬 알고리즘은? (2019. 기말)(교재 158p)
① 버블 정렬 ② 힙 정렬
③ 퀵 정렬 ④ 셸 정렬
정답 : 1번
설명 : 안정적인 정렬 알고리즘은 버블
정렬이므로 정답은 1번입니다.
70.주어진 데이터에 대해 버블 정렬을 적용하여 오름차순으로 정렬할 때 인접한 두 데이터 간의 자리바꿈이 발생하는 총
횟수는? (2019. 기말)(교재 156p)
50 40 30 20 10
|
① 8 ② 10
③ 12 ④ 15
정답 : 2번
설명 : 50이 진행하면서 4번 40이 3번 30이 2번 10이 1번 총 10번이므로 2번이 정답입니다.
71.다음 데이터에 대해서 왼쪽에서 오른쪽으로 진행하는 버블 정렬의 하나의 단계(패스)를 수행한 후의 데이터를 바르게
나열한 것은? (단, 오름차순으로 정렬한다.) (2018. 기말)(교재 156p)
20 60 70 10 80 30 50 40
|
① 20 60 70 10 40 30 50 80
② 20 60 70 10 30 50 40 80
③ 20 60 10 70 40 30 50 80
④ 20 60 10 70 30 50 40 80
정답 : 4번
설명 : 왼쪽부터 차례대로 버블정렬이 진행 된
경우 70과 10이 바뀌고 80과 30이 바뀌고 80과 50이 바뀌고 80과 40이 자리를 바뀌어 4번의 형태를 이룹니다. 정답은 4번입니다.
5장 3절 – 선택 정렬
72.정렬되지 않은 데이터 중에서 가장 작은 값을 골라서, 이 값과 미정렬 데이터 부분의 첫 번째 원소와 교환하는 방식의
정렬 알고리즘은? (단, 오름차순으로 정렬한다.) (2019. 기말)(교재 160p)
① 삽입 정렬 ② 셸 정렬
③ 선택 정렬 ④ 버블 정렬
정답 : 3번
설명 : 선택 정렬의 특징이므로 3번입니다.
73.오름차순으로 정렬하는 선택 정렬에 대한 설명으로 적절하지 못한 것은? (2018. 기말)(교재 164p)
① 데이터의 입력 상태에 따라 성능이 달라진다.
② 제자리 정렬 알고리즘이다.
③주어진 데이터 중에서 가장 작은 값부터 골라서 차례대로 나열한다.
④ 안정적이지 않은 정렬 알고리즘이다.
정답 : 1번
설명 : 최소값을 찾기 때문에 성능은 민감하지
않고 언제나 동일한 시간복잡도를 가지기 때문에 정답은 1번입니다.
나머지는 2,3,4번은 선택 정렬의 특징입니다.
5장 4절 – 삽입 정렬
74. 삽입 정렬에 대한 설명으로 적절하지 못한 것은? (2019. 기말)(교재 169p)
① 입력이 거의 정렬된 경우 빠른 수행 시간
을 갖는다.
② 안정적인 정렬 알고리즘이다.
③ 셸 정렬의 단점을 보완한 방법이다.
④ 제자리 정렬 알고리즘이다.
정답 : 3번
설명 : 삽입 정렬을 보완한 방법이 셸
정렬이므로 반대인 정의입니다. 정답은 3번입니다.
75.삽입 정렬을 적용할 때 가장 좋은 성능을 나타내는 입력 데이터의 상태는? (단, 오름차순으로 정렬한다.) (2018.
기말)(교재 169p)
① 60 50 40 30 20 10
② 60 10 50 20 40 30
③ 10 20 30 40 50 60
④ 10 60 20 50 30 40
정답 : 3번
설명 : 삽입 될 자리를 찾기 위해서 정렬이
되어 있는 상태가 가장 성능이 빠릅니다. 정답은 정렬되있는 3번입니다.
5장 5절 – 셸 정렬
76. 삽입 정렬의 단점을 보완한 정렬 알고리즘은? (2018. 기말)(교재 170p)
① 버블 정렬 ② 선택 정렬
③ 셸 정렬 ④ 힙 정렬
정답 : 3번
설명 : 삽입 정렬의 단점을 보완한 정렬
알고리즘은 셸 정렬로 정답은 3번입니다.
5장 6절 – 합병 정렬과 퀵 정렬
77. 수행시간이
이지만 제자리 정렬 알고리즘이 아닌 것은? (2019.
기말)(교재 178p)
① 셸 정렬 ② 합병 정렬
③ 퀵 정렬 ④ 힙 정렬
정답 : 2번
설명 :
78. 합병 정렬과 퀵 정렬에 대한 공통적인 설명으로 올바른 것은? (2019. 기말)(교재 176p)
① 평균의 경우
, 최악의 경우
의 성능을 갖는다.
②데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지된다.
③입력 데이터를 저장하는 공간 이외에 상수 개를 초과하는 추가적인 저장 공간이 필요하다.
④ 분할정복 방법이 적용되었다.
정답 : 4번
설명 : 분할 정복 방법으로 정렬한 방법이므로 4번이 정답입니다.
79. 평균적인 성능이 O(nlogn)인 안정적인 정렬 알고리즘은? (2018. 기말)(교재 178p)
① 퀵 정렬 ② 셸 정렬
③ 힙 정렬 ④ 합병 정렬
정답 : 4번
설명 : 안정적인 알고리즘은 보기 중 합병
정렬이 있으므로 4번이 정답입니다.
80.비교 기반 알고리즘 중에서 정렬 과정에서 입력 크기에 비례하는 만큼의 추가적인 저장 공간을 요구하는 것은?
(2018. 기말)(교재 178p)
① 셸 정렬 ② 힙 정렬
③ 퀵 정렬 ④ 합병 정렬
정답 : 4번
설명 : 합병정렬은 데이터 n 만큼의 추가저장공간이 필요한 정렬로 정답은 4번입니다.
5장 7절 – 힙 정렬
81.주어진 데이터를 오름차순으로 힙 정렬하기 위해 초기 힙을 구성하였다. 이때 루트 노드에 존재하는 데이터는?
(2019. 기말)(교재 181p)
10 7 15 88 50 30 40
|
① 7 ② 15
③ 40 ④ 88
정답 : 4번
설명 : 오른차순으로 힙을 정렬하기 위해서는
가장 큰 값은 88을 루트 노드에 존재해야 가능하기에 4번이 정답입니다.
82.다음은 초기 힙을 배열로 표현한 것이다. 이 배열에 대해 오름차순으로 정렬하는 힙 정렬의 두 번째 단계를 한 번
수행한 후의 배열의 상태를 올바르게 표현한 것은? (2018. 기말)(교재 190p)
80 60 70 40 20 30 50 10
|
① 60 70 50 40 30 20 10 80
② 70 60 50 40 20 30 10 80
③ 70 60 50 40 30 20 10 80
④ 60 70 40 20 30 50 10 90
정답 : 2번
설명 : 처음 힙 정렬 시 10과 80의 자리가 바뀌어 10 60 70 40 20 30 50 80 이 되고 두 번째 힙 정렬시 10과 70이 바뀌어 70 60 10 40 20
30 50 80이 되고 10은 다시 50의 자리가 바뀌므로 70 60 50 40 20 30 10 80 이 되어 정답은 2번입니다.
5장 9절 – 계수 정렬
83.주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방법에 대한
설명으로 적절한 것은? (2018. 기말)(교재 195p)
① 선형 시간의 성능을 갖는다.
② 안정적이지 않은 정렬 알고리즘이다.
③ 제자리 정렬 알고리즘이다.
④ 비교 기반의 알고리즘이다.
정답 : 1번
설명 : 계수 정렬에 대한 설명으로 정답은 1번입니다.
5장 10절 – 기수 정렬
84. 기수 정렬에 대한 설명으로 올바른 것은? (2019. 기말)(교재 203p)
① 비교 기반의 정렬 알고리즘이다.
② 입력 원소의 값의 자릿수가 상수일 때 유용하다.
③ 제자리 정렬 알고리즘이다.
④ 시간 복잡도
을 갖는다.
정답 : 2번
설명 : 기수 정렬 알고리즘은 제자리 정렬
알고리즘이 아니고 시간 복잡도는 O(n)이며 비교 기반의 정렬
알고리즘이 아니고 데이터 분포 기반 정렬입니다. 설명으로
올바른 것은 2번이 정답입니다.
* 6장 – 탐색 알고리즘
6장 2절 – 순차 탐색
85. 순차 탐색에 대한 설명으로 틀린 것은? (2019. 기말)(교재 213p)
①무순서 데이터에 비해 정렬된 데이터에 대해 보다 효과적인 탐색이 가능하다.
② 모든 데이터 리스트에 적용 가능하다.
③
개의 데이터에
대한 최대 비교 횟수는
번이다.
④ 데이터가 많은 경우에는 적합하지 못한 방법이다.
정답 : 1번
설명 : 모두 순차적으로 검색하기 때문에 정렬된
데이터에 상관없이 항상 똑같은 성능이기에 1번이 틀렸으므로 1번이 정답입니다.
6장 3절 – 이진 탐색
86. 이진 탐색에 대한 설명으로 적절하지 못한 것은? (2019. 기말)(교재 218p)
① 최악의 경우의 탐색 성능은
이다.
② 정렬된 리스트에 대해서만 적용 가능하다.
③ 삽입과 삭제가 빈번한 경우에는 적합하지 않다.
④ 연결 리스트로 구현하면 보다 효과적인 탐색이 가능하다.
정답 : 4번
설명 : 연결리스트는 정렬된 리스트만을 구현하지
않을 수 있으므로 4번이 틀린 개념으로 정답입니다.
87. 이진 탐색 트리에서 노드 35를 삭제하려고 한다. 삭제되는 노드 35의 자리에 위치하는 노드는? (2018.
기말)(교재 217p)
① 7 ② 30
③ 40 ④ 55
정답 : 3번
설명 : 루트노드인 35가 삭제된다면 다음 기준값인 40을 루트노드로 이동시키기 때문에 3번이
정답입니다.
88.이진 탐색 트리에서 최악의 탐색 성능을 갖는 경우의 트리의 높이는? (단, 노드의 개수는 n이다) (2018.
기말)(교재 218p)
① ⌞logn⌟ ② n/2
③ n ④ 2n
정답 : 3번
설명 : 삽입과 삭제의 식나이 필요함으로 3번이 정답입니다.
6장 4절 – 탐색 트리
89. 흑적 트리에 대한 설명으로 적절한 것은? (2019. 기말)(교재 229p)
① 루트 노드는 흑색이거나 적색이다.
②임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 적색 노드가 존재한다.
③ 흑색 노드가 연달아 나타날 수 없다.
④ 이진 탐색 트리의 형태를 갖는 균형 탐색 트리이다.
정답 : 4번
설명 : 루트노드는 흑색이고 임의의 노드로부터
리프 노드까지의 경로 상에는 흑색 노드가 존재하며 흑색 노드가 연달아 나타날 수 도 있습니다. 4번이 적절하므로 정답입니다.
90. 모든 리프 노드의 레벨이 동일한 트리는? (2019. 기말)(교재 240p)
① 흑적 트리 ② 이진 탐색 트리
③ 완전 이진 트리 ④ B-트리
정답 : 4번
설명 : B-트리의 개념으로 4번이 정답입니다. 나머지 세 개는 모든 리프 노드의 레벨이 동일하지 않을 수 있습니다.
91. 탐색 방법 중에서 최악의 경우의 성능이 나머지와 다른 하나는? (2019. 기말)(교재 265p)
① 이진 탐색 ② 흑적 트리
③ 이진 탐색 트리 ④ B-트리
정답 : 3번
설명 : 탐색 중 이진 탐색 트리는 최악의 경우
O(n)이며 나머지 트리들의 최악의 성능은 O(log n)이므로 정답은 3번입니다.
92. 흑적 트리의 설명으로 적절한 것은? (2018. 기말)(교재 229p)
① 루트 노드는 적색이다.
②모든 리프 노드의 레벨은 동일하다.
③ 어떤 노드가 적색이면 부모 노드는 항상 흑색이다.
④임의의 노드에서 리프 노드까지의 경로 상에 존재하는 적색 노드의 개수는 동일하다.
정답 : 3번
설명 : 루트 노드는 흑색이거나 적색이며 모든
리프 노드의 레벨이 동일 하지 않을 수 있으며 임의의 노드에서 리프 노드까지의 경로 상에 존재하는 흑색 노드가 존재합니다. 적절한 정답은 3번입니다.
93. t=2인 B-트리에서 70을 삽입하는 과정에서 부모 노드로 보내지는 키값은 무엇인가? (2018. 기말)(교재
245p)
① 60 ② 70
③ 80 ④ 90
정답 : 3번
설명 : 70은 50보다 크기 때문에 오른쪽 리프 노드에 입력되는데 해당 리프 노드가 분할을
해야함으로 80이 루트 노드로 올라가고 80보다 작은 60과 70은 따로 분할되어 세 번째 리프노드가
되고 90은 4번째 노드가 됩니다. 정답은 3번입니다.
6장 5절 – 해 싱
94.데이터들이 연속된 위치를 점유하여 클러스터를 형성하고 이것이 점점 커지는 현상으로 인해 평균 탐색 시간의 증가를
초래하는 충돌 해결 방법은? (2019. 기말)(교재 260p)
① 선형 탐사 ② 이중 해싱
③ 이차 탐사 ④ 연쇄법
정답 : 1번
설명 : 폐쇄 해싱 충돌 해결 방법은 네가지
방법이 있는데 버킷해킹, 선형탐사, 이차 탐사, 이중 해싱 있습니다. 그중 이차 탐사란 1차 클러스터링을 해결하기 위해 탐사 순서의 단게에 대한 이차식을 이용하여 탐사
순서를 정하는 방법이며, 이중 해싱이란 1차 및 2차 클러스터링을 해결하기 위해 원래의 킷값을 이용하여 탐사 순서를 정하는 방법입니다.
1번이 선형 탐사의 내용이므로 정답은 1번입니다.
95. 다음 중 충돌 해결 방법이 아닌 것은? (2018. 기말)(교재 258p)
① 제산 잔여법 ② 이중 해싱
③ 이차 탐사 ④ 선형 탐사
정답 : 1번
설명 : 폐쇄 해싱은 버킷해싱, 선형탐사, 이차 탐사, 이중 해싱이 있습니다. 해당 충돌 해결방법이 아닌 1번이 정답입니다.
* 7장 – 근사 알고리즘
7장 2절 – 클래스 P와 클래스 NP
96. 다음 중 NP-완전 문제가 아닌 것은? (2018. 기말)(교재 271p)
①무방향 그래프에서 모든
정점을 한 번씩만 지나가는 사이클의
존재 여부를 확인하는 문제
②하나의 정점에서 다른 모든 정점으로의 가장 짧은 경로를 구하는 문제
③정규곱형으로 주어진 논리식을 참으로 만들 수 있는 지 판단하는 문제
④n개의 양의 정수가 주어졌을 때, 각 집합에 포함된 수의 합이 동일하도록 n개의 정수를 두 개의 집합으로 나눌 수 있는지 판정하는 문제
정답 : 2번
설명 : 2번은 동적 프로그래밍 방법을 말한
것으로 Np-완전 문제가 아닙니다.
7장 3절 – NP-완전 문제와 NP-하드 문제
97. 어떤 문제 A가 NP-완전 문제라는 설명으로 적합한 것은? (2018. 기말)(교재 277p)
①클래스 NP의 모든 문제가 문제 A로 지수 시간 변환되며 A가 클래스 NP에 속하는 경우
②클래스 NP의 모든 문제가 문제 A로 다항식 시간 변환되며
A가 클래스 NP에 속하는 경우
③클래스 NP의 모든 문제가 문제 A로 지수 시간 변환되는
경우
④클래스 NP의 모든 문제가 문제 A로 다항식 시간 변환되는
경우
정답 : 2번
설명 : NP-완전 문제의 설명이 올바른 것은 2번이 해당되므로 정답은 2번입니다.
7장 4절 – 근사 알고리즘
98.NP-완전 문제의 근사 알고리즘이다. 이를 통해 해결할 수 있는 문제는? (2019. 기말)(교재 280p)
- 주어진
그래프의 최소 신장 트리를 구한다.
- 임의의
정점 하나를 루트 노드로 지정해서 최소 신장 트리를 깊이 우선 탐색 순서대로 정점을 나열하고 마지막에 첫 정점을 한 번 더 추가한다.
|
① 버텍스 커버 문제
② 외판원 문제
③ CNF-만족성 문제
④ 클리크 판정 문제
정답 : 2번
설명 : 외판원 문제는 최소한의 비용으로 모든
도시를 한번씩 방문하고 처음 도시로 돌아오는 방법을 찾는 것으로 해당 문제에 적절한 답안을 줄 수 있으므로 정답은 2번입니다.
* 8장 – 해 탐색 알고리즘
8장 3절 – 유전 알고리즘
99. 다음 설명에 해당하는 유전 알고리즘의 연산은? (2018. 기말)(교재 340p)
•부모의 형질을 나누어 갖는 연산이다.
•다른 최적화 방법과 구별짓는 연산이다.
|
① 변이 ② 선택
③ 배분 ④ 교차
정답 : 4번
설명 : 형질을 나누고 최적화 방법과 구별이
가능해지는 것은 4번의 교차가 정답입니다.
100. 외판원 문제에 가장 적합한 염색체 인코딩 방법은? (2018. 기말)(교재 337p)
① 순열 인코딩 ② 값 인코딩
③ 이진 인코딩 ④ 트리 인코딩
정답 : 1번
설명 : 외판원 문제는 도시를 순서대로 도는
특징이 있어 순열 인코딩이 적합한 인코딩 방법이기에 정답은 1번입니다.
댓글 없음:
댓글 쓰기