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 running time of algorithm

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

A. A(n)= Ω W(n) B. A(n)= O W(n) C. A(n)= Ѳ W(n) D. A(n)= o W(n)
  1. A(n) = $\omega$ W(n)
  2. A(n) = $O$ W(n)
  3. A(n) = $\theta$ W(n)

  4. A(n) = o W(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

By definition, the worst-case running time W(n) is the upper bound for any input, including the average case. Therefore, A(n) is always O(W(n)).

Multiple choice running time of algorithm

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

  1. A(n) = $\Omega$ W(n)
  2. A(n) = $O$ W(n)
  3. A(n) = $\Theta$ W(n)

  4. A(n) = o W(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Average-case running time $A(n)$ is bounded above by the worst-case running time $W(n)$ for all inputs of size $n$, because the average value of a set cannot exceed its maximum. Therefore, $A(n) = O(W(n))$ always holds. The other options are false because the average case can be asymptotically strictly smaller than the worst case.

Multiple choice

What is time complexity for the following function?

public void printAllPossibleOrderedPairs ( int[] arrayOfItems)
{  
   for (int firstItem : arrayOfItems)
   { 
       for (int secondItem : arrayOfItems)
       {
           int[] orderedPair = new int[] { firstItem, secondItem};
           system.out.print( Arrays.toString(orderedPair));
       }
   }
}
  1. $O (n)$
  2. $O (n logn)$
  3. $O (n^2)$
  4. $O (logn)^2$
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

The function contains two nested loops, each iterating over the entire array of size $n$. This requires $n \times n = n^2$ operations, leading to a quadratic time complexity of $O(n^2)$. Distractors represent linear, logarithmic, or linearithmic complexities.

Multiple choice time complexity of function

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)
{
    if (n <= 1) return n;
    return 2*fun1(n-1);
}

int fun2(int n)
{
    if (n <= 1) return n;
    return fun2(n-1) + fun2(n-1);
}
  1. $O(2^n)$ for both fun1() and fun2()
  2. $O(n)$ for fun1() and $O(2^n)$ for fun2()
  3. $O(2^n)$ for fun1() and $O(n)$ for fun2()
  4. $O(n)$ for both fun1() and fun2()
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

To solve this question, the user needs to know how to determine the time complexity of recursive functions based on the recurrence relation.

Let's analyze the time complexity of each function:

  • fun1(n): This function has a recurrence relation of T(n) = T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with T(n-2) and so on, we get T(n) = T(n-k) + kc. When the base case is reached, we have T(n-k) = 1, so T(n) = k + c. Since k is proportional to n, the time complexity of fun1(n) is O(n).

  • fun2(n): This function has a recurrence relation of T(n) = 2T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with 2T(n-2), 4T(n-3), and so on, we get T(n) = 2^n * T(0) + c * (2^n - 1). Since T(0) = 1, the time complexity of fun2(n) is O(2^n).

Therefore, the answer is:

The Answer is: B. O(n) for fun1() and O(2^n) for fun2().

Multiple choice

What is not true about insertion sort?

  1. Exhibits the worst case performance when the initial array is sorted in reverse order.

  2. Worst case and average case performance is Ο(n2)

  3. Can be compared to the way a card player arranges his card from a card deck.

  4. None of the above!
Reveal answer Fill a bubble to check yourself
D Correct answer
Multiple choice binary search

For a binary search algorithm to work, it is necessary that the array (list) must be

  1. sorted

  2. unsorted

  3. in a heap

  4. popped out of stack
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

The correct answer is A. sorted. For a binary search algorithm to work correctly, the array (or list) must be sorted in ascending or descending order. This allows the algorithm to efficiently divide the search space in half at each step, reducing the number of elements to be searched. If the array is unsorted, the binary search algorithm may not produce the correct results.

Multiple choice

What is the worst case run-time complexity of binary search algorithm?
  1. $Ο(n^2)$
  2. $O(log_2n)$
  3. $O(n logn)$
  4. $O(log logn)$
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Binary search repeatedly halves the search interval, resulting in a worst-case time complexity of $O(\log_2 n)$. Distractors like $O(n^2)$ and $O(n \log n)$ represent much slower, non-logarithmic algorithms, whereas $O(\log \log n)$ is too fast.

Multiple choice

Recursion uses more memory space than iteration because

  1. It uses stack instead of queue.

  2. Every recursive call has to be stored.

  3. Both 1 & 2 are true.

  4. None of the above are true.
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Recursion requires the system to store the state of each function call on the call stack until the base case is reached, consuming memory proportional to the recursion depth.

Multiple choice business mathematics and statistics introduction to index number introduction to index numbers index numbers applied statistics

In multilevel indexes, primary index created for its first level is classified as

  1. zero level of multilevel index.

  2. third level of multilevel index.

  3. second level of multilevel index.

  4. first level of multilevel index.
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

In multilevel indexes, primary index is created for its first level  is classified as second level of multilevel index.