Question 1

Which of the following statements about a heap is NOT correct?
A) A heap is a form of binary tree.
B) The shape of a heap is very regular.
C) A heap is always completely filled at all levels.
D) In a heap, both the right and left subtrees of any node store elements that are at least as large as the node value.

Accepted Answer

A heap is not always completely filled at all levels, but it is always a complete binary tree.

Question 2

What is the efficiency of removing an element from a red-black tree? A) O(1) B) O(n) C) O(n²) D) O(log (n))

Accepted Answer

The efficiency of removing an element from a red-black tree is O(log (n)). This is because red-black trees are self-balancing binary search trees where the height is logarithmic to the number of nodes, ensuring that the complexity of a remove operation is O(log (n)).

Question 3

What is the efficiency of the heapsort algorithm? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

The answer of What is the efficiency of the heapsort...

Question 4

What is the complexity of adding an element to a heap? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

Adding an element to a heap involves inserting the element at the next available leaf position, and then "bubbling up" the element to its correct position by swapping it with its parent until the heap property is restored. This swapping process takes at most O(log n) time since the height of the heap is at most log n. Therefore, the complexity of adding an element to a heap is O(log n).

Question 5

Which of the following statements about inserting a node into a red-black tree is NOT correct?
A) If it is the first node, it must be black.
B) Color the new node red.
C) If the parent of the new node is red, no other actions are required.
D) A double-red result can occur in a left subtree or a right subtree.

Accepted Answer

The answer of Which of the following statements about inserting...

Question 6

If a min-heap has 14 nodes, what is known for certain when we add a new node?
I every level of the tree will be fully occupied
II the tree does not grow a new level
III the root contains the smallest element
A) I
B) I and II
C) I and III
D) I, II and III

Accepted Answer

The answer of If a min-heap has 14 nodes, what...

Question 7

If a min-heap has 15 nodes, what is known for certain?
I every level of the tree is fully occupied
II at least one level is missing a node
III the root contains the smallest element
A) I
B) II
C) I and III
D) II and III

Accepted Answer

The answer of If a min-heap has 15 nodes, what...

Question 8

When we map a min-heap with n elements to an array with n + 1 elements, we ignore array element 0, and place the root value at which array index?
A) 1
B) 2
C) n
D) n+1

Accepted Answer

The answer of When we map a min-heap with n...

Question 9

A min-heap is a binary tree structure in which missing nodes may only occur where?
A) bottom level, left side
B) bottom level, right side
C) anywhere in the bottom two levels
D) left child of the root

Accepted Answer

In a binary min-heap, all levels must be full except for the bottom level, which may be partially filled. Additionally, if any nodes are missing from the bottom level, they must be on the right side to maintain the complete binary tree property. Therefore, the correct choice is B, bottom level, right side.

Question 10

Insert the missing code in the following code fragment. This fragment is intended to create an iterator to be used to process elements of a tree. TreeSet aTree = . . . String first = iter.next(); String second = iter.next(); A) Iterator iter = aTree.iterator(); B) Iterator iter = aTree.iterator(); C) Iterator iter = String.iterator(); D) Iterator iter = aTree.iterator();

Accepted Answer

To create an iterator for a TreeSet, we need to call the iterator() method of the TreeSet object, which returns an Iterator object. The correct syntax for this is: Iterator iter = aTree.iterator(); Option A is incorrect because there is no need to specify the type parameter `` again. We have already declared that `aTree` is a `TreeSet`. Option C is incorrect because `String` is a class and does not have an `iterator()` method. Option D is incorrect because `aTree` is a `TreeSet`, and we need an iterator that can iterate over `String` elements, not over `TreeSet` elements.

Question 11

If a min-heap has 1024 nodes, what is its height?
A) 10
B) 11
C) 12
D) impossible to determine

Accepted Answer

A min-heap of n nodes has a height of log base 2 of n. 
Therefore, a min-heap of 1024 nodes has a height of log base 2 of 1024, which is 10. However, since the root node is at level 0, we add 1 to get the total height of the tree, which is 11.

Question 12

Which action(s) will invalidate a min-heap so that, it may no longer have the properties of a min-heap?
I change the value of the root node
II remove the lowest level, right-most node
III remove the lowest level, left-most node
A) III
B) I and II
C) II and III
D) I and III

