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

Consider the following C functions: int f1 (int n) { If(n == 0 | |n == 1) return n; else return(2*f1(n-1) + 3* f1(n-2)); } int f2 (int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i<=n; i++) { X[i] = Y[i-1] + Z [i-2]; Y[i] = 2*X [i]; Z[i] = 3*X[i]; } Return X[n]; }

The running time of f1 (n) and f2 (n) are
  1. $\odot$(n) and $\odot$(n)
  2. $\odot$(2n) and $\odot$(n)
  3. $\odot$(n) and $\odot$(2n)
  4. $\odot$(2n) and $\odot$ (2n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

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. }

On which of the following contents of Y and x does the program fail?

  1. Y is [1 2 3 4 5 6 7 8 9 10] and x <10

  2. Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

  3. Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

  4. Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

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 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