Deck 22: Binary Trees, Avl Trees, and Priority Queues

Question 1

A binary tree traversal method that visits the root first,and then recursively traverses the left and right subtrees is called

A) top down traversal
B) priority order traversal
C) preorder traversal
D) postorder traversal

Answer 1

C

Question 2

A binary tree traversal method that recursively traverses the left subtree,then visits the root,then traverses the right subtree is called

A) root-centric traversal
B) priority order traversal
C) postorder traversal
D) inorder traversal

Answer 2

D

Question 3

A binary tree with height 1 must have

A) exactly two nodes
B) two or three nodes
C) exactly three nodes
D) one or two nodes

Answer 3

B

Question 4

A binary tree with no root

A) must have only one node
B) must have exactly two nodes
C) must be empty
D) None of the above

Question 5

In a binary tree,

A) there must be at most one node with no predecessor
B) there may be at most two nodes with no predecessor
C) there may be any number of nodes with no predecessor
D) there must be exactly one node with no predecessor

Question 6

An AVL tree is

A) a binary search tree in which the heights of the subtrees at each node differ by at most one
B) a binary tree in which the left and right subtree have heights that differ by at most one
C) a priority queue with a balance condition
D) a binary tree in which each child is greater than its parent

Question 7

A binary tree stores items that have a natural order in such a way that at each node X,all items stored in the left subtree of X are less than the item stored at X,and all items stored in the right subtree are greater than the item stored at X.Such a binary tree is called

A) an ordered binary tree
B) a binary search tree
C) an AVL tree
D) a priority queue

Question 8

Postorder traversal of a binary tree

A) first visits the root,then recursively traverses the left and right subtree
B) recursively traverses the left subtree,then visits the root,then traverses the right subtree
C) recursively traverses the left subtree,then traverses the right subtree,then visits the root
D) visits all the nodes according to their natural order

Question 9

The predecessor of a node in a binary tree is called its

A) progenitor
B) ancestor
C) parent
D) precursor

Question 10

Let X be a node in a binary tree.Any node on the path from X to the root is called

A) a descendant of X
B) an ancestor of X
C) a superior of X
D) a subordinate of X

Question 11

An empty binary tree has height

A) -1
B) 0
C) 1
D) None of the above: the height of an empty binary tree is not defined.

Question 12

Let X be a node in a binary tree.Any node on the path from X to a leaf is called

A) a descendant of X
B) an ancestor of X
C) a relative of X
D) a subordinate of X

Question 13

The successor of a node in a binary tree is called its

A) neighbor
B) child
C) descendant
D) neighbor

Question 14

Let X be a node in a binary tree.The collection of all descendants of X

A) form a binary tree called the subtree rooted at X
B) form the left subtre of X
C) form the right subtree of X
D) None of the above

Question 15

A binary tree with just one node has height

A) -1
B) 0
C) 1
D) None of the above

Question 16

Binary trees have been used

A) in compilers and interpreters to represent expressions
B) in computer hardware to model branching patterns of electronic signals
C) in the Java Collections Framework to internally implement the Vector class
D) None of the above

Question 17

A node in a binary tree that has no children is called

A) a leaf
B) a single node
C) barren
D) a twig

Question 18

A binary tree is a collection of nodes in which

A) each node has at most one predecessor and at most one successor
B) each node has at most one predecessor and exactly two successors
C) each node has at most one predecessor and at most two successors
D) each node has at least one predecessor and at most two successors

Question 19

The length of the longest path from the root of a binary tree to a leaf is called

A) the height of the tree
B) the level of the tree
C) the max-path length of the tree
D) the peak length of the tree

Question 20

Adding all items from a list to a certain data structure and then removing them one at a time yields a sorted version of the list.The data structure is a

A) priority queue
B) binary search tree
C) complete binary tree
D) binary sort tree

Question 21

A binary tree with depth d is complete if

A) each level L < d has 2L nodes
B) every node that is not a leaf has 2 children
C) every node that is not a leaf has 2 children and and all nodes at level d are as far to the left as possible
D) each level L < d has 2L nodes and all nodes at level d are as far to the left as possible

Question 22

Consider the operation of deleting the root of a binary search tree.If the root is a leaf,then

A) the method doing the deletion should throw an exception
B) the root should be replaced with a dummy place-holder node
C) the reference to the root of the tree should be set to null
D) the element stored in the root node should be replaced with null,or with 0.

Question 23

Consider the operation of deleting the root of a binary search tree.If the root has one child,then

A) the root of the subtree should be recursively deleted
B) the element stored in the root node should be replaced with null
C) the reference to the root of the tree should be set to point to the one child
D) the operation should be recursively performed on the one subtree of the root

Question 24

A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0],and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes.If nodes in the same level are stored in left to right order,then the right child of the node stored at A[k] will be stored at

A) A[k/2]
B) A[2k]
C) A[2k+1]
D) A[2k+2]

Question 25

To add a new element X to a binary search tree:

A) if the tree is empty,make X the root of a new tree;otherwise,compare X to the root,if X is less,put it in the left subtree,if it is greater,put in the right subtree
B) First add X in the position of the root.If X is a leaf,or is less than its children,stop.Otherwise,repeatedly swap X with the smaller of its two children until X becomes a leaf,or becomes less than its children.
C) Add X as a leaf,taking care to preserve the completeness of the heap.If X is now the root,or is greater than its parent,stop.Otherwise,repeatedly swap X with its parent until X becomes the root,or becomes greater than its parent.
D) insert X using the same algorithm for insertion in a binary search tree.If the tree remains balanced,stop.Otherwise,execute a rebalancing operation.

