Follow questions have been asked in GATE CS exam.
1 In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003)
a) Θ(n log n)
b) Θ(n)
c) Θ(log n)
d) Θ(1)
Answer(d)
The 7th smallest element must be in first 7 levels. Total number of nodes in any Binary Heap in first 7 levels is at most 1 + 2 + 4 + 8 + 16 + 32 + 64 which is a constant. Therefore we can always find 7th smallest element in Θ(1) time.
2. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree? (GATE CS 2003)
a) 7 5 1 0 3 2 4 6 8 9
b) 0 2 4 3 1 6 5 9 8 7
c) 0 1 2 3 4 5 6 7 8 9
d) 9 8 6 4 2 3 0 1 5 7
Answer (c)
In-order traversal of a BST gives elements in increasing order. So answer c is correct without any doubt.
3. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is (GATE CS 2003)
a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X
Answer(c)
Following questions have been asked in GATE CS exam.
1. Consider the following functions
Which of the following is true? (GATE CS 2000)
(a) h(n) is 0(f(n))
(b) h(n) is 0(g(n))
(c) g(n) is not 0(f(n))
(d) f(n) is 0(g(n))
Answer (d)
g(n) = 2√n Log n = n√n
f(n) and g(n) are of same asymptotic order and following statements are true.
f(n) = O(g(n))
g(n) = O(f(n)).
(a) and (b) are false because n! is of asymptotically higher order than n√n.
2. Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false? (GATE CS 2000)
(a) Every minimum spanning tree of G must contain emin
(b) If emax is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains emax
(d) G has a unique minimum spanning tree
Answer (c)
(a) and (b) are always true.
(c) is false because (b) is true.
(d) is true because all edge weights are distinct for G.
3. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true? (GATE CS 2000)
(a) {u,v} must be an edge in G, and u is a descendant of v in T
(b) {u,v} must be an edge in G, and v is a descendant of u in T
(c) If {u,v} is not an edge in G then u is a leaf in T
(d) If {u,v} is not an edge in G then u and v must have the same parent in T
Answer (c)
See http://geeksquiz.com/data-structures-graph-question-20/ for explanation.
4. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct? (GATE CS 2001)
a) d(r, u) < d (r, v) b) d(r, u) > d(r, v)
c) d(r, u) <= d (r, v) d) None of the above
Answer (c) d(r, u) and d(r, v) will be equal when u and v are at same level, otherwise d(r, u) will be less than d(r, v)
5. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ? (GATE CS 2001)
a) n(n-l)/2
b) 2^n
c) n!
d) 2^(n(n-1)/2)
Answer (d)
In an undirected graph, there can be maximum n(n-1)/2 edges. We can choose to have (or not have) any of the n(n-1)/2 edges. So, total number of undirected graphs with n vertices is 2^(n(n-1)/2).
Following questions have been asked in GATE CS 2006 exam.
1. In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0(1)
Answer (A)
In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)
12
/ \
/ \
8 7
/ \ / \
/ \ / \
2 3 4 5
2. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be. (GATE CS 2006)
(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1
Answer (D)
For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.
A
\
\
B
\
\
C
\
\
D
3. Which one of the following in place sorting algorithms needs the minimum number of swaps? (GATE CS 2006)
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort
Answer (C)
For selection sort, number of swaps required is minimum ( Θ(n) ).
4. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array (GATE CS 2006)
(A) Solves it in linear time using a left to right pass of the array
(B) Solves it in linear time using a right to left pass of the array
(C) Solves it using divide and conquer in time 8(nlogn)
(D) Solves it in time 8(n2)
Answer (B)
Please see this post for explanation.
5. Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)
(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2
Answer (B)
Minimum spanning tree of such a graph is
v1
\
v2
\
v3
\
v4
.
.
.
vn
Weight of the minimum spanning tree
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2
Following questions have been asked in GATE CS exam.
1. The usual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will (GATE CS 2003)
(a) remain Θ(n^2)
(b) become Θ(n(log n)^2)
(c) become Θ(n log n)
(d) become Θ(n)
Answer (a)
If we use binary search then there will be ⌈ Log2(n!) ⌉ comparisons in the worst case, which is Θ(n log n) ( If you want to know how ⌈ Log2(n!) ⌉ can be equal to Θ(n log n)), then see this for proof). But the algorithm as a whole will still have a running time of Θ(n^2) on average because of the series of swaps required for each insertion.
Reference:
http://en.wikipedia.org/wiki/Insertion_sort
2. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
a) n
b) n^2
c) nlogn
d) n(log^2)n
Answer (c)
The number of comparisons that a comparison sort algorithm requires increases in proportion to nlog(n), where n is the number of elements to sort. This bound is asymptotically tight:
Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are n factorial permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutations. If the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2^f(n) cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,
2^f(n) >= n!, or equivalently f(n) > Log2(n!).
References:
http://en.wikipedia.org/wiki/Comparison_sort
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0130.pdf
3. The problem 3-SAT and 2-SAT are
a) both in P
b) both NP complete
c) NP-complete and in P respectively
d) undecidable and NP-complete respectively
Answer (c)
The Boolean satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The problem is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true? A formula of propositional logic is said to be satisfiable if logical values can be assigned to its variables in a way that makes the formula true.
3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT), when each clause contains exactly k = 3 and k = 2 literals respectively.
2-SAT is P while 3-SAT is NP Complete. (See this for explanation)
References:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
4. Consider the following graph
Among the following sequences
I) a b e g h f
II) a b f e h g
III) a b f h g e
IV) a f g h b e
Which are depth first traversals of the above graph? (GATE CS 2003)
a) I, II and IV only
b) I and IV only
c) II, III and IV only
d) I, III and IV only
Answer (d)
Following questions have been asked in GATE CS exam.
1. Consider the following C function.
float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } |
For large values of y, the return value of the function f best approximates (GATE CS 2003)
a) x^y
b) e^x
c) ln(1 + x)
d) x^x
Answer (b)
The function f() is implementation of Taylor’s Series to calculates e^x
e^x = 1 + x + x^2/2! + x^3/3! + ---
More is the value of y more precise value of e^x will be returned by f()
References:
http://en.wikipedia.org/wiki/E_%28mathematical_constant%29
2. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)
a) log 2 n
b) n/2
c) log 2 n – 1
d) n
Answer(d)
In the worst case, the element to be searched has to be compared with all elements of linked list.
3. The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.
Answer (a)
4. Consider the following three claims
I (n + k)^m = Θ(n^m), where k and m are constants
II 2^(n + 1) = 0(2^n)
III 2^(2n + 1) = 0(2^n)
Which of these claims are correct? (GATE CS 2003)
(a) I and II
(b) I and III
(c) II and III
(d) I, II and III
Answer(a)
(I) (n+m)^k = n^k + c1*n^(k-1) + ... k^m = Θ(n^k)
(II) 2^(n+1) = 2*2^n = O(2^n)
5. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is (GATE CS 2004)
a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
b) top1 + top2 = MAXSIZE
c) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
d) top1= top2 -1
Answer(d)
If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)
1. Consider the following C program segment
struct CellNode{ struct CelINode *leftchild; int element; struct CelINode *rightChild;}int Dosomething(struct CelINode *ptr){ int value = 0; if (ptr != NULL) { if (ptr->leftChild != NULL) value = 1 + DoSomething(ptr->leftChild); if (ptr->rightChild != NULL) value = max(value, 1 + DoSomething(ptr->rightChild)); } return (value);} |
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is (GATE CS 2004)
a) The number of leaf nodes in the tree
b) The number of nodes in the tree
c) The number of internal nodes in the tree
d) The height of the tree
Answer: (d)
Explanation: DoSomething() returns max(height of left child + 1, height of left child + 1). So given that pointer to root of tree is passed to DoSomething(), it will return height of the tree. Note that this implementation follows the convention where height of a single node is 0.
2. Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (GATE CS 2004)
a) P, Q, R, S, T, U
b) P, Q, R, U, S, T
c) P, Q, R, U, T, S
d) P, Q, T, R, U, S
Answer (b)
3. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (GATE CS 2004)
a) union only
b) intersection, membership
c) membership, cardinality
d) union, intersection
Answer (d)
Cardinality and membership are definitely not the slowest one. For cardinality, just count the number of nodes in a list. For membership, just traverse the list and look for a match
For getting intersection of L1 and L2, search for each element of L1 in L2 and print the elements we find in L2.
There can be many ways for getting union of L1 and L2. One of them is as follows
a) Print all the nodes of L1 and print only those which are not present in L2.
b) Print nodes of L2.
4. The time complexity of the following C function is (assume n > 0 (GATE CS 2004)
int recursive (mt n){ if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1));} |
a) 0(n)
b) 0(nlogn)
c) 0(n^2)
d) 0(2^n)
Answer(d)
Explanation:
Recursive expression for the above program will be.
T(n) = 2T(n-1) + c
T(1) = c1.
Let us solve it.
T(n) = 2(2T(n-2) + c) + c = 4T(n-2) + 3c T(n) = 8T(n-3) + 6c + c = 8T(n-3) + 7c T(n) = 16T(n-4) + 14c + c = 16T(n-4) + 15c ............................................................ ............................................................. T(n) = (2^(n-1))T(1) + (2^(n-1) - 1)c T(n) = O(2^n)
Following questions have asked in GATE CS exam.
1. Suppose you are given an array s[1…n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence
do, where 1 < k <= n: reverse (s, 1, k); reverse (s, k + 1, n); reverse (s, 1, n);
(GATE CS 2000)
(a) Rotates s left by k positions
(b) Leaves s unchanged
(c) Reverses all elements of s
(d) None of the above
Answer: (a)
Effect of the above 3 reversals for any k is equivalent to left rotation of the array of size n by k. Please see this post for details.
If we rotate an array n times for k = 1 to n, we get the same array back.
2. The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004)
a) queue
b) stack
c) tree
d) list
Answer(b)
There are three types of parentheses [ ] { } (). Below is an arbit c code segment which has parentheses of all three types.
void func(int c, int a[]){ return ((c +2) + arr[(c-2)]) ; } |
Stack is a straightforward choice for checking if left and right parentheses are balanced. Here is a algorithm to do the same.
/*Return 1 if expression has balanced parentheses */bool areParenthesesBalanced(expression ){ for each character in expression { if(character == ’(’ || character == ’{’ || character == ’[’) push(stack, character); if(character == ’)’ || character == ’}’ || character == ’]’) { if(isEmpty(stack)) return 0; /*We are seeing a right parenthesis without a left pair*/ /* Pop the top element from stack, if it is not a pair bracket of character then there is a mismatch. This will happen for expressions like {(}) */ else if (! isMatchingPair(pop(stack), character) ) return 0; } } if(isEmpty(stack)) return 1; /*balanced*/ else return 0; /*not balanced*/} /* End of function to check parentheses *//* Returns 1 if character1 and character2 are matching left and right parentheses */bool isMatchingPair(character1, character2){ if(character1 == ‘(‘ && character2 == ‘)’) return 1; else If(character1 == ‘{‘ && character2 == ‘}’) return 1; else If(character1 == ‘[‘ && character2 == ‘]’) return 1; else return 0;} |
3. Level order traversal of a rooted tree can be done by starting from the root and performing (GATE CS 2004)
a) preorder traversal
b) in-order traversal
c) depth first search
d) breadth first search
Answer(d)
See this post for details
4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value
(GATE CS 2004)
a) i only
b) ii only
c) i and ii only
d) iii or iv
Answer (c)
5. Postorder traversal of a given binary search tree, T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (GATE CS 2005)
a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Answer (a)
Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.
Following questions have been asked in GATE CS exam. 1. Consider the function f defined below.For a given linked list p, the function f returns 1 if and only if (GATE CS 2003) a) the list is empty or has exactly one element b) the elements in the list are sorted in non-decreasing order of data value c) the elements in the list are sorted in non-increasing order of data value d) not all elements in the list have the same data value. Answer (b) The function f() works as follows 1) If linked list is empty return 1 2) Else If linked list has only one element return 1 3) Else if node->data is smaller than equal to node->next->data and same thing holds for rest of the list then return 1 4) Else return 0
structitem{intdata;structitem * next;};intf(structitem *p){return((p == NULL) ||(p->next == NULL) ||(( P->data <= p->next->data) && f(p->next)));}
2. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely (GATE CS 2004)? i) preorder and postorder ii) inorder and postorder iii) preorder and inorder iv) level order and postorder a) (i) only b) (ii), (iii) c) (iii) only d) (iv) only Answer (b) Please see http://geeksforgeeks.org/?p=657 for explanation.
3. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004) a) 2 b) 3 c) 4 d) 6 Answer(b) Constructed binary search tree will be..10 / \ 1 15 \ / \ 3 12 16 \ 5
4. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.
o Delection of the smallest element o Insertion of an element if it is not already present in the setWhich of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be usedAnswer(b)
A self-balancing balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a self balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element (See http://geeksforgeeks.org/?p=1333).Since Heap is a balanced binary tree (or almost complete binary tree), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapify(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present. For a heap, we cannot find out in O(logn) if an element is present or not. Thanks to game for providing the correct solution.
5. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? (GATE 2004)
a) rear node
b) front node
c) not possible with a single pointer
d) node next to frontAnswer(a)
Answer is not “(b) front node”, as we can not get rear from front in O(1), but if p is rear we can implement both enQueue and deQueue in O(1) because from rear we can get front in O(1). Below are sample functions. Note that these functions are just sample are not working. Code to handle base cases is missing.
/* p is pointer to address of rear (double pointer). This function adds newnode after rear and updates rear which is *p to point to new node */voidenQueue(structnode **p,structnode *new_node){/* Missing code to handle base cases like *p is NULL */new_node->next = (*p)->next;(*p)->next = new_node;(*p) = new_node/* new is now rear *//* Note that p is again front and p->next is rear */}/* p is pointer to rear. This function removes the front element andreturns the new front */structnode *deQueue(structnode *p){/* Missing code to handle base cases like p is NULL,p->next is NULL,... etc */structnode *temp = p->next->next;p->next = p->next->next;returntemp;/* Note that p is again front and p->next is rear */}
Following questions have been asked in GATE CS exam1. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true? (GATE CS 2000)
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the aboveAnswer (d)
It is given that the given tree is complete binary tree. For a complete binary tree, the last visited node will always be same for inorder and preorder traversal. None of the above is true even for a complete binary tree.
The option (a) is incorrect because the last node visited in Inorder traversal is right child and last node visited in Postorder traversal is root.
The option (c) is incorrect because the last node visited in Preorder traversal is right child and last node visited in Postorder traversal is root.
For option (b), see the following counter example. Thanks to Hunaif Muhammed for providing the correct explanation.
1 / \ 2 3 / \ / 4 5 6 Inorder traversal is 4 2 5 1 6 3 Preorder traversal is 1 2 4 5 3 6
2. The most appropriate matching for the following pairsX: depth first search 1: heap Y: breadth-first search 2: queue Z: sorting 3: stackis (GATE CS 2000):
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y—3 Z-1Answer: (c)
Stack is used for Depth first Search
Queue is used for Breadth First Search
Heap is used for sorting
3. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
(a) (1 2 (4 5 6 7))
(b) (1 (2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))Answer (c)
4. Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true? (GATE CS 2000)
a) t (n) is 0 (1)
b) n < t (n) < n log2n
c) n log2n < t (n) < nC2
d) t (n) = nC2Answer (a)
Let array be sorted in ascending order, if sum of first two elements is less than 1000 then there are two elements with sum less than 1000 otherwise not. For array sorted in descending order we need to check last two elements. For an array data structure, number of operations are fixed in both the cases and not dependent on n, complexity is O(1)
5. B+ trees are preferred to binary trees in databases because (GATE CS 2000)
(a) Disk capacities are greater than memory capacities
(b) Disk access is much slower than memory access
(c) Disk data transfer rates are much less than memory data transfer rates
(d) Disks are more reliable than memoryAnswer (b)
Disk access is slow and B+ Tree provide search in less number of disk hits. This is primarily because unlike binary seach trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
