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

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.

  1. f(int Y[10], int x) {
  2. int u, j, k;
  3. i = 0; j = 9;
  4. do {
  5. k = (i + j)/2;
  6. if (Y[k] ! = x) && (i < j);
  7. } while ((Y[k] ! = x) && (i < j));
  8. if (Y[k] == x) print f(“x is in the array”);
  9. else print f(“x is not in the array”);
  10. }

The correction needed in the program to make it work properly is

  1. Change line 6 to : if Y[k] < x) i = k + 1; else j = k - 1;

  2. Change line 6 to : if Y[k] < x) i = k - 1; else j = k + 1;

  3. Change line 6 to : if Y[k] <= x) i = k; else j = k;

  4. Change line 7 to:} while ((Y[K] ==x) && (i < j));

Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

  1. X[i, j] = X[i - 1, j] vX [i, j - ai]

  2. X[i, j] = X[i - 1, j] vX [i, 1, j - ai]
  3. X[i, j] = X[i - 1, j] $\land$X [i, j - ai]
  4. X[i, j] = X[i - 1, j] $\land$X [i-1, j - ai]
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?

struct node {
  int value;
  struct node * next;
};
Void rearrange struct node * list {
  struct node * p, * q;
  int temp;
  if (!list || !!list - &gt; next) return;
  p = list; | q = list - &gt; next;
  while q {
    temp = p - &gt; value;
    p - &gt; value = q - &gt; value;
    q - &gt; value = temp;
    p = q - &gt; next;
    q = p ? p - &gt; next : 0;
  }
}

  1. 1,2,3, 4,5, 6, 7

  2. 2,1, 4,3, 6,5, 7

  3. 1,3, 2,5, 4, 7, 6

  4. 2, 3, 4,5, 6, 7,1
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field and the file organisation is unspanned. The file is stored in a file system with block size 1024 bytes and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file and a multi-level index scheme is used to store the secondary index, then the numbers of first-level and second-level blocks in the multi-level index are respectively

  1. 8 and 0

  2. 128 and 6

  3. 256 and 4

  4. 512 and 5
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i, j] = l(i,j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(I, j)?

  1. All elements L should be initialized to 0 for the values of l(i, j) to be properly computed.

  2. The values of l(i, j) may be computed in a row major order or column major order of L(M,N).

  3. The values of l(i, j) cannot be computed in either row major order or column major order of L(M,N).

  4. L[p, q] needs to be computed before L[r, s] if either p<r or q<s.

Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Multiple choice

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below: l (i, j) = 0, if either i=0 or j=0 = expr1, if i,j>0 and X [i-1] = Y [j 1] = expr2, if i,j>0 and X [i-1] = Y [j 1]

Which one of the following options is correct?

  1. expr1 = l (i − 1, j) + 1

  2. expr1 = l (i, j − 1)

  3. expr2 = max (l (i − 1, j), l (i,j - 1))

  4. expr2 = max (l (i − 1, j − 1), l (i, j))
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

The following key values are inserted into a B+ - tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+ - tree is initially empty. 10, 3, 6, 8, 4, 2, 1 The maximum number of times leaf nodes would get split as a result of these insertions is

  1. 2

  2. 3

  3. 4

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