Papers, Notes, Books & Help For Students

.

**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

.

**MIDTERM EXAMINATION**

Spring 2010

CS301- Data Structures

Ref No: 1349576

Time: 60 mina

Marks: 38

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

In an array we can store data elements of different types.

**► **True

**► **False

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

In an array list the current element is

**► **The first element

**► **The middle element

**► **The last element

**► **The element where the current pointer points to

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

Which one of the following calling methods does not change the original value of the argument

in the calling function?

**► **None of the given options

**► **Call by passing the value of the argument

**► **Call by passing reference of the argument

**► **Call by passing the address of the argument

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

Which one of the following statements is NOT correct?

.

**► **Array size can be changed after its creation.

**► **Link List size can be changed after its creation

**► **Binary Search Tree size can be changed after its creation

**► **AVL Tree size can be changed after its creation

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

Suppose that the class declaration of SomeClass includes the following function prototype.

bool LessThan( SomeClass anotherObject );

**Which of the following tests in the client code correctly compares two class objects alpha**

**and beta?**

**► **if (alpha < beta)

**► **if (alpha.LessThan(beta))

**► **if (LessThan(alpha, beta))

**► **if (LessThan(alpha).beta)

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

A queue is a ________data structure, whereas a stack is a ________data structure.

**► **FIFO, LIFO

**► **LIFO,FIFO

**► **none of these

**► **both of these

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

Which one of the following operators has higher priority than all of others ?

**► **Multiplication operator

**► **Minus operator

**► **Plus operator

**► **Exponentiation operator

.

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

Each node in Binary Search Tree has

**► **1 pointer

**► **2 pointers

**► **3 pointers

**► **4 pointers

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

Four statements about trees are below. Three of them are correct. Which one is INCORRECT?

**► **Trees are recursively defined multi-dimensional data structures

**► **The order of a tree indicates a maximum number of childen allowed at each node of the

tree

**► **A search tree is a special type of tree where all values (i.e. keys) are ordered

**► **If Tree1’s size is greater than Tree2’s size, then the height of Tree1 must also be greater than

Tree2’s height.

