gate 2007 paper

Hi Friends,

Was trying to solve some DS questions from GATE
2008. The questions asked were some what simple. Here I'm posting my
solutions to those problems. I am getting the answers, but if you find
any errors in the solution please be kind enough to leave a comment.

GATE2007CSE Question Paper Analysis for DS:

Total Marks for Data Structures :14

1 mark questions : 2 [ 12(C), 13(B) ]
2 mark questions: 6 [ 38(A),39(A),40(B),42(D),43(C),46(C) ]

///////////////////////////////////////////////////////

G07\CSE\Q12\DS

Q. 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) 2h B) 2h-1 C)2h+1 D)2 h+1

ANS:

A node in a binary tree cannot have more than 2 children. The maximum
number of nodes is possible when each node has 2 children
when height , h=0 number of nodes, N =1
h=1, N = 1+2 = 3
h=2, N = 1+2+4 = 7
h=3, N = 1+2+4+8 = 15
h=h, N = 2^0 + 2^1 + 2^2 +... + 2^h = 2^(h+1) -1

There fore answer is B

///////////////////////////////////////////////////////////////////////

G07\CSE\Q13\DS

Q. The maximum number of binary trees that can be formed with three
unlabeled nodes.

A)1 B)5 C)4 D) 3

ANS:
A binary tree can have utmost 2 nodes.

I wish I could have drawn the tree to make explanations simple. But
drawing is taking a lot of time, so please forgive me the lack of
visual info and try to get the picture.

While placing a new node , two conditions should be met.

1. It should be connected to a previously placed node , unless its the
first node , ie root
2. It should be placed in a valid position, ie as a right child or
left child of an existing node , if its not the first node.
When we add a node to a binary tree, each newly added node consumes
one previously existing valid position and adds two new valid
positions. There fore net addition in no of valid positions after
connecting a new node to a binary tree is 2-1=1.
In a more general case, if it was an n-ary tree, each new node will
consume one previously existing valid position for adding a new node
and adds n new valid positions to the n-ary tree. So the net addition
of valid positions in an n-ary tree after adding a new node will be
n-1.
Another point is that , if a binary tree has k nodes the number of
valid positions to add a new node that the resulting tree is still a
binary tree will be always k+1.
Now with this concept lets approach the problem ,
With one unlabeled node, there is only one way to create a binary tree.
With 2 unlabeled nodes, we can create 2 binary trees by connecting the
second node either as a left child or right child of root.
With 2 nodes , the number of valid positions we have to create a three
nodes binary tree is 3.

But there are two ways in which we can create a 2 node binary three .
Therefore total options we have to create a 3-node binary tree is 2*3
= 6. But among these 6 trees two are symmetric, and since the nodes
are unlabelled we have to consider them as a single tree. There fore
the total number of binary trees possible with 3 unlabelled nodes is
6-1 =5.

There fore answer is B

Can some one tell how many identical trees (same shape) will be there
in a binary tree if there are n-labeled nodes. If n is even there will
be no identical trees. But if n is odd, i think there will be (n-1)/2
identical trees. Can someone please give me a proof for this ? I
simply drew all the trees and counted them.
In the above problem if there were n unlabelled trees the maximum
number of binary trees possible will be what ?

////////////////////////////////////////////////////////////

G07\CSE\Q38\DS

Q. The following postfix expression with single digit operands is
evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is exponentiation operator . The top two elements of the
stack after the first * is evaluated are :
A) 6,1 B)5,7 C) 3,2 D)1,5
ANS:
postfix notation is also know as reverse polish notation. Refer: Mark
Allen Weiss, chapter 3.
The concept we need to know here is that when evaluating a postfix
expression using stack, when ever an operand is seen its pushed into
stack, when ever we read an operator, the required operands are popped
out of stack the result is computed and the result is pushed into the
top of stack.
In postfix the relative position of operands remain same as the
original expression but the relative position of operators can change.
If operation is binary operator the top most is second operator.

8 2 3 ^ / 2 3 * + 5 1 * -

Reading : 8 // push 8
Stack : 8
Reading :2 // push 2
Stack :8 2
Reading :3 // push 3
Stack :8 2 3
Reading :^ // pop 3,2 compute 2^3 = 8,( don't do 3^2 =9 ) and push
8 to top of stack.
//Note top most is second operand
Stack :8 8
Reading : / // pop 8,8 computer 8/8 =1 and push 1 to stack
Stack : 1
Reading : 2 // push 2
Stack :1 2
Reading :3 // push 3
Stack : 1 2 3
Reading : * // pop 3,2 and do 2*3 = 6 , push 6
Stack :1,6

There fore top two elements after evaluating the first * operator is 6,1

So answer is A

////////////////////////////////////////////////////////////////

G07\CSE\Q39\DS

Q. The in order and pre order traversal of a binary tree are
d b e a f cg and a b d e c f g , respectively.
The post order traversal of the binary tree is

A) debfgca
B) edbgfca
C) edbfgca
D) defgbca

ANS:

To solve this question first we must construct the tree from
inorder and pre order.

How are we going to make the tree ? We know that , in pre order the
root is always the first element. Using this concept we should keep on
dividing the inorder arrangement into groups until we get the tree. I
know this sounds vague. Well, I don't know how to put the idea in
words, but i'll try my best to show what i know.

preorder : a b d e c f g
in order: d b e a f cg

for group dbeafcg , a is root
divide dbeafcg into two groups. dbe and fcg, a is parent for these two groups
for group dbe, b is root
divide dbe into two groups, d and e, b is parent for d and e
for group fcg , c is root
divide fcg into two groups, f and g

Now the tree is complete

I will try to scan the picture of the tree and post here as a
comment when i get time.

it looks something like. Now just compute the postorder using usual
standard technique and u will get the answer as debfcga.
a
..........................
| |
b c
............... ..................
| | | |
d e f g


////////////////////////////////////////////////////////////////////////////

G07\CSE\Q40\DS

Q. Consider a hash table of size 7,with starting index 0,and a hash
function (3x+4)mod 7.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 _
denotes empty location in the table.

A) 8,_,_,_,_,_,10
B) 1,8,10,_,_,_,3
C) 1,_,_,_,_,_,3
D) 1,10,8,_,_,_,3

ANS:

Hashing is explained well in weiss, I just skimmed through the
matter.. need to read it thoroughly sometime later.Please go through
that to get a better idea about hashing.

Hash function is (3x+4)mod7

Keys are 1,3,8,10

(3*1+4) mod 7 = 0
(3*3+4) mod 7 = 6
(3*8+4) mod 7 = 0
(3*10+4) mod 7 = 6

Imagine 7 rooms in a hotel , room 0 , room 1 , room 2 ,room 3 , room 4
, room 5, room 6

Mr.1 is inserted in room 0

Miss. 3 is inserted in room 6

When Mr. 8 tries to get into adress 0 ,he will find Mr. 1 sitting
there, so there will be a collision. Since we are using closed hashing
or linear probing policy, when we find 0 and 8 fighting for the same
room in memory , we say the second comer ie 8 to go and occupy the
next room. So 8 goes and sits in adress 1.
Mr.8 is inserted in adress 1

Now Mr. 10 comes and tries to sit in room 6. he finds Miss 3 already
sitting in room 6. Another collision begins, and Miss 3 gives a slap
and so Mr.10 tries to go to the next room ie room 0, there he finds
Mr. 1, so he goes to room 1 , there he finds Mr.8 , so he goes to next
room ie room 2 which he finds vacant and so he occupies it.

This is a classic example of clustering.

so finally we have the positions :

1,8,10,_,_,_,3

So answer is B

/////////////////////////////////////////////////////////////////////////

G07\CSE\Q42\DS

Q. Consider the following C-function.

