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 […]
Following questions have been asked in GATE 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 […]
1) A program P reads in 500 integers in the range [0..100] representing 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 […]
1) 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) 2) Consider the following operation along with Enqueue and Dequeue operations on […]
