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

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e. of type A $\rightarrow$$\in$ Î and A $\rightarrow$ a) to parse a string with n tokens?

  1. n/2

  2. n-1

  3. 2n-1

  4. 2n
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

2 × (4) − 1 = 7 reductions $\Rightarrow$2n − 1 reductions are required. [Note: Unit production is given as A $\rightarrow$ a, it was typo] Above reductions are not in reverse of RMD but when they are reduced in bottom-up parsing, we will get same number of reductions.

Multiple choice

The number of elements that can be sorted in $Θ(\log n)$ time using heap sort is
  1. $\Theta(1)$
  2. $\Theta(\sqrt{\log} n)$
  3. $\Theta(\frac{\log n}{\log \log n})$
  4. $\Theta(\log n)$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

After constructing a max-heap in the heap sort, the time to extract maximum element and then heapifying the heap takes $\Theta$(log n) time by which we could say that $\Theta$ (log n) time is required to correctly place an element in sorted array. If $\Theta$ (logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is $\Theta$ (1).

Multiple choice

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h1 is:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

  4. 1.7 ns
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h2 is:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

  4. 1.7 ns
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional array of size 512×512 with elements that occupy 8-bytes each. Consider the following two C code segments, P1 and P2. P1: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x +=A[i] [j]; } } P2: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x +=A[j] [i]; } } P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2 .

The value of the ratio $\dfrac{M_1}{M_2}$

  1. 0
  2. $\dfrac{1}{16}$
  3. $\dfrac{1}{8}$

  4. 16
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set. I. Deletion of the smallest element II. Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose?

  1. A heap can be used but not a balanced binary search tree

  2. A balanced binary search tree can be used but not a heap

  3. Both balanced binary search tree and heap can be used

  4. Neither balanced binary search tree nor heap can be used
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Both the tasks can be performed by both the data structures but heap is a data structure where to perform these function every element has to be checked so  O (n) complexity. But the balance binary search tree is efficient data structure since at every decision it selects one of its sub tree to no. of elements to be checked are reduced by a factor of / 1 2 every time. $\dfrac{n}{2!} = x$ x = log n

Multiple choice

Let S be a stack of size n $\ge$1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

  1. n(X + Y)

  2. 3Y + 2X

  3. n(X + Y) - X

  4. Y + 2X
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Multiple choice

Consider the function f defined below.

struct item {
  int data;
  struct item * next;
};
int f(struct item * p) {
  return ((p == NULL) || (p - &gt; next == NULL) ||
    ((p - &gt; data &lt;= p - &gt; next - &gt; data) &amp; amp; &amp; amp; f(p - &gt; next)));
}

For a given linked list p, the function f returns 1 if and only if

  1. the list is empty or has exactly one element

  2. the elements in the list are sorted in non-decreasing order of data value

  3. the elements in the list are sorted in non-increasing order of data value

  4. not all elements in the list have the same data value
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

Consider the following C-function in which a [n] and b [m] are two sorted integer arrays and c [n + m] be another integer array.

void xyz(int a[], int b[], int c[]) {
  int i, j, k;
  i = j = k = 0;
  while ((i &lt; n) &amp;&amp; (j &lt; m))
    if (a[i] &lt; b[j]) c[k++] = a[i++];
    else c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?

  1. only (i)

  2. only (ii)

  3. either (i) or (ii) but not both

  4. neither (i) nor (ii)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation