the right child of N the subtree\'s rightmost node the subtree\'s leftmost node

ID: 3760188 • Letter: T

Question

the right child of N

the subtree's rightmost node

the subtree's leftmost node

the left child of N

QUESTION 2

A null child is

a child that does not exist but will be created next.

one of the two potential children of a leaf node where an insertion will be made.

a non-existent left child of a node with a right child (or vice versa).

a child with no children of its own.

QUESTION 3

In a red-black tree, adding an entry to a red-black tree results in

a new red node

a node split

a new black node

a rotation

QUESTION 4

Which of the following properties is true for a red-black tree?

the root is black

every path from the root to a leaf contains the same number of black nodes

any children of a red node are black

all of the above

QUESTION 5

Which of the following is not a red-black rule?

Every path from a root to a leaf, or to a null child, must contain the same number of black nodes.

The root is always black.

If a node is black, its children must be red.

All three are valid rules.

QUESTION 6

When adding an entry to a binary search tree, when does the search ends?

when the item is found

at a leaf if the entry is not already in the tree

both a & b

none of the above

QUESTION 7

The maximum possible height of a binary search tree with n nodes is

n - 1

log n

n - 2

QUESTION 8

Suppose T is a binary tree with 14 nodes, what is the minimum possible depth of T?

QUESTION 9

A binary search tree with 14 nodes. What is the maximum tree height?

QUESTION 10

If the numbers 5, 13, and 23 are added to an empty red black tree in that order, in order to maintain the red black tree property, you need a(n)

no rotation

right rotation

left rotation

both left and right rotation

QUESTION 11

Assuming larger keys on the right, the partition is

the left element in the right subarray.

the element between the left and right subarrays.

the key value of the left element in the right subarray

the key value of the element between the left and right subarrays.

QUESTION 12

The worst case situation for quick sort is when

the array elements are initially completely random

each partition has one empty subarray

each partition is of equal size

the pivot element cannot be determined

QUESTION 13

In a _____ traversal of a binary tree, you visit the root of a binary tree between visiting the nodes o the root¡¯s subtrees.

postorder

preorder

level order

inorder

QUESTION 14

The worst-case performance for shell sort is

O(n2.5)

O(n2)

O(n1.5)

O(n3)

QUESTION 15

Radix sort

distributes digits into buckets

merges the array back into place

is suitable for any application

partitions the array

QUESTION 16

If a node x is the inorder successor of node y then node x must appear in y's _____ subtree.

right

left

middle

all of the above

QUESTION 17

The quick sort algorithm uses a ________ to divide the array into two pieces.

pivot

divider

mid-point

break point

QUESTION 18

A binary tree like this: what is the inorder predecessor of node 35

QUESTION 19

In quick sort, the majority of the work occurs

before the recursive calls

in creating the partition

both a & b

none of the above

QUESTION 20

If the numbers 13, 5, 23, 34 are added to an empty red black tree in that order. At the end of the execution, the root of the tree is

QUESTION 21

A red black tree like this: has black height of

QUESTION 22

The worst-case performance of quick sort for n items is

O(n log n)

O(log n)

O(n2)

O(n)

QUESTION 23

In quick sort, having every partition form sub arrays of roughly the same size

does not affect the performance

is optimal

slows the processing down

creates more work because of repeated comparisons

QUESTION 24

A binary search tree like this: How many leaves in this tree?

QUESTION 25

When quick sort partitions arrays as small as 10 entries, the best strategy is to

use quick sort down to arrays as small as two entries

use shell sort on the small array

use insertion sort on the small array

use merge sort on the small array

QUESTION 26

The worst-case performance of quick sort for n items is

O(n)

O(log n)

O(n2)

O(n log n)

QUESTION 27

The ideal situation in quick sort is when the pivot moves

to the beginning of the array

to the end of the array

to a random place in the array

to the center of the array

QUESTION 28

Which sort does not use comparisons?

merge sort

shell sort

quick sort

radix sort

QUESTION 29

Shell sort works by

iteratively searching for the smallest entry in subarrays of equally spaced entries

using insertion sort on subarrays of equal size consecutive entries

iteratively searching for the smallest entry in subarrays of equal size consecutive entries

using insertion sort on subarrays of equally spaced entries

QUESTION 30

Which of the following statements about binary search tree is not true?

Every binary search tree has at most two children.

Every binary search tree has at least one node.

Every binary search tree has at most one root node.

Every non-root node has exactly one parent.

QUESTION 31

Consider this binary search tree: Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

QUESTION 32

The elements in a tree are called

indexes

search keys

entries

nodes

QUESTION 33

If the numbers 23, 16, and 34 are added to an empty red black tree in that order, in order to rebalance it, you need a(n)

left rotation

left and then right rotation

no rotation

right rotation

QUESTION 34

which of the following statements is not true?

Radix sort sorts any types of data in O(n).

Radix sort sorts numbers from the least significant digit (the rightmost digit) to the most significant digit(the leftmost digit).

Radix sort implements bucket sort.

Radix sort is faster than merge sort in worst case.

QUESTION 35

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

The pivot could be the 7, but it is not the 9.

Neither the 7 nor the 9 is the pivot.

The pivot could be either the 7 or the 9.

The pivot is not the 7, but it could be the 9.

QUESTION 36

In quick sort, the partition step takes at most ______ comparisons for n items.

QUESTION 37

A binary tree like this: what is the inorder successor of node 35

QUESTION 38

In the quick sort algorithm, using the median-of-three pivot selection scheme

avoids worst-case performance for arrays that are already sorted

avoids worst-case performance for arrays that are nearly sorted

does not avoid worst-case for randomly distributed arrays

all of the above

QUESTION 39

A node is balanced if its two subtrees differ by no more than

none of the above

QUESTION 40

