Final Exam Questions

Question 1

What will be the minimum height of a binary search tree (BST) that contains 3 different data items? Note that the height of a tree at the root node is 0

Answer 1

1

Question 1

What are the max number of nodes in a balanced binary tree?

Answer 1

n = 2^(h+1) - 1

Question 2

To remove the root from a heap structure, you need to start a process by first placing ______ to the place of the root and re-heap it to maintain the heap property

Answer 2

The last node of the heap

Question 3

What would be the best case time complexity in finding the presence of an edge between two vertices of a graph when the graph is implemented using adjacency list?

Answer 3

O(1)

Question 4

Which probing methods in hashing might fail to insert a next data item in the table, if the load factor is set to be 70%?
-Separate chaining
-Quadratic Probing
-Double Hashing
-None of the above will fail

Answer 4

Quadratic Probing
-can fail if the table becomes too full because it may not find an empty slot due to clustering

Question 5

What is the best case time complexity of adding an edge to a graph with n vertices that is implemented using adjacency matrix ?

Answer 5

O(1)

Question 6

In finding the Fibonacci number recursively, at an index n, what will be the worst case time complexity of the process? Why?

Answer 6

It is proportional to n^2
-The function “branches out” at each step, like a tree splitting into two parts at every level, with overlapping (repeated) calculations.

Question 7

Two algorithms with the same time complexity may not be equally efficient [True or False]

Answer 7

True
-time complexity doesn’t take into account hidden overhead, input sizes, and constant factors

Question 8

The best-case time complexity of a sequentially searched chain of n number of linked nodes is O(1) [True or False]

Answer 8

True
-Only one comparison is required to find the element

Question 9

Binary search is impractical when performed on an unsorted data collection [True or False]

Answer 9

True
-Binary search relies on the data being sorted to function properly
-The algorithm works by repeatedly dividing the search interval in half, which assumes the elements are in order.

Question 10

The worst-case time complexity in a binary searched sorted-data-collection of size n is O(logn) [True or False]

Answer 10

True
-The worst-case occurs when the search continues until the collection is reduced to a single element, requiring the maximum number of divisions (which is proportional to the height of the tree Log2(n))

Question 11

The max number of Max-Heap trees that can be formed with 3 nodes with unequal entries is:

Answer 11

2
-largest node stays the at the root meanwhile the two smaller nodes can be switched from left and right

Question 12

For an n-node Binary Search Tree (BST), what will be the worst-case time complexity in removing an entry from the tree?

Answer 12

O(n)
-If the tree is unbalanced

Question 13

A Red-black tree is preferred over an AVL tree when the application requires frequent insertion and deletion operations [True or False]

Answer 13

True
-less strict balancing requirements which lead to fewer rotations

Question 14

The root of a red black tree is always black [True or False]

Answer 14

True

Question 15

In ensuring the balance of a red black tree, when a newly inserted node has a red parent and a black ‘uncle’, the rotation must be done before recolouring [True or False]

Answer 15

True

Question 16

What are the conditions for a rotation in a Red-Black tree?

Answer 16

-The newly inserted node is red
-Its parent is also red
-The “uncle” of the newly inserted node (the sibling of its parent) is black.

Question 17

A red-black tree is a self balancing binary search tree [True or False]

Answer 17

True

Question 18

Which of the following trees is used to implement the sorting algorithm in TreeSet<>class in Java?
(a) Red and Black Tree
(b) Minheap Tree
(c) Maxheap Tree
(d) AVL Tree
(e) None of the above

Answer 18

Red and Black Tree
-it guarantees O(logn) time complexity for common operations like insertion, deletion, and search.

Question 19

Which of the following built-in classes in Java stores elements in their natural order?
(a) HashSet<>
(b) LinkedHashSet<>
(c) ArrayList<>
(d) Vector<>
(e) None of the above

Answer 19

None
-use a TreeSet<>

Question 20

If open addressing with linear probing resolves collisions with a maximum of 50% load
factor, what will be minimum required size of the hash table, when 15 different search
keys need to be inserted into an initially empty table?

Answer 20

31

Question 21

O(nlogn) is equivalent to O(n) [True or False]

Answer 21

False
-O(nlogn) grows a lot faster than O(n)

Question 22

O(5n3 + n log n + 106) is equivalent to O(n3) [True or False]

Answer 22

True
-n^3 is a lot faster than nlogn and 106 -the expression is the same as O(n^3)

Question 23

O(n2 + n log n) is equivalent to O(n2) [True or False]

Answer 23

True
-n^2 is a lot faster than nlogn

Question 24

O(n/22) is equivalent to O(n) [True or False]

Answer 24

True -both grow linearly

Question 25

Which of the following trees can be used to realize the boarding of airplane-passengers with special need who get priority in boarding the airplane (a) AVL tree (b) Red-Black tree (c) Binary Search Tree (d) None of the above.

Answer 25

(d) None of the above -The trees do not give priority to nodes

Question 26

If you need to insert a data item into a max heap-tree, what will be the worst-case time- complexity?

Answer 26

O(logn) -the inserted element is swapped up until the root (the height)

Question 27

Let’s assume that we’ve accommodated 6 hash-keys in a hash table of size 13. If the table uses a load factor of 50%, and open addressing with linear probing method is used to resolve collisions, how many more hash-keys can be inserted into the table before rehashing it?

Answer 27

Already reached max load factor limit of 6 so can't add any more keys

Question 28

Which of the following trees might be an unbalanced and/or a incomplete tree? (a) Binary Search Tree (b) Heap Tree (c) 2-3 Tree (d) 2-4 Tree (e) None of the above

Answer 28

Binary Search Tree -Does not guarantee completeness because there is no requirement for nodes to be filled level by level

Question 29

Given a complete binary search tree, what would be the worst-case time efficiency, in terms of big-Oh, to search for an item from this tree?

Answer 29

O(logn) -The target value is either not present in the tree or located at the lowest level, requiring traversal down the full height

Question 30

Where can you locate the largest element in a Max-Heap tree? (a) It is located amongst the leaf nodes of the tree. (b) It is the rightmost leaf node of the tree. (c) It is the leftmost leaf node of the tree. (d) It is the median of the leaf nodes of the tree. (e) It is the root of the tree.

Answer 30

It is the root of the tree -guaranteed to be greater than or equal to its children

Question 31

What does a Hash Function do?

Answer 31

maps a key with any arbitrary size of data to fixed sized integer data called hash / hash code / hash sum

Question 32

What is a collision?

Answer 32

When a hash function allows more than one search key to map into a single index

Question 33

What makes a good hash function?

Answer 33

-Minimize collisions -Distribute entries uniformly throughout the hash table -Be fast to compute

Question 34

What are the two ways of resolving collisions?

Answer 34

-Use another location in the table -Change the structure of the hash table

Question 35

List the collision handling schemes

Answer 35

-Open addressing -Separate Chaining

Question 36

What is open addressing?

Answer 36

Finding an unused, or open location in the hash table

Question 37

What does the load factor have to be for open addressing with quadratic probing to be successful?

Answer 37

-load factor should be less than 50%

Question 38

Why does probing with open addressing fail?

Answer 38

A hash table may not have a null location -better to increase the size of the hash table