컴퓨터과학개론 , 다음 8문제 중에서 반드시 5개만을 선택해서 정리하여 제출하시오.

소개글

컴퓨터과학개론입니다. 부족하지만 나름대로 정리해보았습니다. 잘 참고하셔서 좋은 결과 거두세요^^*

목차

1. 이진 트리, 완전 이진 트리, 포화 이진 트리를 설명하고 비교하시오.
2. 교재에서 다룬 모든 정렬 알고리즘들을 설명하고 비교하시오.
3. 가상기억장치의 페이징 기법과 세그먼테이션 기법을 설명하고 비교하시오.
4. 조합회로와 순차회로의 개념과 종류를 나열하고 설명하시오.
5. 데이터베이스 시스템의 3단계 구조와 관련해서 스키마에 대해 설명하고 비교하시오.
6. 참고문헌

본문내용

이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 단순한 이진트리는 자식을 두 가지 밖에 못 가지는 한계점을 가지고 있지만 범용성으로 인해 널리 이용된다. 루트는 트리의 최상위에 있는 노드이고 자식노드는 노드 하위에 연결된 노드이며 차수는 자식노드의 수, 부모노드는 노드의 상위에 연결된 노드이다. 이진 검색 트리 알고리즘을 구축하기 위해서는 프리픽스 필드들 사이의 크기 비교를 통한 정렬을 정의하고, 프리픽스 필드의 네스팅 관계에 대한 개념을 정의해야 한다. 먼저, 크기 비교를 통한 정렬을 정의함에 있어서 각각의 프리픽스 필드가 고정된 길이를 갖는 것이 아니고 서로 다른 길이를 갖기 때문에 어려움이 있다. 이러한 프리픽스 필드의 가변성은 같은 길이를 갖는 프리픽스 필드의 경우에는 프리픽스 필드의 값 비교를 통해 크기를 결정하고, 서로 다른 길이의 프리픽스 필드를 갖는 경우에는 짧은 쪽 프리픽스 필드 길이까지의 값을 비교하여 크기를 비교함으로써 해결 할 수 있다.

포화이진트리는 모든 단말 노드의 깊이가 같은 완전이진 트리이다. 트리 전체가 모든 노드가 가득 체워져 있는 셈이다. 포화이진트리는 단말 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리이다. 각각의 사람이 정확히 두 명의 생물학적 부모(한 명의 어머니와 한 명의 아버지)를 갖는 것처럼, 주어진 깊이에 대한 한 사람의 가계도가 포화 이진 트리의 예가 될 수 있다. 높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 1 높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다. 이에 비해 완전 이진트리는 노드가 왼쪽부터 차곡차곡 채워진 형태의 트리를 말한다. 완전 이진트리는 끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진 (마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진트리이다.

참고 자료

컴퓨터과학개론, 한국방송통신대학교 출판문화원