Accepted Answer

The answer of Which action(s) will invalidate a min-heap so...

Question 13

Which of the following statements about inserting a node into a red-black tree is correct?
A) If it is the first node, it must be red.
B) Color the new node black.
C) If the parent of the new node is red, no other actions are required.
D) If a double-red situation results, you must correct this.

Accepted Answer

Whenever a new node is inserted, it must be colored red. However, if the insertion creates a double-red situation (where the parent and child nodes are both red), corrective actions must be taken to maintain the balance of the red-black tree. This may involve recoloring certain nodes, performing rotations, or both. Therefore, choice D is correct. Choices A, B, and C are all incorrect because they do not address how to handle double-red situations.

Question 14

What is the complexity of removing an element from a heap? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

Removing an element from a heap takes O(log n) time complexity because of the heap property which needs to be maintained after the removal of the element. The maximum element needs to be shifted to the root, and then the heap needs to be restructured to maintain the heap property. This restructuring process takes O(log n) time complexity.

Question 15

What is the efficiency of locating an element in a red-black tree? A) O(n) B) O(log (n)) C) O(1) D) O(n²)

Accepted Answer

The efficiency of locating an element in a red-black tree is O(log (n)). This is because red-black trees are balanced and their height is proportional to log (n), where n is the number of elements in the tree. Therefore, the search time for an element is proportional to log (n), making it an efficient data structure for searching and inserting elements.

Question 16

What is the efficiency of adding an element to a red-black tree? A) O(n) B) O(log (n)) C) O(1) D) O(n²)

Accepted Answer

Adding an element to a red-black tree takes O(log (n)) time, as the height of a red-black tree is always balanced, and thus the search, insertion, and deletion operations take logarithmic time.

Question 17

Which of the following is NOT a property of a red-black tree?
A) All nodes must be red or black.
B) All child nodes of a red node must be black.
C) The root is black.
D) All paths from root to null have the name number of nodes.

Accepted Answer

All paths from root to null must have the same number of black nodes, not the same number of nodes in general.

Question 18

How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?
A) log(n)
B) n-1
C) n
D) n+1

Accepted Answer

Title How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?

Question 19

If we have a heap with n elements, and we add another n elements to it, what is the maximum increase of height associated with the binary tree representation of the heap?
A) 1
B) 2
C) n-1
D) n

Accepted Answer

The answer of If we have a heap with n...

Question 20

When we map a min-heap with n elements to an array with n + 1 elements, the right child of the root is stored at which array index?
A) 1
B) 2
C) 3
D) 4

Accepted Answer

The answer of When we map a min-heap with n...

Quiz 17: Tree Structures

Which of the following statements about a heap is NOT correct?

What is the efficiency of removing an element from a red-black tree?

What is the efficiency of the heapsort algorithm?

What is the complexity of adding an element to a heap?

Which of the following statements about inserting a node into a red-black tree is NOT correct?

If a min-heap has 14 nodes, what is known for certain when we add a new node? I every level of the tree will be fully occupied II the tree does not grow a new level III the root contains the smallest element

If a min-heap has 15 nodes, what is known for certain? I every level of the tree is fully occupied II at least one level is missing a node III the root contains the smallest element

When we map a min-heap with n elements to an array with n + 1 elements, we ignore array element 0, and place the root value at which array index?

A min-heap is a binary tree structure in which missing nodes may only occur where?

Insert the missing code in the following code fragment. This fragment is intended to create an iterator to be used to process elements of a tree. TreeSet<String> aTree = . . . String first = iter.next() ; String second = iter.next() ;

If a min-heap has 1024 nodes, what is its height?

Which action(s) will invalidate a min-heap so that, it may no longer have the properties of a min-heap? I change the value of the root node II remove the lowest level, right-most node III remove the lowest level, left-most node

Which of the following statements about inserting a node into a red-black tree is correct?

What is the complexity of removing an element from a heap?

What is the efficiency of locating an element in a red-black tree?

What is the efficiency of adding an element to a red-black tree?

Which of the following is NOT a property of a red-black tree?

How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?

If we have a heap with n elements, and we add another n elements to it, what is the maximum increase of height associated with the binary tree representation of the heap?

When we map a min-heap with n elements to an array with n + 1 elements, the right child of the root is stored at which array index?