Algorithms

Question 1

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n – 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n – 1)/2⌋, ⌊(n – 3)/2⌋, ….., 0. The time required to construct a heap in this manner is

A
O(log n)
B
O(n)
C
O(n log log n)
D
O(n log n)
       Algorithms       Binary-Trees       GATE 2004-IT
Question 1 Explanation: 
The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n).
Question 2

Which one of the following binary trees has its inorder and preorder traversals as BCAD  and ABCD, respectively?

A
B
C
D
       Algorithms       Tree Traversals       GATE 2004-IT
Question 2 Explanation: 
Inorder traversal is,
Left root right.
Preorder traversal is,
Root left right.
Question 3

Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?

A
f(n) + g(n) = O(h(n)) + h(n))
B
f(n) = O(h(n))
C
fh(n) ≠ O(f(n))
D
f(n)h(n) ≠ O(g(n)h(n))
       Algorithms       Time-Complexity       GATE 2004-IT
Question 3 Explanation: 
f(n) = O(h(n)) [Using transitivity]
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 4

Consider the undirected graph below:


Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

A
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
B
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
C
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
D
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
       Algorithms       Greedy-Method       GATE 2004-IT
Question 4 Explanation: 
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim’s algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 5

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

RECURSIVE ALGORITHM		  RECURRENCE RELATION
 P. Binary search	      I. T(n) = T(n-k) + T(k) + cn
 Q. Merge sort	             II. T(n) = 2T(n-1) + 1
 R. Quick sort	            III. T(n) = 2T(n/2) + cn
 S. Tower of Hanoi	     IV. T(n) = T(n/2) + 1 
A
P-II, Q-III, R-IV, S-I
B
P-IV, Q-III, R-I, S-II
C
P-III, Q-II, R-IV, S-I
D
P-IV, Q-II, R-I, S-III
       Algorithms       General       GATE 2004-IT
Question 5 Explanation: 
Quick sort – T(n) = T(n-k) + T(k) + cn
Binary search – T(n/2) + 1
Merge sort – T(n) = 2T(n/2)+ cn
Tower of hanoi – T(n) = 2T(n-1) +1
Question 6

For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.

Then T(n) is

A
θ(loga logb n)
B
θ(logb loga n)
C
θ(log2 log2 n)
D
θ(logab n)
       Algorithms       Recurrences       GATE 2020       Video-Explanation
Question 6 Explanation: 
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Question 7

Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

A
θ(|E|+|V|)
B
θ(|E| log|V|)
C
θ(|E||V|)
D
θ(|V|)
       Algorithms       Minimum-Spanning-Tree       GATE 2020       Video-Explanation
Question 7 Explanation: 
Method-1:
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).
Method-2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method-1 is the most appropriate answer for giving a question.
Question 8

Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is ______.

A
99
       Algorithms       Minimum-Spanning-Tree       GATE 2020       Video-Explanation
Question 8 Explanation: 
• If there are n vertices in the graph, then each spanning tree has n − 1 edges.
• N =100
• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So, 99 edges of weight is 99.
Question 9
Which one of the following statements is TRUE for all positive functions f (n) ?
A
f ( n ^2 ) ( f ( n ) ^2 ), when f ( n ) is a polynomial
B
f ( n ^2 ) o ( f ( n ) ^2 )
C
f ( n ^2 ) O ( f ( n ) ^2 ), when f ( n ) is an exponential function
D
       Algorithms       Asymptotic-Complexity       GATE 2022       Video-Explanation
