Trees

Question 1

A queue operates under a WHAT policy?

Answer 1

FIFO - First In, First Out

Question 2

You may only read or remove the item at the WHAT of a queue?

Answer 2

Front/Head

Question 3

You may only add an item at the WHAT of a queue?

Answer 3

Back/Tail

Question 4

List the methods of Java’s Queue interface.

Answer 4

add(E item), element(), offer(E e), peek(), poll(), remove()

Question 5

The element() method of Java’s Queue interface removes the head of the queue: true or false?

Answer 5

False; it retrieves, but does NOT remove the head of the queue.

Question 6

You want to insert an item into a queue. Which one of Java’s Queue interface methods do you use?

Answer 6

Either add(E e) or offer(E e). The only difference is in the return type.

Question 7

You want to retrieve, but NOT remove, the first element in a queue. Which one of Java’s Queue interface methods do you use?

Answer 7

Either E element() or E peek(). The only difference is in the return type.

Question 8

You want to retrieve AND remove the first element in a queue. Which one of Java’s Queue interface methods do you use?

Answer 8

Either E remove() or E poll(). The only difference is in the return type.

Question 9

A Deque allows insertion and deletion at both the head and tail: true or false?

Answer 9

True. That’s why it’s called a DOUBLY ENDED Queue.

Question 10

Number of edges in a tree = ?

Answer 10

Number of vertices - 1.

Question 11

Define “minimally connected”.

Answer 11

The tree will become disconnected if any edge is removed.

Question 12

Define “maximally acyclic”.

Answer 12

If an edge is added, the tree will contain a cycle.

Question 13

The child of a child of a given node is referred to as?

Answer 13

A “descendant”.

Question 14

A node that has no children is called?

Answer 14

A “leaf”.

Question 15

What is the height of a node?

Answer 15

The distance of a node from its deepest descendant.

Question 16

A node has three children. What is the node’s degree?

Answer 16

Three. A node’s degree is defined as the number of children that node has. A leaf has a degree of 0.

Question 17

In a binary tree, each node has no more than how many children?

Answer 17

Two.

Question 18

Put these three in order for a preorder traversal: visit, traverse left, traverse right.

Answer 18

Visit, traverse left, traverse right.

Question 19

Put these three in order for a postorder traversal: visit, traverse left, traverse right.

Answer 19

Traverse left, traverse right, visit.

Question 20

Put these three in order for an inorder traversal: visit, traverse left, traverse right.

Answer 20

Traverse left, visit, traverse right.

Question 21

List the types of tree traversal.

Answer 21

Preorder, inorder, postorder, and level-order.

Question 22

If a tree is empty, what is its height?

Answer 22

-1

Question 23

If a tree is NOT empty, what is its height?

Answer 23

1 + max(height of left subtree, height of right subtree)

Question 24

What is the definition of a set?

Answer 24

A collection of elements with NO duplicates.

Question 25

What is the binary search tree property?

Answer 25

For any node X, every key
in the left subtree of X is less than X’s key, and every key in the right subtree of X is greater than X’s key.

Question 26

The binary search tree representation of a set is unique: true or false?

Answer 26

False. The BST representation of a set is NOT unique.

Question 27

A(n) ___ traversal of a binary search tree visits the nodes in sorted order.

Answer 27

Inorder.

Question 28

Balanced trees have a height of?

Answer 28

O(log n)