Loading

SET 5


  Question 1

Consider the following segment of C-code:
int j, n;
j = 1;
while (j <= n)
j = j*2;
The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.


A : ceil(log n) +2
B : n
C : ceil(log n)
D : floor(log n) +1


  •  
    .

     Correct answer is :A

     Solution :
      We can see it by taking few examples like n = 1, n = 3, etc.
    For example, for n=5 we have the following (4) comparisons:
    ------------------------
    1 <= 5 (T)
    2 <= 5 (T)
    4 <= 5 (T)
    8 <= 5 (F)
    ------------------------
    CEIL(log_2 n)+2 = CEIL(log_2 5) + 2 = CEIL(2.3) + 2 = 3 + 2 = 5

  •   Question 2

    Consider the following C function, what is the output?
    int f(int n)
    {
    static int r = 0;
    if (n <= 0)
    return 1;
    if (n > 3)
    {
    r = n;
    return f(n-2)+2;
    }
    return f(n-1)+r;
    }
    int main()
    {
    printf("%d", f(5));
    }


    A : 5
    B : 7
    C : 9
    D : 18


  •  
    .

     Correct answer is :D


  •   Question 3

    Consider the following C program segment where CellNode represents a node in a binary tree:
    struct CellNode
    {
    struct CellNOde *leftChild;
    int element;
    struct CellNode *rightChild;
    };
    int GetValue(struct CellNode *ptr)
    {
    int value = 0;
    if (ptr != NULL)
    {
    if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
    value = 1;
    else
    value = value + GetValue(ptr->leftChild) + GetVal


    A : the number of nodes in the tree
    B : the number of internal nodes in the tree
    C : the number of leaf nodes in the tree
    D : the height of the tree


  •  
    .

     Correct answer is :C


  •   Question 4

    Consider the following C code segment:
    int IsPrime(n)
    {
    int i,n;
    for(i=2;i<=sqrt(n);i++)
    if(n%i == 0)
    {printf(“Not Prime\n”); return 0;}
    return 1;
    }
    Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?


    A : T(n) = O(sqrt(n)) and T(n) = Ω(sqrt(n))
    B : T(n) = O(sqrt(n)) and T(n) = Ω(1)
    C : T(n) = O(n) and T(n) = Ω(sqrt(n))
    D : None of the above


  •  
    .

     Correct answer is :B

     Solution :
      Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.
    The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) = Ω(1)

  •   Question 5

    Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?
    a = ( x > y ) ? (( x > z ) ? x : z) : (( y > z ) ? y : z )


    A : x = 3, y = 4, z = 2
    B : x = 6, y = 5, z = 3
    C : x = 6, y = 3, z = 5
    D : x = 5, y = 4, z = 5


  •  
    .

     Correct answer is :A

     Solution :
      The given expression assigns maximum among three elements (x, y and z) to a.

  •   Question 6

    Which of the following are true?
    I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
    II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions
    III. Recursion in programming languages cannot be implemented with dynamic storage allocation
    IV. Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records
    V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records


    A : II and V only
    B : I,III and IV only
    C : I,II and V only
    D : II,III and V only


  •  
    .

     Correct answer is :A


  •   Question 7

    What is printed by the following C program?
    int f(int x, int *py, int **ppz)
    {
    int y, z;
    **ppz += 1;
    z = **ppz;
    *py += 2;
    y = *py;
    x += 3;
    return x + y + z;
    }
    void main()
    {
    int c, *b, **a;
    c = 4;
    b = &c;
    a = &b;
    printf( "%d", f(c,b,a));
    getchar();
    }


    A : 18
    B : 19
    C : 21
    D : 22


  •  
    .

     Correct answer is :B

     Solution :
      /* Explanation for the answer */

    /*below line changes value of c to 5. Note that x remains unaffected by this change as x is a copy of c and address of x is different from c*/
    **ppz += 1

    /* z is changed to 5*/
    z = **ppz;

    /* changes c to 7, x is not changed */
    *py += 2;

    /* y is changed to 7*/
    y = *py;

    /* x is incremented by 3 */
    x += 3;

    /* return 7 + 7 + 5*/
    return x + y + z;

  •   Question 8

    Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.
    void reverse(void)
    {
    int c;
    if (?1) reverse();
    ?2
    }
    int main()
    {
    printf ("Enter Text ") ;
    printf ("\n") ;
    reverse();
    printf ("\n") ;
    }


    A : ?1 is (getchar() != ’\n’)
    ?2 is getchar(c);

    B : ?1 is (c = getchar() ) != ’\n’)
    ?2 is getchar(c);

    C : ?1 is (c != ’\n’)
    ?2 is putchar(c);

    D : ?1 is ((c = getchar()) != ’\n’)
    ?2 is putchar(c);



  •  
    .

     Correct answer is :D

     Solution :
      getchar() is used to get the input character from the user and putchar() to print the entered character, but before printing reverse is called again and again until ‘ ’ is entered. When ‘ ’ is entered the functions from the function stack run putchar() statements one by one. Therefore, last entered character is printed first.

  •   Question 9

    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->next)
          return;
      p = list;
      q = list->next;
      while(q)
      {
         temp = p->value;
         p->value = q->value;
         q->value = temp;
         p = q->next;
         q = p?p->next:0;
      }
    }
    
    
    


    A : 1,2,3,4,5,6,7
    B : 2,1,4,3,6,5,7
    C : 1,3,2,5,4,7,6
    D : 2,3,4,5,6,7,1


  •  
    .

     Correct answer is :B

     Solution :
      The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

  •   Question 10

    Consider the following C program
    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


    A : θ (n) and θ (n)
    B : θ (2n) and θ (n)
    C : θ (n) and θ (2n)
    D : θ (2n) and θ (2n)


  •  
    .

     Correct answer is :B

     Solution :
      For f1(), let T(n) be the function for time complexity.
    T(n) = T(n-1) + T(n-2)
    Above recursion is a standard one for Fibonacci Numbers. After solving the recursion, we get
    T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n
    Above recursion can also be written as ?(1.618.^n)

    In f2(), there is a single loop, so time complexity is ?(n)
    Among all the 4 given choices, (B) looks closest.

  •   Question 11

    Consider the following C program
    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] ;
    }
    f1(8) and f2(8) return the values


    A : 1661 and 1640
    B : 59 and 59
    C : 1640 and 1640
    D : 1640 and 1661


  •  
    .

     Correct answer is :C

     Solution :
      Both functions perform same operation, so output is same, means either (B) or (C) is correct.
    f1(2) = 2*f1(1) + 3*f1(0) = 2
    f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
    f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
    f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61

    We can skip after this as the only remaining choice is (C)
    f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
    f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
    f1(8) = 2*f1(7) +

  •   Question 12

    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 i, 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) printf ("x is in the array ") ;
    9. else printf (" x is not in the array ") ;
    10. } On which of the following contents of Y and x does the program fail?


    A : Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
    B : Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
    C : Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
    D : Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even


  •  
    .

     Correct answer is :C

     Solution :
      (C) The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

  •   Question 13

    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 i, 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) printf ("x is in the array ") ;
    9. else printf (" x is not in the array ") ;
    10. }
    the correction needed in the program to make it work properly is


    A : Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
    B : Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
    C : Change line 6 to: if (Y[k] <= x) i = k; else j = k;
    D : Change line 7 to: } while ((Y[k] == x) && (i < j));


  •  
    .

     Correct answer is :A

     Solution :
      Below is the corrected function
    f(int Y[10], int x) {
       int i, j, k;
       i = 0; j = 9;
       do {
               k =  (i + j) /2;
               if( Y[k] < x)  i = k + 1; else j = k – 1;
           } while(Y[k] != x && i < j);
       if(Y[k] == x) printf ('x is in the array '); 
       else printf ('x is not in the array ') ;
    }


  • MY REPORT
    TOTAL = 13
    ANSWERED =
    CORRECT / TOTAL = /13
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =