Data Structures And Algorithm Techniques Practice Test Practice Tests

Question 1

A min-heap is implemented using an array. Given the array representation `[2, 5, 8, 6, 9, 10, 12]`, what is the value of the left child of the node at index 1 (root is at index 0)? If the child does not exist, write 'None'.

Accepted Answer

6

Question 2

Consider constructing a heap from the array `[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]` using the bottom-up approach. After the initial heap construction, what will be the value of the root node?

Accepted Answer

1

Answer

4

Answer

3

Answer

2

Question 3

A 2-3 tree contains the keys `[1, 2, 3, 4, 5, 6, 7, 8, 9]`. After inserting the key '10', what is the maximum possible height of the tree?

Accepted Answer

3

Question 4

In a Red-Black tree, which of the following properties must always be true?

Accepted Answer

The number of black nodes on every path from the root to a leaf is the same.

Answer

The root node must be red.

Answer

There can be two consecutive red nodes.

Answer

All leaf nodes must be red.

Question 5

In a B-tree of order 3, a node can contain at most 3 keys.

Accepted Answer

True

Answer

False

Question 6

Which of the following are valid properties of a heap?

Answer

It is a complete binary tree.

Answer

The value of each node is greater than or equal to the value of its children (in a max-heap).

Answer

It is a balanced tree.

Answer

The value of each node is less than or equal to the value of its children (in a max-heap).

Question 7

A B-tree of order 4 has a node that is full. How many keys does this node contain?

Accepted Answer

3

Question 8

Consider an array of integers. Describe a transform and conquer approach to find the pair of numbers with the smallest absolute difference. What is the time complexity of your approach, assuming an efficient sorting algorithm is used?

Accepted Answer

Presort the array first. Then, iterate through the sorted array, calculating the absolute difference between consecutive elements. Keep track of the minimum difference found. The time complexity is dominated by the sorting algorithm, typically O(n log n).

Question 9

Which of the following is NOT a major variation of the transform and conquer technique?

Accepted Answer

D. Divide and Merge

Answer

A. Instance Simplification

Answer

B. Representation Change

Answer

C. Problem Reduction

Question 10

Given an unsorted array of integers, explain how presorting can be used to efficiently determine if there are any duplicate elements within a specified range $k$. What is the time complexity of this approach?

Accepted Answer

First, sort the array. Then, iterate through the sorted array, checking if any two consecutive elements are equal and within the range k in the original array. The time complexity is dominated by the sorting algorithm, which is typically O(n log n).

Question 11

What is the worst-case time complexity of the brute-force approach to solve the element uniqueness problem for an array of size $n$?

Accepted Answer

C. $\Theta(n^2)$

Answer

A. $\Theta(n)$

Answer

B. $\Theta(n \log n)$

Answer

D. $\Theta(\log n)$

Question 12

Describe how presorting can be used to find the mode of a list of numbers. What is the time complexity of this approach, assuming an efficient sorting algorithm?

Accepted Answer

Presort the list. Then, scan the sorted list to find the longest run of consecutive equal elements. The time complexity is dominated by the sorting algorithm, typically O(n log n).

Question 13

Which of the following algorithms utilize input enhancement as a space-time tradeoff technique?

Answer

A. Counting Sort

Answer

B. Horspool's Algorithm

Answer

C. Boyer-Moore Algorithm

Answer

D. Merge Sort

Question 14

Explain how comparison counting sort works. What are its time and space complexities for an array of $n$ elements?

Accepted Answer

Comparison counting sort counts the number of elements smaller than each element and uses these counts to place elements in their sorted positions. Its time complexity is $O(n^2)$ and its space complexity is $O(n)$.

Question 15

Given a text 'ABABDABACDABABCABAB' and a pattern 'ABABCABAB', how many shifts will Horspool's algorithm perform before finding the first match?

Accepted Answer

6

Answer

3

Answer

5

Answer

8

Question 16

Construct the shift table for Horspool's algorithm for the pattern 'GCAGAGAG'. Provide the shift values for the characters 'A', 'C', 'G', and 'T'.

Accepted Answer

A: 2, C: 6, G: 1, T: 8

Question 17

What is the worst-case time complexity of Horspool's algorithm when searching for a pattern of length m in a text of length n?

Accepted Answer

O(nm)

Answer

O(n)

Answer

O(m)

Answer

O(n+m)

Question 18

In the Boyer-Moore algorithm, if a mismatch occurs and the bad symbol shift suggests a shift of 3 and the good suffix shift suggests a shift of 5, what shift value will be used?

Accepted Answer

5

Answer

2

Answer

3

Answer

8

Question 19

Consider the text 'ABCDEFG' and the pattern 'EFG'. Using the Boyer-Moore algorithm, what is the shift value determined by the good suffix heuristic after the initial alignment?

Accepted Answer

0

Question 20

Given the frequencies A:5, B:9, C:12, D:13, E:16, F:45, which two symbols would be merged first in Huffman's algorithm?

Accepted Answer

A and B

Answer

C and D

Answer

E and F

Answer

A and F

Data Structures And Algorithm Techniques Practice Test Practice Tests

Practice Tests

Data Structures and Algorithm Techniques Practice Test

Generate Data Structures And Algorithm Techniques Practice Test practice tests with AI