Question 26

A sorting algorithm based on a priority queue is

A) quicksort
B) insertion sort
C) bubble sort
D) heap sort

Question 27

When a new item is added to an AVL tree

A) the tree may become unbalanced in only one way
B) the tree may become unbalanced two different ways,but the two imbalances are mirror images of each other
C) the tree may become unbalanced in four different ways,but because of mirror images,there are really only two fundamentally different imbalances
D) the height of one of the subtrees of the root may become three times the height of the other subtree

Question 28

A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0],and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes.If nodes in the same level are stored in left to right order,then the left child of the node stored at A[k] will be stored at

A) A[k/2]
B) A[2k]
C) A[2k+1]
D) A[2k+2]

Question 29

A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0],and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes.If nodes in the same level are stored in left to right order,then the parent of the node stored at A[k] will be stored at

A) A[(k-1)/2]
B) A[k-1]
C) A[2k+1]
D) A[k/2]

Question 30

A priority queue is

A) a binary search tree in which the heights of the subtrees at each node differ by at most one
B) is an AVL tree in which the root is the minimum element
C) is a binary search tree that stores elements according to their natural order
D) is a collection that allows elements to be added,but only allows the minimum element to be removed

Question 31

A complete binary tree with N nodes has depth approximately equal to

A) 2N
B) log N
C) N2
D) N

Question 32

The level of a node X in a binary tree

A) is the length of a shortest path from X to a leaf
B) is the length of a longest path from X to a leaf
C) is the length of the path from the root to X
D) is one more than the level of a child of X

Question 33

Consider the operation of deleting the root of a binary search tree.If the root has two children,then

A) the root node should be removed,then the least node in the right subtree should be deleted and used to replace the root
B) the rood node should be removed,and the deepest rightmost leaf should be used to replace the root
C) the rood node should be removed,the deepest rightmost leaf should be used to replace the root,and then a sift down should be performed to take the root replacement to its proper place
D) the operation should be recursively performed on the two subtrees of the root.

Question 34

Traversing a binary search tree in inorder

A) yields the same sequence as a postorder traversal
B) yields a sequence in which the minimum element is at the approximate midpoint of the sequence
C) will yield a sorted sequence
D) is more efficient than traversing the tree in preorder

Question 35

To find the minimum node in a binary search tree

A) you should start at the root,and then keep passing from each node to its left child until you come to a node with no left child
B) you should start at the root,and then keep passing from each node to its right child until you come to a node with no right child
C) you should look at the root of the binary tree
D) you need to examine every node,and then pick the one with the least value

Question 36

To add a new element X to a heap:

A) if the tree is empty,make X the root of a new tree;otherwise,compare X to the root,if X is less,put it in the left subtree,if it is greater,put in the right subtree
B) First add X in the position of the root.If X is a leaf,or is less than its children,stop.Otherwise,repeatedly swap X with the smaller of its two children until X becomes a leaf,or becomes less than its children.
C) Add X as a leaf,taking care to preserve the completeness of the heap.If X is now the root,or is greater than its parent,stop.Otherwise,repeatedly swap X with its parent until X becomes the root,or becomes greater than its parent.
D) insert X using the same algorithm for insertion in a binary search tree.If the tree remains balanced,stop.Otherwise,execute a rebalancing operation.

Question 37

A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0],and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes.If nodes in the same level are stored in left to right order,then the node stored at A[k] will be a leaf if and only if

A) 2k+1 ≥ N
B) 2k+1 > N
C) k/2 > N
D) None of the above

Question 38

The order condition that characterizes a heap states that

A) at each node X,any element stored in a child of X must be greater than the element stored at X
B) at each node X,any element stored in a left child of X must be less than the element stored at X,and any element stored in right child must be greater than the element stored at X
C) an inorder traversal of the heap's binary tree must yield a sorted sequence
D) None of the above

Question 39

To find the minimum element stored in a heap

A) you should start at the root,and then keep passing from each node to its left child until you come to a node with no left child
B) you should start at the root,and then keep passing from each node to its right child until you come to a node with no right child
C) you should look at the root of the binary tree
D) you need to examine every node,and then pick the one with the least value

Question 40

The depth of a binary tree

A) is the length of the longest path from the root to a leaf
B) is the length of the shortest path from the root to a leaf
C) is the total number of leaves in the tree
D) is the depth of one of the subtrees plus one

Question 41

A ternary tree is like a binary tree,except each node may have up to three successors.Write a TNode class that can be used to represent a ternary tree.Define a notion of preorder and postorder traversal for ternary trees,and write methods void postorder(TNode tree)and void preorder(TNode tree)that implements your notion of those traversals.

Question 42

Assuming a Node class
class Node
{
int element;
Node left,right;
Node(int el,Node left,Node right){
element = el;
this.left = left;
this.right = right;
}
}
Write a method int numberLeaves(Node tree)that returns the number of leaves in the binary tree whose root is tree.

Question 43

Assuming a Node class
class Node
{
int element;
Node left,right;
Node(int el,Node left,Node right){
element = el;
this.left = left;
this.right = right;
}
}
Write a method int depth(Node tree)that returns the length of the longest path that begins at the node tree and ends at any leaf of the binary tree.

Question 44

Assuming a Node class
class Node
{
int element;
Node left,right;
Node(int el,Node left,Node right){
element = el;
this.left = left;
this.right = right;
}
}
Write a method int size(Node tree)that returns the number of nodes in the binary tree whose root is tree.

Question 45

The heap sort method has a worst case complexity function that is in

A) O(log n)
B) O(n.
C) O(n2.
D) O(n log n.