CS 1주차 발자국&미션

1주차 발자국학습알고리즘비선형 자료구조 - 트리 (Tree) : 노드와 링크로 구성포화 이진 트리 : 터미널 노드가 아닌 내부 노드들은 모두 2개의 자식 노드를 갖고 있음완전 이진 트리 : 포화 이진 트리에서 터미널 노드중 오른쪽 노드가 없는 트리 이진 탐색 (Binary Search) : 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색, O(logN)이진 트리의 탐색전위순회 PreOrderTraversal ( 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 )중위순회 InOrderTraversal (왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 )후위순회 PostOrderTraversal ( 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 )이진 탐색 트리 (Binary Search Tree) 규칙왼쪽 자식 노드는 부모 노드 보다 작은 값오른쪽 자식 노드는 부모 노드 보다 큰 값서브트리도 이진탐색트리 유지중복안됨탐색, 추가, 삭제 시 루트노드부터 비교시작해서 내려감삭제 case자식 노드가 없는 터미널 노드일 경우자식 노드 1개자식 노드 2개 1주차 미션컴퓨터 구조1. 4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.2. 다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.A( (BB)’+ 0A) + (CC)' = (AB’) +CA( (B)' + 0) + (C)' = (AB') + CA(B') + C' = (AB') + CAB' + C' = AB' + C (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’)(B') + AD'D + (CA)'D = B' + (DC') + (DA')B' + A0 + (CA)'D = B' + (DC') + (DA')B' + (CA)'D = B' + (DC') + (DA')B' + (C' + A')D = B' + (DC') + (DA')B' + C'D + A'D = B' + DC' + DA'(A’B) + B(B1 + BC) = B(A’B) + B(B + BC) = B(A’B) + BB + BBC = B(A’B) + B + BC = B(A’B) + B = BA’B + B = BB = B B’(1C + BD) + DB = (B’C) + (DB)B’(C + BD) + DB = (B’C) + DBB’C + B’BD + DB = B’C + DBB’C + 0D + DB = B’C + DBB’C + DB = B’C + DB3. 다음 2진수를 10진수로 변환해보세요.110111 = (2^5) * 1 + (2^4) * 1 + (2^3) * 0 + (2^2) * 1 + (2^1) * 1 + (2^0) * 1 = 5510000001 = (2^7) * 1 + (2^6) * 0 + (2^5) * 0 + (2^4) * 0 + (2^3) * 0 + (2^2) * 0 + (2^1) * 0 + (2^0) * 1 = 12911111100000 = (2^10) * 1 +(2^9) * 1 +(2^8) * 1 + (2^7) * 1 + (2^6) * 1 + (2^5) * 1+ (2^4) * 0 + (2^3) * 0 + (2^2) * 0 + (2^1) * 0 + (2^0) * 0 = 2016101010 = (2^5) * 1 + (2^4) * 0 + (2^3) * 1 + (2^2) * 0 + (2^1) * 1 + (2^0) * 0 = 424. 다음 10진수를 2진수로 변환해보세요. ( 각 수를 2로 계속 나누어 나머지를 기록하여 거꾸로 읽기 )10 = 0 -> 1 -> 0 -> 1 = 1010 27 = 1 -> 1 -> 0 -> 1 -> 1 = 11011 86 = 0 -> 1 -> 1 -> 0 -> 1 -> 0 - > 1 = 1010110 516 = 0 -> 0 -> 1 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 1 = 10000001005. 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부) (B’C) + (DB)(AB’) +CB’ + (DC’) + (DA’).circ 파일 링크 연결