Question 9 Explanation: 
constant < logarithmic < linear < polynomial < exponential < factorial
f(n)=n^c where c is a constant
f(n^2) = (n^2)^c = n^2c
(f(n))^2 = (n^c)^2 = n^2c
f(n^2) = (f(n))^2 is TRUE asymptotically.
Option-B: FALSE: The small omega function indicates the tightest upper bound.
f(n)^2 < o(f(n)^2) is FALSE asymptotically.
Option-C: FALSE: Consider f(n)=logn
f(n^2)=logn^2 = 2*logn
(f(n))^2 = (logn)^2 = logn * logn
f(n^2) <=Ω(f(n))^2 is FALSE asymptotically.
Option-D: FALSE:
Exponential values(Eg: 2^n, 3^n,..,k^n where k is a constant ”
f(n)=3^n
f(n^2)=f(3^(n^2)
(f(n))^2 = (3^n)^2 = 3^2n
f(n^2) >= O(f(n))^2 is FALSE asymptotically.
Question 10
Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h 1 and h 2 . Further suppose our hashing scheme uses h 1 for the odd keys and h 2 for the even keys. What is the expected number of keys in a slot?
A
m/n
B
n/m
C
2n/m
D
n/2m
       Algorithms       Hashing       GATE 2022       Video-Explanation
Question 10 Explanation: 
For n keys and m elements without any condition the expected number of elements in a slot are n/m.
How?
For 1st element the probability of key1 ends up in slot 1 is 1/m.
For 2nd element the probability of key2 ends up in slot 2 is 1/m
..
..
For nth element the probability of keyn ends up in slot n is 1/m
Hence expected number of elements in a slot is:
1/m+1/m+… (n times)= n/m
In the given question h1 is for elements at even sequence position and h2 is for odd number of sequence positions. This will not affect the overall probability.
Hence here also it is n/m
Question 11
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.
A
509
       Algorithms       Binary-search-tree       GATE 2022       Video-Explanation
Question 11 Explanation: 
Array indices shown beside node

Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Question 12
Consider a simple undirected weighted graph G , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
A
The edge with the second smallest weight is always part of any minimum spanning tree of G .
B
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G .
C
D
G can have multiple minimum spanning trees.
       Algorithms       Minimum-Spanning-Tree       GATE 2022       Video-Explanation
Question 12 Explanation: 
Let assume the graph and minimum spanning tree of the corresponding graph.


Option-A: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.
The second smallest weight is always in MST because it will not form a cycle.
Option-B: TRUE: Graph G is having more than 4 vertices. Suppose 3rd smallest element is forming a cycle then it takes 4th smallest element. So, the given statement is TRUE.
Option-C: TRUE: As per the example graph, it is always correct.
Option-D: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
Question 13
Consider the following recurrence:

Then, which of the following statements is/are TRUE?
A
f (2^ n -1) 2^ n -1
B
f (2 ^n ) 1
C
f (5 . 2 ^n ) 2^ n + 1 1
D
f (2^ n + 1) 2 ^n + 1
       Algorithms       Asymptotic-Complexity       GATE 2022       Video-Explanation
Question 13 Explanation: 
We can solve this problem by eliminating options. Substitute n=1024
Based on the “n” value we can get Option-A, B and C are correct.
Question 14
Let G ( V , E ) be a directed graph, where V = {1, 2,3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A .
A
24
       Algorithms       Minimum-Spanning-Tree       GATE 2022       Video-Explanation
Question 14 Explanation: 
Graph have 2 elements –> We get 1 MST
Graph have 3 elements –> We get 2 MSTs
Graph have 4 elements –> We get 6 MSTs (3*2*1)
Graph have 5 elements –> We get 24 MSTs(4*3*2*1)
Question 15

A two dimensional array A[1…n][1…n] of integers is partially sorted if

    ∀i, j ∈ [1...n−1],   A[i][j] < A[i][j+1] and 
                           A[i][j] < A[i+1][j] 

Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.

procedure  insert (x: integer);
var        i,j: integer;
begin
(1) i:=1; j:=1, A[i][j]:=x;
(2) while (x > ...... or x > ......) do
(3) if A[i+1][j] < A[i][j] ......... then begin
(4) A[i][j]:=A[i+1][j]; i:=i+1;
(5) end
(6) else begin
(7) ............
(8) end
(9) A[i][j]:= .............
    end  
A
Theory Explanation.
       Algorithms       Sorting       GATE 1996
Question 16

Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function

 h(x) = (ord(x) – ord("a") + 1) mod10 

and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.

A
Theory Explanation.
       Algorithms       Hashing       GATE 1996
Question 17

A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v

A
Theory Explanation.
       Algorithms       Minimum-Spanning-Tree       GATE 1996
Question 18

Let G be the directed, weighted graph shown in below figure.

We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?

A
Theory Explanation.
       Algorithms       Dijkstra Algorithm       GATE 1996
Question 19

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 
A
Theory Explanation.
       Algorithms       Binary-search-tree       GATE 1996
Question 20

(a) Solve the following recurrence relation:

  xn = 2xn-1 - 1, n>1
  x1 = 2 

(b) Consider the grammar

  S →  Aa | b
  A → Ac | Sd | ε 

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

A
Theory Explanation.
       Algorithms       Theory-of-Computation       GATE 1998
Question 21

Let A be an n×n matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree which finds 1st, 2nd and 3rd smallest elements in minimum number of comparisons.

A
Theory Explanation.
       Algorithms       Minimum-comparisons       GATE 1999
Question 22

(a) Consider the following algorithm. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in O-notation.

         algorithm what (n)      
             begin 
                  if n = 1 then call A 
             else begin
                   what (n-1);
                   call B(n)
             end
         end. 

(b) Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.

A
Theory Explanation.
       Algorithms       Time-Complexity       GATE 1999
Question 23

Merge sort uses

A
Divide and conquer strategy
B
Backtracking approach
C
Heuristic search
D
Greedy approach
       Algorithms       Sorting       GATE 1995
Question 23 Explanation: 
Merge sort uses the divide and conquer strategy.
Question 24

The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:

A
AB + CD + *F/D + E*
B
ABCD + *F/DE*++
C
A *B + CD/F *DE++
D
A + *BCD/F* DE++
E
None of the above
       Algorithms       Post-fix-and-Prefix       GATE 1995
Question 24 Explanation: 
The postfix expression will be,
A B C D + * F / + D E * +
Question 25

Which of the following statements is true?

    I. As the number of entries in a hash table increases, the number of collisions increases.
    II. Recursive programs are efficient
    III. The worst case complexity for Quicksort is O(n2)
A
I and II
B
II and III
C
I and IV
D
I and III
       Algorithms       General       GATE 1995
Question 25 Explanation: 
Binary search using linked list is not efficient as it will not give O(log n), because we will not be able to find the mid in constant time. Finding mid in linked list takes O(n) time.
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind iterative one in terms of performance.
Question 26

Consider the following sequence of numbers

  92, 37, 52, 12, 11, 25  

Use bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.

A
Theory Explanation.
       Algorithms       Sorting       GATE 1995
Question 27

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).

A
Theory Explanation.
       Algorithms       Minimum-Spanning-Tree       GATE 1995
Question 28

FORTRAN implementation do not permit recursion because

A
they use static allocation for variables
B
they use dynamic allocation for variables
C
stacks are not available on all machines
D
it is not possible to implement recursion on all machines
       Algorithms       Recursions       GATE 1994
Question 28 Explanation: 
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
Question 29

The recurrence relation that arises in relation with the complexity of binary search is:

A
T(n) = T(n/2) + k, k a constant
B
T(n) = 2T(n/2) + k, k a constant
C
T(n) = T(n/2) + log n
D
T(n) = T(n/2) + n
       Algorithms       Time-Complexity       GATE 1994
Question 29 Explanation: 
In binary search, search for the half of the list and constant time for comparing. So,
∴ T(n) = 2T(n/2) + k, k a constant
Question 30

Which of the following algorithm design techniques is used in the quicksort algorithm?

A
Dynamic programming
B
Backtracking
C
Divide and conquer
D
Greedy method
       Algorithms       Quick-Sort       GATE 1994
Question 30 Explanation: 
In quick sort, we use divide and conquer technique.
Question 31

In which one of the following cases is it possible to obtain different results for call-by reference and call-by-name parameter passing methods?

A
Passing a constant value as a parameter
B
Passing the address of an array as a parameter
C
Passing an array element as a parameter
D
Passing an array following statements is true
       Algorithms       Call-by-reference-and-Call-by-value       GATE 1994
Question 31 Explanation: 
Passing an array element as a parameter then it gives different output values for the call-by-reference and call-by-name parameters.
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
Question 32

Which one of the following statements is false?

A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find connected components of a graph.
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
       Algorithms       Searching       GATE 1994
Question 32 Explanation: 
In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.
Question 33

Consider the following two functions:

Which of the following is true?

A
g1(n) is O(g2(n))
B
g1 (n) is O(3)
C
g2 (n) is O(g1 (n))
D
g2 (n) is O(n)
E
Both A and B
       Algorithms       Asymptotic-Notations       GATE 1994
Question 33 Explanation: 
In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Question 34

An array A contains n integers in locations A[0],A[1], …………… A[n-1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n-1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.

 min:=n;
 i=0;
 while _____do
 begin
     temp:=A[i];
     j:=i;
     while _____do
 begin
     A[j]:=_____;
     j:=(j+K) mod n;
 if j
A
Theory Explanation.
       Algorithms       Asymptotic-Complexity       GATE 1994
Question 35

(a) Use the patterns given to prove that


(You are not permitted to employ induction)

(b) Use the result obtained in (a) to prove that

A
Theory Explanation.
       Algorithms       Recurrences       GATE 1994
Question 36

Consider the following recursive function:

 function fib (1:integer);integer;
 begin
 if (n=0) or (n=1) then fib:=1
 else fib:=fib(n-1) + fib(n-2)
 end; 

The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.

A
Theory Explanation.
       Algorithms       Asymptotic-Complexity       GATE 1994
Question 37

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I); 

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.

A
Theory Explanation.
       Algorithms       Greedy-approach       GATE 1994
Question 38

The root directory of a disk should be placed

A
at a fixed address in main memory
B
at a fixed location on the disk
C
anywhere on the disk
D
at a fixed location on the system disk
E
anywhere on the system disk
       Algorithms       GATE 1993
Question 38 Explanation: 
Root directory can points to the various user directories. Then they will be stored in a way that user can't be easily modify them. Then they should be at fixed location on the disk.
Question 39

Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true?

A
G has no cycles.
B
The graph obtained by removing any edge from G is not connected.
C
G has at least one cycle.
D
The graph obtained by removing any two edges from G is not connected.
E
Both C and D.
       Algorithms       Graphs       GATE 1993
Question 39 Explanation: 
If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3.
Question 40

where O(n) stands for order n is:

A
O(n)
B
O(n2)
C
O(n3)
D
O(3n2)
E
O(1.5n2)
F
B, C, D and E
       Algorithms       Time-Complexity       GATE 1993
Question 40 Explanation: 

⇒ In this 'n' is constant. So, n is added to n times itself which is O(n2).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 41

Consider the recursive algorithm given below:

 procedure bubblersort (n);
 var i,j: index; temp : item;
 begin
    for i:=1 to n-1 do
    if A[i] > A [i+1] then
 begin
    temp : A[i];
    A[i]:=A[i+1]; 
    A[i+1]:=temp
    end;
   bubblesort (n-1)
 end 

Let an be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining an in terms of an-1. Solve for an.

A
Theory Explanation.
       Algorithms       Sorting       GATE 1993
Question 42

The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

A
p
B
p + 1
C
n - p
D
n - p + 1
       Algorithms       Tree Traversals       GATE 2005-IT
Question 42 Explanation: 
Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
Question 43

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

A
k
B
k + 1
C
n - k - 1
D
n - k
       Algorithms       Graph-Traversal       GATE 2005-IT
Question 43 Explanation: 
In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
Question 44

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

1. Bellman-Ford algorithm       A: O ( m log n)   
2. Kruskal’s algorithm          B: O (n3) 
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        D: O (n + m) 
A
1→ C, 2 → A, 3 → B, 4 → D
B
1→ B, 2 → D, 3 → C, 4 → A
C
1→ C, 2 → D, 3 → A, 4 → B
D
1→ B, 2 → A, 3 → C, 4 → D
       Algorithms       General       GATE 2005-IT
Question 44 Explanation: 
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Question 45

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

A
2
B
3
C
4
D
6
       Algorithms       Sorting-and-Searching       GATE 2005-IT
Question 45 Explanation: 
43%10 = 3 [occupy 3]
165%10 = 5 [occupy 5]
62%10 = 2 [occupy 2]
123%10 = 3 [3 already occupied, so occupies 4]
142%10 = 2 [2, 3, 4, 5 are occupied, so it occupies 6]
Question 46

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

A
2h-1
B
2h-1 + 1
C
2h - 1
D
2h
       Algorithms       Tree Traversals       GATE 2005-IT
Question 46 Explanation: 
Let's take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 47

Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?

A
T(n) = θ(log n)
B
T(n) = θ(√n)
C
T(n) = θ(n)
D
T(n) = θ(n log n)
       Algorithms       Recursion       GATE 2005-IT
Question 47 Explanation: 
Apply Master's theorem.
Question 48

Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?

A
There exists a cutset in G having all edges of maximum weight
B
There exists a cycle in G having all edges of maximum weight
C
Edge e cannot be contained in a cycle
D
All edges in G have the same weight
       Algorithms       Graph-Theory       GATE 2005-IT
Question 48 Explanation: 
(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 49

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be

A
8, 7, 6, 5, 4, 3, 2, 1
B
1, 2, 3, 4, 8, 7, 6, 5
C
2, 1, 4, 3, 6, 7, 8, 5
D
2, 1, 4, 3, 7, 8, 6, 5
       Algorithms       Tree Traversals       GATE 2005-IT
Question 49 Explanation: 
Pre-order is given as
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,

Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
Question 50

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

A
4
B
7
C
23
D
99
       Algorithms       Graph-Theory       GATE 2005-IT
Question 50 Explanation: 
Edge set consists of edges from i to j, using either
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now