Education In Pakistan

VU CS301- Data Structures MIDTERM EXAMINATION Spring 2010

.

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?

 Stack

 Queue

 Tree

Question: ( Marks: 1 ) – Please choose one

Recursive function calls are implemented internally using a data structure

 Stack

 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

VU CS301- Data Structures MIDTERM EXAMINATION Spring 2010

.

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?

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 )

The 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

VU CS301- Data Structures MIDTERM EXAMINATION Spring 2010

.

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