int f(int n)
{
static int r = 0;
if (n <= 0) return 1;

if (n > 3)
{
r = n;
return f(n-2)+2;
}

return f(n-1)+r;
}

What is the value of f(5) ?
A)5 B)7 C)9 D)18

ANS:

When attacking recursion questions, you need to have an idea about
activation record. Each time a function is invoked as set of separate
variables is assigned to it unless it is declared as static. Static
variables retains their values throughout the life of the program.This
, if a function is exited and reentered at a later time, the static
variables defined within function will retain their former values.
This is the most important thing to remember while solving the above
question. If u treat static variable r just like a local variable ,
every time u will initialize r to 0 and u will get a wrong answer (you
will get it as 3 instead of 18).


##########################
f(5)
r = 0
r = 5
return f(3)+2 // 16+2 =18
###################
f(3)
// note since r is defined as static r is not assigned as 0 every time
the function is called.
return f(2) + 5 // 11 +5 =16
##################
f(2)
return f(1) +5 // 6+5 =11
###################
f(1)
return f(0) +5 //1 +5 = 6
#################
f(0)
return 1
#################

So answer is 18. ie choice D

///////////////////////////////////////////////////////////////

G07\CSE\Q43\DS

Q. A complete n-ary tree is a tree in which each node has n children
or no children. Let I be the number of internal nodes and L be the
number of leaves in a complete n-ary tree. If L=41 and I=10, what is
the value of n ?
A)3 B)4 C)5 D)6

ANS:
L = I (n-1) +1
41 = 10 (n-1)+1

Therefore, n=5
He he he ....... So simple right ? U get 2 marks for solving an
equation that even a 5th standard student can solve.. but did u get
the logic ?
If u refer Q13 , i have mentioned that if u add a new node to an
existing n-ary tree, u are consuming one valid position and adding n
new positions. So after addition of a new node u add n-1 valid
positions to the previous number of valid positions. here they say
that there are 10 internal nodes. So each time u add these 10 internal
nodes u are adding (n-1) leaves.
Tree looks something like this if n = 5

So answer is C

├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐

///////////////////////////////////////////////////////////////
G07\CSE\Q46\DS
Q. Consider the following C program segment where Cell Node represents
a node in a binary tree:
struct CellNode {
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};

int GetValue (struct CellNode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)+
GetValue(ptr->rightChild)
}
return(value);
}
The value returned by GetValue when a pointer to the root of a binary
tree is passed as its argument is :

A) the number of nodes in the tree
B) the number of internal nodes in the tree
C) the number of leaf nodes in the tree
D) the height of the tree

ANS:

In think this is a little difficult question. First draw a complete
binary tree with say 3 levels. Now point ptr to root.

The key code to watch is

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;

ie if there are no children for a node value is set as one. that node
is counted if it is a leaf node.

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;


This code helps us to descent to just one level above the level of leaf nodes.

So the program computes the number of leaf nodes in a tree.
There fore, the answer is C

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Hi friends,

I hope three hours of my effort would be of some use to you. If you
see any errors in the explanations or if u know any better/faster way
to solve these questions I would be very thankful if you would leave a
comment. If you don't mind please tell me whether u liked this
presentation or not. You can use these solutions for any
non-commercial purpose, if u want to share these contents with others,
please mention the source from which u got this.


Wish u all the Best for GATE 2008

if u are also preparing for GATE2008 Computer Science, please get in
touch... we can share a lot of stuff.. I am looking for solved GATE
papers. If u know of any such sources please let me know. I hope to
solve and post more of the 2007 paper after i obtain some more gyan
but... before that i should eat something...

Bye 4 now ,

aamzillaa
Posted by AamzillaA at Sunday, September 23, 2007
3 comments:

Anonymous said...

thank you boss for your solutions.
these will defintely help in our preparation
November 22, 2007 11:28 PM
nimit said...

hey bro...
i m a 2nd yr student from UP Technical University......
I wanna give Gate next yr..
Suggest some thing to me