Data structures questions

I had following question paper for data structures on 29th Oct, 2007. There were total 10 questions in the engineering paper to be done in 1 hr. I remember only 9 of those:

1. A binary search tree was given. Tell the 4th smallest value in it.

2. An infix expression was given. Draw a binary tree and write it in prefix/postfix notation.

3. A stack has to be implemented. Following methods are given:
PUSH[value] : stack[i] := value; i := i + 1;

POP[] : i := i - 1; return stack[i];
What should be done to make them standard stack operations:
i. exchange method names
ii. exchange return types of methods
iii. change the sequence of steps in both the methods.
iv. everything is fine.

a. i & ii
b. ii & iii
c. iii
d. iv

4. There is a set of n computers, say {C1, C2.... Cn} and a set of k connections between them, say {[Ca, Cb], [Ca, Gx]...}. All the connections are symmetric and transitive. Write an algorithm to find whether all computers can talk to each other or not.

5. A set of assembly language instructions was given. Out of some options, find out what was being done. Correct answer was (XY)^2 + Y + Z.

6. A threading problem was given similar to consumer-producer problem.

7. A set of assembly language instructions was given to operate on a stack. Use those to write assembly code to perform following using a stack:
i := 0; A := 300;
while (i < 10) {
A := A + 200;
i := i + 1;
}

8. Write an algorithm to find whether two binary trees are equal (content-wise) or not.

9. Represent (-5) of base 10 in 2�s complement representation.

muktajindal
Profile Answers by muktajindal Questions by muktajindal
Nov 10th, 2007
2
3090

Questions by muktajindal

Data Structures

Answer

Showing Answers 1 - 2 of 2 Answers

manishmodgil
Profile Answers by manishmodgil

Dec 28th, 2007

First Question's Ans :

Create a FIFO list of 4 digits.

start from the root of the BST and keep on insrting the nodes in the FIFO till either there is no left subtree of the BST is left and the FIFO is not empty.

IF FIFO is empty and there is not node on the left sub-tree move to right subtree.

At the end , the front of the queue / FIFO is the answer.