DS | GATE-2010 | PREVIOUS YEAR QUESTIONS| SET-11

Set-12 DS GATE-2009

DS | GATE-2010 | Data Structures

  1. In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child? [GATE – 2010]

a. 0
b. 1
c. n-1
d. (n-1)/2

Answer : a)
DS | GATE-2010 |


  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. [GATE – 2010]

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;
}

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)
DS | GATE-2010 |


  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? [GATE – 2010]

a. 7
b. 8
c. 9
d. 10

Answer : d)


  1. 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 shown below:
0 
1 
242
323
434
552
646
733
8 
9 

Which one of the following choices give a possible order in which the key values could have been inserted in the table? [GATE – 2010]

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)
DS | GATE-2010 |


  1. 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.
0 
1 
242
323
434
552
646
733
8 
9 

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? [GATE – 2010]

a. 10
b. 20
c. 25
d. 30

Answer : d)
DS | GATE-2010 |


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *