파이썬 자료구조와 알고리즘 for Beginner 8장 연습문제 정답

8장 이진 트리 연습문제 정답

 

1. 트리에 대한 설명 1~4에 알맞은 용어를 다음 중에서 고르시오.

트리의 맨 위를 '1'라고 한다. '1'를 '2'0으로 두고 나뭇잎에 해당하는 아래로 내려올수록 '2'이 1씩 증가한다. 트리에서 각 위치를 '3'라고 한다. 각 '3'는 '4'로 연결되어 있다.

• '1' = 루트
• '2' = 레벨
• '3' = 노드
• '4' = 에지

 

2. 이진 트리를 모두 고르시오.

• 정답 : 1, 2, 3, 4

 

3. 다음 중 1~3 설명에 해당하는 것을 고르시오.

• 1 모든 노드가 오른쪽이나 왼쪽으로 연결된 트리다. -> 편향 이진 트리
• 2 모든 노드가 꽉 차 있는 상태의 트리다. -> 포화 이진 트리
• 3 번호 부여 순서로 노드가 배치된다. 노드가 일부 비어 있어도 된다. -> 완전 이진 트리

 

4. 이진 트리의 노드 구조에 대한 설명 중 가장 거리가 먼 것은?

1. 데이터와 링크 2개로 구성되어 있다.
2. 링크는 왼쪽 링크와 오른쪽 링크 두 가지다.
3. 필요한 경우 링크를 3개 이상 구성할 수도 있다.
4. 보통 왼쪽 링크, 데이터, 오른쪽 링크의 순서로 구성한다.

• 정답 : 3

 

5. 이진 트리의 순회는 전위, 중위, 후위 세 가지가 있다. 다음은 어떤 순회에 대한 설명인가?

1. 왼쪽 서브 트리로 이동
2. 오른쪽 서브 트리로 이동
3. 현재 노드 데이터 처리

• 정답 : 후위 순회

 

 

6. 다음 이진 트리를 전위 순회, 중위 순회, 후위 순회한 결과를 각각 쓰시오

• 전위 순회 : 화사 -> 솔라 -> 휘인 -> 쯔위 -> 문별 -> 선미
• 중위 순회 : 휘인 -> 솔라 -> 쯔위 -> 화사 -> 선미 -> 문별
• 후위 순회 : 휘인 -> 쯔위 -> 솔라 -> 선미 -> 문별 -> 화사

 

 

7. 이진 탐색 트리의 특징과 가장 거리가 먼 것은?

1. 왼쪽 서브 트리는 루트 노드보다 모두 작은 값을 가진다.
2. 오른쪽 서브 트리는 루트 노드보다 모두 작은 값을 가진다.
3. 각 서브 트리도 1, 2의 특징을 갖는다.
4. 모든 노드 값은 필요하다면 중복될 수도 있다.

• 정답 : 2, 3, 4

 

 

8. 이진 탐색 트리의 삭제 동작 중에서 재귀함수를 사용해야 하는 경우는?

1. 리프 노드를 삭제하는 경우
2. 자식 노드가 하나(왼쪽)인 노드를 삭제하는 경우
3. 자식 노드가 하나(오른쪽)인 노드를 삭제하는 경우
4. 자식 노드가 둘 있는 노드를 삭제하는 경우

• 정답 : 4

 

9. 다음은 이진 탐색 트리에서 반복적으로 자리를 찾아가는 코드다. 1~3에 적합한 코드를 다음에서 고르시오.

name = 6
node = TreeNode()
node.data = name

current = root
while True:
	if 빈칸1 :
    	if current.left == None :
        	current.left = node
            break
    	빈칸2
    else :
    	if current.right == None :
        	current.right = node
            break
        빈칸3

• 정답 : 빈칸1 = name < current.data
• 빈칸2 = current = current.left
• 빈칸3 = current = current.right

 

10. 이진 탐색 트리의 삽입 작통 코드의 일부다. 빈칸1에 알맞은 코드는?

node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in 빈칸1 :
	node = TreeNode()
    	node.data = name
    생략...

• 정답 : nameAry[1:]

 

 

 

 

 

---

https://www.hanbit.co.kr/store/books/look.php?p_code=B4186876690

IT CookBook, 파이썬 자료구조와 알고리즘 for Beginner