Core Data Structures And Algorithm Fundamentals Practice Tests

Question 1

Consider a sorted linked list implemented with the `List342` class. If the list contains the elements [2, 4, 6, 8, 10], what is the minimum number of comparisons required to insert the element 5 using the `insert` operation?

Accepted Answer

3

Answer

2

Answer

4

Answer

5

Question 2

Explain the key difference between an Abstract Data Type (ADT) and a data structure, emphasizing how ADTs enforce behavior.

Accepted Answer

An ADT defines behavior and rules, focusing on what operations are allowed and their guarantees, while a data structure is a specific way of organizing and storing data in memory. ADTs enforce behavior by limiting what you're allowed to do, not by exposing how it's done.

Question 3

You are given two sorted linked lists, list1 and list2, containing integers. You need to merge list2 into list1 using the `merge` operation of the `List342` class. List1 contains [1, 3, 5, 7] and List2 contains [2, 4, 6]. After the merge operation, what will be the order of elements in List1?

Accepted Answer

[1, 2, 3, 4, 5, 6, 7]

Answer

[1, 3, 5, 7, 2, 4, 6]

Answer

[2, 4, 6, 1, 3, 5, 7]

Answer

[7, 6, 5, 4, 3, 2, 1]

Question 4

In a Stack ADT, the `pop()` operation removes the most recently added element, following the LIFO (Last-In, First-Out) principle.

Accepted Answer

True

Answer

False

Question 5

A queue is implemented using a `std::list`. If the queue contains the elements [10, 20, 30] where 10 is the front element, what will be the content of the queue after calling `dequeue()` twice?

Accepted Answer

[30]

Answer

[10, 20, 30]

Answer

[20, 30]

Answer

[]

Question 6

Explain the purpose of container adapters in C++ with respect to ADTs, and provide an example.

Accepted Answer

Container adapters in C++ wrap another container and expose only ADT operations, guaranteeing ADT behavior (LIFO/FIFO) and preventing misuse of the underlying container. An example is `std::stack`, which adapts containers like `std::vector` or `std::list` to provide stack functionality.

Question 7

Which of the following operations are typically associated with the Queue ADT?

Answer

push(x)

Answer

enqueue(x)

Answer

pop()

Answer

dequeue()

Answer

top()

Answer

front()

Answer

empty()

Question 8

What is the result of the following recursive function call `factorial(5)` where `factorial(n)` is defined as:

```
function factorial(n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
```

Accepted Answer

D. 120

Answer

A. 1

Answer

B. 5

Answer

C. 24

Question 9

Consider the following recursive function to calculate the nth Fibonacci number:

```
function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}
```

What is the time complexity of this recursive implementation?

Accepted Answer

C. O(2^n)

Answer

A. O(n)

Answer

B. O(n log n)

Answer

D. O(log n)

Question 10

Which of the following tree traversal methods visits the root node *after* visiting both the left and right subtrees?

Accepted Answer

C. Post-order

Answer

A. Pre-order

Answer

B. In-order

Answer

D. Level-order

Question 11

A sorted array contains the values [2, 5, 7, 8, 11, 12]. Using binary search, how many comparisons are needed to find the value 12?

Accepted Answer

3

Question 12

In a Binary Search Tree (BST), the value of every node in the left subtree is greater than the value of the root node.

Accepted Answer

True

Answer

False

Question 13

Which of the following are advantages of using balanced Binary Search Trees (BSTs) compared to unbalanced BSTs?

Answer

A. Guaranteed O(log n) time complexity for search operations.

Answer

B. Guaranteed O(log n) time complexity for insertion operations.

Answer

C. Prevents worst-case scenarios where the BST degenerates into a linked list.

Answer

D. Simpler implementation compared to unbalanced BSTs.

Question 14

Given an array $[5, 1, 4, 2, 8]$, how many swaps are performed in the first pass of Bubble Sort?

Accepted Answer

4

Answer

2

Answer

3

Answer

5

Question 15

What is the time complexity of Insertion Sort in the best-case scenario, expressed in Big O notation?

Accepted Answer

O(n)

Question 16

Which of the following sorting algorithms has a guaranteed time complexity of $O(n \log n)$ in all cases (best, average, and worst)?

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Insertion Sort

Answer

Selection Sort

Question 17

What is the space complexity of Merge Sort for arrays, expressed in Big O notation?

Accepted Answer

O(n)

Question 18

In Merge Sort, what is the smallest subproblem that is solved recursively?

Accepted Answer

An array with only one element

Answer

An empty array

Answer

An array with two elements

Answer

An array with three elements

Question 19

Merge sort on linked lists requires $O(n)$ auxiliary space due to the need for creating new nodes during the merge operation.

Accepted Answer

True

Answer

False

Question 20

Which of the following steps are involved in Merge Sort when applied to a linked list?

Answer

Splitting the list into two halves using slow and fast pointers

Answer

Recursively sorting both halves

Answer

Merging the two sorted halves

Answer

Swapping adjacent nodes

Core Data Structures And Algorithm Fundamentals Practice Tests

Practice Tests

Core Data Structures and Algorithm Fundamentals

Generate Core Data Structures And Algorithm Fundamentals practice tests with AI