The program will print nothing, i.e. when only one element from structure is initialised and remaining are not then they are initialized by 0 by default if it is an int and NULL if it is char and 0.0 if float.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider a doubly linked list implemented as following:
typedef struct Node
{
int data;
struct Node *f, *b;
};
Where *f, and *b are forward and backward links to the adjacent nodes in the linked list.
Consider a pointer ‘middle’ pointing to a node in the list, which is neither the first nor the last node of the doubly linked list. Which among the following code segments deletes the node pointed by ‘middle’ pointer?
middle -> b -> f = middle -> f ; middle -> f -> b = middle -> b;
middle -> b -> b = middle -> f ; middle -> f -> f = middle -> b;
middle -> f -> b = middle -> f ; middle -> b -> f = middle -> b;
middle -> b -> f = middle -> b ; middle -> f -> b = middle -> f;
Correct Answer
Option 1
Solution
Consider the doubly linked list as above.
middle -> b -> f = middle -> f ; middle -> f -> b = middle -> b;
middle -> b -> f means pointing to 3rd node and it gets assigned by middle -> f means 4th node, hence now f link of 2nd node is pointing to 4th node now.
Similarly the same thing happens from 3 -> 4 links too.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Choose the correct option, from the following:
I) We can find a cycle in the graph using BFS.
II) We can find a cycle in the graph using DFS.
Only I is correct
Only II is correct
Both I and II are correct
None is correct.
Correct Answer
Option 2
Solution
Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle. This makes DFS a lot more convenient.
Consider the following example:
Visiting a node twice in BFS does not necessarily mean a cycle is present in the graph. For example, in the graph,
BFS will proceed as (with source = A):
1) Visit A
2) Visit B,F
3) Visit C, D
4) Visit D, E
As we can see, the D gets visited twice, but there is no cycle in the graph. So, BFS is a bad choice if we wish to find a cycle in a directed graph, but BFS works fine to detect a cycle if our graph is undirected (in which case nearly any graph traversal will work, anyways).
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
The number of different Unlabeled Binary Trees can be there with 4 nodes are ___
14
Correct Answer
Option 1
Solution
The tree below is considered as unlabeled tree with 3 nodes
T(i-1) represents number of nodes on the left-sub-tree
T(n−i-1) represents number of nodes on the right-sub-tree
n’th Catalan Number can also be evaluated using direct formula.
T(n) = (2n)! / (n+1)!n!
Number of Binary Search Trees (BST) with n nodes is also same as number of unlabeled trees. The reason for this is simple, in BST also we can make any key as root, If root is i’th key in sorted order, then i-1 keys can go on one side and (n-i) keys can go on other side.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
A program attempts to generate as many permutations as possible of the string, ‘abcd’ by pushing the characters m, n, q, r in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?
n r q m
m n r q
q r n m
None of the above
Correct Answer
Option 4
Solution
So we have a sequence of elements m, n, q,r on which we can apply push and/pop operations. When we pop, the element at top will be popped off and printed in the sequence and we need to find which sequence among the options doesn’t matches to valid output.
m n q r
a)
b)
c)
All a,b,c options are valid sequences hence none of the above is the correct option.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
#include "stdio.h"
int main()
{
char a,b;
printf("%d", scanf("%c %c",&a, &b));
return 1;
}
What will be the output printed when the input given by the user to the program is “kt” on terminal?
1
2
0
Compiler error
Correct Answer
Option 2
Solution
scanf() : It returns a total number of Inputs Scanned successfully, or EOF if input failure occurs before the first receiving argument was assigned.
The first scanf() function in the code written below returns 2, as it is scanning 2 items.
Reference: No specific video on printf and scanf but can be answered by logic
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
int main()
{
int a = 333;
char *ptr;
ptr =( char *)&a;
printf("%d",*ptr);
return 0;
}
What will be the output of the above code?
64
77
75
76
Correct Answer
Option 2
Solution
To understand it you have to convert 333 to binary form which is 101001101, (9 digits) Now code is type casting this value to char*, which takes 8 bits; so from the 9 digits ptr will store only 8 values (1001101) which comes 77.
333 = 00000001 01001101
77 = 01001101
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
#include<stdio.h>
int main()
{
static int i=5;
int j;
j=i+1;
if(--i)
{
main();
printf("%d",j);
}
}
What will be the output of the above program?
1111
3456
2345
0000
Correct Answer
Option 2
Solution
\
Hence O/p: 3 4 5 6
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
A function fun is called and it takes a 2 dimensional array arr as its parameter. arr has 5 rows and 5 columns. The correct function signature for the function fun among the following is/are? [MSQ]
[Assume that there are no complex error & warnings]
fun (int arr[])
fun (int (*arr)[])
fun (int arr[][5])
fun (int arr[5][])
Correct Answer
Option 2,3
Solution
int (*arr)[]
Here the end dimension is fixed.
int arr[][10]
Here arr[] is a pointer which has 10 elements each
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
#include <stdio.h>
void main()
{
int i=0,j=2,k=0
if (i && (j=i++))
k=1;
printf ("%d %d %d", i,j,k);
}
Output of the program is ?
0 1 1
0 2 0
0 0 1
1 0 1
Correct Answer
Option 2
Solution
In the code value of the variable i is 0. Hence the second condition in && is not evaluated. Due to this, the expression inside parentheses results in 0. Hence ‘if’ condition is not satisfied; so all values remain as it is.
Logical operators also guarantee evaluation of their operands from left to right. However, they evaluate the smallest number of operands needed to determine the result of the expression. This is called "short-circuit" evaluation. Thus, some operands of the expression may not be evaluated. For example, in the expression
x && y++
the second operand, y++, is evaluated only if x is true (nonzero). Thus, y is not incremented if x is false (0).
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
#include<stdio.h>
void main()
{ int i=-1, j=-2,k ;
k=-i++*++j ;
printf("%d %d %d", i,j,k) ;
}
0 -1 -1
0 0 -1
1 0 1
1 1 1
Correct Answer
Option 1
Solution
The expression is evaluated as follows:
k=1*-1 as the unary minus (‘-’) has higher associativity than post increment & after evaluation of the variable ‘k’ the value of variable ‘i’ is incremented by 1.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
#include<stdio.h>
void main()
{
int i=0;
for(;i<20 && printf("%d ",i);i++)
{
switch(i)
{
case 0 : i++; i*2;
case 20: i+=2;
case 70: i+=6;
default: i+=3;
}
}
What will be the output of the above program?
0 13 17
1 15 19
0 14 18
0 14 19
Correct Answer
Option 1
Solution
The printf() function returns the number of characters sent to the output screen.
In the iteration of for loop the variable i=0, hence printf() prints value '1' and returns value 1. In the 'switch' block 'break' statement is not used, hence all conditions are evaluated and the value of variable '1' becomes 13.
When the loop goes for a second iteration ;i; becomes 14 due to i++. Hence printf() prints the '14' and returns the value 2(as 2 characters printd).
The 'for' loop continue execution in the similar way
Few extra prints in the program and then the output of the following code will make you understand the code in more clarity:
#include<stdio.h>
void main()
{
int i=0;
for(;i<20 && printf("value of i in condition: %d ",i);i++)
{ printf("|Inside for i==%d\t",i);
switch(i)
{
case 0 : i++; i*2; printf("| case 0, i=%d\t",i);
case 20: i+=2; printf("| case 20, i=%d\t",i);
case 70: i+=6; printf("| case 70, i=%d\t",i);
default: i+=3; printf("| default, i=%d\t\n",i);
}
}
}
Output:
value of i in condition: 0 |Inside for i==0 | case 0, i=1 | case 20, i=3 | case 70, i=9 | default, i=12
value of i in condition: 13 |Inside for i==13 | default, i=16
value of i in condition: 17 |Inside for i==17 | default, i=20
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the implementation of multiple stacks in single array S of size P from index 0 to P-1.
Size of each stack is Q. The following function PUSH(), used to push data x onto a particular stack i, where Ti is used as top variable for stack i(i indicates stack number).
PUSH(S,P,Q,Ti,x)
{
if(___A___)
{
printf(“stack overflow”);
exit(1);
}
else
Ti++;
S[Ti]=x;
}
Stack 0 stores elements from 0 to Q-1, stack 1 stores from q to 2Q-1 and similarly other stack will store elements. Which of the following is the correct expression to replace A in the above function?
Correct Answer
Option 2
Solution
While performing push operation on to stack we always perform “Overflow condition check”, to ensure if stack is full or not.
Number of stack possible is P/Q
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
#include<stdio.h>
void fun(int x, int *p)
{
p=&x;
x=10;
}
void main()
{
int a=5, b=6;
int *p=&a, *q=&b;
*p=20;q=&p;
fun(a,&b);
*q=&b;
*p=30;
printf("%d %d\n",a,b);
}
What is the output of the above program?
10 20
20 30
30 30
30 10
Correct Answer
Option 2
Solution
Visualization for 1st 2 lines in main function:
Line 5:
fun(a, &b)
fun(20, 200)
Inside fun ⇒
The pointer p inside fun has local scope limited to fun & hence it does not affect variables in main function.
Line 6:
Line 7:
a=20, b=30
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following infix expression:
(((P+Q)*(R+S))/T)+(A*(B+C))
What will be the minimum size of stack required to convert the above infix expression into postfix expression? _____
5
Correct Answer
Option 1
Solution
1)
PQ+
2)
3)
PQ+RS+*T/
4)
PQ+RS+*T/ABC
5)
PQ+RS+*T/ABC+*
Hence 5 is the size needed.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Height of complete 10-ary tree with 10000 nodes is : ____
4
Correct Answer
Option 1
Solution
A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k. How many leaves does a complete k-ary tree of height h have? The root has k children at depth 1, each of which has k children at depth 2, etc. Thus, the number of leaves at depth h is kh. Consequently, the height of a complete k-ary tree with n leaves is logkn. The number of internal nodes of a complete k-ary tree of height h is
Log 10000 to the base 10 = 4
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
Given a tree T. Choose a proper option which describes the tree. [MSQ]
T is BST but not AVL.
T is AVL & BST.
Inserting ‘g’ into T will violate AVL property.
Inserting ‘6’ into T will violate AVL property.
Correct Answer
Option 2,4
Solution
Given tree is a Binary search tree. An AVL tree is a BST where for every node in the tree, the height of left & right subtree differ by at most 1.
When 9 is inserted, the height of the left & right subtree of 8 is 0, which is acceptable. Whereas when 6 is inserted, the height of the left subtree of 8 is 2 & right subtree is 0 & difference = (2 - 0) = 2. This is a violation of AVL property.
Hence only ii & iv are correct.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
What is the time complexity to find kruskal’s algorithm [MSQ]
O(ElogE)
O(ElogV)
O(E+V)
O(E^2 logV)^2
Correct Answer
Option 1,2
Solution
The time complexity to find Kruskal's algorithm depends upon the edge sorting.
If edges are in sorted order then time complexity will be O(ElogV)
If edges are not in sorted then time complexity will be O(ElogE)
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
What is the time complexity for given code segment
O(log2n)
O(n)
O(n^2)
O(n^3)
Correct Answer
Option 2
Solution
for (i = 0; i < N*3 ; i++) --> O(n)
{
for (j = 0; j < 100; j++) { --> O(1) because it executes only constant amount of time
and independent variable
for (k = 0; k < j*j*j; k++) --> O(1) because it executes constant amount of time even
though it is a dependent variable.
check++; --> O(1)
}
}
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let f(n)=n^3, g(n)=n^4 and h(n)=log(n!). Which of the following is true? [ MSQ ]
f(n) is not O(h(n)) and h(n) is not O(g(n))
f(n) is not O(h(n)) but h(n) is O(g(n))
g(n) is O(h(n)), but h(n) is not O(f(n))
h(n) is O(f(n)) and f(n) is O(g(n))
Correct Answer
Option 2,4
Solution
f(n)=n^3
g(n)=n^4
h(n)=log(n!) = log(n^n) = nlogn
g(n) > f(n) > h(n)
FALSE: f(n) is not O(h(n)) and h(n) is O(g(n)) because g(n) > h(n)
TRUE: f(n) is not O(h(n)) but h(n) is O(g(n))
FALSE: g(n) is not O(h(n)), but h(n) is O(f(n)) because g(n) > f(n) > h(n)
TRUE: h(n) is O(f(n)) and f(n) is O(g(n))
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
Running time of an algorithm T(n), where n is input size, is given by T(n)=24T(√n)+(logn)^2 if n>2 and T(n)=1 otherwise.
The algorithm is ordered by __?
θ(n^2)
θ(n^3)
θ(log2n)^4.58
θ(log2n)^5.48
Correct Answer
Option 3
Solution
Note: We can’t directly apply Master’s theorem in these questions. So, we have to substitute a value so that we can apply the Master's theorem. There are 2 general types with intuition/ practice. We know, if we convert these equations to a form of equation which can be solved by Master’s theorem. Here we are not forcefully converting, we are converting the equation to a form on which we can apply Master’s theorem.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(1, 2, 8),(2, 1, 7),(6, 5, 1),(5, 6, 2),(0, 2, 2),(9, 1, 9),(4,4,4)]. We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input?
Stable sort definition: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
Step-1: [(6,5,1),(5, 6, 2),(0, 2, 2),(4,4,4),(2, 1, 7),(1, 2, 8),(9, 1, 9)] it sort according to third coordinate. But in question they are expecting to find us with the help of a second coordinate.
Note: The pairs with equal values on the second coordinate are [(2, 1, 7), (9, 1, 9)and (1, 2, 8),(0, 2, 2)]. These should appear in the same order in the output.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Given elements, Find the height of the optimal merge pattern?
17, 28, 13, 7, 8, 12, 10, 4
[ Hint: Height starts with 0 ]
4
Correct Answer
Option 1
Solution
Height of the tree is 4 and the root started with 0.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Which of the following represents a binary max-heap?
25, 12, 16, 13, 10, 12, 4
25, 12, 13, 16, 4, 10, 12
25, 10, 13, 16, 4, 10, 12
25, 14, 16, 13, 10, 4, 12
Correct Answer
Option 4
Solution
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
While forming the Minimum Spanning Tree(MST) of the following graph using Prim's Algorithm, in what order will the edges be added?(Start from Vertex A)
A-C, C-E, E-F, C-G, G-B, B-D, E-H
A-B, A-E, E-F, C-G, G-B, B-D, E-H
A-E, A-B, E-F, C-G, G-B, B-D, E-H
A-C, A-B, B-D, C-G, G-B, A-E, E-F
Correct Answer
Option 1
Solution
A-C, C-E, E-F, C-G, G-B, B-D, E-H.
The MST Prim’s algorithm starts from vertex A and will reach
A-C because of minimum weight.
C-E next minimum weight or we can also traverse C-G. Both are correct.
E-F next minimum weight
C-G next minimum weight
G-B next minimum weight
B-D next minimum weight.
E-H next minimum weight
Note: Total 8 vertices and 8-1(n-1) edges.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The Knapsack bag maximum Capacity is 20. Find out the difference between the number of used and unused objects when we find the maximum profit using greedy Knapsack___?
Given the frequencies and corresponding full binary tree using huffman code algorithm.
Character
A
B
C
D
E
F
Frequency
50
35
15
12
2
3
Find the difference between Y and X is _____?
3
Correct Answer
Option 1
Solution
Difference= 35-32 = 3
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
here are 2 strings named as X and Y, Find the length of the longest common subsequence(LCS) of the giving below two string X and Y is______
X = ababcdefe
Y = badbcefg
6
Correct Answer
Option 1
Solution
LCS of X = ababcdefe and Y = badbcefg
Note: If string length is small better to go for brute force method, and start with tracing X array. We can also follow row major order or column major order.
X = ababcdefe
Y = badbcefg
So, the total length is 6 and the string is babcef.
The optimal substructure of the LCS problem gives the recursive formula
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Which of the following statement(s) is/are FALSE? [ MSQ ]
Given a connected graph G = (V,E), if a vertex v ∈ V is visited during level k of a breadth-first search from source vertex s ∈ V, then every path from s to v has length at most k.
Any Dynamic Programming algorithm with n subproblems will run in O(n) time
Depth-first search will take Θ(V^2) time on a graph G = (V,E) represented as an adjacency matrix.
Given an adjacency-list representation of a directed graph G = (V,E), it takes O(V ) time to compute the in-degree of every vertex
Correct Answer
Option 1,2,4
Solution
A: False. The level of a vertex only provides the length of the shortest path from s.
B: False. The subproblems may take longer than constant time to compute, as was the case with the longest increasing subsequence.
C: True. In this case, finding the neighbors of a vertex takes O(V ) time, which makes the total running time(V2).
D: False. The adjacency list structure needs to be traversed to find the incoming edges for each vertex. This structure has a total size Θ(V + E), so this takes(V + E) time to compute.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Which of the following statement(s) is/are FALSE? [ MSQ ]
Radix Sort does not work correctly (Means, It does not produce the correct output) if we sort each individual digit using insertion sort instead of counting sort.
Suppose we use a hash function ‘h’ to hash ‘n’ distinct keys into an array ‘’T’ of length ‘m’. Assuming simple uniform hashing, the expected number of colliding pairs of elements is θ(n^2/m)
Let T be a complete binary tree with n nodes. Finding a path from the root of T(T is not necessarily sorted) to a given vertex v ∈ T using breadth-first search takes O(logn) time.
Selection sort and heap sort satisfying stable property.
Correct Answer
Option 1,3,4
Solution
A: False. Insertion sort (as presented in class) is a stable sort, so Radix sort remains correct. The change can worsen running time, though.
B:True.Let Xi,j be an indicator random variable equal to 1 if elements i and j collide, and equal to 0 otherwise. Simple uniform hashing means that the probability of element i hashing to slot k is 1/m. Therefore, the probability that i and j both hash to the same slot Pr(Xi,j)=1/m. Hence,E [Xi,j] = 1/m. We now use linearity of expectation to sum over all possible pairs i and j.
C:False. Breadth-first search requires Ω(n) time. Breadth-first search examines each node in the tree in breadth-first order. The vertex v could well be the last vertex explored.
D:False:
→ Heap-Sort: Heapsort is an in-place algorithm, but it is not a stable sort. The final sequence of the results from heapsort comes from removing items from the created heap in purely size order (based on the key field). Any information about the ordering of the items in the original sequence was lost during the heap creation stage, which came first.
→ Selection Sort: Selection sort algorithm picks the minimum and swaps it with the element at current position.
Example: A={5,2,3,8,4,5,6}
Let's distinguish the two 5's as 5(a) and 5(b) .
After first iteration : 2 will be swapped with the element in 1st position:
A={2,3,4,5(b),5(a),6,8}
Note:Stable with O(n) extra space. Using linked lists .
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
A min heap contains 512 distinct elements with keys ranging from 0 to 511. These keys are stored in an array of 512 indices. To place an element 25 in a min heap, find the maximum difference between maximum level and minimum level is____? [ Hint: Assume root as level 0 ]
8
Correct Answer
Option 1
Solution
Method-1:
The heap is a complete binary tree. The total 512 elements hence there will be 9 levels of the heap. We can get (n/2)th element that can be present at the last level in the worst case. The last level is 9 and level starts from 0.
The heap is not a binary search tree, so we can get the best case as 1st level.
So, The difference= 9-1=8
Method-2:
If you draw a min heap then you will get 512 elements in the worst case position is the last level of the tree.
The best case possibility is level-1 and worst case possibility is level-8.
So, the difference is 9-1=8
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Suppose we are implementing quadratic probing with a Hash function, Hash(y)=X mod 100. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is ____? [ Note: i >= 1 ]
3
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Find the correct topological sequence using indegree elimination method for given graph G=(V,E)
1,6,5,0,3,2,4,7
0,1,3,7,2,4,5,6
1,7,6,5,0,3,2,4
0,5,7,2,3,1,4,6
Correct Answer
Option 1
Solution
Here, we have to take the sequence when indegree becomes ‘0’.
Step-1: identify indegree “0” vertices.
The given graph has two indegree “0” vertices. The vertices are 0 and 1. So, we can start the sequence with either vertex 0 or 1.
Step-2: Remove outgoing edges of vertex 0 or 1. Because of removal of outgoing edges some vertices become indegree “0”.
Step-3: Will continue the process until all vertices indegree 0.
→ The given problem is easy by choosing the eliminating option method.
Option-B: INCORRECT: The last and highest indegree vertex is 7 but we are given a sequence before than his parent vertices.
Option-C: INCORRECT: The last and highest indegree vertex is 7 but we are given a sequence before than his parent vertices.
Option-D: INCORRECT: The last and highest indegree vertex is 7 but we are given a sequence before than his parent vertices.
\
