CS301 Mid term paper 2009

MIDTERM EXAMINATION  

Spring 2010 

CS301- Data Structures

Time: 60 min
M a r k s: 38


Question No: 1 ( M a r k s: 1 ) http://vuzs.net

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

► True

► False


Question No: 2 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net

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 ( M a r k s: 1 ) http://vuzs.net

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 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 )


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

► Multiplication operator

► Minus operator

► Plus operator

► Exponentiation operator
 

 

Question No: 8 ( M a r k s: 1 ) http://vuzs.net

Each node in Binary Search Tree has,

► 1 pointer

► 2 pointers

► 3 pointers

► 4 pointers

Question No: 9 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net

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 ( M a r k s: 1 ) http://vuzs.net


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

► 1

► 3

► 2

► 4

Question No: 13 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net


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 ( M a r k s: 1 ) http://vuzs.net


Which of the following is a non linear data structure?

► Linked List

► Stack

► Queue

► Tree

Question No: 16 ( M a r k s: 1 ) http://vuzs.net


“+” is a _________operator.

► Unary

► Binary

► Ternary

► None of the above


Question No: 17 ( M a r k s: 2 )


Which process places data at the back of the queue?


Question No: 18 ( M a r k s: 2 )


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


Question No: 19 ( M a r k s: 2 )


Why we use Reference Variables. Give one example.


Question No: 20 ( M a r k s: 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

www.vuzs.net
Question No: 21 ( M a r k s: 3 )


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

Question No: 22 ( M a r k s: 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 ( M a r k s: 5 )


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