.

**MIDTERM EXAMINATION**

Spring 2010

CS301- Data Structures

**Question: ( Marks: 1 ) – Please choose one**

In a complete binary tree of depth 5 the number of non-leaf nodes is

15

32

16

31

**Question: ( Marks: 1 ) – Please choose one**

Which of the following is NOT a linear data structure?

Linked List

Stack

Queue

Tree

**Question: ( Marks: 1 ) – Please choose one**

Recursive function calls are implemented internally using a data structure

Stack

Link-List

Tree

Queue

**Question: ( Marks: 1 ) – Please choose one**

**We access elements in AVL Tree in,**

Linear way only

Non Linear way only

Both linear and non linear ways

None of the given options.

**Question: ( Marks: 1 ) – Please choose one**

Consider the following tree,

.

How many leaves does it have?

2

4

6

9

**Question: ( Marks: 1 ) – Please choose one**

In the statement int x[6]; , we cannot assign any value to x because x is not an

lvalue.

True

False

**Question: ( Marks: 1 ) – Please choose one**

In the following C++ code, how many function calls are made?

**int x, y, z;**

**x = 2;**

**y = 3 + x;**

**z = foobar(x,y);**

1

4

7

8

**Question: ( Marks: 1 ) – Please choose one**

**Consider the following infix expression:**

**3 + 5 * 6 – 7 * (8 + 5)**

**Which of the following is a correct equivalent expression(s) for the above?**

6 5 + * 7 5 8 + – *

6 5 7 5 8 + * + – *

5 6 + * 7 8 5 + – *

3 5 6 * + 7 8 5 + * –

**Question: ( Marks: 1 ) – Please choose one**

A subscript of an array may be an integer or an integer expression.

True

False

**Question: ( Marks: 1 ) – Please choose one**

Which of the following is “TRUE” about arrays,

We can increase the size of arrays after their creation.

We can decrease the size of arrays after their creation.

We can increase but can’t decrease the size of arrays after their creation.

We can neither increase nor decrease the array size after their creation.

.

**Question: ( Marks: 1 ) – Please choose one**

Searching an element in an AVL tree take maximum _______ time (where n is

no. of nodes in AVL tree),

Log2(n+1)

Log2(n+1) -1

1.44 Log2n

1.66 Log2n

**Question: ( Marks: 1 ) – Please choose one**

There is/are ________ case/s for rotation in an AVL tree,

1

3

2

4

**Question: ( Marks: 1 ) – Please choose one**

Consider the following infix expression.

5 + 6/2

If one converts the above expression into postfix, what would be the resultant

expression?

56/ + 2

5 6 2 / +

5 6 / 2 +

/62 + 5

**Question No: 16 ( Marks: 1 ) – Please choose one**

**“+” is a _________ operator.**

Unary

Binary

Ternary

None of the above

**Descriptive Questions**

Q) How we can degenerate a binary tree

Q) Why we use queue data structure for level order traversal?

Q) Define the following

The Height of the Tree:

The balance of a node:

Q) Give preorder and post order traversal for the following

.

Q) Balancing AVL after inserting a node

50

30

25 33

26 39

52 60

54

53