GATE CS Applied Course

GATE Previous Year Wise Questions

GATE Previous Subject Wise Questions

Question 221
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 m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.
A
110
B
111
C
112
D
113
Algorithms Binary-Trees GATE 2014 SET 3
Question 222
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. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); } 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  
A
number of internal nodes in the tree
B
height of the tree.
C
number of nodes without a right sibling in the tree
D
number of leaf nodes in the tree
Algorithms GATE 2014 SET 3
Question 223
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
A
1.54
B
1.55
C
1.56
D
1.57
computer organization GATE 2014 SET 3
Question 224
A
P, Q and R are true
B
Only Q and R are true
C
Only P and Q are true
D
Only R is true
GATE 2014 SET 3
Question 225
There are two elements , in a group ( ,∗) such that every element in the group can be written as a product of some number of x's and 's in some order. It is known that x*x=y*y=x*y*x=y*x*y*x=e where    is the identity element. The maximum number of elements in such a group is  
A
4
B
5
C
6
D
7
GATE 2014 SET 3
Question 226
If G is a forest with n vertices and k connected components, how many edges does G have?
A
⌊n/k⌋
B
⌈n/k⌉
C
n–k
D
n-k+1
GATE 2014 SET 3
Question 227
The CORRECT formula for the sentence, “not all rainy days are cold” is
A
∀d (Rainy(d) ∧∼Cold(d))
B
∀d (∼Rainy(d) → Cold(d))
C
∃d (∼Rainy(d) → Cold(d))
D
∃d (Rainy(d) ∧∼Cold(d))
GATE 2014 SET 3
Question 228
Consider the following relational schema: employee(empId,empName,empDept) customer(custId,custName,salesRepId,rating) salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return? SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C.salesRepId = E.empId AND(GATEC.rating<>’GOOD’);
A
Names of all the employees with at least one of their customers having a ‘GOOD’ rating.
B
Names of all the employees with at most one of their customers having a ‘GOOD’ rating.
C
Names of all the employees with none of their customers having a ‘GOOD’ rating.
D
Names of all the employees with all their customers having a ‘GOOD’ rating
GATE 2014 SET 3
Question 229

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________

Submit
Algorithms GATE 2019
Question 230
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
A
θ(n)
B
θ(m)
C
θ(m+n)
D
θ(mn)
Data Structures Graphs GATE 2008 CS
Question 231
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
  
A
MNOPQR
B
NQMPOR
C
QMNPRO
D
QMNPOR
Data Structures GATE 2017 SET2 Graphs GATE 2008 CS
Question 232
Consider the following functions: f (n) = 2n g(n) = n! h (n) = nlogn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
A
f(n) = O(g(n)); g(n) = O(h(n))
B
f(n) = Ω(g(n)); g(n) = O(h(n))
C
g(n) = O(f(n)); h(n) = O(f(n))
D
h(n) = O(f(n)); g(n) = Ω(f(n))
Algorithms Time-Complexity GATE 2008 CS
Question 233
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
A
θ(n)
B
θ(logn)
C
θ(log*n)
D
θ(1)
Algorithms Time-Complexity GATE 2008 CS
Question 234
G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
A
For every subset of k vertices, the induced subgraph has at most 2k–2 edges
B
The minimum cut in G has at least two edges
C
There are two edge-disjoint paths between every pair to vertices
D
There are two vertex-disjoint paths between every pair of vertices
Data Structures Graphs GATE 2008 CS
Question 235
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
A
T(n) ≤ 2T(n/5) + n
B
T(n) ≤ T(n/5) + T(4n/5) + n
C
T(n) ≤ 2T(4n/5) + n
D
T(n) ≤ 2T(n/2) + n
Algorithms Sorting GATE 2008 CS
Question 236
Dijkstra’s single source shortest path algorithm when run from vertex in the above graph, computes the correct shortest path distance to   
A
only vertex a
B
only vertices a, e, f, g, h
C
only vertices a, b, c, d
D
all the vertices
Algorithms Shortest-Path GATE 2008 CS
Question 237
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
A
θ(log n)
B
θ(n)
C
θ(nlog n)
D
None of the above, as the tree cannot be uniquely determined
Data Structures Binary-Trees GATE 2008 CS
Question 238
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
A
θ(log n)
B
θ(n)
C
θ(nlog n)
D
θ(n2)
Data Structures Heap-Tree GATE 2008 CS
Question 239
Let xn denote the number of binary strings of length n that contain no consecutive 0s. Which of the following recurrences does xn satisfy?
A
xn = 2xn-1
B
xn = x⌊n/2⌋+1
C
xn = x⌊n/2⌋+n
D
xn = xn-1+xn-2
Algorithms GATE 2008 CS Recurrence
Question 240
Let xn denote the number of binary strings of length n that contain no consecutive 0s. The value of x5 is  
A
5
B
7
C
8
D
16
Algorithms GATE 2008 CS Recurrence
© 2024 - All rights are reserved- AAIC Technologies pvt ltd