Computer Knowledge

Data Structures and Algorithms

1,518 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

Which of the following is based on the suffix tree data structure and is one of the fastest and most efficient systems available for this task, enabling it to be applied to very long sequences?

  1. Pfam

  2. ProDom

  3. MUMmer

  4. KEGG

  5. TIGRFAMs
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

MUMmer is a bioinformatics software system for sequence alignment. It is based on the suffix tree data structure and is one of the fastest and most efficient systems available for this task, enabling it to be applied to very long sequences.

Multiple choice

The balance of parenthesis in an arithmetic expression can be best checked with which of the following data structures?

  1. Queue

  2. Stack

  3. Tree

  4. Heap

  5. List
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

A stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. It is the best data for checking the balancing of parenthesis.

Multiple choice

____________ function is an operation against the set of records, which returns affinities or patterns that exists among the collection of items.

  1. Sequential pattern

  2. Clustering / segmentation

  3. Association

  4. EIther Sequential pattern or Clustering / segmentation

  5. None of these
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

An association function is an operation against this set of records, which returns affinities or patterns that exists among the collection of items.

Multiple choice time complexity of function

What is time complexity of fun()?

int fun(int n)
{
  int count = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        count = count + 1;
  return count;
}
  1. $\theta(n^2)$
  2. $\theta(nlogn)$
  3. $\theta(n)$
  4. $\theta(logn)^2$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

To solve this question, the user needs to know the concept of time complexity and how to analyze the time complexity of a given algorithm.

The given function fun() contains two nested loops that iterate over the range of n and j respectively. The outer loop runs n times, and the inner loop runs from i to 1. Therefore, the total number of iterations is the sum of the first n positive integers, which is n*(n+1)/2.

Since the number of iterations is proportional to n^2, the time complexity of the function is $\theta(n^2)$.

Therefore, the correct answer is:

The Answer is: A. $\theta(n^2)$

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.