Deck 10: Trees

Question 1

A min-heap is a binary tree in which each node is less than or equal to both of its children.

Answer 1

True

Question 2

A file system is similar to a binary search tree.

Answer 2

False

Question 3

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

Answer 3

False

Question 4

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.

Question 5

The heap sort algorithm builds a heap from a set of data and then repeatedly removes the leaf item and adds it to the end of a list.

Question 6

A grammar in a programming language consists of a vocabulary, syntax rules, and a list of operators.

Question 7

The height of an empty tree is -1.

Question 8

You should use a postorder iteration method for the tree's __iter__ method to enable the user to create a clone of the tree with the same shape as the original.

Question 9

In a tree, an interior node is a node that has no children.

Question 10

In a tree, the root item has no parent item.

Question 11

In the replace method for a binary search tree interface, None is returned if the first argument cannot be found.

Question 12

Because the recursive search algorithm doesn't require a parameter for a tree node, you can define it as a top-level method.

Question 13

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

Question 14

Two trees are considered equal if they contain the same items in the same positions.

Question 15

The level order traversal guides the visits to items from left to right through the levels of the tree, much like reading lines of text in a document.

Question 16

An expression tree is never empty.

Question 17

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

Question 18

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

Question 19

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

Question 20

A parse tree describes the syntactic structure of a sentence in terms of its component parts.

Question 21

Syntax rules specify how sentences in the language should be interpreted.

Question 22

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

A) postorder traversal
B) inorder traversal
C) preorder traversal
D) unordered traversal

Question 23

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 ).

Question 24

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

Question 25

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

A) postorder traversal
B) inorder traversal
C) preorder traversal
D) unordered traversal

Question 26

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

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 node

Question 27

Array-based binary trees are the easiest to define and implement.

Question 28

Which is true about binary search trees?

A) they cannot support logarithmic insertions
B) they can support logarithmic searches
C) they don't work well for sorted collections
D) each node in the right subtree of a given node is less than that node

Question 29

In a tree, which of the following is true?

A) all items have a distinct predecessor and successor
B) each item can have multiple children
C) each item can have multiple parents
D) the root has exactly one parent

Question 30

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

A) postorder traversal
B) inorder traversal
C) preorder traversal
D) unordered traversal

Question 31

Which of the following is described as a node's parent, its parent's parent, and so on up to the root?

A) descendant
B) path
C) depth
D) ancestor

Question 32

What is the formula for determining the number of nodes in a full binary tree where H is the height of the tree?

A) 2 ^{H - 1} + 1
B) 2 ^H + 1
C) 2 ^{H + 1}
D) 2 ^{H + 1} - 1

Question 33

One of the types of symbols used by an EBNF is metasymbols.

Question 34

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

A) 5
B) 8
C) 6
D) 7

Question 35

Which of the following is NOT a common application for a binary tree?

A) heap
B) expression tree
C) search tree
D) stack

Question 36

Which of the following is the topmost node in a tree and does not have a parent?

A) root
B) child
C) leaf
D) interior node

Question 37

What is the number of nodes in a full binary tree with a height of 4?

A) 23
B) 19
C) 31
D) 47

Question 38

Which of the following is true about a binary tree?

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 child

Question 39

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?

A) O(log n )
B) O ⁿ
C) O( n )
D) O(log₂ n )

Question 40

What kind of tree would be useful in analyzing the syntax of a sentence?

A) binary search tree
B) sorting tree
C) parse tree
D) linear tree

Question 41

In the following code for the find method, what is the missing code? def find(self, item):
Def recurse(node):
If node is None:
Return None
Elif item == node.data:
< missing code >
Elif item < node.data:
Return recurse(node.left)
Else:
Return recurse(node.right)
Return recurse(self.root)

A) return node.data
B) return self.data
C) return recurse(node.root)
D) return node.root

Question 42

In the code for the inorder method for a binary search tree, what is the missing code? def inorder(self):
Lyst = list()
Def recurse(node):
If node != None:
< missing code >
Lyst.append(node.data)
Recurse(node.right)
Recurse(self.root)
Return iter(lyst)

A) recurse(node.root)
B) return(node.data)
C) recurse(node.left)
D) return iter(self.root)

Question 43

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

A) interpreter
B) parser
C) recognizer
D) compiler

Question 44

Which traversal type guides visits to items in the tree from left to right through the levels of the tree?

A) levelorder
B) inorder
C) preorder
D) postorder

Question 45

Which symbol type is NOT found in an EBNF?

A) terminal symbols
B) metasymbols
C) hypersymbols
D) nonterminal symbols

Question 46

In the code for the add method in the implementation of a heap, what is the missing code? def add(self, item):
Self.size += 1
Self.heap.append(item)
CurPos = len(self.heap) - 1
While curPos > 0:
Parent = (curPos - 1) // 2
ParentItem = self.heap[parent]
If parentItem <= item:
< missing code >
Else:
Self.heap[curPos] = self.heap[parent]
Self.heap[parent] = item
CurPos = parent

A) curPos += 1
B) break
C) self.heap[ curPos ] = item
D) parent = curpos

Question 47

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

A) sequential
B) postorder
C) preorder
D) inorder

Question 48

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)

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

Question 49

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

A) =
B) is
C) +
D) in

Question 50

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

A) vocabulary
B) semantic rules
C) syntax rules
D) method rules