Computer Knowledge

Data Structures and Algorithms

1,256 Questions

Data Structures and Algorithms form the core of computer science, focusing on arrays, linked lists, trees, and sorting mechanisms. These concepts are essential for solving complex computational problems efficiently. Test takers preparing for technical and administrative IT exams will find these questions highly relevant.

Array OperationsLinked List ApplicationsSorting AlgorithmsTree Data StructuresMultilevel IndexingAlgorithm Time Complexity

Data Structures and Algorithms Questions

Multiple choice

Recursive procedures are implemented by

  1. queues

  2. stacks

  3. strings

  4. none of these
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Recursive procedures rely on the call stack to store return addresses, local variables, and parameters for each active function call.

Multiple choice

The following sequence of operations is performed on a stack push (1), push (2), pop, push(1), push(2), pop, pop, pop, push(2), pop. The sequence of the popped out values is

  1. 2, 2, 1, 1, 2

  2. 2, 2, 1, 2, 2

  3. 2, 1, 2, 2, 1

  4. 2, 1, 2, 2, 2
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Sequence: push(1) [1], push(2) [1,2], pop [1](val 2), push(1) [1,1], push(2) [1,1,2], pop [1,1](val 2), pop [1](val 1), pop [](val 1), push(2) [2], pop [](val 2). Popped values: 2, 2, 1, 1, 2.

Multiple choice

A priority queue Q is used to implement a stack S that stores characters. PUSH (C) is implemented as INSERT (Q, C, K), where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN (Q). For a sequence of operations, the keys chosen are in

  1. non-increasing order

  2. non-decreasing order

  3. strictly increasing order

  4. strictly decreasing order
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

To simulate a stack (LIFO) using a priority queue (which returns the smallest key), we need to assign keys such that the most recently added item has the smallest key. Therefore, keys must be strictly decreasing.

Multiple choice

Bubble sort's average time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Bubble sort uses nested loops to compare adjacent elements, leading to an average time complexity of O(n^2).

Multiple choice

Insertion sort's average time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Insertion sort has an average time complexity of O(n^2) because, on average, each element must be compared and shifted against half of the already sorted elements.

Multiple choice

Merge sort's average time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Merge sort uses a divide and conquer approach, splitting the array into halves recursively and merging them, resulting in a consistent O(n log n) complexity.

Multiple choice

Quick sort's average time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Quick sort's average performance is O(n log n) because the partitioning process effectively divides the array into roughly equal halves on average.

Multiple choice

Selection sort's worst-case time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Selection sort always performs a nested loop to find the minimum element, resulting in O(n^2) complexity regardless of the initial order of elements.

Multiple choice

Bubble sort's worst-case time complexity is

  1. O(n2)

  2. O(nlogn)

  3. O(logn)

  4. O(n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Bubble sort compares adjacent elements in nested loops, leading to O(n^2) in the worst case when the array is sorted in reverse order.