Question 1

The preorder traversal algorithm traverses the left subtree, visits the root node, and traverses the right subtree.

Accepted Answer

A) True 
 B)False

Question 2

When a linked binary search tree is instantiated, the self.root variable is set to self .

Accepted Answer

A) True 
 B)False

Question 3

Which of the following carries out the actions specified by a sentence?

Accepted Answer

A)   interpreter
B)   parser
C)   recognizer
D)   compilerE) C) and D)
F) A) and D)

Question 4

The number of comparisons required for a removal in an array-based heap is at most log2 n , so the pop operation is O(log n ).

Accepted Answer

A) True 
 B)False

Question 5

The peek method in a heap implementation returns the bottom most item in the heap.

Accepted Answer

A) True 
 B)False

Question 6

The maximum amount of work that it takes to access a given node in a full binary tree is O( N ).

Accepted Answer

A) True 
 B)False

Question 7

With trees, each item, including the first and last, have a distinct successor.

Accepted Answer

A) True 
 B)False

Question 8

Which type of binary tree traversal visits the tree's root node, the left subtree and then the right subtree?

Accepted Answer

A)   postorder traversal
B)   inorder traversal
C)   preorder traversal
D)   unordered traversalE) A) and B)
F) B) and C)

Question 9

When the shape of a BST approaches that of a perfectly balanced binary tree, what is the worst case performance characteristic of searches and insertions?

Accepted Answer

A)   O(log n ) 
B)   O n 
C)   O( n ) 
D)   O(log2 n ) E) None of the above
F) C) and D)

Question 10

What is the height of a full binary tree with 63 nodes?

Accepted Answer

A)   5
B)   8
C)   6
D)   7E) A) and B)
F) B) and C)

Question 11

Which of the following is true about a max-heap?

Accepted Answer

A)   each node is less than or equal to its children
B)   the largest nodes are nearer to the root
C)   the largest items are in the leaves
D)   the smallest item is in the root nodeE) C) and D)
F) All of the above

Question 12

What type of traversal occurs in the binary search trees __iter__ method?

Accepted Answer

A)   sequential
B)   postorder
C)   preorder
D)   inorderE) B) and D)
F) B) and C)

Question 13

An access, an insertion, or a removal of a node in vine-like tree with N nodes and a height of N - 1 would be linear in the worst case.

Accepted Answer

A) True 
 B)False

Question 14

The inorder traversal algorithm visits a tree's root node and then traverses the left subtree and the right subtree in a similar manner.

Accepted Answer

A) True 
 B)False

Question 15

In the following code for the __init__ method for the linked binary search tree, what is the missing code? def __init__(self, sourceCollection = None) :

AbstractCollection.__init__(sourceCollection)

Accepted Answer

A)   self.root = sourceCollection
B)   self.root = None
C)   sourceCollection.__init__(AbstractCollection) 
D)   self.leaf = rootE) A) and D)
F) A) and C)

Question 16

An expression tree is never empty.

Accepted Answer

A) True 
 B)False

Question 17

Which type of binary tree traversal traverses the left subtree, visits, the root node, and traverses the right subtree?

Accepted Answer

A)   postorder traversal
B)   inorder traversal
C)   preorder traversal
D)   unordered traversalE) All of the above
F) B) and D)

Question 18

Which of the following is true about a binary tree?

Accepted Answer

A)   each node has at most two children
B)   each node has only one child
C)   child nodes can have multiple parents
D)   the root node must have only one childE) None of the above
F) All of the above

Question 19

What operator causes the __contains__ method to run in the binary search tree implementation?

Accepted Answer

A)   =
B)   is
C)   +
D)   inE) A) and D)
F) None of the above

Question 20

Which of the following is not a part of a grammar?

Accepted Answer

A)   vocabulary
B)   semantic rules
C)   syntax rules
D)   method rulesE) B) and C)
F) None of the above

Exam 10: Trees

What type of traversal occurs in the binary search trees __iter__ method?

Correct AnswerverifiedShow Answer

The maximum amount of work that it takes to access a given node in a full binary tree is O( N ).

Correct AnswerverifiedShow Answer

The number of comparisons required for a removal in an array-based heap is at most log2 n , so the pop operation is O(log n ).

Correct AnswerverifiedShow Answer

When a linked binary search tree is instantiated, the self.root variable is set to self .

Correct AnswerverifiedShow Answer

With trees, each item, including the first and last, have a distinct successor.

Correct AnswerverifiedShow Answer

The inorder traversal algorithm visits a tree's root node and then traverses the left subtree and the right subtree in a similar manner.

Correct AnswerverifiedShow Answer

Which of the following is true about a binary tree?

Correct AnswerverifiedShow Answer

When the shape of a BST approaches that of a perfectly balanced binary tree, what is the worst case performance characteristic of searches and insertions?

Correct AnswerverifiedShow Answer

Which type of binary tree traversal traverses the left subtree, visits, the root node, and traverses the right subtree?

Correct AnswerverifiedShow Answer

In the following code for the __init__ method for the linked binary search tree, what is the missing code? def __init__(self, sourceCollection = None) : < missing code > AbstractCollection.__init__(sourceCollection)

Correct AnswerverifiedShow Answer

An access, an insertion, or a removal of a node in vine-like tree with N nodes and a height of N - 1 would be linear in the worst case.

Correct AnswerverifiedShow Answer

Which of the following is not a part of a grammar?

Correct AnswerverifiedShow Answer

The peek method in a heap implementation returns the bottom most item in the heap.

Correct AnswerverifiedShow Answer

Which of the following is true about a max-heap?

Correct AnswerverifiedShow Answer

Which of the following carries out the actions specified by a sentence?

Correct AnswerverifiedShow Answer

An expression tree is never empty.

Correct AnswerverifiedShow Answer

What operator causes the __contains__ method to run in the binary search tree implementation?

Correct AnswerverifiedShow Answer

What is the height of a full binary tree with 63 nodes?

Correct AnswerverifiedShow Answer

Which type of binary tree traversal visits the tree's root node, the left subtree and then the right subtree?

Correct AnswerverifiedShow Answer

The preorder traversal algorithm traverses the left subtree, visits the root node, and traverses the right subtree.

Correct AnswerverifiedShow Answer

What type of traversal occurs in the binary search trees iter method?

Correct Answer
verified

Correct Answer
verified

The number of comparisons required for a removal in an array-based heap is at most log₂ n , so the pop operation is O(log n ).

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

In the following code for the init method for the linked binary search tree, what is the missing code? def init(self, sourceCollection = None) : < missing code > AbstractCollection.init(sourceCollection)

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

What operator causes the contains method to run in the binary search tree implementation?

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified