[solved] data structures gate previous year questions

data structures gate previous year questions with solutions

Q1➡ | GATE 2021 Set-1
Consider the following statements.
S1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
i ➥ S1 is false and S2 is true
ii ➥ S1 is false and S2 is false
iii ➥ S1 is true and S2 is false
iv ➥ S1 is true and S2 is true

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph and Tree Help-Line

Q2➡ | GATE 2021 Set-1
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
i ➥ Θ(logn)
ii ➥ Θ(nlogn)
iii ➥ Θ(1)
iv ➥ Θ(n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Search Tree Help-Line

Q3➡ | GATE 2021 Set-1
Consider a dynamic hashing approach for 4-bit integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a
binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collison.

Consider the following state of the hash table.
Consider a dynamic hashing approach for 4-bit integer keys: 1.	There is a main hash table of size 4. 2.	The 2 least significant bits of a key is used to index into the main hash table. 3.	Initially, the main hash table entries are empty. 4.	Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand. 5.	First, the 3rd least significant bit is used to divide the keys into left and right subtrees. 6.	To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit. 7.	A split is done only if it is needed, i.e., only when there is a collison.Consider the following state of the hash table.  Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)? A	10, 9, 6, 7, 5, 13 B	9, 5, 13, 6, 10, 14 C	9, 5, 10, 6, 7, 1 D	5, 9, 4, 13, 10, 7
Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
i ➥ 9, 5, 13, 6, 10, 14
ii ➥ 10, 9, 6, 7, 5, 13
iii ➥ 5, 9, 4, 13, 10, 7
iv ➥ 9, 5, 10, 6, 7, 1

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHashing Help-Line

Q4➡ | GATE 2021 Set-1
Consider the following sequence of operations on an empty stack.
push(54);
push(52);
pop();
push(55);
push(62);
s=pop();
Consider the following sequence of operations on an empty queue.
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
The value of s + q is __

Show Answer With Best Explanation

Answer: 86
Explanation: Upload Soon

More DiscussionExplanation On YouTubeQueues and stacks Help-Line

Q5➡ | GATE 2021 Set-1
i ➥ The program will compile successfully and output 8 when executed.
ii ➥ The program will not compile successfully.
iii ➥ The program will compile successfully and output 13 when executed.
iv ➥ The program will compile successfully and output 10 when executed.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC Programming Help-Line

Q6➡ | GATE 2021 Set-2
i ➥ 24
ii ➥ 14
iii ➥ 30
iv ➥ 20

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC programming Help-Line

Q7➡ | GATE 2021 Set-2
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Help-Line

Q8➡ | GATE 2021 Set-2
Consider a complete binary tree with 7 nodes, Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of |A – B| is _______.

Show Answer With Best Explanation

Answer: 1
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTree Help-Line

Q9➡ | GATE 2021 Set-2

Show Answer With Best Explanation

Answer: 15
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC Programming Help-Line

Q10➡ | GATE 2021 Set-2

Assume that the variable y points to a struct (allocated on the head) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and de-reference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:
i ➥ 303 and 2
ii ➥ 403 and 102
iii ➥ 203 and 2
iv ➥ 303 and 102

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC Programming Help-Line

Q11➡ | GATE 2021 Set-2

i ➥ Upon execution, the program goes into an infinite loop.
ii ➥ It dereferences an uninitialized pointer that may result in a run-time error.
iii ➥ Upon execution, the program creates a linked-list of five nodes.
iv ➥ It has a missing return which will be reported as an error by the compiler.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC Programming Help-Line

Q12➡ | GATE 2021 Set-2

Show Answer With Best Explanation

Answer: 60
Explanation: Upload Soon

More DiscussionExplanation On YouTubeC Programming Help-Line

Q13➡ | GATE 2020
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
i ➥ θ(n2 log n)
ii ➥ θ(n3)
iii ➥ θ(n2)
iv ➥ θ(n4)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q14➡ | GATE 2020
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?
i ➥ 10, 11, 12, 15, 16, 18, 19, 20
ii ➥ 20, 19, 18, 16, 15, 12, 11, 10
iii ➥ 11, 12, 10, 16, 19, 18, 20, 15
iv ➥ 19, 16, 18, 20, 11, 12, 10, 15

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Binary Tree Help-Line

Q15➡ | GATE 2020
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
i ➥ θ(n)
ii ➥ θ(n log n)
iii ➥ θ(1)
iv ➥ θ(n2)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLinked List Help-Line

Q16➡ | GATE 2020
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is
h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume
that the probe sequence begins at probe 0) for key value k=90 is _______.

Show Answer With Best Explanation

Answer: 13
Explanation: Upload Soon

More DiscussionExplanation On YouTube Hashing Help-Line

Q17➡ | GATE 2020
Consider the following C program.

The output of the program is ______.

Show Answer With Best Explanation

Answer: 19
Explanation: Upload Soon

More DiscussionExplanation On YouTubeArrays Help-Line

Q18➡ | GATE 2020
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.
i ➥ θ(k log n)
ii ➥ θ(log n)
iii ➥ θ(n log k)
iv ➥ θ(log n + k)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q19➡ | GATE 2020
Let G = (V,E) be a directed, weighted graph 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) + f(u) – f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _________”.
i ➥ if and only if ∀u ∈ V, f(u) is negative
ii ➥ for every f: V→R
iii ➥ if and only if ∀u ∈ V, f(u) is positive
iv ➥ if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph and Tree Help-Line

Q20➡ | GATE 2020
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

Show Answer With Best Explanation

Answer: 511
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Tree Help-Line

Q21➡ | GATE 2020
Consider the following C functions:

The return value of fun2 (5) is ______.

Show Answer With Best Explanation

Answer: 55
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q22➡ | GATE 2020
Consider the following C functions:

The value returned by pp(3,4) is _______.

Show Answer With Best Explanation

Answer: 81
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q23➡ | GATE 2019

The value printed by the program is __.

Show Answer With Best Explanation

Answer: 26
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunctions Help-Line

Q24➡ | GATE 2019
Consider the following C program:

Which one of the following values will be displayed on execution of the programs?
i ➥ 52
ii ➥ 630
iii ➥ 41
iv ➥ 63

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFor Loop Help-Line

Q25➡ | GATE 2019
Consider the following C function:

Which one of the following will happen when the function convert is called with any positive integer n as argument?
i ➥ It will print the binary representation of n and terminate.
ii ➥ It will print the binary representation of n in the reverse order and terminate.
iii ➥ It will print the binary representation of n but will not terminate.
iv ➥ It will not print anything and will not terminate.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Functions Help-Line

Q26➡ | GATE 2019
Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a max-heap in Θ(n) time.

Which of the above statements are TRUE?
i ➥ I, II and III
ii ➥ I, III and IV
iii ➥ II, III and IV
iv ➥ I, II and IV

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q27➡ | GATE 2019
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between
a and b) is (rounded off to 2 decimal places) __________.

Show Answer With Best Explanation

Answer: 4.25
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q28➡ | GATE 2019
Consider the following C program:

The output of the above C program is _______.

Show Answer With Best Explanation

Answer: 10
Explanation: Upload Soon

More DiscussionExplanation On YouTubeControl Statement Help-Line

Q29➡ | GATE 2019
Consider the following C program:

The number of times the variable sum will be printed, when the above program is executed, is ________.

Show Answer With Best Explanation

Answer: 5
Explanation: Upload Soon

More DiscussionExplanation On YouTube Control Statement Help-Line

Q30➡ | GATE 2018
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let ‘enqueue’ be implemented by inserting a new node at the head, and ‘dequeue’ be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of ‘enqueue’ and ‘dequeue, respectively, for this data structure?
i ➥ θ(n), θ(1)
ii ➥ θ(n), θ(n)
iii ➥ θ(1), θ(1)
iv ➥ θ(1), θ(n)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeQueue Help-Line

Q31➡ | GATE 2018
i ➥ ‘0’, ‘a+2’
ii ➥ ‘0’, ‘c’
iii ➥ 0, c
iv ➥ 0, a+2

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgramming in C Help-Line

Q32➡ | GATE 2018
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is_____.

Show Answer With Best Explanation

Answer: 4 To 4
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTrees TraversalHelp-Line

Q33➡ | GATE 2018
Consider the following C program:

The output of this program is __.

Show Answer With Best Explanation

Answer: 4
Explanation: Upload Soon

More DiscussionExplanation On YouTube C program Help-Line

Q34➡ | GATE 2018
Consider the following C code. Assume that unsigned long int type length is 64 bits.

The value returned when we call fun with the input 240 is
i ➥ 4
ii ➥ 5
iii ➥ 6
iv ➥ 40

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube For Loop Help-Line

Q35➡ | GATE 2018
Consider the following C program:

The output of the program above is.
i ➥ Hi Bye Bye Hi
ii ➥ Hi Bye Hi Bye
iii ➥ Bye Hi Hi Bye
iv ➥ Bye Hi Bye Hi

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q36➡ | GATE 2018

Show Answer With Best Explanation

Answer: 10230
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q37➡ | GATE 2018
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is_______.

Show Answer With Best Explanation

Answer: 80
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap-Tree Help-Line

Q38➡ | GATE 2017 Set-1
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.
i ➥ 4 and 14 respectively
ii ➥ 3 and 15 respectively
iii ➥ 3 and 14 respectively
iv ➥ 4 and 15 respectively

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q39➡ | GATE 2017 Set-1
Consider the C code fragment given below.

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will
i ➥ either cause a null pointer dereference or append list m to the end of list n.
ii ➥ cause a null pointer dereference for all inputs.
iii ➥ append list n to the end of list m for all inputs.
iv ➥ append list m to the end of list n for all inputs.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLinked List Help-Line

Q40➡ | GATE 2017 Set-1
Consider the following C code:

The code suffers from which one of the following problems:
i ➥ compiles successfully but execution may result in memory leak
ii ➥ compiles successfully but execution may result in dangling pointer
iii ➥ compiler error as the return of malloc is not typecast approximately
iv ➥ compiler error because the comparison should be made as x==NULL and not as shown

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubemalloc Function Help-Line

Q41➡ | GATE 2017 Set-1
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _______.

Show Answer With Best Explanation

Answer: 18.0
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTree Help-Line

Q42➡ | GATE 2017 Set-1
Consider the C functions foo and bar given below:

Invocations of foo(3) and bar(3) will result in:
i ➥ Abnormal termination and infinite loop respectively.
ii ➥ Both terminating abnormally.
iii ➥ Return of 6 and 6 respectively.
iv ➥ Infinite loop and abnormal termination respectively.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q43➡ | GATE 2017 Set-1
Consider the following two functions:

The output printed when fun1(5) is called is
i ➥ 53423122132435
ii ➥ 53423122233445
iii ➥ 53423120112233
iv ➥ 53423120213243

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q44➡ | GATE 2017 Set-1
Consider the following C program:

Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. The output of the program is _________.

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q45➡ | GATE 2017 Set-1
The output of executing the following C program is _________.

Show Answer With Best Explanation

Answer: 23
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q46➡ | GATE 2017 Set-2
Match the following:
i ➥ P→(iii), Q→(iv), R→(i), S→(ii)
ii ➥ P→(ii), Q→(iv), R→(iii), S→(i)
iii ➥ P→(ii), Q→(i), R→(iv), S→(iii)
iv ➥ P→(ii), Q→(iv), R→(i), S→(iii)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgramming concept Help-Line

Q47➡ | GATE 2017 Set-2
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
 The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
i ➥ NQMPOR
ii ➥ MNOPQR
iii ➥ QMNROP
iv ➥ POQNMR

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeNetwork Security Help-Line

Q48➡ | GATE 2017 Set-2
Consider the following function implemented in C:

The output of invoking printxy(1, 1) is
i ➥ 1, 1
ii ➥ 1, 0
iii ➥ 0, 1
iv ➥ 0, 0

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubePointer Help-Line

Q49➡ | GATE 2017 Set-2
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?
I: Next pointer of front node points to the rear node.
II: Next pointer of rear node points to the front node.
i ➥ Neither I nor II
ii ➥ Both I and II
iii ➥ II only
iv ➥ I only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeQueue and Linked List Help-Line

Q50➡ | GATE 2017 Set-2
Consider the C program fragment below which is meant to divide x and y using repeated subtractions. The variables x, y, q and r are all unsigned int.

Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y*q + r)?
i ➥ (q == 0) && (y > 0)
ii ➥ (q == 0) && (r == x) && (y > 0)
iii ➥ (x > 0) && (r == x) && (y > 0)
iv ➥ (q == r) && (r == 0)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q51➡ | GATE 2017 Set-2
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
i ➥ 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12
ii ➥ 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
iii ➥ 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
iv ➥ 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Trees Help-Line

Q52➡ | GATE 2017 Set-2
Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y.

The output of the program is _______.

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q53➡ | GATE 2017 Set-2
Consider the following C program:

The output of the program is ________.

Show Answer With Best Explanation

Answer: 0
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q54➡ | GATE 2017 Set-2
Consider the following C program.

The output of the program is _________.

Show Answer With Best Explanation

Answer: 2
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q55➡ | GATE 2016 Set-1
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
i ➥ Both operations can be performed in O(1) time
ii ➥ At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
iii ➥ The worst case time complexity for both operations will be Ω(n)
iv ➥ Worst case time complexity for both operations will be Ω(logn)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More Discussion Explanation On YouTube Queue Help-Line

Q56➡ | GATE 2016 Set-1
Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ___________.

Show Answer With Best Explanation

Answer: 6
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTopological Ordering Help-Line

Q57➡ | GATE 2016 Set-1
Consider the following C program:

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
i ➥ f(i, *p)
ii ➥ f(i, *s)
iii ➥ i = f(i, s)
iv ➥ f(s, *s)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q58➡ | GATE 2016 Set-1
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
• P: Minimum spanning tree of G does not change
• Q: Shortest path between any pair of vertices does not change
i ➥ Both P and Q
ii ➥ Neither P nor Q
iii ➥ Q only
iv ➥ P only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph Help-Line

Q59➡ | GATE 2016 Set-1
Consider the following C program.

The output of the program is ________.

Show Answer With Best Explanation

Answer: 2016
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q60➡ | GATE 2016 Set-1
The following function computes the maximum value contained in an integer array p[] of size n (n >= 1).

The missing loop condition is
i ➥ a != n
ii ➥ b != 0
iii ➥ b > (a + 1)
iv ➥ b != a

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q61➡ | GATE 2016 Set-1
What will be the output of the following C program?
i ➥ 3 1 2 2 1 3 4 4 4
ii ➥ 3 1 2 1 1 1 2 2 2
iii ➥ 3 1 2 2 1 3 4
iv ➥ 3 1 2 1 1 1 2

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q62➡ | GATE 2016 Set-1
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed?
i ➥ 6, 2
ii ➥ 6, 6
iii ➥ 4, 2
iv ➥ 4, 4

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q63➡ | GATE 2016 Set-1
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
i ➥ O(1)
ii ➥ O(d) but not O(1)
iii ➥ O(2d) but not O(d)
iii ➥ O(d 2d) but not O(2d)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Heap Help-Line

Q64➡ | GATE 2016 Set-1
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry Wij in the matrix W.

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge
with weight x is ________.

Show Answer With Best Explanation

Answer: 12
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph Help-Line

Q65➡ | GATE 2016 Set-1
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q
without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given
below.

The maximum possible number of iterations of the while loop in the algorithm is ___________.

Show Answer With Best Explanation

Answer: 256
Explanation: Upload Soon

More DiscussionExplanation On YouTubeQueue and Stack Help-Line

Q66➡ | GATE 2016 Set-1
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard many-one reduction).
Which one of the following statements is TRUE?
i ➥ W can be recursively enumerable and Z is recursive.
ii ➥ W can be recursive and Z is recursively enumerable.
iii ➥ W is not recursively enumerable and Z is recursive.
iv ➥ W is not recursively enumerable and Z is not recursive.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Trees Help-Line

Q67➡ | GATE 2016 Set-2
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

Show Answer With Best Explanation

Answer: 31
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBFS Help-Line

Q68➡ | GATE 2016 Set-2
The value printed by the following program is _________.

Show Answer With Best Explanation

Answer: 30
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q69➡ | GATE 2016 Set-2
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.
An algorithm performs the following operations on the list in this order: Θ(N) delete,O(logN) insert, O(logN) find, and Θ(N) decrease-key. What
is the time complexity of all these operations put together?
i ➥ O(log2 N)
ii ➥ O(N)
iii ➥ O(N2)
iv ➥ Θ(N2 logN)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLinked List Help-Line

Q70➡ | GATE 2016 Set-2
A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is ________.

Show Answer With Best Explanation

Answer: 8
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Tree Help-Line

Q71➡ | GATE 2016 Set-2
The following function computes XY for positive integers X and Y.

Which one of the following conditions is TRUE before every iteration of the loop?
i ➥ XY = ab
ii ➥ (res * a)Y = (res * X)b
iii ➥ XY = res * ab
iv ➥ XY = (res * a)b

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q72➡ | GATE 2016 Set-2
Consider the following New-order strategy for traversing a binary tree:
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ˆ 6 7 * 1 + – is given by:
i ➥ – 1 6 7 * 2 ˆ 5 – 3 4 *
ii ➥ + 1 * 6 7 ˆ 2 – 5 * 3 4
iii ➥ + 1 * 7 6 ˆ 2 – 5 * 4 3
iv ➥ 1 7 6 * + 2 5 4 3 * – ˆ –

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Binary Tree Help-Line

Q73➡ | GATE 2016 Set-2
Consider the following program:

Note: max(x,y) returns the maximum of x and y.
The value printed by this program is ________.

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q74➡ | GATE 2016 Set-2
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree
has height 6, is __________.
Note: The height of a tree with a single node is 0.

Show Answer With Best Explanation

Answer: 64
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTrees Help-Line

Q75➡ | GATE 2016 Set-2
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
i ➥ Θ(n2)
ii ➥ Θ(n+m)
iii ➥ Θ(m2)
iv ➥ Θ(n4)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph Help-Line

Q76➡ | GATE 2015 Set-1
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
i ➥ 63 and 6, respectively
ii ➥ 64 and 5, respectively
iii ➥ 32 and 6, respectively
iv ➥ 31 and 5, respectively

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Tree Help-Line

Q77➡ | GATE 2015 Set-1
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)

I. 3,5,7,8,15,19,25
II. 5,8,12,10,15,25
III. 2,7,10,8,14,16,20
IV. 4,6,7,9,18,20,25
i ➥ I and VI only
ii ➥ II and III only
iii ➥ II and IV only
iv ➥ II only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Binary Search Tree Help-Line

Q78➡ | GATE 2015 Set-1
The output of the following C program is __________.

Show Answer With Best Explanation

Answer: -5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q79➡ | GATE 2015 Set-1
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
i ➥ Θ(logn) for both insertion and deletion
ii ➥ Θ(n) for both insertion and deletion
iii ➥ Θ(n) for insertion and Θ(logn) for deletion
iv ➥ Θ(logn) for insertion and Θ(n) for deletion

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Search Tree Help-Line

Q80➡ | GATE 2015 Set-1
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
i ➥ 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
ii ➥ 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
iii ➥ 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
iv ➥ 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Help-Line

Q81➡ | GATE 2015 Set-1
What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory.
int main()
{
unsigned int x[4][3] =
{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};
printf(“%u, %u, %u”, x+3, *(x+3), *(x+2)+3);
}
i ➥ 2036, 2036, 2036
ii ➥ 2012, 4, 2204
iii ➥ 2036, 10, 10
iv ➥ 2012, 4, 6

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q82➡ | GATE 2015 Set-1
Consider the following C function.

Which one of the following most closely approximates the return value of the function fun1?
i ➥ n3
ii ➥ n(log n)2
iii ➥ nlog n
iv ➥ nlog (log n)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q83➡ | GATE 2015 Set-1
Consider the following pseudo code, where x and y are positive integers.
begin
q := 0
r := x
while r >= y do

begin
r := r – y
q := q + 1
end

end
The post condition that needs to be satisfied after the program terminates is
i ➥ {r = qx + y ∧ r< y}
ii ➥ {x = qy + r ∧ r<y}
iii ➥ {y = qx + r ∧ 0<r< y}
iv ➥ {q +1 < r – y ∧ y > 0}

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q84➡ | GATE 2015 Set-2
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
i ➥ Θ(nlog n)
ii ➥ Θ(n)
iii ➥ Θ(log n)
iv ➥ Θ(1)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Array Help-Line

Q85➡ | GATE 2015 Set-2
Consider the following function written the C programming language.

The output of the above function on input “ABCD EFGH” is
i ➥ ABCD EFGH
ii ➥ ABCD
iii ➥ HGFE DCBA
iv ➥ DCBA

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More Discussion Explanation On YouTube Program Help-Line

Q86➡ | GATE 2015 Set-2
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
i ➥ Ω(logn)
ii ➥ Ω(n)
iii ➥ Ω(nlog n)
iv ➥ Ω(n2)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More Discussion Explanation On YouTube Heap Tree Help-Line

Q87➡ | GATE 2015 Set-2
A binary tree T has 20 leaves. The number of nodes in T having two children is ________.

Show Answer With Best Explanation

