Programming and data structure miscellaneous

Programming and data structure miscellaneous

Easy Questions

Programming & Data Structure

Programming and data structure miscellaneous
  1. Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row– major or column–major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be








  1. View Hint View Answer Discuss in Forum

    Since the matrices are stored in array, there is no dependence of time complexity on row major or column major. Here only the starting address is known & on the basis of indexes the next memory locations are calculated.
    Hence (d) is correct option.

    Correct Option: D

    Since the matrices are stored in array, there is no dependence of time complexity on row major or column major. Here only the starting address is known & on the basis of indexes the next memory locations are calculated.
    Hence (d) is correct option.

  1. A set X can be represented by an array x [n] as follows

    Consider the following algorithm in which x, y and z are Boolean arrays of size n:
      algorithm zzz (x[], y[], z []) {
      int i;
      for (i = 0; i < n; + + i)
       z [i] = (x[i] ^ ∼ y [i] ∨ ( ∼ x [i] ^ y [i])
    }
    The set Z computed by the algorithm is








  1. View Hint View Answer Discuss in Forum

    The condition given in the FOR loop is
    z[i] = {x[i] ∧ ∼ y[i]} ∨ (∼ x[i] ∧ y[i])
    Now, we clearly can see that the condition reflect the XOR operation and in the XOR operation set obtained is (X ∩ Y') ∪ (X' ∩ Y)
    Since, the formula is X ∩ Y' = X' – Y
    Result obtained is (X – Y) ∪ (Y – X)

    Correct Option: D

    The condition given in the FOR loop is
    z[i] = {x[i] ∧ ∼ y[i]} ∨ (∼ x[i] ∧ y[i])
    Now, we clearly can see that the condition reflect the XOR operation and in the XOR operation set obtained is (X ∩ Y') ∪ (X' ∩ Y)
    Since, the formula is X ∩ Y' = X' – Y
    Result obtained is (X – Y) ∪ (Y – X)

  1. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is true about the number of comparisons needed?








  1. View Hint View Answer Discuss in Forum

    One possible way to do this is we select first element as max & also min. Then we compare it with all others. At most this would take 2n comparisons during linear search. But if we use divide & conquer as for merge sort we have.
    T(n) 2T(n / 2) + 2 for n > 2
    T(n) = 3n / 2 – 2
    = 1.5n - 2

    Correct Option: B

    One possible way to do this is we select first element as max & also min. Then we compare it with all others. At most this would take 2n comparisons during linear search. But if we use divide & conquer as for merge sort we have.
    T(n) 2T(n / 2) + 2 for n > 2
    T(n) = 3n / 2 – 2
    = 1.5n - 2

Direction: 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 = k; else j = k;
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.   }

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








  1. View Hint View Answer Discuss in Forum

    The correction in the program is needed as in the above solution we can see that the program cannot work properly.
    Now, when y[k] < x
    Increase 1 to k + 1
    Otherwise, decrease j to k –1
    This will ensure that in the while condition, element at k position will be checked for equality.

    Correct Option: A

    The correction in the program is needed as in the above solution we can see that the program cannot work properly.
    Now, when y[k] < x
    Increase 1 to k + 1
    Otherwise, decrease j to k –1
    This will ensure that in the while condition, element at k position will be checked for equality.

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








  1. View Hint View Answer Discuss in Forum

    We are given that
    i = 0; j = 9;
    k = (i + j)/2
    I iteration
    Let consider x = 4
    Now, k = (0 + 9)/2 = 4
    Therefore, y[4] < x is true
    → i = 4 and j = 9
    II iteration
    As i = 4
    Now, k = (4 + 9) / 2 = 6
    Therefore, y[6] < x is true.
    → i = 6 and j = 9
    III iteration
    As i = 6
    Now, k = (6 + 9) / 2 = 7
    Therefore, y[7] < x is true
    → i = 7 and j = 9
    IV iteration
    As i = 7
    Now, k = (7 + 9)/2 = 8
    Therefore, y[8] < x is true
    → i = 8 and j = 9
    V iteration
    As i = 8
    Now, k = (8 + 9) / 2 = 8
    Therefore, y[8] < x is true
    → i = 8 and j = 9
    As we have proved that 4[8]! = x & i < j, the program will remain forever in loop.

    Correct Option: C

    We are given that
    i = 0; j = 9;
    k = (i + j)/2
    I iteration
    Let consider x = 4
    Now, k = (0 + 9)/2 = 4
    Therefore, y[4] < x is true
    → i = 4 and j = 9
    II iteration
    As i = 4
    Now, k = (4 + 9) / 2 = 6
    Therefore, y[6] < x is true.
    → i = 6 and j = 9
    III iteration
    As i = 6
    Now, k = (6 + 9) / 2 = 7
    Therefore, y[7] < x is true
    → i = 7 and j = 9
    IV iteration
    As i = 7
    Now, k = (7 + 9)/2 = 8
    Therefore, y[8] < x is true
    → i = 8 and j = 9
    V iteration
    As i = 8
    Now, k = (8 + 9) / 2 = 8
    Therefore, y[8] < x is true
    → i = 8 and j = 9
    As we have proved that 4[8]! = x & i < j, the program will remain forever in loop.