DSA quiz 3 set 1

Consider a directed, weighted graph G = (V, E) with weight function w: E→R. For some function f: V→R, for each edge (u, v) ∈ E, define w'(u, v) as w(u, v) + af(u) - bf(v), where a and b are two constants.

Which one of the options completes the following sentence so that it is TRUE?

“The shortest paths in G under w are the shortest paths under w’ too, ______”.

• If a = b

• If a<b

• If a>b

• Any value of a and b

Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then y + z = _______ .

• 100

• 110

• 109

• None of these

Consider BFS on a binary tree starting from the root node. There is a vertex t at a distance 6 from the root. If t is the nth vertex in this BFS traversal, then the minimum and maximum possible values of n are ________

• 32,64

• 31,63

• 64,127

• 127,128

Consider following statements written in C

i) sizeof(int)

ii) sizeof(int*)

iii) sizeof(int**)

Consider the size of int as 4 bytes and size of pointer as 4 bytes. Pick the correct option -

• Only i) would compile successfully, and it would return size as 4.

• i), ii) and iii) would compile successfully and the size of each would be same i.e. 4

• i), ii) and iii) would compile successfully, but the size of each would be different and would be decided at run time

• ii) and iii) would result in compile error but i) would compile and result in size as 4.

Consider the following code snippet.

#include <stdlib.h>

int main()

{

 int *ptr;

 int **ptr1;

 int **ptr2;

 ptr = (int*)malloc(sizeof(int));

 ptr1 = (int**)malloc(10*sizeof(int*));

 ptr2 = (int**)malloc(10*sizeof(int*));

 free(ptr);

 free(ptr1);

 free(*ptr2);

 return 0;

}

Pick the Correct option -

• malloc() for ptr1 and ptr2 isn’t correct. It’ll give a compile time error.

• free(*ptr2) is not correct. It’ll give a run time error.

• free(*ptr2) is not correct. It’ll give a compile time error.

• No issue with any of the malloc() and free() i.e. no compile/run time error.

Which data structure is best suited to print the documents in the printer?

• Queue

• Stack

• Linked List

• Array

Consider the following code snippet.

#include <stdio.h>

int func(int *a, int data)

{

    *a = data;

    return a;

}

int main()

{

    int *x = malloc(sizeof(int));

    if (NULL == x) return;

    x = func(x, 0);

    if(x)

    {

        x = (int*) malloc(sizeof (int));

        if (NULL == x) return;

        x = func(x, 10);

    }

    printf("%d\n", *x);

    free(x);

}

• compiler error because the comparison should be made as x==NULL and not as shown.

• compiler error as the return of malloc is not typecast appropriately.

• compiles successfully but execution may result in memory leak.

• compiles successfully but execution may result in dangling pointer.

Consider C code.

int abc(int val)

{

    int x = 0;

    while (val > 0)

    {

        x = x + abc(val--);

    }

    return val;

}

Calling of abc(3) will result in -

• Return 6

• Infinite loop

• Abnormal termination

• Both B & C

 Let A be an array of 16 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________.

• 2

• 3

• 4

• 5

Let’s say you have been given 2 GB of data with only 200 MB of available Main Memory. You need to sort this data. Which sorting technique will be most appropriate?

• Heap sort

• Merge sort

• Quick sort

• Insertion sort