Answer: 19
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q88➡ | GATE 2015 Set-2
Consider the following C functions

The return value of fun(5) is ________.

Show Answer With Best Explanation

Answer: 51
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q89➡ | GATE 2015 Set-2
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is __________.

Show Answer With Best Explanation

Answer: 5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeArray Help-Line

Q90➡ | GATE 2015 Set-2
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
i ➥ h(i) = i2 mod 10
ii ➥ h(i) = i3 mod 10
iii ➥ h(i) = (11 *i2) mod 10
iv ➥ h(i) = (12 * i) mod 10

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHashing Help-Line

Q91➡ | GATE 2015 Set-2
Consider the C program below.

The value printed by the above program is __________.

Show Answer With Best Explanation

Answer: 15
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q92➡ | GATE 2015 Set-3
Consider the following C program segment.

What will be printed by the program?
i ➥ 12
ii ➥ 120400
iii ➥ 1204
iv ➥ 1034

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q93➡ | GATE 2015 Set-3
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.

Show Answer With Best Explanation

Answer: 199
Explanation: Upload Soon

More Discussion Explanation On YouTube Binary Tree Help-Line

Q94➡ | GATE 2015 Set-3
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.

Show Answer With Best Explanation

Answer: 80
Explanation: Upload Soon

More Discussion Explanation On YouTube Hashing Help-Line

Q95➡ | GATE 2015 Set-3
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
i ➥ 65
ii ➥ 67
iii ➥ 69
iv ➥ 83

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Tree Help-Line

Q96➡ | GATE 2015 Set-3
The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
i ➥ 284
ii ➥ 213
iii ➥ 142
iv ➥ 71

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubePostfix Expression Help-Line

Q53➡ | GATE 2015 Set-3
Consider the following array of elements.
〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉.
The minimum number of interchanges needed to convert it into a max-heap is
i ➥ 4
ii ➥ 5
iii ➥ 2
iv ➥ 3

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Help-Line

Q97➡ | GATE 2015 Set-3
Consider the following recursive C function.


If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
i ➥ 15
ii ➥ 25
iii ➥ 35
iv ➥ 45

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q98➡ | GATE 2015 Set-3
Consider the following C program.

The output of the program is ______.

Show Answer With Best Explanation

Answer: 230
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q99➡ | GATE 2015 Set-3
Consider the following C program.

The output of the program is ______.

Show Answer With Best Explanation

Answer: 140
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q100➡ | GATE 2015 Set-3
Consider the following C program:

The number of times printf statement is executed is __.

Show Answer With Best Explanation

Answer: 10
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgramming in C Help-Line

Q44➡ | GATE CSE 2015 Set-3
Suppose c = 〈c[0], … , c[k – 1]〉 is an array of length k, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.



If k = 4, c = 〈1, 0, 1, 1〉, a = 2 and n = 8, then the output of DOSOMETHING(c, a, n) is __.

Show Answer With Best Explanation

Answer: 0
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q101➡ | GATE 2014 Set-1
Consider the following program in C language:

Which one of the following statements is TRUE?
i ➥ Compilation fails.
ii ➥ Execution results in a run-time error.
iii ➥ On execution, the value printed is 5 more than the address of variable i.
iv ➥ On execution, the value printed is 5 more than the integer value entered.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More Discussion Explanation On YouTube Programming in CHelp-Line

Q102➡ | GATE 2014 Set-1
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
i ➥ θ(n)
ii ➥ θ(n+m)
iii ➥ θ(n2)
iv ➥ θ(m2)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More Discussion Explanation On YouTube Graph-DFS Help-Line

Q103➡ | GATE 2014 Set-1
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(na logb n). Then the value of a+10b is __.

Show Answer With Best Explanation

Answer: 1
Explanation: Upload Soon

More Discussion Explanation On YouTubeComplexityHelp-Line

Q104➡ | GATE 2014 Set-1
Consider the directed graph given below.

Which one of the following is TRUE?
i ➥ The graph does not have any topological ordering.
ii ➥ Both PQRS and SRQP are topological.
iii ➥ Both PSRQ and SPRQ are topological orderings.
iv ➥ PSRQ is the only topological ordering.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraphHelp-Line

Q105➡ | GATE 2014 Set-1
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
i ➥ t1=5
ii ➥ t1 < t2 </t
iii ➥ t1 > t2
iv ➥ t1=t2

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting- quick-sortHelp-Line

