Open In App

Data Structures and Algorithms | Set 3

Last Updated : 03 Feb, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Following questions have asked in GATE CS exam. 

1. Suppose you are given an array s[1…n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence 

do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);

(GATE CS 2000)

(a) Rotates s left by k positions

(b) Leaves s unchanged

(c) Reverses all elements of s 

(d) None of the above 

Answer: (a) Effect of the above 3 reversals for any k is equivalent to left rotation of the array of size n by k. Please see this post for details. If we rotate an array n times for k = 1 to n, we get the same array back. 

2. The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004) 

a) queue

b) stack

c) tree

d) list 

Answer(b) There are three types of parentheses [ ] { } (). Below is an arbitrary c code segment which has parentheses of all three types. 

c




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. 

c




/*Return 1 if expression has balanced parentheses */
bool areParenthesesBalanced(expression )
{
   for each character in expression
   {
      if(character == ’(’ || character == ’{’ || character == ’[’)
        push(stack, character);
      if(character == ’)’ || character == ’}’ || character == ’]’)
      {
         if(isEmpty(stack)) 
           return 0; /*We are seeing a right parenthesis 
                       without a left pair*/
 
         /* Pop the top element from stack, if it is not a pair
             bracket of character then there is a mismatch.
             This will happen for expressions like {(}) */
         else if (! isMatchingPair(pop(stack), character) )
           return 0;  
      }
   }
   
   if(isEmpty(stack))
     return 1; /*balanced*/
   else 
     return 0;  /*not balanced*/  
} /* End of function to check parentheses */
 
/* Returns 1 if character1 and character2 are matching left
   and right parentheses */
bool isMatchingPair(character1, character2)
{
   if(character1 == ‘(‘ && character2 == ‘)’)
     return 1;
   else If(character1 == ‘{‘ && character2 == ‘}’)
     return 1;
   else If(character1 == ‘[‘ && character2 == ‘]’)
     return 1;
   else
     return 0;
}


3. Level order traversal of a rooted tree can be done by starting from the root and performing (GATE CS 2004) 

a) preorder traversal

b) in-order traversal 

c) depth first search

d) breadth first search

 Answer(d) See this post for details

4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 has to the same value iii. All elements hash to the same value iv. Each element hashes to a different value (GATE CS 2004) 

a) i only 

b) ii only 

c) i and ii only

d) iii or iv 

Answer (c) 

5. Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (GATE CS 2005) 

a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95 

b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29 

c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29 

Answer (a) Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.



Previous Article
Next Article

Similar Reads

Data Structures and Algorithms | Set 2
Following questions have been asked in GATE CS exam. 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 &lt;= p->next->data) &amp;&amp; f(p->next)) ); } For a given linked list p, the function f returns 1
5 min read
Data Structures and Algorithms | Set 4
Following questions have been asked in GATE CS exam. 1. Consider the following C program segment C/C++ Code 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
3 min read
Data Structures and Algorithms | Set 5
Following questions have been asked in GATE CS exam. 1. Consider the following C function. float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } For large values of y, the return value of the function f best approximates (GATE CS 2003) a) x^y b) e^x c) ln(1 + x) d) x^x Answer (b) The functio
2 min read
Data Structures and Algorithms | Set 6
Following questions have been asked in GATE CS exam. 1. The usual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will (GATE
3 min read
Data Structures and Algorithms | Set 7
Following questions have been asked in GATE CS 2006 exam. 1. In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006) (A) 0(n) (B) O(logn) (C) 0(loglogn) (D) 0(1) Answer (A) In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. W
3 min read
Data Structures and Algorithms | Set 8
Following questions have been asked in GATE CS exam. 1. Consider the following functions Which of the following is true? (GATE CS 2000) (a) h(n) is 0(f(n)) (b) h(n) is 0(g(n)) (c) g(n) is not 0(f(n)) (d) f(n) is 0(g(n)) Answer (d) g(n) = 2√n Log n = n√n f(n) and g(n) are of same asymptotic order and following statements are true. f(n) =
3 min read
Data Structures and Algorithms | Set 9
Follow questions have been asked in GATE CS exam. 1 In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003) a) Θ(n log n) b) Θ(n) c) Θ(log n) d) Θ(1) Answer(d) The 7th smallest element must be in first 7 levels. Total number of nodes in any Binary Heap in
2 min read
Data Structures and Algorithms | Set 10
Following questions have been asked in GATE CS 2007 exam. 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
4 min read
Data Structures and Algorithms | Set 11
Following questions have been asked in GATE CS 2007 exam. 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 '_' den
4 min read
Data Structures and Algorithms | Set 12
Following questions have been asked in GATE CS 2007 exam. 1. Consider the following C program segment where CellNode represents a node in a binary tree: C/C++ Code struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild =
3 min read
Data Structures and Algorithms | Set 13
Following questions have been asked in GATE CS 2002 exam 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 (For details, pleas
3 min read
Data Structures and Algorithms | Set 14
Following questions have been asked in GATE CS 2008 exam. 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) Θ(n2) The worst case time complexity for insertion in a binary heap
2 min read
Data Structures and Algorithms | Set 15
Following questions have been asked in GATE CS 2008 exam. 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 algori
3 min read
Data Structures and Algorithms | Set 17
Following questions have been asked in GATE CS 2006 exam. 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 i
2 min read
Data Structures and Algorithms | Set 22
Following questions have been asked in GATE CS 2005 exam. 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 100 numbers (c) An array of 500 numbe
4 min read
Data Structures and Algorithms | Set 16
Following questions have been asked in GATE CS 2009 exam. 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
3 min read
Data Structures and Algorithms | Set 18
Following questions have been asked in GATE CS 2006 exam. 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.
3 min read
Data Structures and Algorithms | Set 19
Following questions have been asked in GATE CS 2009 exam. 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. Answe
4 min read
Data Structures and Algorithms | Set 20
Following questions have asked in GATE CS 2006 exam. 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 Answe
3 min read
Data Structures and Algorithms | Set 21
Following questions have been asked in GATE CS 2008 exam. 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.
3 min read
Data Structures and Algorithms | Set 23
Following questions have been asked in GATE CS 2005 exam. 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)
3 min read
Data Structures and Algorithms | Set 24
Following questions have been asked in GATE CS 2010 exam. 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_fron
3 min read
Data Structures and Algorithms | Set 25
Following questions have been asked in GATE 2010 exam. 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) T
3 min read
Data Structures and Algorithms | Set 26
Following questions have been asked in GATE 2011 exam. 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 possib
3 min read
Data Structures and Algorithms | Set 27
Following questions have been asked in GATE CS 2011 exam. 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 t
3 min read
Data Structures and Algorithms | Set 28
Following questions have been asked in GATE 2012 exam. 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) A(n) = Ω(W(n)) (B) A(n) = Θ(W(n)) (C) A(n) = O(W(n)) (D) A(n) = o(W(n)) Answer (C) The worst case time complexity is
3 min read
Data Structures and Algorithms | Set 29
Following questions have been asked in GATE 2012 exam. 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
2 min read
Data Structures and Algorithms | Set 31
Following questions have been asked in GATE CS 2013 exam. 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) 30
5 min read
Data Structures and Algorithms | Set 30
Following questions have been asked in GATE CS 2013 exam. 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 su
4 min read
Data Structures and Algorithms | Set 32
Following questions have been asked in GATE CS 2014 exam. 1) Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix. (A) O(n) (B) O(m+n) (C) O(n2) (D) O(mn) Answer: (C) Explanation: Depth First Search of a graph takes
4 min read
three90RightbarBannerImg