# VU CS301 -Data Structure MIDTERM Solved/Unsolved Papers Spring 2010

MIDTERM EXAMINATION

Spring 2010

CS301- Data Structures

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          (Page 101)

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     (Page 5)

► 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

Here function argument passing by reference method is used, so when we call a function we will give the variable reference as parameter.

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       (Page 202)

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

The tree data structure is a
► Linear data structure

► Non-linear data structure        (Page 112)

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

Declaring a parameter as a const simply means that the function can’t change the value of its parameters.

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.

Only the x and y can alter the private member variable of the foo class object. Last Option is more correct but not exact. In the last option the two function name are not mentioned

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            (Page 139)

► 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        (Page 53)

► 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       (Page 70)

► 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

► 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 that requires re-balancing. Consider the two cases given below:

1) An insertion into left sub tree of the left child of a

2) An insertion into right sub tree 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,

► Linear data structure

► Hybrid data structure (Mixture of Linear and Non Linear) ► None of the given options.

# VU CS301 -Data Structure MIDTERM Solved/Unsolved Papers Spring 2010

MIDTERM EXAMINATION

Spring 2010

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

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

► True

► False         (Page 7)

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

In an array list the current element is

► 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     Click here for detail

► 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.         Click here for detail
► 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 (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      (Page 161,54)

► 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?

► Minus operator

► Plus operator

► Exponentiation operator

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

Each node in Binary Search Tree has

► 1 pointer

► 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 tree

► The order of a tree indicates a maximum number of children allowed at each node of the ► 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.      Click here for detail

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

Searching an element in an AVL tree take maximum in AVL tree,

► Log2(n+1)

time (where n is no. of nodes
► Log2(n+1) -1

► 1.44 Log2n    (Page 227)

► 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         (Page 229)

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

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 / +      (Page 66)

► 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         (Page 112)

Question No: 16 ( Marks: 1 ) – Please choose one
“+” is a operator.

► Unary

► Binary    (Page 64)

► Ternary

► None of the above

# VU CS301 -Data Structure MIDTERM Solved/Unsolved Papers Spring 2010

MIDTERM EXAMINATION

Spring 2010

1. Addition of new items in stack make the pointer ———— by 2

a. Increment, bits

b. Increment, bytes

c. Decrement, bits

2. Next item in a linked list is known as

a. Index

b. Item

d. Child

3. What will be the postfix notation of 5+6/2.

a. 56+/2

b. 562+/

c. 562/+       (Page 66)

d. 5+62/

4. In an AVL tree to delete a parent with two childs in a straight line following rotations will be required:-

a. Single

b. Double

c. Triple

d. None.

5. To check the depth of an AVL tree following time will be taken:-

a. 1.66 Log2n

b. 1.44 Log2n     (Page 227)

c. Log2 (n+1)-1

d.        1.66 Log2n (n+1)

6. BST is a Structure:-

a. Linear

b. Non Linear

c. Circular

d. None of Above

7. After creation of an array:-

a. Size can be increase but can not be decreased.

b. Size can be decreased but can not be increased.

c. Size can neither be increased nor be decreased.  Click here for detail

d. Size can be increased and can also be decreased.

8. Each node in a BST has Pointers:-

a. 1

b. 2

c. 3

d. 4

9. Highest Operators Precedence is of the following operator:-

a. Plus

b. Minus

d. Exponentiation

10. Following are the linear data structures:-

a. Stacks

b. Queues

c. Both a & b   (Page 52, 87)

d. None of the above

11. Each entry which points to a null value in a Singly Linked List is known as:-

a. Node

b. First Node

c. Last Node

12. Non recursive calls are faster than the Recursive calls.

a. True       (Page 323)

b. False

13. Tree data structure is a

a. Linear

b. Non Linear       (Page 112)      rep

c. Circular

d. None of Above

14. What will be the valid postfix notation of A+B*C-D

a. ABC+*D-

b. ABC*+D-    (According to rule)

c. ABCD+-*

d. AB+D*C

15. When an operator is used in between two operands this is which type of notation

a. Prefix

b. Postfix

c. Infix     (Page 64)

d. None of the Above