Which of the following algorithms solves the all pair shortest path problem? Diskstra’s algorithm Floyd algorithm Prim’s algorithm Warshall’s algorithm The minimum number of colors required to color a graph having n (n>3) vertices and 2 edges is 4 3 2 1 The maximum degree of any vertex in a […]
The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is a 4 digit decimal number) 280 40 47 38 If each node in a tree has a value greater than every value in its left sub tree and has value less than […]
Which of the following programming languages features require a stack-base allocation pointer Block-structure recursion dynamic scoping Push down stack or push down list is stack queue linked list dequeue Stack is useful for radix sort breadth first search recursion Heap sort Stacks can not be used to evaluate an arithmetic […]
The recurrence relation that arises in relation with the complexity of binary search is T(n)=T(n/2)+k, where k is constant T(n)=2T(n/2)+k, where k is constant T(n)=T(n/2)+log(n) T(n)=T(n/2)+n The running time T(n), where `n’ is the input size of a recursive algorithm is given as followsT(n)=c+T(n-1),if n>1 d, if n≤ 1 […]
Q.101 The data structure needed to convert a recursion to an iterative procedure is (A) Queue. (B) Graph. (C) Stack. (D) Tree. Ans: (C) Q.102 A binary tree stored using linked representation can be converted to its mirror image by traversing it in (A) Inorder. (B) Preorder. (C) Postorder. (D) […]
Q.51 What is the output of following statement? for(i=1; i<4; i++) printf(“%d”,(i%2) ? i : 2*i); (A) 1 4 3 (B) 1 2 3 (C) 2 4 6 (D) 2 2 6 Ans: A for i=1, (i%2) is true so the statement will print 1; for for i=2, (i%2) is […]
Q.1 What is the output of the following program? main ( ) { int x = 2, y = 5; if (x < y) return (x = x+y); else printf (“z1”); printf(“z2”); } (A) z2 (B) z1z2 (C) Compilation error (D) None of these Ans: D There is no compilation […]
Follow questions have been asked in GATE CS exam. 1 In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003) a) Θ(n log n) b) Θ(n) c) Θ(log n) d) Θ(1) Answer(d) The 7th smallest […]
Q.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is : (A) less than 1. (B) less than n. (C) less than m. (D) less than […]
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 […]