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

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

  1. full: (REAR+l) mod n == FRONT empty: REAR ==FRONT

  2. full:(REAR+l)mod n == FRONT empty: (FRONT+l)mod n==REAR

  3. full: REAR == FRONT empty: (REAR+l) mod n == FRONT

  4. full:(FRONT+ l)mod n == REAR empty: REAR == FRONT
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

A list of n stings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

  1. O(nlogn)

  2. O(n2 logn)

  3. O(n2 +logn)

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

The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n2 logn)

Multiple choice

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) The appropriate expressions for the two boxes B1 and B2 are
  1. B1: (1 + height (n$\rightarrow$right)) B2: (1 - max (h1, h2))
  2. B1: (height (n$\rightarrow$right)) B2: (1 - max (h1, h2))
  3. B1: height (n$\rightarrow$right) B2: max (h1, h2)
  4. B1: (1 + height (n$\rightarrow$right)) B2: max (h1, h2)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered from 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from

  1. (j mod v) *k to (j mod v) * k + (k - 1)

  2. (j mod v) to (j mod v) + (k - 1)

  3. (j mod k) to (j mod k) + (v - 1)

  4. (j mod k) * v to (j mod k) * v + (v - 1)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Set number in the cache = (main memory block number) MOD number of sets in the cache As the lines in the set are placed in sequence, we can have the lines from 0 to K – 1 in the set. Number of sets = v Main memory block number = j First line = (j mod v); last line = (j mod v) + (k – 1)

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

A certain computation generates two arrays a and b such that a [i] = f (i) for 0 $\le$ i < n and b [i] = g (a [i]) for 0 $\le$ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialised to zero. The array a is shared by the two processes. The structures of the processes are shown below.

Process X; 
Process Y;
private i;
private i;
for (i = 0; i &lt; n; i + +) {                            
  for (i = 0; i &lt; n; i + +) {
         a [i] = f (i);
         EntryY (R, S);
         ExitX (R, S); 
         b [i] = g (a [i]);
    }
}

Which one of the following represents the CORRECT implementations of ExitX and EntryY?

 
  1. ExitX (R, S) {
   P (R) ;
   V (S) ;
}
EntryY (R, S) {
   P (S);
   V (R);
}

  2. ExitX(R, S) { 
  V (R); 
  V (S);
}
EntryY (R, S) {
  P (R);
  P (S);
}

  3. ExitX (R, S) {
  P (S);
  V (R);
}
EntryY (R, S) {
  V (S);
   P (R);
}

  4. ExitX (R, S) {
  V (R);
  P (S);
}
EntryY (R, S) {
  V (S);
  P (R);
}
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Process X produces a[i] and signals completion. Process Y consumes a[i] and must wait for X to produce it. ExitX signals completion by V(R) and V(S) (signal both semaphores). EntryY waits for X's signal by P(R) then P(S) (wait on both semaphores). This ensures Y only accesses a[i] after X has written it. Option B implements this correctly - V(R), V(S) in ExitX and P(R), P(S) in EntryY ensures proper synchronization.

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