방통대 컴퓨터과학개론 시험자료정리 (1)

방통대 컴퓨터과학개론 시험자료정리 (1)

컴퓨터: 프로그램이 가능한 자료처리기

ENIAC: 모클리와 에커드가 개발한 최초의 완전 전자식 범용 컴퓨터

EDVAC: 폰 노이만의 내장 프로그램 방식에 기반한 최초의 컴퓨터

1.1 자료처리기로서 컴퓨터에서 처리가능한 작업의 유형과 연산의 집합을 결정하는것?

- 프로그램

1.2 컴퓨터에 자료를 표현하는 방식에 따라 컴퓨터를 분류할 때 이에 속하는 것?

- 디지털, 아날로그 컴퓨터

1.3 컴퓨터과학은 문제 해결을 위해 (알고리즘) 과 관련된 이슈를 다루는 분야이다.

1.4 하나의 완전한 컴퓨터 시스템을 구성하는 4가지 요소

- 하드웨어, 소프트웨어, 자료(데이터), 사용자

1.5 폰노이만 모델과 관련된 설명

- 내장프로그램, 프로그램은 명령어의 나열이다, 저장된 프로그램 방식을 제안

자료: 현실 세계로부터 관찰이나 측정을 통해 단순히 얻어지는 사실

정보: 자료를 처리해서 얻은 결과

2.1 다음 중에서 가장 작은 값을 나타내는 것은? 0.43(8) 

2.2 이진수 1100101.10011을 8진수와 16진수로 각각 올바르게 변환한 것은?

 - 145.46, 65.98

2.3 2의 보수 방식을 사용해서 8비트로 표현된 정수 10100001은 십진수로 얼마인가?

 - "-95"

2.4 십진수 53.625를 부동소수점 방식으로 올바르게 표현한 것은?

 - 10100, 1010110100

2.5 미국표준협회에서 개발한 코드체계, 7비트 코드체계로 총 128개 다른 문자 표현

 - ASCII 코드

자료구조: 추상화를 통해 자료의 논리적 관계를 구조화 한 것

스택: 데이터의 삽입과 삭제가 한 쪽에서만 이루어지는 자료구조

큐: 선형리스트의 한쪽에서는 삭제만 다른 한쪽에서는 삽입만 이루어지는 자료구조

3.1 비선형 자료구조에 속하는 것? 트리, 그래프

3.2 배열에 대한 설명으로 올바른 것은?

 - 삽입과 삭제 연산 수행 시 추가 연산으로 인해 오버헤드가 발생하는 정적 구조를 가진다.

3.3. 한 쪽 끝에서는 삽입, 다른 한 쪽에서는 삭제를 수행하는 구조 - 큐

잎노드: 단말 노드라고도 하며 노드의 차수가 0

내부노드: 비단말노드라고 하며, 루트 노드와 단말 노드를 제외한 나머지 노드

이진트리: 차수가 2인 트리, 모든 노드는 최대 2개의 서브 트리를 가짐

이진 트리의 순회 : 데이터의 삽입 삭제가 한 쪽에서만 이루어짐

완전 이진트리: 트리의 최대 레벨이 k일 때 k-1 까지는 포화 이진 트리를 형성하고 k에선 왼쪽부터 오른쪽으로 채워진트리

4.1 트리의 루트노드에서 리프노드에 이르는 가장 긴 경로에 존재하는 노드의 개수 - 깊이

4.2 이진트리: 각 노드 차수 중 최소 차수가 2이상이다.

4.3. 그래프 관련 용어에 대한 설명으로 틀린 것?

 - 세 개 이상의 정점을 가진 경로 중 시작 정점과 끝 정점이 같은 경로를 사이클이라고 한다(O)

욕심쟁이 방법: 그 단계에서 가장 최고라고 여겨지는 최적해를 계속 찾는 전략

분할정복 방법: 더는 쪼갤 수 없을 때까지 작은 문제로 나누고 해결 후 다시 결합

동적프로그래밍: 여러 부분 문제로 분할하고 가장 작은 부문 문제부터 해를 구해 테이블에 저장하는 상향식 접근방법

거스름돈 문제: 고객이 받을 동전의 수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제

배낭 문제: 배낭의 용량을 초과하지 않는 범위에서 이익의 합이 최대가 되도록 물체를 넣는 방법

선택정렬: 주어진 원소 중 가장 작은 키 값을 갖는 원소를 선택하여 차례대로 나열

버블정렬: 주어진 리스트 왼쪽 부터 인접한 두 원소를 차례대로 비교

삽입정렬: 주어진 원소를 하나씩 뽑은 후 나열된 원소들이 항상 정렬된 형태를 가지도록 바른위치에 삽입하여 나열

5.1 알고리즘에 대한 설명으로 적절하지 못한것은?

 - 0개 이상의 외부입력과 1개 이상의 출력이 있으면 된다(O)

5.2 대표적인 알고리즘 설계 기법은? 욕심쟁이 방법, 동적 프로그래밍 방법, 분할정복 방법

5.3 욕심쟁이 방법으로 해결 가능한 것은? 거스름돈, 배낭 문제

extra 동적 프로그래밍 방법 - 모든 정점 쌍 간의 최단 경로를 구하는 플로이드 알고리즘

5.4 알고리즘의 시간 복잡도에 대한 설명으로 적절한 것은?

 - 알고리즘에서 사용된 단위 연산들의 수행횟수의 합으로 정의

 - 단순히 단위 연산 개수가 아닌 입력크기의 함수로 표현

 - 입력되는 데이터의 상태에 따라 달라지고 일반적으로 최악의 수행시간을 평가 척도로 사용

5.5 f(n) > 2g(n) :  f(n)이 더 클 경우 오메가

5.6 미정렬 데이터 중 가장 작은 키 값을 찾는 데이터를 선택하고 차례로 나열하는 것은? 선택정렬

5.7 주어진 데이터에 대해 왼쪽부터 인접한 두 키를 비교하는 정렬? 버블정렬