Following questions have been asked in GATE CS exam
1. 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 above
Answer (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.
2. The most appropriate matching for the following pairs
(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-1
Answer: (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
c) n log 2 n < t (n) <
d) t (n) =
Answer (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 memory
Answer (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.
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
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)
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..
(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 used
Answer(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 BST, we can easily find out minimum element in O(nlogn).
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 front
Answer(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.
1. Consider the following C program segment
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 (a)
Cardinality and membership are definably 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.
All of these methods will require more operations than intersection as we have to process intersection node plus other nodes.
4. The time complexity of the following C function is (assume n > 0 (GATE CS 2004)
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.
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. 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)
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.
1. Consider the following C function.
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
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)
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. 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
comparisons in the worst case, which is 
(n log n) ( If you want to know how 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)[Tex]\log_2[/Tex](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)
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)
(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) 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 ,v} such that the weight of the edge (v,,v) 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
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2
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^
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^.
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)
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).
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(c)
Given a Min-heap, to get the 7th smallest element, we need to call Extract-Min 7 times which means(7logn)( = (logn)) operations
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)
We can easily arrive at the result by taking few examples.
1. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
(A) 2^h -1
(B) 2^(h-1) – 1
(C) 2^(h+1) -1
(D) 2*(h+1)
Answer (C)
Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1
2: The maximum number of binary trees that can be formed with three unlabeled nodes is:
(A) 1
(B) 5
(C) 4
(D) 3
Answer (B)
3. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort
(B) Bubble sort
(C) Quick sort
(D) Selection sort
Answer (A)
Worst case complexities for the above sorting algorithms are as follows:
Merge Sort — nLogn
Bubble Sort — n^2
Quick Sort — n^2
Selection Sort — n^2
4. The following postfix expression with single digit operands is evaluated using a stack:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
Answer (A)
The algorithm for evaluating any postfix expression is fairly straightforward:
Let us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows
5. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
(A) d e b f g c a
(B) e d b g f c a
(C) e d b f g c a
(D) d e f g b c a
Answer (A)
Please see http://lcm.csa.iisc.ernet.in/dsa/node38.html for closed hashing and probing.
Let us put values 1, 3, 8, 10 in the hash of size 7.
Initially, hash table is empty
- - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0
1 - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6
1 - - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 8 is 0, but 0 is already occupied, let us put the value(8) at next available space(1)
1 8 - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 10 is 6, but 6 is already occupied, let us put the value(10) at next available space(2)
1 8 10 - - - 3 0 1 2 3 4 5 6
2. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
(A) Dijkstra’s algorithm starting from S.
(B) Warshall’s algorithm
(C) Performing a DFS starting from S.
(D) Performing a BFS starting from S.
Answer(D)
* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E) * Time Comlexity of the Warshall’s algorithm is O(|V|^3) * DFS cannot be used for finding shortest paths * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)
3. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
(A) 3
(B) 4
(C) 5
(D) 6
Answer (C)
For an n-ary tree where each node has n children or no children, following relation holds
L = (n-1)*I + 1 Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data.
L = 41 , I = 10 41 = 10*(n-1) + 1 (n-1) = 4 n = 5
4. In the following C function, let n >= m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?
(A)(logn)?
(B)
(n)
(C)(loglogn)
(D)(sqrt(n))
Answer (A)
Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).
Please see http://mathworld.wolfram.com/EuclideanAlgorithm.html for time complexity.
5. What is the time complexity of the following recursive function:
int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); } (A)(n)
(B)(nlogn)
(C)(logn)
(D)(loglogn)
Answer (D)
Recursive relation for the DoSomething() is
T(n) = T(
) + C1 if n > 2 We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.
Let n = 2^m, T(n) = T(2^m) Let T(2^m) = S(m) From the above two, T(n) = S(m) S(m) = S(m/2) + C1 /* This is simply binary search recursion*/ S(m) = O(logm) = O(loglogn) /* Since n = 2^m */ Now, let us go back to the original recursive function T(n) T(n) = S(m) = O(LogLogn)
1. Consider the following C program segment where CellNode represents a node in a binary tree:
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
(A) the number of nodes in the tree
(B) the number of internal nodes in the tree
(C) the number of leaf nodes in the tree
(D) the height of the tree
Answer (C)
2. Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
(A)(logn)
(B)(LogLogn )
(C)(n)
(D)(nLogn)
Answer (B)
The height of a Max Heap is(logn). If we perform binary search for finding the correct position then we need to do (LogLogn) comparisons.
3. Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?
(A) There is a minimum spanning tree containing e.
(B) If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
(C) Every minimum spanning tree has an edge of weight w .
(D) e is present in every minimum spanning tree.
Answer (D)
(A), (B) and (C) are correct.
(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.
4. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
(A) At least 2n – c comparisons, for some constant c, are needed.
(B) At most 1.5n – 2 comparisons are needed.
(C) At least nLog2n comparisons are needed.
(D) None of the above.
Answer (B)
5. Consider the following C code segment:
Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
(A) T(n) = O(sqrt(n)) and T(n) =(sqrt(n))
(B) T(n) = O(sqrt(n)) and T(n) =(1)
(C) T(n) = O(n) and T(n) =(sqrt(n))
(D) None of the above
Answer (B)
Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.
The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) =(1)
1. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
a) n/2
b) (n-1)/3
c) (n-1)/2
d) (2n+1)/3
Answer(d)
Let L be the number of leaf nodes and I be the number of internal nodes, then following relation holds for above given tree
2. The running time of the following algorithm
a) O(n)
b) O(log n)
c) O(1og log n)
d) O(1)
Answer(c)
3. A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
a)
b)
c)
d)
Answer(d)
Let the maximum possible height of a tree with n nodes is represented by H(n).
The maximum possible value of H(n) can be approximately written using following recursion
. We can simply get it by drawing a recursion tree.
4. Consider the following algorithm for searching for a given number x in an unsorted – array A[1..n] having n distinct values:
a) n
b) n-l
c) 2n
d) n/2
Answer(a)
If you remember the coin and dice questions, you can just guess the answer for the above.
Below is proof for the answer.
Let expected number of comparisons be E. Value of E is sum of following expression for all the possible cases.
(A)(logn)
(B)(n)
(C)(nlogn)
(D)(n^2)
Answer(C)
The worst case time complexity for insertion in a binary heap is O(Logn) (Refer Wiki). So inserting n elements in a heap of size n should take(nlogn) time.
2. 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
Answer (C)
3. Consider the following functions:
f(n) = 2^n g(n) = n! h(n) = n^logn 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))
Answer (D)
According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) )
We can easily see above order by taking logs of the given 3 functions
lognlogn < n < log(n!) (logs of the given f(n), g(n) and h(n)). Note that log(n!) =(nlogn)
4. 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)(n)
Answer (B)
1. 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)
Answer (C)
Connected components can be found in O(m + n) using Tarjan’s algorithm. Once we have connected components, we can count them.
2. 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
Answer (B)
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot.
If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
3 Dijkstra’s single source shortest path algorithm when run from vertex a in the below 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
Answer (D)
Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.
Let us see…
Let us run the 1st pass
b 1
b is minimum, so shortest distance to b is 1.
After 1st pass, distances are
c 3, e -2.
e is minimum, so shortest distance to e is -2
After 2nd pass, distances are
c 3, f 0.
f is minimum, so shortest distance to f is 0
After 3rd pass, distances are
c 3, g 3.
Both are same, let us take g. so shortest distance to g is 3.
After 4th pass, distances are
c 3, h 5
c is minimum, so shortest distance to c is 3
After 5th pass, distances are
h -2
h is minimum, so shortest distance to h is -2
4. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
(A) 1,2,3,4,5,6,7
(B) 2,1,4,3,6,5,7
(C) 1,3,2,5,4,7,6
(D) 2,3,4,5,6,7,1
Answer (B)
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.
1. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D) 25,14,12,13,10,8,16
Answer (C)
A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data.
In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.
(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10
Answer(D)
For Heap trees, deletion of a node includes following two operations.
1) Replace the root with last element on the last level.
2) Starting from root, heapify the complete tree from top to bottom..
Let us delete the two nodes one by one:
1) Deletion of 25:
Replace 25 with 12
Replace 16 with 8
(A)(n)
(B)(nLogn)
(C)(n^2)
(D)(n^2 log n)
Answer(B)
The recursion expression becomes:
T(n) = T(n/4) + T(3n/4) + cn
After solving the above recursion, we get(nLogn).
4. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
(A) 2
(B) 3
(C) 4
(D) 5
Answer(B)
AVL trees are binary trees with the following restrictions.
1) the height difference of the children is at most 1.
2) both children are AVL trees
http://en.wikipedia.org/wiki/AVL_tree
1. An implementation of a queue Q, using two stacks S1 and S2, is given below:
(A) n+m <= x < 2n and 2m <= y <= n+m
(B) n+m <= x < 2n and 2m<= y <= 2n
(C) 2m <= x < 2n and 2m <= y <= n+m
(D) 2m <= x <2n and 2m <= y <= 2n
Answer(A)
The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())
2. Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?(A) (a—b),(d—f),(b—f),(d—c),(d—e)
(B) (a—b),(d—f),(d—c),(b—f),(d—e)
(C) (d—f),(a—b),(d—c),(b—f),(d—e)
(D) (d—f),(a—b),(b—f),(d—e),(d—c)
Answer (D)
The edge (d-e) cannot be considered before (d-c) in Kruskal’s minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.
3. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
(A)(n)
(B)(nlogn)
(C)(n^2)
(D)(n^3)
Answer (B)
If median is always used as pivot, then recursion remains T(n) = 2T(n/2) + cn for all the cases where cn is combined time for median finding and partition. So, worst case time complexity of this quick sort becomes(nlogn). In practical implementations, however, this variant is considerably slower on average (seehttp://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting)
1. Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
Answer (A)
Multiplications can be minimized using following order for evaluation of the given expression.
p(x) = a0 + x(a1 + x(a2 + a3x))
2. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
(A) Queue
(B) Stack
(C) Heap
(D) B-Tree
Answer(A)
The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.
3. A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1
Answer (D)
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer(A)
(A) There is no polynomial time algorithm for X.
(B) If X can be solved deterministically in polynomial time, then P = NP.
(C) If X is NP-hard, then it is NP-complete.
(D) X may be undecidable.
Answer (C)
(A) is incorrect because set NP includes both P(Polynomial time solvable) and NP-Complete .
(B) is incorrect because X may belong to P (same reason as (A))
(C) is correct because NP-Complete set is intersection of NP and NP-Hard sets.
(D) is incorrect because all NP problems are decidable in finite set of operations.
2. What is the number of swaps required to sort n elements using selection sort, in the worst case?
(A)(n)
(B)(n log n)
(C)(n^2 )
(D)(n^2 log n)
Answer (A)
Here is Selection Sort algorithm for sorting in ascending order.
1. Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) As we can see from the algorithm, selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort.
Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.
References:
http://en.wikipedia.org/wiki/Selection_sort
3. The running time of an algorithm is represented by the following recurrence relation:
if n <= 3 then T(n) = n else T(n) = T(n/3) + cn Which one of the following represents the time complexity of the algorithm?
(A)(n)
(B)(n log n)
(C)(n^2)
(D)(n^2log n)
Answer(A)
T(n) = cn + T(n/3) = cn + cn/3 + T(n/9) = cn + cn/3 + cn/9 + T(n/27) Taking the sum of infinite GP series. The value of T(n) will be less than this sum. T(n) <= cn(1/(1-1/3)) <= 3cn/2 or we can say cn <= T(n) <= 3cn/2 Therefore T(n) =(n) This can also be solved using Master Theorem for solving recurrences. The given expression lies in Case 3 of the theorem.
4. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
Answer (C)
To get the idea of open addressing concept, you can go through below lines from Wikipedia
.
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:
linear probing in which the interval between probes is fixed–often at 1.
quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function).
double hashing in which the interval between probes is fixed for each record but is computed by another hash function.
1. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
Answer (B)
(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.
(B) Correct because a NP Complete problem S is polynomial time educable to R.
(C) Incorrect because Q is not in NP.
(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.
2) A set X can be represented by an array x[n] as follows:
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
(A) (X Intersection Y)
(B) (X Union Y)
(C) (X-Y) Intersection (Y-X)
(D) (X-Y) Union (Y-X)
Answer (D)
The expression x[i] ^ ~y[i]) results the only 1s in x where corresponding entry in y is 0. An array with these set bits represents set X – Y
The expression ~x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 0. An array with these set bits represents set Y – X.
The operator “V” results in Union of the above two sets.
3. Consider the following recurrence:
Which one of the following is true?
(A) T(n) =(loglogn)
(B) T(n) =(logn)
(C) T(n) =(sqrt(n))
(D) T(n) =(n)
Answer (B)
(m). You can also prove using Master theorem.
(A) X[i, j] = X[i - 1, j] V X[i, j -ai]
(B) X[i, j] = X[i - 1, j] V X[i - 1, j - ai]
(C) X[i, j] = X[i - 1, j] V X[i, j - ai]
(D) X[i, j] = X[i - 1, j] V X[i -1, j - ai]
Answer (B)
X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true
1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true.
2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.
2. In question 1, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
(A) X[1, W]
(B) X[n ,0]
(C) X[n, W]
(D) X[n -1, n]
Answer (C)
If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.
Reference: http://en.wikipedia.org/wiki/Subset_sum_problem
3. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
On which of the following contents of Y and x does the program fail?
(A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
(B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
(C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
(D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Answer (C)
The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.
4. In question 3, the correction needed in the program to make it work properly is
(A) Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
(B) Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
(C) Change line 6 to: if (Y[k] <= x) i = k; else j = k;
(D) Change line 7 to: } while ((Y[k] == x) && (i < j));
Answer (A)
Below is the corrected function
Reference: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations
1) A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
(a) An array of 50 numbers
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers
Answer (a)
An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value/
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?
(a) Graph G has no minimum spanning tree (MST)
(b) Graph G has a unique MST of cost n-1
(c) Graph G has multiple distinct MSTs, each of cost n-1
(d) Graph G has multiple spanning trees of different costs
Answer (c)
If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1. See the below example.
The connected graph:
Below are three Minimum Spanning trees each of cost 2.0.
Minimum Spanning Tree 1
Minimum Spanning Tree 2
Minimum Spanning Tree 3
3) The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:
a) O(n)
b) O(nLogn)
c) O(n^(3/2))
d) O(n^3)
Answer (d)
In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.
In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node other node b in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed in an O(1) operation one may determine that node c is reachable from node a.
Warshall’s algorithm can be used to construct the Transitive closure of directed graphs (). In Warshall’s original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).
References:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://en.wikipedia.org/wiki/Transitive_closure
4. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
(a) 10, 8, 7, 5, 3, 2, 1
(b) 10, 8, 7, 2, 3, 1, 5
(c) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5
Answer (D)
Original Max-Heap is:
(a) Database relations have a large number of records
(b) Database relations are sorted on the primary key
(c) B-trees require less memory than binary search trees
(d) Data transfer form disks is in blocks.
Answer (d)
A disk block contains fairly large number of keys. Unlike BST where each node contains only one key, B-Tree is designed to contain large number of keys so that tree height is small.
2. How many distinct binary search trees can be created out of 4 distinct keys?
(a) 5
(b) 14
(c) 24
(d) 42
Answer (b)
Here is a systematic way to enumerate these BSTs. Consider all possible binary search trees with each element at the root. If there are n nodes, then for each choice of root node, there are n – 1 non-root nodes and these non-root nodes must be partitioned into those that are less than a chosen root and those that are greater than the chosen root.
Let’s say node i is chosen to be the root. Then there are i – 1 nodes smaller than i and n – i nodes bigger than i. For each of these two sets of nodes, there is a certain number of possible subtrees.
Let t(n) be the total number of BSTs with n nodes. The total number of BSTs with i at the root is t(i – 1) t(n – i). The two terms are multiplied together because the arrangements in the left and right subtrees are independent. That is, for each arrangement in the left tree and for each arrangement in the right tree, you get one BST with i at the root.
Summing over i gives the total number of binary search trees with n nodes.
The base case is t(0) = 1 and t(1) = 1, i.e. there is one empty BST and there is one BST with one node.
3. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:
(a) nk
(b) (n – 1) k+ 1
(c) n( k – 1) + 1
(d) n(k – 1)
Answer (c)
4) Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false.
a) T(n) = O(n^2)
b) T(n) =(nLogn)
c) T(n) =(n^2)
d) T(n) = O(nLogn)
Answer (c)
The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).
T(n) =(nLogn)
By definition of Big O notation, we can say.
(nLogn) = O(nLogn) = O(n^2)
(nLogn) ca be equal to (n) or (nLogn), but not (n^2)
1. The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
Answer(D)
When the while loop ends, q contains address of second last node and p contains address of last node. So we need to do following things after while loop.
i) Set next of q as NULL (q->next = NULL).
ii) Set next of p as head (p->next = head).
iii) Make head as p ( head = p)
Step (ii) must be performed before step (iii). If we change head first, then we lose track of head node in the original linked list.
2. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52
Answer (C)
The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.
3. How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?(A) 10
(B) 20
(C) 30
(D) 40
Answer (C)
In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33.
Total number of different sequences = 3! x 5 = 30
In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.
1 Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
(A) 7
(B) 8
(C) 9
(D) 10
Answer (D)
To get the minimum spanning tree with vertex 0 as leaf, first remove 0th row and 0th column and then get the minimum spanning tree (MST) of the remaining graph. Once we have MST of the remaining graph, connect the MST to vertex 0 with the edge with minimum weight (we have two options as there are two 1s in 0th row).
2. In the graph given in question 1, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
(A) 7
(B) 8
(C) 9
(D) 10
Answer (B)
Path: 1 -> 0 -> 4 -> 2
Weight: 1 + 4 + 3
3. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II
(B) III and IV
(C) IV only
(D) II and IV
Answer (D)
In sequence IV, we have a vertex with degree 8 which is not possible in a simple graph (no self loops and no multiple edges) with total vertex count as 8. Maximum possible degree in such a graph is 7.
In sequence II, four vertices are connected to 6 other vertices, but remaining 4 vertices have degrees as 3, 3, 2 and 2 which are not possible in a simple graph (no self loops and no multiple edges).
4. Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
(A) 1
(B) 2
(C) 3
(D) 4
Answer (B)
Since the maximum number of keys is 5, maximum number of children a node can have is 6. By definition of B Tree, minimum children that a node can have would be 6/2 = 3. Therefore, minimum number of keys that a node can have becomes 2 (3-1).
1) A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap?
Answer: (B)
A binary tree is max-heap if it is a complete binary tree (A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible) and it follows the max-heap property (value of each parent is greater than or equal to the values of its children).
A) is not a max-heap because it is not a complete binary tree
B) is a max-heap because it is complete binary tree and follows max-heap property.
C) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property.
D) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property. There are many other nodes in this tree which violate max-heap property in this tree.
2) Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
A) 248000
B) 44000
C) 19000
D) 25000
Answer (C)
We get minimum number of multiplications using ((M1 X (M2 X M3)) X M4).
Total number of multiplications = 100x20x5 (for M2 x M3) + 10x100x5 + 10x5x80 = 19000.
3) Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
A) f3, f2, f4, f1
B) f3, f2, f1, f4
C) f2, f3, f1, f4
D) f2, f3, f4, f1
Answer (A)
4) We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
A) 0
B) 1
C) n!
D) (1/(n+1)).2nCn
Answer (B)
See this explanation from PeddaBoku.
5) An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Which of the following statements is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Answer: (A)
1) An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?(A) 1/12(11n^2 – 5n)
(B) n^2 – n + 1
(C) 6n – 11
(D) 2n + 1
Answer: (B)
Minimum spanning tree for 2 nodes would be
Minimum spanning tree for 3 nodes would be
Minimum spanning tree for 4 nodes would be
Minimum spanning tree for 5 nodes would be
Minimum spanning tree for 6 nodes would be
We can observe from above examples that when we add kth node, the weight of spanning tree increases by 2k-2. Let T(n) be the weight of minimum spanning tree. T(n) can be written as
T(n) = T(n-1) + (2n-2) for n > 2
T(1) = 0, T(2) = 0 and T(2) = 3
The recurrence can be written as sum of series (2n – 2) + (2n-4) + (2n-6) + (2n-8) + …. 3 and solution of this recurrence is n^2 – n + 1.
2) The length of the path from v5 to v6 in the MST of previous question with n = 10 is
(A) 11
(B) 25
(C) 31
(D) 41
Answer: (C)
Any MST which has more than 5 nodes will have the same distance between v5 and v6 as the basic structure of all MSTs (with more than 5 nodes) would be following.
3) Consider two binary operators '
' and '
' with the precedence of operator being lower than that of the operator. Operator is right associative while operator is left associative. Which one of the following represents the parse tree for expression (7 3 4 3 2)?
Answer: (B)
Let us consider the given expression (
).
Since the precedence of is higher, the sub-expression (
) will be evaluated first. In this sub-expression, 
would be evaluated first because is right to left associative. So the expression is evaluated as 
. Also, note that among the two 
operators, first one is evaluated before the second one because the associativity of is left to right.
1) Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?
(A)
(B)
(C)
(D)
Answer (C)
The worst case time complexity is always greater than or same as the average case time complexity.
2) The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
(A)
(B)
(C)
(D)
Answer (C)
Time taken to search an element is
where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be 
which is 
Which is 
which can be written as .
3) Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete
P = 
(C) NP-hard = NP
(D) P = NP-complete
Answer (B)
The answer is B (no NP-Complete problem can be solved in polynomial time). Because, if one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.
4) The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.
The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)
Answer (A)
The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one.
The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.
5) A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
(A)
(B)
(C)
(D)
Answer (B)
The recurrence tree for merge sort will have height n. And O(n^2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be.
1) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is
(A) T(n) = 2T(n – 2) + 2
(B) T(n) = 2T(n – 1) + n
(C) T(n) = 2T(n/2) + 1
(D) T(n) = 2T(n – 1) + 1
Answer (D)
Following are the steps to follow to solve Tower of Hanoi problem recursively.
T(n) = 2T(n-1) + 1
2) Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
(A) SDT
(B) SBDT
(C) SACDT
(D) SACET
Answer (D)
3) Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation 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
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Answer (A)
1) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A) P Only
B) Q Only
C) Both P and Q
D) Neither P nor Q
Answer (C)
Q is true: Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.
2) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
(A) 1/8
(B) 1
(C) 7
(D) 8
Answer (C)
A cycle of length 3 can be formed with 3 vertices. There can be total 8C3 ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (8C3)*(1/2)^3 = 7
3) What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A)
(B)
(C)
(D)
Answer (C).
Time complexity of Bellman-Ford algorithm is
where V is number of vertices and E is number edges (See this). If the graph is complete, the value of E becomes 
. So overall time complexity becomes 
4) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only
Answer (A)
1 is true because cycle detection can be done in polynomial time using DFS (See this).
2 is true because P is a subset of NP.
3 is true because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution exists. (See this)
5) Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Answer (C)
The worst case occurs for a skewed tree. In a skewed tree, when a new node is inserted as a child of bottommost node, the time for insertion requires traversal of all node. For example, consider the following tree and the case when something smaller than 70 is inserted.
6) Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)
Answer (B)
Selection sort requires only O(n) swaps. See this for details.
7) Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter
(A)
(B)
(C)
(D)
Answer (A)
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is
1) 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.
(B) 6561
(C) 55440
(D) 161051
Answer (B)
Since c is passed by value and x is passed by reference, all functions will have same copy of x, but different copies of c.
f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x*x*x = 1*x*x*x*x = x^4
Since x is incremented in every function call, it becomes 9 after f(x, 2) call. So the value of expression x^4 becomes 9^4 which is 6561.
1) 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?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30
Ans (D)
The following is the constructed tree
3) Consider the following function
(A)
(B)
(C)
(D)
Answer (B)
The outer loop runs n/2 or times. The inner loop runs 
times (Note that j is divide by 2 in every iteration). So the statement "k = k + n/2;" runs 
times. The statement increases value of k by n/2. So the value of k becomes n/2* which is
4) The number of elements that can be sorted in
time using heap sort is
(A)
(B)
(C)
(d)
Answer (C)
Time complexity of Heap Sort is
for m input elements. For m = , the value of 
will be![\Theta( [Log n/(Log Log n)] * [Log (Log n/(Log Log n))] )](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_twsCrKuu3tJDiU76tqKhOnp4wh1jpMT-JuuGoGFHdK143RHXjhM1ykkXLoTkZbWPSERx5cu0X3kyzdnWTbaLKCqIJppqaMR67mMc2qZqRWJ7mHqBvp0mXrjKjpETVi7ovwdHt5QostjU_IwGFBJD8WrUY1gcB46HeXLBBcMRUOp0xTWAXWp2fY_1I=s0-d "Rendered by QuickLaTeX.com")
which will be ![\Theta( [Log n/(Log Log n)] * [ Log Log n - Log Log Log n] )](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_utj9zyv1G-yumqeHVJOKJALQ9MWe3PX2adeKr9uS7vvIwZvhPcD3WA_Q_KyMvm7-hXatDaVhqW3d3yQjUwWTl8RsYqC_QqEL62YK1NSAm5OHjGE9lffAUobqlWurs29G3giUiCFVnK-b35-cFmQ07_esFxCYOzTPDDs7FRXRsdfel10fsuS2sn1A=s0-d "Rendered by QuickLaTeX.com")
which is
5) The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
(1) oldc = "abc", newc = "dab"
(2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda"
(4) oldc = "abc", newc = "bac"
The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?
(A) Only one
(B) Only two
(C) Only three
(D) All four
Answer (B)
The test cases 3 and 4 are the only cases that capture the flaw. The code doesn't work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This doesn't happen in test cases (1) and (2), it happens only in cases (3) and (4).
6) If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
(A) None
(B) 2 only
(C) 3 and 4 only
(D) 4 only
Answer (C)
1. 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 above
Answer (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.
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 pairs
X: 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-1
Answer: (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
c) n log 2 n < t (n) <
d) t (n) =
Answer (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 memory
Answer (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.
1. Consider the function f defined below.
struct item{ int data; struct item * next;};int f(struct item *p){ return ( (p == NULL) || (p->next == NULL) || (( P->data <= p->next->data) && f(p->next)) );} |
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
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)
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 used
Answer(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 BST, we can easily find out minimum element in O(nlogn).
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 front
Answer(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 new node after rear and updates rear which is *p to point to new node */void enQueue(struct node **p, struct node *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 and returns the new front */struct node *deQueue(struct node *p){ /* Missing code to handle base cases like p is NULL, p->next is NULL,... etc */ struct node *temp = p->next->next; p->next = p->next->next; return temp; /* Note that p is again front and p->next is rear */} 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);} |
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 (a)
Cardinality and membership are definably 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.
All of these methods will require more operations than intersection as we have to process intersection node plus other nodes.
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));} |
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)
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. 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)
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.
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 constantsII 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 =
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. 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
comparisons in the worst case, which is (n log n) ( If you want to know how 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)[Tex]\log_2[/Tex](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)
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 ,v} such that the weight of the edge (v,,v) 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
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^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^
.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)
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).
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(c)
Given a Min-heap, to get the 7th smallest element, we need to call Extract-Min 7 times which means
(7logn)( = (logn)) operations2. 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)
We can easily arrive at the result by taking few examples.
1. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
(A) 2^h -1
(B) 2^(h-1) – 1
(C) 2^(h+1) -1
(D) 2*(h+1)
Answer (C)
Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1
2: The maximum number of binary trees that can be formed with three unlabeled nodes is:
(A) 1
(B) 5
(C) 4
(D) 3
Answer (B)
O
/ \
O O
(i)
O
/
O
/
O
(ii)
O
/
O
\
O
(iii)
O
\
O
\
O
(iv)
O
\
O
/
O
(v)
Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.3. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort
(B) Bubble sort
(C) Quick sort
(D) Selection sort
Answer (A)
Worst case complexities for the above sorting algorithms are as follows:
Merge Sort — nLogn
Bubble Sort — n^2
Quick Sort — n^2
Selection Sort — n^2
4. The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
Answer (A)
The algorithm for evaluating any postfix expression is fairly straightforward:
1. While there are input tokens left
o Read the next token from input.
o If the token is a value
+ Push it onto the stack.
o Otherwise, the token is an operator
(operator here includes both operators, and functions).
* It is known a priori that the operator takes n arguments.
* If there are fewer than n values on the stack
(Error) The user has not input sufficient values in the expression.
* Else, Pop the top n values from the stack.
* Evaluate the operator, with the values as arguments.
* Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
o That value is the result of the calculation.
3. If there are more values in the stack
o (Error) The user input has too many values.
Source for algorithm: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithmLet us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows
8, 2, 3When ^ is read, top two are popped and power(2^3) is calculated
8, 8When / is read, top two are popped and division(8/8) is performed
1Next two tokens are values, so they are simply pushed. After pushing 2 and 3, the stack is as follows
1, 2, 3When * comes, top two are popped and multiplication is performed.
1, 6
5. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
(A) d e b f g c a
(B) e d b g f c a
(C) e d b f g c a
(D) d e f g b c a
Answer (A)
Below is the given tree.
a
/ \
/ \
b c
/ \ / \
/ \ / \
d e f g
1. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. (A) 8, _, _, _, _, _, 10 (B) 1, 8, 10, _, _, _, 3 (C) 1, _, _, _, _, _,3 (D) 1, 10, 8, _, _, _, 3Answer (B)
Please see http://lcm.csa.iisc.ernet.in/dsa/node38.html for closed hashing and probing.
Let us put values 1, 3, 8, 10 in the hash of size 7.
Initially, hash table is empty
- - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0
1 - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6
1 - - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 8 is 0, but 0 is already occupied, let us put the value(8) at next available space(1)
1 8 - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 10 is 6, but 6 is already occupied, let us put the value(10) at next available space(2)
1 8 10 - - - 3 0 1 2 3 4 5 6
2. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
(A) Dijkstra’s algorithm starting from S.
(B) Warshall’s algorithm
(C) Performing a DFS starting from S.
(D) Performing a BFS starting from S.
Answer(D)
* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E) * Time Comlexity of the Warshall’s algorithm is O(|V|^3) * DFS cannot be used for finding shortest paths * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)
3. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
(A) 3
(B) 4
(C) 5
(D) 6
Answer (C)
For an n-ary tree where each node has n children or no children, following relation holds
L = (n-1)*I + 1 Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data.
L = 41 , I = 10 41 = 10*(n-1) + 1 (n-1) = 4 n = 5
4. In the following C function, let n >= m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?
(A)
(logn)?(B)
(n)(C)
(loglogn)(D)
(sqrt(n))Answer (A)
Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).
Please see http://mathworld.wolfram.com/EuclideanAlgorithm.html for time complexity.
5. What is the time complexity of the following recursive function:
int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); } (A)
(n)(B)
(nlogn)(C)
(logn)(D)
(loglogn)Answer (D)
Recursive relation for the DoSomething() is
T(n) = T(
) + C1 if n > 2 We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.Let n = 2^m, T(n) = T(2^m) Let T(2^m) = S(m) From the above two, T(n) = S(m) S(m) = S(m/2) + C1 /* This is simply binary search recursion*/ S(m) = O(logm) = O(loglogn) /* Since n = 2^m */ Now, let us go back to the original recursive function T(n) T(n) = S(m) = O(LogLogn)
1. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode{ struct CellNOde *leftChild; int element; struct CellNode *rightChild;};int GetValue(struct CellNode *ptr){ int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value = value + GetValue(ptr->leftChild) + GetValue(ptr->rightChild); } return(value);} |
(A) the number of nodes in the tree
(B) the number of internal nodes in the tree
(C) the number of leaf nodes in the tree
(D) the height of the tree
Answer (C)
2. Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
(A)
(logn)(B)
(LogLogn )(C)
(n)(D)
(nLogn)Answer (B)
The height of a Max Heap is
(logn). If we perform binary search for finding the correct position then we need to do (LogLogn) comparisons.3. Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?
(A) There is a minimum spanning tree containing e.
(B) If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
(C) Every minimum spanning tree has an edge of weight w .
(D) e is present in every minimum spanning tree.
Answer (D)
(A), (B) and (C) are correct.
(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.
4. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
(A) At least 2n – c comparisons, for some constant c, are needed.
(B) At most 1.5n – 2 comparisons are needed.
(C) At least nLog2n comparisons are needed.
(D) None of the above.
Answer (B)
5. Consider the following C code segment:
int IsPrime(n){ int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf(“Not Prime\n”); return 0;} return 1;} |
(A) T(n) = O(sqrt(n)) and T(n) =
(sqrt(n))(B) T(n) = O(sqrt(n)) and T(n) =
(1)(C) T(n) = O(n) and T(n) =
(sqrt(n))(D) None of the above
Answer (B)
Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.
The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) =
(1)1. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
a) n/2
b) (n-1)/3
c) (n-1)/2
d) (2n+1)/3
Answer(d)
Let L be the number of leaf nodes and I be the number of internal nodes, then following relation holds for above given tree
L = (3-1)I + 1 = 2I + 1Total number of nodes(n) is sum of leaf nodes and internal nodes
n = L + IAfter solving above two, we get L = (2n+1)/3
2. The running time of the following algorithm
Procedure A(n) If n <= 2 return(1) else return A(is best described by);
a) O(n)
b) O(log n)
c) O(1og log n)
d) O(1)
Answer(c)
3. A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
a)
b)
c)
d)
Answer(d)
Let the maximum possible height of a tree with n nodes is represented by H(n).
The maximum possible value of H(n) can be approximately written using following recursion
H(n) = H(2n/3) + 1The solution of above recurrence is
. We can simply get it by drawing a recursion tree.4. Consider the following algorithm for searching for a given number x in an unsorted – array A[1..n] having n distinct values:
1) Choose an i uniformly at random from 1..n; 2) If A[i] = x then Stop else Goto 1;Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?
a) n
b) n-l
c) 2n
d) n/2
Answer(a)
If you remember the coin and dice questions, you can just guess the answer for the above.
Below is proof for the answer.
Let expected number of comparisons be E. Value of E is sum of following expression for all the possible cases.
number_of_comparisons_for_a_case * probability_for_the_caseCase 1
If A[i] is found in the first attempt number of comparisons = 1 probability of the case = 1/nCase 2
If A[i] is found in the second attempt number of comparisons = 2 probability of the case = (n-1)/n*1/nCase 3
If A[i] is found in the third attempt number of comparisons = 2 probability of the case = (n-1)/n*(n-1)/n*1/nThere are actually infinite such cases. So, we have following infinite series for E.
E = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + …. (1)After multiplying equation (1) with (n-1)/n, we get
E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 +
[(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)
Subtracting (2) from (1), we getE/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………The expression on right side is a GP with infinite elements. Let us apply the sum formula (a/(1-r))
E/n = [1/n]/[1-(n-1)/n] = 1 E = n
1. 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)
(logn)(B)
(n)(C)
(nlogn)(D)
(n^2)Answer(C)
The worst case time complexity for insertion in a binary heap is O(Logn) (Refer Wiki). So inserting n elements in a heap of size n should take
(nlogn) time.2. 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
Answer (C)
3. Consider the following functions:
f(n) = 2^n g(n) = n! h(n) = n^logn 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))Answer (D)
According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) )
We can easily see above order by taking logs of the given 3 functions
lognlogn < n < log(n!) (logs of the given f(n), g(n) and h(n)). Note that log(n!) =
(nlogn)4. 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)
(n)Answer (B)
1. 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)Answer (C)
Connected components can be found in O(m + n) using Tarjan’s algorithm. Once we have connected components, we can count them.
2. 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
Answer (B)
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot.
If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
3 Dijkstra’s single source shortest path algorithm when run from vertex a in the below 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
Answer (D)
Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.
Let us see…
Let us run the 1st pass
b 1
b is minimum, so shortest distance to b is 1.
After 1st pass, distances are
c 3, e -2.
e is minimum, so shortest distance to e is -2
After 2nd pass, distances are
c 3, f 0.
f is minimum, so shortest distance to f is 0
After 3rd pass, distances are
c 3, g 3.
Both are same, let us take g. so shortest distance to g is 3.
After 4th pass, distances are
c 3, h 5
c is minimum, so shortest distance to c is 3
After 5th pass, distances are
h -2
h is minimum, so shortest distance to h is -2
4. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
struct node{ int value; struct node *next;};void rearrange(struct node *list){ struct node *p, * q; int temp; if ((!list) || !list->next) return; p = list; q = list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; }} |
(B) 2,1,4,3,6,5,7
(C) 1,3,2,5,4,7,6
(D) 2,3,4,5,6,7,1
Answer (B)
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.
1. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D) 25,14,12,13,10,8,16
Answer (C)
A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data.
In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.
25
/ \
/ \
14 16
/ \ / \
/ \ / \
13 10 8 12
2. What is the content of the array after two delete operations on the correct answer to the previous question?(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10
Answer(D)
For Heap trees, deletion of a node includes following two operations.
1) Replace the root with last element on the last level.
2) Starting from root, heapify the complete tree from top to bottom..
Let us delete the two nodes one by one:
1) Deletion of 25:
Replace 25 with 12
12
/ \
/ \
14 16
/ \ /
/ \ /
13 10 8
Since heap property is violated for root (16 is greater than 12), make 16 as root of the tree. 16
/ \
/ \
14 12
/ \ /
/ \ /
13 10 8
2) Deletion of 16:Replace 16 with 8
8
/ \
/ \
14 12
/ \
/ \
13 10
Heapify from root to bottom. 14
/ \
/ \
8 12
/ \
/ \
13 10
14
/ \
/ \
13 12
/ \
/ \
8 10
3. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?(A)
(n)(B)
(nLogn)(C)
(n^2)(D)
(n^2 log n)Answer(B)
The recursion expression becomes:
T(n) = T(n/4) + T(3n/4) + cn
After solving the above recursion, we get
(nLogn).4. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
(A) 2
(B) 3
(C) 4
(D) 5
Answer(B)
AVL trees are binary trees with the following restrictions.
1) the height difference of the children is at most 1.
2) both children are AVL trees
a
/ \
/ \
b c
/ \ /
/ \ /
d e g
/
/
h
References:http://en.wikipedia.org/wiki/AVL_tree
1. An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
push (S1, x);
}
void delete(Q){
if(stack-empty(S2)) then
if(stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?(A) n+m <= x < 2n and 2m <= y <= n+m
(B) n+m <= x < 2n and 2m<= y <= 2n
(C) 2m <= x < 2n and 2m <= y <= n+m
(D) 2m <= x <2n and 2m <= y <= 2n
Answer(A)
The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())
2. Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?(A) (a—b),(d—f),(b—f),(d—c),(d—e)
(B) (a—b),(d—f),(d—c),(b—f),(d—e)
(C) (d—f),(a—b),(d—c),(b—f),(d—e)
(D) (d—f),(a—b),(b—f),(d—e),(d—c)
Answer (D)
The edge (d-e) cannot be considered before (d-c) in Kruskal’s minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.
3. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
(A)
(n)(B)
(nlogn)(C)
(n^2)(D)
(n^3)Answer (B)
If median is always used as pivot, then recursion remains T(n) = 2T(n/2) + cn for all the cases where cn is combined time for median finding and partition. So, worst case time complexity of this quick sort becomes
(nlogn). In practical implementations, however, this variant is considerably slower on average (seehttp://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting)1. Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
Answer (A)
Multiplications can be minimized using following order for evaluation of the given expression.
p(x) = a0 + x(a1 + x(a2 + a3x))
2. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
(A) Queue
(B) Stack
(C) Heap
(D) B-Tree
Answer(A)
The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.
3. A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1
Answer (D)
9
/ | \
/ | \
5 6 8
/ |
/ |
3 1
4. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer(A)
After insertion of 7
9
/ | \
/ | \
7 6 8
/ | \
/ | \
3 1 5
After insertion of 2 9
/ | \
/ | \
7 6 8
/ | \ /
/ | \ /
3 1 5 2
After insertion of 10 10
/ | \
/ | \
7 9 8
/ | \ / |
/ | \ / |
3 1 5 2 6
After insertion of 4 10
/ | \
/ | \
7 9 8
/ | \ / | \
/ | \ / | \
3 1 5 2 6 4
1. Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?
(A) There is no polynomial time algorithm for X.
(B) If X can be solved deterministically in polynomial time, then P = NP.
(C) If X is NP-hard, then it is NP-complete.
(D) X may be undecidable.
Answer (C)
(A) is incorrect because set NP includes both P(Polynomial time solvable) and NP-Complete .
(B) is incorrect because X may belong to P (same reason as (A))
(C) is correct because NP-Complete set is intersection of NP and NP-Hard sets.
(D) is incorrect because all NP problems are decidable in finite set of operations.
2. What is the number of swaps required to sort n elements using selection sort, in the worst case?
(A)
(n)(B)
(n log n)(C)
(n^2 )(D)
(n^2 log n)Answer (A)
Here is Selection Sort algorithm for sorting in ascending order.
1. Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) As we can see from the algorithm, selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort.
Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.
References:
http://en.wikipedia.org/wiki/Selection_sort
3. The running time of an algorithm is represented by the following recurrence relation:
if n <= 3 then T(n) = n else T(n) = T(n/3) + cn Which one of the following represents the time complexity of the algorithm?
(A)
(n)(B)
(n log n)(C)
(n^2)(D)
(n^2log n)Answer(A)
T(n) = cn + T(n/3) = cn + cn/3 + T(n/9) = cn + cn/3 + cn/9 + T(n/27) Taking the sum of infinite GP series. The value of T(n) will be less than this sum. T(n) <= cn(1/(1-1/3)) <= 3cn/2 or we can say cn <= T(n) <= 3cn/2 Therefore T(n) =
(n) This can also be solved using Master Theorem for solving recurrences. The given expression lies in Case 3 of the theorem.4. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
Answer (C)
To get the idea of open addressing concept, you can go through below lines from Wikipedia
.
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:
linear probing in which the interval between probes is fixed–often at 1.
quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function).
double hashing in which the interval between probes is fixed for each record but is computed by another hash function.
1. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
Answer (B)
(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.
(B) Correct because a NP Complete problem S is polynomial time educable to R.
(C) Incorrect because Q is not in NP.
(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.
2) A set X can be represented by an array x[n] as follows:
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[] , y[], z [])
{
int i;
for (i=O; i<n; ++i)
z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
}
The set Z computed by the algorithm is:(A) (X Intersection Y)
(B) (X Union Y)
(C) (X-Y) Intersection (Y-X)
(D) (X-Y) Union (Y-X)
Answer (D)
The expression x[i] ^ ~y[i]) results the only 1s in x where corresponding entry in y is 0. An array with these set bits represents set X – Y
The expression ~x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 0. An array with these set bits represents set Y – X.
The operator “V” results in Union of the above two sets.
3. Consider the following recurrence:
Which one of the following is true?
(A) T(n) =
(loglogn)(B) T(n) =
(logn)(C) T(n) =
(sqrt(n))(D) T(n) =
(n)Answer (B)
Let n = 2^m T(2^m) = T(2^(m/2)) + 1 Let T(2^m) = S(m) S(m) = 2S(m/2) + 1Above expression is a binary tree traversal recursion whose time complexity is
(m). You can also prove using Master theorem.S(m) =Now, let us go back to the original recursive function T(n)
T(n) = T(2^m) = S(m)
= (Logn)
1. The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?
(A) X[i, j] = X[i - 1, j] V X[i, j -ai]
(B) X[i, j] = X[i - 1, j] V X[i - 1, j - ai]
(C) X[i, j] = X[i - 1, j] V X[i, j - ai]
(D) X[i, j] = X[i - 1, j] V X[i -1, j - ai]
Answer (B)
X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true
1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true.
2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.
2. In question 1, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
(A) X[1, W]
(B) X[n ,0]
(C) X[n, W]
(D) X[n -1, n]
Answer (C)
If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.
Reference: http://en.wikipedia.org/wiki/Subset_sum_problem
3. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1. f(int Y[10], int x) {2. int i, j, k;3. i = 0; j = 9;4. do {5. k = (i + j) /2;6. if( Y[k] < x) i = k; else j = k;7. } while(Y[k] != x && i < j);8. if(Y[k] == x) printf ("x is in the array ") ;9. else printf (" x is not in the array ") ;10. } |
(A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
(B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
(C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
(D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Answer (C)
The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.
4. In question 3, the correction needed in the program to make it work properly is
(A) Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
(B) Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
(C) Change line 6 to: if (Y[k] <= x) i = k; else j = k;
(D) Change line 7 to: } while ((Y[k] == x) && (i < j));
Answer (A)
Below is the corrected function
f(int Y[10], int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k – 1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ("x is in the array ") ; else printf (" x is not in the array ") ;} |
1) A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
(a) An array of 50 numbers
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers
Answer (a)
An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value/
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?
(a) Graph G has no minimum spanning tree (MST)
(b) Graph G has a unique MST of cost n-1
(c) Graph G has multiple distinct MSTs, each of cost n-1
(d) Graph G has multiple spanning trees of different costs
Answer (c)
If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1. See the below example.
The connected graph:
Below are three Minimum Spanning trees each of cost 2.0.
Minimum Spanning Tree 1
Minimum Spanning Tree 2
Minimum Spanning Tree 3
3) The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:
a) O(n)
b) O(nLogn)
c) O(n^(3/2))
d) O(n^3)
Answer (d)
In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.
In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node other node b in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed in an O(1) operation one may determine that node c is reachable from node a.
Warshall’s algorithm can be used to construct the Transitive closure of directed graphs (). In Warshall’s original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).
References:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://en.wikipedia.org/wiki/Transitive_closure
4. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
(a) 10, 8, 7, 5, 3, 2, 1
(b) 10, 8, 7, 2, 3, 1, 5
(c) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5
Answer (D)
Original Max-Heap is:
10
/ \
8 5
/ \
3 2
After Insertion of 1. 10
/ \
8 5
/ \ /
3 2 1
After Insertion of 7. 10
/ \
8 7
/ \ / \
3 2 1 5
1. Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?
(a) Database relations have a large number of records
(b) Database relations are sorted on the primary key
(c) B-trees require less memory than binary search trees
(d) Data transfer form disks is in blocks.
Answer (d)
A disk block contains fairly large number of keys. Unlike BST where each node contains only one key, B-Tree is designed to contain large number of keys so that tree height is small.
2. How many distinct binary search trees can be created out of 4 distinct keys?
(a) 5
(b) 14
(c) 24
(d) 42
Answer (b)
Here is a systematic way to enumerate these BSTs. Consider all possible binary search trees with each element at the root. If there are n nodes, then for each choice of root node, there are n – 1 non-root nodes and these non-root nodes must be partitioned into those that are less than a chosen root and those that are greater than the chosen root.
Let’s say node i is chosen to be the root. Then there are i – 1 nodes smaller than i and n – i nodes bigger than i. For each of these two sets of nodes, there is a certain number of possible subtrees.
Let t(n) be the total number of BSTs with n nodes. The total number of BSTs with i at the root is t(i – 1) t(n – i). The two terms are multiplied together because the arrangements in the left and right subtrees are independent. That is, for each arrangement in the left tree and for each arrangement in the right tree, you get one BST with i at the root.
Summing over i gives the total number of binary search trees with n nodes.
The base case is t(0) = 1 and t(1) = 1, i.e. there is one empty BST and there is one BST with one node.
3. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:
(a) nk
(b) (n – 1) k+ 1
(c) n( k – 1) + 1
(d) n(k – 1)
Answer (c)
4) Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false.
a) T(n) = O(n^2)
b) T(n) =
(nLogn)c) T(n) =
(n^2)d) T(n) = O(nLogn)
Answer (c)
The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).
T(n) =
(nLogn)By definition of Big O notation, we can say.
(nLogn) = O(nLogn) = O(n^2)(nLogn) ca be equal to (n) or (nLogn), but not (n^2)1. The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node
{
int value;
struct node *next;
}Node;
Node *move_to_front(Node *head)
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
return head;
}
Choose the correct alternative to replace the blank line.(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
Answer(D)
When the while loop ends, q contains address of second last node and p contains address of last node. So we need to do following things after while loop.
i) Set next of q as NULL (q->next = NULL).
ii) Set next of p as head (p->next = head).
iii) Make head as p ( head = p)
Step (ii) must be performed before step (iii). If we change head first, then we lose track of head node in the original linked list.
2. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52
Answer (C)
The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.
3. How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?(A) 10
(B) 20
(C) 30
(D) 40
Answer (C)
In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33.
Total number of different sequences = 3! x 5 = 30
In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.
1 Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?(A) 7
(B) 8
(C) 9
(D) 10
Answer (D)
To get the minimum spanning tree with vertex 0 as leaf, first remove 0th row and 0th column and then get the minimum spanning tree (MST) of the remaining graph. Once we have MST of the remaining graph, connect the MST to vertex 0 with the edge with minimum weight (we have two options as there are two 1s in 0th row).
2. In the graph given in question 1, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
(A) 7
(B) 8
(C) 9
(D) 10
Answer (B)
Path: 1 -> 0 -> 4 -> 2
Weight: 1 + 4 + 3
3. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II
(B) III and IV
(C) IV only
(D) II and IV
Answer (D)
In sequence IV, we have a vertex with degree 8 which is not possible in a simple graph (no self loops and no multiple edges) with total vertex count as 8. Maximum possible degree in such a graph is 7.
In sequence II, four vertices are connected to 6 other vertices, but remaining 4 vertices have degrees as 3, 3, 2 and 2 which are not possible in a simple graph (no self loops and no multiple edges).
4. Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
(A) 1
(B) 2
(C) 3
(D) 4
Answer (B)
Since the maximum number of keys is 5, maximum number of children a node can have is 6. By definition of B Tree, minimum children that a node can have would be 6/2 = 3. Therefore, minimum number of keys that a node can have becomes 2 (3-1).
1) A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap?
Answer: (B)
A binary tree is max-heap if it is a complete binary tree (A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible) and it follows the max-heap property (value of each parent is greater than or equal to the values of its children).
A) is not a max-heap because it is not a complete binary tree
B) is a max-heap because it is complete binary tree and follows max-heap property.
C) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property.
D) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property. There are many other nodes in this tree which violate max-heap property in this tree.
2) Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
A) 248000
B) 44000
C) 19000
D) 25000
Answer (C)
We get minimum number of multiplications using ((M1 X (M2 X M3)) X M4).
Total number of multiplications = 100x20x5 (for M2 x M3) + 10x100x5 + 10x5x80 = 19000.
3) Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
A) f3, f2, f4, f1
B) f3, f2, f1, f4
C) f2, f3, f1, f4
D) f2, f3, f4, f1
Answer (A)
4) We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
A) 0
B) 1
C) n!
D) (1/(n+1)).2nCn
Answer (B)
See this explanation from PeddaBoku.
5) An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Which of the following statements is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Answer: (A)
1) An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?(A) 1/12(11n^2 – 5n)
(B) n^2 – n + 1
(C) 6n – 11
(D) 2n + 1
Answer: (B)
Minimum spanning tree for 2 nodes would be
(v1) _ (v2)Total weight 3
Minimum spanning tree for 3 nodes would be
(v1) _ (v2)
|
(v3)
Total weight= 3 + 4 = 7Minimum spanning tree for 4 nodes would be
(v1) _ (v2) _ (v4)
|
(v3)
Total weight= 3 + 4 + 6 = 13Minimum spanning tree for 5 nodes would be
(v1) _ (v2) _ (v4)
|
(v3)
|
(v5)
Total weight= 3 + 4 + 6 + 8 = 21Minimum spanning tree for 6 nodes would be
(v1) _ (v2) _ (v4) _ (v6)
|
(v3)
|
(v5)
Total weight= 3 + 4 + 6 + 8 + 10 = 31We can observe from above examples that when we add kth node, the weight of spanning tree increases by 2k-2. Let T(n) be the weight of minimum spanning tree. T(n) can be written as
T(n) = T(n-1) + (2n-2) for n > 2
T(1) = 0, T(2) = 0 and T(2) = 3
The recurrence can be written as sum of series (2n – 2) + (2n-4) + (2n-6) + (2n-8) + …. 3 and solution of this recurrence is n^2 – n + 1.
2) The length of the path from v5 to v6 in the MST of previous question with n = 10 is
(A) 11
(B) 25
(C) 31
(D) 41
Answer: (C)
Any MST which has more than 5 nodes will have the same distance between v5 and v6 as the basic structure of all MSTs (with more than 5 nodes) would be following.
(v1) _ (v2) _ (v4) _ (v6) _ . . (more even numbered nodes)
|
(v3)
|
(v5)
|
.
.
(more odd numbered nodes)
Distance between v5 and v6 = 3 + 4 + 6 + 8 + 10 = 313) Consider two binary operators '
' and '' with the precedence of operator being lower than that of the operator. Operator is right associative while operator is left associative. Which one of the following represents the parse tree for expression (7 3 4 3 2)?
Answer: (B)
Let us consider the given expression (
).Since the precedence of
is higher, the sub-expression () will be evaluated first. In this sub-expression, would be evaluated first because is right to left associative. So the expression is evaluated as . Also, note that among the two operators, first one is evaluated before the second one because the associativity of is left to right.1) Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?
(A)
(B)
(C)
(D)
Answer (C)
The worst case time complexity is always greater than or same as the average case time complexity.
2) The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
(A)
(B)
(C)
(D)
Answer (C)
Time taken to search an element is
where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be which is Which is which can be written as .3) Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete
P = (C) NP-hard = NP
(D) P = NP-complete
Answer (B)
The answer is B (no NP-Complete problem can be solved in polynomial time). Because, if one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.
4) The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.
The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)
Answer (A)
The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one.
The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.
5) A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
(A)
(B)
(C)
(D)
Answer (B)
The recurrence tree for merge sort will have height n. And O(n^2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be
.1) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is
(A) T(n) = 2T(n – 2) + 2
(B) T(n) = 2T(n – 1) + n
(C) T(n) = 2T(n/2) + 1
(D) T(n) = 2T(n – 1) + 1
Answer (D)
Following are the steps to follow to solve Tower of Hanoi problem recursively.
Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
move n-1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n?1 discs from B to C so they sit on disc n
The recurrence function T(n) for time complexity of the above recursive solution can be written as following.T(n) = 2T(n-1) + 1
2) Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
(A) SDT
(B) SBDT
(C) SACDT
(D) SACET
Answer (D)
3) Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation 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
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Answer (A)
1) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A) P Only
B) Q Only
C) Both P and Q
D) Neither P nor Q
Answer (C)
Q is true: Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.
2) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
(A) 1/8
(B) 1
(C) 7
(D) 8
Answer (C)
A cycle of length 3 can be formed with 3 vertices. There can be total 8C3 ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (8C3)*(1/2)^3 = 7
3) What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A)
(B)
(C)
(D)
Answer (C).
Time complexity of Bellman-Ford algorithm is
where V is number of vertices and E is number edges (See this). If the graph is complete, the value of E becomes . So overall time complexity becomes 4) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only
Answer (A)
1 is true because cycle detection can be done in polynomial time using DFS (See this).
2 is true because P is a subset of NP.
3 is true because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution exists. (See this)
5) Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Answer (C)
The worst case occurs for a skewed tree. In a skewed tree, when a new node is inserted as a child of bottommost node, the time for insertion requires traversal of all node. For example, consider the following tree and the case when something smaller than 70 is inserted.
100
/
90
/
80
/
70
6) Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)
Answer (B)
Selection sort requires only O(n) swaps. See this for details.
7) Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter
MultiDequeue(Q){
m = k
while (Q is not empty and m > 0) {
Dequeue(Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (A)
(B)
(C)
(D)
Answer (A)
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is
1) 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.
int f(int &x, int c) {
c = c - 1;
if (c == 0) return 1;
x = x + 1;
return f(x, c) * x;
}
(A) 3024(B) 6561
(C) 55440
(D) 161051
Answer (B)
Since c is passed by value and x is passed by reference, all functions will have same copy of x, but different copies of c.
f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x*x*x = 1*x*x*x*x = x^4
Since x is incremented in every function call, it becomes 9 after f(x, 2) call. So the value of expression x^4 becomes 9^4 which is 6561.
#include <stdio.h>
int f(int &x, int c)
{
c = c - 1;
if (c == 0) return 1;
x = x + 1;
return f(x, c) * x;
}
int main()
{
int p = 5;
printf("%d", f(p, p));
}
1) 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?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30
Ans (D)
The following is the constructed tree
30
/ \
20 39
/ \ / \
10 25 35 42
\ /
15 23
3) Consider the following function
int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}
What is the returned value of the above function?(A)
(B)
(C)
(D)
Answer (B)
The outer loop runs n/2 or
times. The inner loop runs times (Note that j is divide by 2 in every iteration). So the statement "k = k + n/2;" runs times. The statement increases value of k by n/2. So the value of k becomes n/2* which is 4) The number of elements that can be sorted in
time using heap sort is (A)
(B)
(C)
(d)
Answer (C)
Time complexity of Heap Sort is
for m input elements. For m = , the value of will be which will be which is 5) The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
void find_and_replace(char *A, char *oldc, char *newc) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases(1) oldc = "abc", newc = "dab"
(2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda"
(4) oldc = "abc", newc = "bac"
The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?
(A) Only one
(B) Only two
(C) Only three
(D) All four
Answer (B)
The test cases 3 and 4 are the only cases that capture the flaw. The code doesn't work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This doesn't happen in test cases (1) and (2), it happens only in cases (3) and (4).
6) If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
(A) None
(B) 2 only
(C) 3 and 4 only
(D) 4 only
Answer (C)
#include <stdio.h>
#include <string.h>
void find_and_replace(char *A, char *oldc, char *newc) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
int main()
{
char *oldc1 = "abc", *newc1 = "dab";
char *oldc2 = "cde", *newc2 = "bcd";
char *oldc3 = "bca", *newc3 = "cda";
char *oldc4 = "abc", *newc4 = "bac";
char test[] = "abcde";
printf("Test 2\n");
printf("%s\n", test);
find_and_replace(test, oldc2, newc2);
printf ("%s\n", test);
printf("\nTest 3\n");
strcpy(test, "abcde");
printf("%s\n", test);
find_and_replace(test, oldc3, newc3);
printf ("%s\n", test);
printf("\nTest 4\n");
strcpy(test, "abcde");
printf("%s\n", test);
find_and_replace(test, oldc4, newc4);
printf ("%s\n", test);
}
Output:Test 2 abcde abbcd Test 3 abcde addde Test 4 abcde aacde
No comments:
Post a Comment