Which of the following statements about Shellsort is true?

Shellsort is a stable sorting algorithm.

The choice of the interval sequence has nothing to do with the time complexity of executing Shellsort.

Shellsort is an in-place sorting algorithm.

The idea came from sorting sea shells.

the right child of N

the subtree's rightmost node

the subtree's leftmost node

the left child of N

Explanation / Answer

Question 1:

Answer: the subtree's rightmost node.

In the binary search tree, the left subtree of a node has keys less than or equal to the value of its root node and right subtree of a node has keys greater than or equal to the value of its root node.

Question 2:

Answer: a non-existent left child of a node with a right child (or vice versa).

A null child of the BST is no-leaf node. It consists of left child but not right child (or vice versa).

Question 3:

Answer: a new red node

In a red-black tree, adding an entry to a red-black tree results in a new red node. If the tree is not empty, the adding a node to the tree result in a new node of red color.

Question 4:

Answer: All of the above

The following properties are true for a red-black tree:

Question 5:

Answer: All three are valid rules.

The following properties are the red-black rule:

Question 6:

Answer: both a & b

The search in the binary search tree ends when the item is found or ends at a leaf if the entry is not already in the tree.

Question 7:

Answer: n-1.

The maximum possible height of a binary search tree with n nodes is n-1. If the binary search tree is fully skewed, the maximum possible height of a binary search tree with n nodes is n-1.

Question 8:

Answer: 3.

The minimum depth is the number of nodes along the shortest path from root node to the nearest leaf node. If the binary tree T has 14 nodes, then the minimum possible depth of T is 3.

Question 9:

Answer: 13

A binary search tree with 14 nodes. Then the maximum tree height n- 1 = 14-1 =13

Question 10:

Answer: right rotation

If the numbers 5, 13, and 23 are added to an empty red black tree in that order, in order to maintain the red black tree property, then a(n) is right rotation

Question 11:

Answer: the left element in the right subarray.

Assuming larger keys on the right, the partition is the left element in the right subarray of the tree.

Question 12:

Answer: the pivot element cannot be determined.

The worst-case situation for quick sort is when the pivot element cannot be determined.

Question 13:

Answer: inorder

The inorder traversal of the binary tree, visit the root of a binary tree between visiting the nodes of the subtrees. This traversal visits root node between visiting the left node and right node of the subtrees.

Question 14:

Answer: O(n1.5)

The worst-case performance for shell sort is O(n1.5).

Question 15:

Answer: distributes digits into buckets

The Radix sort uses bucket-sort as the stable sorting algorithm for the array and distributes digits into buckets.

Question 16:

Answer: left.

The inorder traversal first visits the left node of the tree then visits the root node and then right node of the tree. If a node x is the inorder successor of node y then node x must appear in y's left subtree.

Question 17:

Answer: pivot.

The quick sort algorithm uses a pivot to divide the array into two pieces. Based on the pivot value, the quick sort algorithm divides the array into subarrays to sort the elements of the order.

Question 18: The tree image is not provided

Question 19:

Answer: both a & b

In quick sort, the majority of the work occurs in creating the partition of the array before the recursive calls.

Question 20:

Answer: 13.

If the numbers 13, 5, 23, 34 are added to an empty red black tree in that order. At the end of the execution, the root of the tree is 13.

Question 21: The tree image is not provided

Question 22:

Answer: O(n2)

The worst-case performance of quick sort for n items is O(n2).

Question 23:

Answer: is optimal

In quick sort, having every partition form sub arrays of roughly the same size is optimal.

Question 24: The tree image is not provided

Question 25:

Answer: use quick sort down to arrays as small as two entries.

When quick sort partitions arrays as small as 10 entries, the best strategy is to use quick sort down to arrays as small as two entries.

Question 26:

Answer: O(n2)

The worst-case performance of quick sort for n items is O(n2).

Question 27:

Answer: to the center of the array.

The ideal situation in quick sort is when the pivot moves to the center of the array.

Question 28:

Answer: radix sort.

The radix sort does not use comparisons to sort the elements of the array.

Question 29:

Answer: using insertion sort on subarrays of equal size consecutive entries.

Question 30:

Answer: Every binary search tree has at least one node.

Question 31: The tree image is not provided

Question 32:

Answer: nodes

The elements in a tree are called nodes.

Question 33:

Answer: no rotation.

If the numbers 23, 16, and 34 are added to an empty red black tree in that order, in order to rebalance it, the a(n) is no rotation.

Question 34:

Answer: Radix sort implements bucket sort. Radix sort is faster than merge sort in worst case.

The Radix sort does not implement bucket sort and it is not faster than merge sort in worst case. The Radix sort sorts any types of data in O(n). It sorts numbers from the least significant digit (the rightmost digit) to the most significant digit (the leftmost digit).

Question 35:

Answer: The pivot could be either the 7 or the 9.

Here, the pivot can be selected at the middle of the array. Therefore, the pivot could be either the 7 or the 9.

Question 36:

Answer: n

In quick sort, the partition step takes at most n comparisons for n items.

Question 37: The tree image is not provided.

Question 38:

Answer: avoids worst-case performance for arrays that are already sorted.

The median-of-three pivot selection scheme selects leftmost, middle and rightmost element and sorted them to the left partition, pivot and right partition.

Question 39:

Answer: A node is balanced if its two subtrees differ by no more than 1.

Question 40:

Answer: The following statements about Shellsort is true:

Shellsort is an in-place sorting algorithm.

The idea came from sorting sea shells.

Navigate

the right answer. (45 marks I Choose 1. The C-preprocessors are specified with a

the right. Which of the following values would be closest to the correlatión toP

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

the right child of N the subtree\'s rightmost node the subtree\'s leftmost node

Question

Explanation / Answer

Related Questions

Navigate