Deck 11: Trees

Question 1

Which of the following ADT is value-oriented?

A)list
B)sorted list
C)stack
D)queue
E)binary tree

Answer 1

B

Question 2

The ADT stack manages an association between data items and the ______ of the data items.

A)names
B)values
C)sizes
D)positions

Answer 2

D

Question 3

A node directly below node n in a tree is called a ______ of node n.

A)root
B)leaf
C)parent
D)child

Answer 3

D

Question 4

The node that is directly above node n in a tree is called the ______ of node n.

A)root
B)leaf
C)parent
D)child

Question 5

A node on the path from the root to node n is a(n)______ of node n.

A)ancestor
B)descendant
C)subtree
D)leaf

Question 6

Which of the following is NOT a property of a complete binary tree of height h?

A)all nodes at level h - 2 and above have two children each
B)when a node at level h - 1 has children,all nodes to its left at the same level have two children each
C)when a node at level h - 1 has one child,it is a left child
D)all leaves are at level h

Question 7

A ______ of height h is full down to level h - 1,with level h filled in from left to right.

A)full binary tree
B)complete binary tree
C)balanced binary tree
D)general tree

Question 8

A subtree of node n is a subtree rooted at ______.

A)node n
B)the parent of node n
C)a child of node n
D)a sibling of node n

Question 9

Each node in a tree has ______.

A)exactly one parent
B)at most one parent
C)exactly two parents
D)at most two parents

Question 10

A node of a tree is called a(n)______.

A)edge
B)root
C)branch
D)vertex

Question 11

In ______,the left and right subtrees of any node have heights that differ by at most 1.

A)all trees
B)all binary tress
C)n-ary trees
D)balanced binary trees

Question 12

A descendant of node n is a node on a path from node n to ______.

A)the root
B)a leaf
C)a sibling of node n
D)a child of node n

Question 13

Each node in a binary tree has ______.

A)exactly one child
B)at most one child
C)exactly two children
D)at most two children

Question 14

The operations of the ADT sorted list are based upon the ______ of data items.

A)names
B)values
C)sizes
D)positions

Question 15

Which of the following ADT is position-oriented?

A)binary tree
B)sorted list
C)table
D)priority queue

Question 16

The ______ of a tree is the number of nodes on the longest path from the root to a leaf.

A)height
B)length
C)width
D)age

Question 17

The ______ is a position-oriented ADT that is not linear.

A)sorted list
B)queue
C)binary tree
D)list

Question 18

The lines between the nodes of a tree are called ______.

A)branches
B)edges
C)arches
D)subtrees

Question 19

In a ______ of height h,all nodes that are at a level less than h have two children each.

A)general tree
B)binary tree
C)full binary tree
D)complete binary tree

Question 20

In a tree,the children of the same parent are called ______.

A)leafs
B)siblings
C)roots
D)contemporaries

Question 21

The maximum height of a binary tree of n nodes is ______.

A)n
B)n / 2
C)(n / 2)- 2
D)log2(n + 1)

Question 22

The traversal of a binary tree is ______.

A)O(n)
B)O(1)
C)O(n²)
D)O(log2ⁿ)

Question 23

The ADT queue is value-oriented.

Question 24

A binary tree cannot be empty.

Question 25

The maximum number of comparisons for a retrieval operation in a binary search tree is the ______.

A)length of the tree
B)height of the tree
C)number of nodes in the tree
D)number of leaves in the tree

Question 26

The ADT binary search tree is value-oriented.

Question 27

Inorder traversal visits a node before it traverses either of its subtrees.

Question 28

All trees are hierarchical in nature.

Question 29

The minimum height of a binary tree of n nodes is ______.

A)n
B)n / 2
C)(n / 2)- 2
D)log2(n + 1)

Question 30

The array based representation of a binary tree requires a complete binary tree.

Question 31

In a general tree,the leftmost child of a node is called the ______.

A)left child
B)oldest child
C)youngest child
D)binary child

Question 32

A data element within a record is called a ______.

A)field
B)tree
C)collection
D)key

Question 33

In an array based representation of a complete binary tree,which of the following represents the parent of node tree[i]?

A)tree[i-2]
B)tree[(i-1)/2]
C)tree[2*i-1]
D)tree[2*i-2]

Question 34

In an array based representation of a complete binary tree,which of the following represents the right child of node tree[i]?

A)tree[i+2]
B)tree[i-2]
C)tree[2*i+1]
D)tree[2*i+2]

Question 35

In an array based representation of a complete binary tree,which of the following represents the left child of node tree[i]?

A)tree[i+2]
B)tree[i-2]
C)tree[2*i+1]
D)tree[2*i+2]

Question 36

The root of a tree has one parent.

Question 37

A full binary tree with height 4 has ______ nodes.

A)7
B)8
C)15
D)31

Question 38

The root of a tree is at level 0.

Question 39

A complete binary tree of n nodes has a height of log2(n + 1).

Question 40

The ADT binary tree is position-oriented.

Question 41

In a binary tree,what is the maximum number of siblings a node may have? What is the minimum?

Question 42

Define the root of a tree.

Question 43

Define the left child of node n in a binary tree.

Question 44

What are the three methods that a class that implements the Iterator interface must provide?

Question 45

In preorder traversal,what is the order of visiting a node and its subtrees?

Question 46

What is a subtree?

Question 47

List three position-oriented ADTs.

Question 48

Briefly describe an algorithm for finding the largest key value in a binary search tree.

Question 49

What is a search key?

Question 50

What are the three properties of each node n in a binary search tree?

Question 51

In an array-based representation of a binary tree,what kind of information is stored in a free list?

Question 52

What are the three general categories of data management operations?

Question 53

Suppose a binary tree has 3 nodes.The root node is A,and A has a left child B.B has a right child C.Write the inorder,preorder and postorder traversals of this tree.

Question 54

In a binary tree,if a node does not have a parent,can it have any children?

Question 55

In postorder traversal,what is the order of visiting a node and its subtrees?

Question 56

Suppose we insert these values into a binary search tree: 1,7,2,5,8,3,6.Give a postorder traversal of this tree.

Question 57

Define a leaf of a tree.

Question 58

In inorder traversal,what is the order of visiting a node and its subtrees?

Question 59

Define an n-ary tree.

Question 60

What are the characteristics of a binary tree?