June 2012 - Paper II

Hey everyone, back after a two day break. Since we are done with December 2010 paper, I want to choose the next one and it would be June 2012 now. From June 2012, Paper-II and Paper-III are objective so we will do with paper-II first and then get on to paper-III. Like all other solutions, it is all about understanding the answer and arriving at it conclusively, so that we can learn something out of it which can be used in another situation.
It is never about simply remembering the answer for every question. It is all about understanding it. That is why i am spending some time going through the explanation for answering every question. Infact i wanted to do only one question a day, but that way we would take a lot of time in finishing the solutions for the question papers and so i try to answer more than one question. Okay, without wasting much of time, let us start.

1. The postfix expression AB + CD – * can be evaluated using a
(A) stack
(B) tree
(C) queue
(D) linked list

Ans:-A

Explanation:-This is a simple question. The postfix expression can be evaluated using a stack. First the operands are pushed into the stack and the moment a operator is encountered, operands are popped out, operation performed on the operands and the result once again pushed into the stack. This series of activities continue till the entire expression is not evaluated. So the answer is A.

---

2. The post order traversal of a binary tree is DEBFCA. Find out the pre- order traversal.

(A) ABFCDE
(B) ADBFEC
(C) ABDECF
(D) None of the above

Ans:-C

Explanation:-
A binary tree is a data structure which has at most two child nodes. A binary tree can be traversed in three ways. Inorder, preorder and postorder. The three methods of traversal can be explained this way.

TYPE	FIRST	SECOND	THIRD
Inorder	L - Left	Ro - Root	R - Right
Preorder	Ro - Root	L - Left	R - Right
Postorder	L - Left	R - Right	Ro - Root

Left will always be followed by right. But Root would be either in the front or in the middle or at the last depending on whether it is pre, in or postorder traversal. So given a post order traversal of a binary tree, we can know the root first. In the question, the post order traversal is given as DEBFCA. Since Root is the last node to be traversed in a post order traversal we know one thing for sure. A is the root.
Next, we are left with only DEBFC. Here some of the nodes belong to the left side of the binary tree and some belong to the right side. How many nodes belong to the left and how many belong to the right. Since left side of the binary tree is considered first, and since every node is expected to have at most two child, DEB will be the left side of the binary tree and FC would be the right.
Now, we know that FC is in the right side of the binary tree. Again the last node would be the root of the sub tree and F its left side.
Next we come to the left side of the binary tree and it is DEB. Again B would be the root of the sub tree. D and E are its left and right side respectively. So the binary tree would look something like this given below.

After constructing the binary tree, writing the preorder traversal is very simple. In preorder traversal root comes first. Since A is the root, A would appear first. Following Root would be the Left and Right sub tree and so the left subtree would be BDE. Again B would be the root of the left sub tree followed by D and E which are the left and right child respectively. SO the preorder traversal till now would be ABDE. Last comes the Right sub tree. Here again C would be the root of the right sub tree followed by C its left child. So the entire preorder traversal of the tree would be ABDECF. So option C is the right answer.

---

3.The branch logic that provides making capabilities in the control unit is known as

(A) Controlled transfer
(B) Conditional transfer
(C) Unconditional transfer
(D) None of the above

Ans:-A

Explanation:- This question is available in lot of websites and other materials and the answer given there is unconditional transfer which is option C. But UGC answer key is given as option A. I am just going to go with A, but will find out more about this and post it. Meanwhile, if there are any explanation for this question,please post it, so that everyone can benefit.

---