Q106➡ | GATE 2014 Set-1
Consider a hash table with 9 slots. The hash function is ℎ(k) = k Nod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17,
The maximum, minimum, and average chain lengths in the hash table, respectively, are
i ➥ 3, 0, and 1
ii ➥ 3, 3, and 3
iii ➥ 4, 0, and 1
iv ➥ 3, 0, and 2

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHashing Help-Line

Q107➡ | GATE 2014 Set-1
Consider the following C function in which size is the number of elements in the array E:

The value returned by the function MyX is the
i ➥ maximum possible sum of elements in any sub-array of array E.
ii ➥ maximum element in any sub-array of array E.
iii ➥ sum of the maximum elements in all possible sub-arrays of array E.
iv ➥ the sum of all the elements in the array E.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSecant mathod Help-Line

Q108➡ | GATE 2014 Set-1
Consider the following pseudo code.

What is the total number of multiplications to be performed?
i ➥ Half of the product of the 3 consecutive integers.
ii ➥ One-third of the product of the 3 consecutive integers.
iii ➥ One-sixth of the product of the 3 consecutive integers.
iv ➥ None of the above.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q109➡ | GATE 2014 Set-2
Consider the function func shown below:


The value returned by func(435)is______.

Show Answer With Best Explanation

Answer: 9
Explanation: Upload Soon

More Discussion Explanation On YouTube Programming in CHelp-Line

Q110➡ | GATE 2014 Set-2
Suppose n and p are unsigned int variables in a C program. We wish to set p to nC3. If n is large, which one of the following statements is most likely to set p correctly?
i ➥ p = n * (n-1) * (n-2) / 6;
ii ➥ p= n * (n-1) / 2 * (n-2) / 3;
iii ➥ p = n * (n-1) / 3 * (n-2) / 2;
iv ➥ p = n * (n-1) * (n-2) / 6.0;

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More Discussion Explanation On YouTube ProgrammingHelp-Line

Q111➡ | GATE 2014 Set-2
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
i ➥ 10, 8, 7, 3, 2, 1, 5
ii ➥ 10, 8, 7, 2, 3, 1, 5
iii ➥ 10, 8, 7, 1, 2, 3, 5
iv ➥ 10, 8, 7, 5, 3, 2, 1

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More Discussion Explanation On YouTube Max-HeapHelp-Line

Q112➡ | GATE 2014 Set-2
For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.
t0 = i ∗ 1024
t1 = j ∗ 32
t2 = k ∗ 4
t3 = t1 + t0
t4 = t3 + t2
t5 = X[t4]
Which one of the following statements about the source code for the C program is CORRECT?
i ➥ X is declared as “int X[32][32][8]”.
ii ➥ X is declared as “int X[4][1024][32]”.
iii ➥ X is declared as “char X[4][32][8]”.
iv ➥ X is declared as “char X[32][16][2]”.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgramHelp-Line

Q113➡ | GATE 2014 Set-2
Consider the following function

Give a value q (to 2 decimals) such that f(q) will return q:__________,

Show Answer With Best Explanation

Answer: 1.72 To 1.74
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgramming in cHelp-Line

Q114➡ | GATE 2014 Set-2
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?
i ➥ A queue cannot be implemented using this stack.
ii ➥ A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
iii ➥ A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
iv ➥ A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube QUEUE Help-Line

Q115➡ | GATE 2014 Set-2
Consider the C function given below.


Which one of the following is TRUE?
i ➥ The function returns 0 for all values of j.
ii ➥ The function prints the string something for all values of j.
iii ➥ The function returns 0 when j = 50.
iv ➥ The function will exhaust the runtime stack or run into an infinite loop when j = 50.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunctionHelp-Line

Q116➡ | GATE 2014 Set-2
The number of distinct minimum spanning trees for the weighted graph below is

Show Answer With Best Explanation

Answer: 6
Explanation: Upload Soon

More DiscussionExplanation On YouTube TREEHelp-Line

Q117➡ | GATE 2014 Set-3
Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
i ➥ The matrix A itself
ii ➥ Transpose of the matrix A
iii ➥ Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A
iv ➥ None of the above

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More Discussion Explanation On YouTube Program Help-Line

Q118➡ | GATE 2014 Set-3
The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given value of X, using only one temporary variable is _________.

Show Answer With Best Explanation

Answer: 7
Explanation: Upload Soon

More Discussion Explanation On YouTube Arithmetic Operations Help-Line

Q119➡ | GATE 2014 Set-3
Consider the following rooted tree with the vertex labeled P as t he root:

The order in which the nodes are visited during in-order traversal is
i ➥ SQPTRWUV
ii ➥ SQPTUWRV
iii ➥ SQPTWUVR
iv ➥ SQPTRUWV

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More Discussion Explanation On YouTube Tree Help-Line

Q120➡ | GATE 2014 Set-3
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _______.

Show Answer With Best Explanation

Answer: 19
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph Help-Line

Q121➡ | GATE 2014 Set-3
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are N such numbers in T. If the tightest upper bound on the time to compute the sum is 0(na logb n+ mc logd n), the value of a + 10b + 100c + 1000d is_____.
.

Show Answer With Best Explanation

Answer: 110
Explanation: Upload Soon

More DiscussionExplanation On YouTube binary search treeHelp-Line

Q122➡ | GATE 2014 Set-3
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
i ➥ (97 × 97 × 97)/1003
ii ➥ (99 × 98 × 97)/1003
iii ➥ (97 × 96 × 95)/1003
iv ➥ (97 × 96 × 95)/(3! × 1003)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHashing Help-Line

Q123➡ | GATE 2014 Set-3
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
i ➥ number of internal nodes in the tree.
ii ➥ height of the tree.
iii ➥ number of nodes without a right sibling in the tree.
iv ➥ number of leaf nodes in the tree.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeStructHelp-Line

Q124➡ | GATE 2014 Set-3
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

Which one of the following statements about the function ProcessArray is CORRECT?
i ➥ It will run into an infinite loop when x is not in listA.
ii ➥ It is an implementation of binary search.
iii ➥ It will always find the maximum element in listA.
iv ➥ It will return −1 even when x is present in listA.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProgram Help-Line

Q125➡ | GATE 2013
Consider the following function:
i ➥ Θ(n2)
ii ➥ Θ(n2 log n)
iii ➥ Θ(n3)
iv ➥ Θ(n3 logn)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q126➡ | Programming
Consider the following function:
i ➥ Θ(n2)
ii ➥ Θ(n2 log n)
iii ➥ Θ(n3)
iv ➥ Θ(n3 logn)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Program Help-Line

Q127➡ | GATE 2013
What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
i ➥ 3024
ii ➥ 6561
iii ➥ 55440
iv ➥ 161051

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubePass by value and Pass by referenceHelp-Line

Q128➡ | GATE 2013
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
i ➥ 10, 20, 15, 23, 25, 35, 42, 39, 30
ii ➥ 15, 10, 25, 23, 20, 42, 35, 39, 30
iii ➥ 15, 20, 10, 23, 25, 42, 35, 39, 30
iv ➥ 15, 10, 23, 25, 20, 35, 42, 39, 30

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTree Traversal Help-Line

Q129➡ | GATE 2013
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
i ➥ Θ(n)
ii ➥ Θ(n + k)
iii ➥ Θ(nk)
iv ➥ Θ(n2)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeQueue Help-Line

Q130➡ | GATE 2012
What will be the output of the following C program segment?
char inchar = 'A';
switch (inchar)
{
case 'A' :
printf ("choice A n") ;
case 'B' :
printf ("choice B ") ;
case 'C' :
case 'D' :
case 'E' :
default:
printf ("No Choice") ;
}
i ➥ No Choice
ii ➥ Choice A
iii ➥ Choice A
Choice B No Choice
iv ➥ Program gives no output as it is erroneous

Show Answer With Best Explanation

Answer: Marks to All
Explanation: Upload Soon

More DiscussionExplanation On YouTube Switch Statement Help-Line

Q131➡ | GATE 2012
The worst case running time to search for an element in a balanced binary search tree with n2n elements is
i ➥ Θ (n log n)
ii ➥ Θ (n2n)
iii ➥ Θ (n)
iv ➥ Θ (log n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Tree Help-Line

Q132➡ | GATE 2012
Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
i ➥
full: (REAR+1)mod n == FRONT
empty: REAR == FRONT
ii ➥
full: (REAR+1)mod n == FRONT
empty: (FRONT+1) mod n == REAR
iii ➥
full: REAR == FRONT
empty: (REAR+1) mod n == FRONT
iv ➥
full: (FRONT+1)mod n == REAR
empty: REAR == FRONT