Advanced Data Structures And Algorithmic Efficiency Assessment Practice Tests

Question 1

In a singly linked list with $n$ nodes, if you are tasked with deleting a node at position $k$ (where $1 < k < n$), calculate the total number of operations required to reach the predecessor node, assuming each pointer traversal counts as one operation.

Accepted Answer

$k-2$

Question 2

Consider a doubly linked list of $n$ nodes. If you perform a reverse traversal starting from the tail, what is the asymptotic time complexity in Big-O notation?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 3

For a nearly sorted list of $n$ elements, the number of swaps required by Bubble Sort is always less than or equal to the number of shifts required by Insertion Sort.

Accepted Answer

False

Answer

True

Question 4

Which of the following statements regarding Quick Sort pivot selection are true?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 5

Trace one pass of Radix Sort on the set of numbers {170, 045, 075, 090, 802, 024, 066} using the least significant digit (base 10). What is the value at the front of the '0' bucket after the first pass?

Accepted Answer

170

Question 6

If a Shell Sort uses a gap sequence of $h_k = \lfloor \frac{n}{2^k} \rfloor$, and we have a list of $n=16$ elements, what is the gap size used in the first pass?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 7

In a singly linked list, the time complexity to find the predecessor of a node at position $k$ is $O(k)$.

Accepted Answer

True

Answer

False

Question 8

Given an empty Binary Search Tree, determine the final root node after inserting the sequence of integers: $15, 10, 20, 8, 12, 18, 25$.

Accepted Answer

15

Question 9

Consider a BST containing the set of values $S = \{5, 10, 15, 20, 25\}$. If the tree was constructed by inserting elements in the order $20, 10, 25, 5, 15$, which node is the parent of the node containing $15$?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 10

In a BST, if a node $N$ has two children, the algorithm to delete $N$ involves replacing $N$ with the maximum value from its left subtree to maintain the BST property.

Accepted Answer

True

Answer

False

Question 11

A node $N$ in a BST has a right child but no left child. According to standard deletion algorithms, what is the most efficient way to remove $N$?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 12

A BST is traversed using an Inorder algorithm. If the resulting sequence is $x_1, x_2, x_3, x_4, x_5$ where $x_1 < x_2 < x_3 < x_4 < x_5$, what can be concluded about the order of the output?

Accepted Answer

The output is sorted in ascending order.

Question 13

Given a tree where the Preorder traversal is $A, B, D, E, C$ and the Inorder traversal is $D, B, E, A, C$, which of the following statements are true?

Accepted Answer

Option A

Answer

Option B

Answer

Option C

Answer

Option D

Question 14

Calculate the number of nodes visited in a Breadth-First traversal of a complete binary tree with height $h=3$ (where the root is at level 0).

Accepted Answer

15

Question 15

In a min-heap stored in a zero-indexed array, if a node is located at index $i$, determine the index of its right child.

Accepted Answer

2i + 2

Answer

2i - 1

Answer

2i + 1

Answer

\frac{i-1}{2}

Question 16

Consider a min-heap represented by the array $[2, 5, 12, 7, 6, 22, 14]$. If the value $3$ is inserted, calculate the final array state after the heapify process restores the min-heap property.

Accepted Answer

[2, 3, 12, 5, 6, 22, 14, 7]

Question 17

Searching for an arbitrary value $x$ in a min-heap of size $n$ has a worst-case time complexity of $O(\log n)$.

Accepted Answer

False

Answer

True

Question 18

When performing Quick Sort on an array, if the chosen pivot is consistently the smallest element in the sub-array, what is the resulting time complexity?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n \log n)

Answer

O(\log n)

Question 19

Which of the following statements regarding sorting algorithm efficiency are correct?

Answer

Merge Sort maintains a stable sort order.

Answer

Quick Sort is always faster than Merge Sort regardless of pivot selection.

Answer

Shell Sort improves upon Insertion Sort by reducing the number of swaps for distant elements.

Answer

Bubble Sort has a best-case time complexity of O(n \log n).

Question 20

Trace one pass of Radix Sort on the set of numbers $\{170, 045, 075\}$ using the least significant digit (base 10). What is the order of the numbers after this first pass?

Accepted Answer

170, 045, 075

Advanced Data Structures And Algorithmic Efficiency Assessment Practice Tests

Practice Tests

Advanced Data Structures and Algorithmic Efficiency Assessment

Generate Advanced Data Structures And Algorithmic Efficiency Assessment practice tests with AI