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

Let A[1,....n] be an array storing a bit (1 or 0) at each location, and f (m) is a function whose time complexity is è(m). Consider the following program fragment written in a C like language:

The complexity of this program fragment is
  1. $\Omega$(n2)
  2. $\Omega$ (nlogn) and O(n2)
  3. $\theta$(n)

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

Here the fragment of code contains for loop which goes from 1 to n. Since due to given conditions m < n. So complexity of code is $\Theta$ 6(n)

Multiple choice

Consider the following C-function:

The space complexity of the above function is foo O and store the values of foo (i),0 <= i < n, as and when they are computed. With this modification, the time complexity for function fooO is significantly reduced. The space complexity of the modified function would be:

  1. O(1)

  2. O(n)

  3. O(n2)

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

Here we store values in foo(i ) only when they are completed then in every recursion we require space to store 1 double. So overall n calls we require 0(n)

Multiple choice

If the strings of the language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?

  1. L is necessarily finite.

  2. L is regular but not necessarily finite.

  3. L is context free but not necessarily regular.

  4. L is recursive but not necessarily context free.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

The strings of a language L can be effectively enumerated means a Turing machine exists for language L which will enumerate all valid strings of the language.If the string is in lexicographic order then TM will accept the string and halt in the final state. But, if the string is not lexicographic order then TM will reject the string and halt in non-final state.Thus, L is recursive language.We can not construct PDA for language L. So, the given language is not context free.

Multiple choice

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* → \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following CANNOT be true?
  1. $L_1$ $\in P$ and $L_2$ is finite
  2. $L_1$ $\in NP$ and $L_2$ $\in P$
  3. $L_1$ is undecidable and $L_2$ is decidable
  4. $L_1$ is recursively enumerable and $L_2$ is recursive
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

We have one to one mapping for all instances of L1 to L2. L1 is given to be undecidable. Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction  

Multiple choice

The top down parsing method is also called

  1. recursive descent parsing

  2. shift reduce parsing

  3. operator precedence parsing

  4. none of the above
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Top-down parsing is also called recursive descent parsing because it recursively expands non-terminals starting from the root. Shift-reduce and operator precedence are bottom-up techniques.

Multiple choice

Handle pruning is the technique used to obtain

  1. canonical derivation sequence

  2. canonical reduction sequence

  3. both (1) and (2) above

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

Handle pruning is used in LR parsing to efficiently find the canonical reduction sequence - the unique reverse of rightmost derivation. It helps identify handles without exploring all possibilities.

Multiple choice

Which one of the following sorting algorithms is using divide and conquer method?

  1. Bubble sort

  2. Selection sort

  3. Quick sort

  4. All of the above
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Quick sort choose one element and divide the list into two. It uses divide and conquer method. A key element is chosen then it is compared and the element is placed in such a way that all smaller elements as compared to key are on one side and larger than key are on other side. Then likewise list is broken into two, again algorithm is applied.

Multiple choice

For height H and root at level 0, how many number of nodes will be there in a binary tree?

  1. 2H+1 - 1

  2. 2H-1

  3. 2H+1 + 1

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

2H+1 - 1, gives total number of nodes present in any binary tree for tree at level 0. 2H gives the total number of nodes at any level. If root is at level zero, 2H+1 will give the same, e.g. at level 3, total no. of nodes will be 8 and total number of nodes at level 2 if root is at level 0, is 7. So this relation works here 2H+1 - 1.