방통대 컴퓨터과학개론 시험자료정리 (알고리즘, 컴퓨터구조)

피벗: 퀵정렬에서 주어진 리스트를 두 개의 서브 리스트로 분할할 때 기준이 되는 원소

퀵정렬: 피벗을 기준으로 입력 리스트 원소를 두 개의 서브 리스트로 분할하고 각 서브 리스트에 대해 독립적으로 퀵 정렬을 순환적으로 적용

합병정렬: 동일한 크기의 두개의 서브 리스트로 분할하고 각각 정렬한 뒤 합병

6.1 분할정복방법사용, 최악의 경우 시간복잡도 O(n2), 평균수행시간은 O(nlogn) : 퀵정렬

6.2 퀵 정렬 분할 과정을 한 번 적용 후 리스트에 존재하는 데이터 개수는? 6개

 [35 26 15 77 10 61 11 59 17 48 19 40]

6.3 합병 정렬 알고리즘의 합병 과정에 입력으로 주어지는 두 서브 리스트 X, Y는 어떤 상태?

 - X, Y 각각 제 순서로 정렬되어 있어야 한다.

6.4 임의의 순서로 원소가 저장된 배열에서 입력데이터에 대한 어떠한 처리도 없이 바로 탐색 시 적절한 것?

 - 무순서일 경우 '순차탐색'

6.5 이진 탐색에서 가장 빨리 찾아낼 수 있는 데이터 위치는? 가운데

6.6 이진탐색 트리에서 탐색 과정에 대한 최악의 시간 복잡도와 평균 시간 복잡도 인 것?

 - O(n) - O(logn)

6.7 해싱에서 연쇄법과 개방 주소법에 대한 설명으로 틀린 것은?

 - 키 값을 해시 테이블 주소로 변환하는 함수들의 종류이다(X) -> 해시함수

6.8 1차 클러스터링 현상이 발생하기 쉬운 충돌 해결 방법은? 선형탐사

+ 2차 클러스터링 현상은 이차형탐사

불대수: 디지털 회로의 선택과 분석을 위해 이진 변수의 노리연산을 나타내는 대수

조합회로: 논리게이트로 구성되고 기억회로는 X, 출력 값이 단순 입력값의 '조합'에 의해 결정

순차회로: 연산의 각 단계마다 회로의 특정 상태가 저장되고 참조, 출력값이 입력값과 기억소자에 저장된

현재상태에 따라 결정

플립플롭: 1비트의 정보를 저장할 수 있는 장치로서 입력신호로 상태를 바꾸도록 지시 전까지는 현재의 이진상태를 유지

7.1 시스템 버스의 종류

 - 제어버스, 주소버스, 데이터버스 (암기 : 제주대)

7.2 다음 회로에서 출력이 다른 셋과 다른 것은? X 1, Y 1, Z 0

7.3 플립플롭을 사용하는 논리회로: "카운터", 레지스터

7.4 n개의 비트표현을 최대 2n개의 서로 다른 정보로 변환, 출력 중 하나는 1 나머지는 모두 0

 - 디코더

7.5 기억장치 계층적 구조에서 접근 속도가 가장 빠른 것은? 레지스터

인터럽트: CPU 정상 수행을 잠시 멈추고 CPU 이외의 다른 장치 요구사항을 수행하기 위한 기능

누산기: 데이터를 일시적으로 저장하는 레지스터

8.1 주소지정방식 중 유효주소를 얻기 위해 두 번의 기억장치 접근이 필요한 것?

 - 간접 주소지정방식

8.2 기억장치, 기억장치에서 읽어온 데이터를 임시로 저장하는 레지스터는? MBR

8.3 제어장치 명령어사이클 -> 인출 해독 실행 저장

8.4 입출력제어 방식 중 전용 프로세서를 사용해서 CPU와 같은 다양한 연산 작업도 가능한것? 채널방식

8.5 하나의 연산을 여러 개의 단계로 분할하여 각 단계가 동시에 서로 다른 데이터를 취급하는 명령어 수준의 병렬처리 기법은? 파이프라인 처리