**Question No: 10 ( 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 No: 11 ( 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 No: 12 ( Marks: 1 ) – Please choose one**

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

**► **1

**► **3

**► **2

**► **4

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

Consider the following statements.

(i) A binary tree can contain at least 2L Nodes at level L.

(ii) A complete binary tree of depth d is a binary tree that contains 2L Nodes at each level L

between 0 and d, both inclusive.

(iii) The total number of nodes (Tn ) in a complete binary tree of depth d is 2 d+1 – 1 .

(iv) The height of the complete binary tree can be written as h = log 2 (Tn+1)-1 where Tn is

Total number of Nodes.

Which one of the following is correct in respect of the above statements regarding the Binary trees?

**► **(i) and (iii) only

**► **(i), (ii) and (iii) only

**► **(ii) and (iii) only

**► **(ii), (iii) and (iv) only

**Question No: 14 ( 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: 15 ( Marks: 1 ) – Please choose one**

Which of the following is a non linear data structure?

**► **Linked List

**► **Stack

**► **Queue

**► **Tree

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

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

**► **Unary

**► **Binary

**► **Ternary

**► **None of the above

**Question No: 17 ( Marks: 2 )**

Which process places data at the back of the queue?

**Question No: 18 ( Marks: 2 )**

How we can delete a node with two Childs in a binary search tree using its right sub tree.

**Question No: 19 ( Marks: 2 )**

Why we use Reference Variables. Give one example.

**Question No: 20 ( Marks: 3 )**

**T****he nodes of a binary tree have data 1, 2, 3, 4. The in-order traversal of the tree yields**

**2,1,4,3. The postorder traversal is 2, 4, 3, 1. The root of the tree is at level 0.**

**Q3: Which value is in the right child of the root? (1 Pt)**

(A) 1 (B) 2 (C) 3 (D) 4 (E) none

**Question No: 21 ( Marks: 3 )**

What normally is the sequence of operations while constructing an AVL tree?

.

**Question No: 22 ( Marks: 5 )**

Here is a small binary tree:

**14**

**/ \**

**2 11**

**/ \ / \**

**1 3 10 30**

**/ /**

**7 40**

Write the order of the nodes visited in:

A. An in-order traversal:

B. A pre-order traversal:

**Question No: 23 ( Marks: 5 )**

**Is the given tree is an AVL tree? If Not then redraw is so that it becomes AVL**

.

**MIDTERM EXAMINATION**

Spring 2010

CS301- Data Structures

Time: 60 min

Marks: 38

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

A

queue where the de-queue operation depends not on FIFO, is called a priority queue

**► **False

**► **True

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

The

data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we

should

**► **Use better data structures

**► **Increase the hard disk space

**► **Use the better algorithm

**► **Use as much data as we can store on the hard disk

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

Consider the function X as under

int X (int& Value)

{

return Value;

}

Now a and b are integers in a calling function. Which one of the following is a valid call to the

above function X.

**► **a = X (b) ;

**► **a = X (&b) ;

.

**► **a = X (*b) ;

**► **None of the given options

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

In the call by value methodology, a copy of the object is passed to the called function.

**► **False

**► **True

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

The tree data structure is a

**► **Linear data structure

**► **Non-linear data structure

**► **Graphical data structure

**► **Data structure like queue

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

When should you use a **const reference **parameter?

**► **Whenever the parameter has huge size.

**► **Whenever the parameter has huge size, the function changes the parameter within its

body, and you do NOT want these changes to alter the actual argument.

**► **Whenever the parameter has huge size, the function changes the parameter within its

body, and you DO want these changes to alter the actual argument.

**► **Whenever the parameter has huge size, and the function does not change the parameter

.

within its body.

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

Here is the start of a C++ class declaration:

class foo

{

public:

void x(foo f);

void y(const foo f);

void z(foo f) const;

…

Which of the three member functions can alter the PRIVATE member variables of the foo object

that activates the function?

**► **Only x can alter the private member variables of the object that activates the function.

**► **Only y can alter the private member variables of the object that activates the function.

**► **Only z can alter the private member variables of the object that activates the function.

**► **Two of the functions can alter the private member variables of the object that activates

the function.

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

What is the maximum depth of recursive calls a function may make?

**► **1

**► **2

**► **n (where n is the argument)

**► **There is no fixed maximum

.

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

Suppose n is the number of nodes in a complete Binary Tree then maximum steps required

for a search operation are,

**► **Log2 (n+1) -1

**► **Log2 (n+1)

**► **Log2 (n) – 1

**► **Log2 (n)

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

In the linked list implementation of the stack class, where does the push member function places

the new entry on the linked list?

**► **At the head

**► **At the tail

**► **After all other entries that are greater than the new entry.

**► **After all other entries that are smaller than the new entry.

.

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

Suppose we have a *circular *array implementation of the queue class, with ten items in the queue

stored at data[2] through data[11]. The CAPACITY is 42, i.e., the array has been declared to be

of size 42. Where does the push member function place the new entry in the array?

**► **data[1]

**► **data[2]

**► **data[11]

**► **data[12]

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

The expression AB+C* is called ?

**► **Prefix expression

**► **Postfix expression

**► **Infix expression

**► **None of these

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

_________ is a binary tree where every node has a value, every node’s left subtree contains only

values less than or equal to the node’s value, and every node’s right subtree contains only values

that are greater then or equal ?

**► **Strictly Binary Tree

**► **Binary Search tree

.

**► **AVL tree

**► **All of these

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

Consider the following binary search tree (BST):

If node A in the BST is deleted, which two nodes are the candidates to take its place?

**► **J and I

**► **H and E

**► **D and E

**► **L and M

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

**Let’s call the node as a that requires re-balancing. Consider the two cases given below:**

1) An insertion into left subtree of the left child of a

2) An insertion into right subtree of the right child of a.

.

Which of the following statement is correct about these two cases.

1) The insertion occurs outside (i.e., left-left or right-right) in cases 1 and 2. single rotation can

fix the balance in these two cases.

2) The insertion occurs inside ((i.e., left-left or right-right) in cases 1 and 2. single rotation

cannot fix the balance in these two cases

**Question No: 16 ( 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 No: 17 ( Marks: 2 )**

AVL Tree is,

**► **Non Linear data structure

**► **Linear data structure

**► **Hybrid data structure (Mixture of Linear and Non Linear)

**► **None of the given options.

**Question No: 18 ( Marks: 2 )**

.

How we can delete a node with two Childs in a binary search tree using its right sub tree.

**Question No: 19 ( Marks: 2 )**

What is Function Call Stack Give short answer.

**Question No: 20 ( Marks: 3 )**

xplain the two cases in which we apply double rotation in an AVL tree.

**Question No: 21 ( Marks: 3 )**

Here is a small binary tree.

**Write the order of the nodes visited in**

a) A Post-order traversal

b) A level-order traversal

.

**Question No: 22 ( Marks: 5 )**

Please consider the following AVL tree.

1. Insert new node 87 in this tree and make tree balance.

2. Write balance factor of each node after and before inserting node 87.

**Question No: 23 ( Marks: 5 )**

Consider the following binary tree

Show the state of the tree after deleting 24.