한국방송통신대 컴퓨터과학개론 기말과제물

소개글

방송대 컴퓨터과학과 1학년 2학기 컴퓨터과학개론 기말과제

1. 컴퓨터에서 정수와 실수의 표현 방법에 대해서 설명하시오.
2. 이진 트리, 완전 이진 트리, 포화 이진 트리를 설명하고 비교하시오.
3. 교재에서 다룬 모든 정렬 알고리즘들을 설명하고 비교하시오.
4. 가상기억장치의 페이징 기법과 세그먼테이션 기법을 설명하고 비교하시오.
5. 조합회로와 순차회로의 개념과 종류를 나열하고 설명하시오.
6. 함수의 매개변수 전달방식인 값호출 방식과 참조호출 방식을 설명하고 비교하시오.
7. 데이터베이스 시스템의 3단계 구조와 관련해서 스키마에 대해 설명하고 비교하시오.
8. OSI 참조 모델에 대해서 설명하시오.

목차

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

참고문헌

본문내용

이진 트리(binary tree)는 트리 중에서 모든 노드의 차수가 최대 2개를 넘지 않는 트리이다. 즉 노드의 차수가 하나 또는 두 개이고, 따라서 루트를 기준으로 최대 두 개의 서브트리를 가지고 왼쪽 서브트리와 오른쪽 서브트리로 구분된다. 서브트리가 최대 두 개를 가질 수 있으니 서브트리가 한 개인 이진트리도 가능한데 이렇게 차수가 모두 1인 한쪽으로만 치우친 이진 트리와 차수가 모두 2인 이진트리를 구성할 수 있는 이진트리의 특성으로 이진트리의 최대 높이와 최소 높이를 계산할 수 있다. 노드의 개수가 N인 경우 최대 높이는 노드의 개수와 같은 N이 되고 최소 높이는 [log₂N]+1이 된다. 이진트리는 주요 연산은 삽입, 삭제, 순회인데 그 중에서 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 순회 연산이 가장 대표적이다. 이런 순회 연산을 이용해서 트리 내의 정보를 선형적인 순서의 정보로 만들 수 있다. 트리의 루트 노드를 (D), 왼쪽 서브트리를 (L), 오른쪽 서브트리를(R)로 단순하게 가정하고, 항상 왼쪽 서브트리와 오른쪽 서브트리에 대해서 왼쪽 우선적으로 방문한다고 하면 아래와 같이 세 가지 형태의 방문 순서를 얻을 수 있는데
(1)D(루트노드)>L(왼쪽 서브트리)>R(오른쪽 서브트리)
(2)L(왼쪽서브트리)>D(루트노드)>R(오른쪽 서브트리)
(3)L(왼쪽 서브트리)>R(오른쪽 서브트리)>D(루트노드)
이는 루트 노드를 어느 시점에 방문 하느냐에 따라 결정되는 것을 확인 할 수 있다. 루트노드를 가장 먼저 방문하면 전위(preorder) 순회, 루트노드를 중간에 방문하면 중위(inorder) 순회, 루트노드를 가장 나중에 방문하면 후위(postorder) 순회가 된다. [그림 2] 이진트리의 순회 방법
이진트리에는 특수한 조건을 갖는 포화 이진트리(full binary tree)와 완전 이진트리(complete binaty tree)가 있다. 포화 이진트리는 쉽게 말해 빈 곳이 없이 모두 꽉 차 있는 이진트리이다.

참고 자료

이관용, 정광식, 컴퓨터과학개론, 한국방송통신대학교출판문화원(2015년 07월 25일).