NEW
Font size
WorksheetsDSA quiz 3 set 1
Total questions: 10
Worksheet time: 30mins
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
