CS301 Data Structures MIDTERM EXAMINATION 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

d. Decrement, bytes                  Click here for detail

2. Next item in a linked list is known as a. Index

b. Item

c. Node               Click here for detail

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                 Click here fordetail

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

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

d. Size can be increased andcan also be decreased.

8. Each node in a BST has Pointers:- a. 1

b. 2                  Click here fordetail

c. 3 d. 4

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

b. Minus

c. MultiplyClick here for detail

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. LastNode d. Head 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)

c. Circular

d. None of Above

14. What will be the valid postfix notation ofA+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

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

Which one of the following is a valid postfix expression?

► ab+c*d-

► abc*+d- (According to rule)

► abc+*d-

► (abc*)+d-

Question No: 2 ( 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: 3 ( Marks: 1 ) - Please choose one

ACompound Data Structure is the data structure which can have multiple data items of same type or of different types. Which of the following can be considered compound data structure?

► Arrays Click here for detail

► LinkLists

► Binary Search Trees

► All of the given options

Question No: 4 ( Marks: 1 ) - Please choose one

Suppose a pointer has been declared in main but has not assigned any variable address then

►That pointer points to First byte in main function

►That pointer contains a NULL value

►None of these

►That pointer points to any memory address

Question No: 5 ( 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 thePRIVATE member variables of the foo object that activates the function?

►Only x can alter the private member variables ofthe 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 ofthe object that activates the function.

►Two of the functions canalter 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 thetwo function name are not mentioned

Question No: 6 ( Marks: 1 ) - Please choose one

The operation for removing an entry from a stack is traditionally called:

► delete

► peek

► pop (Page 53)

► remove

Question No: 7 ( Marks: 1 ) - Please choose one

Which statement of the following statements is incorrect?

► Lists can be implemented byusing arrays or linked lists

► A list is a sequence ofone or more data items

► Stack is a special kind of list in which all insertions and deletions take place at one end

► Stacks are easier to implement than lists

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

Parameters in function call are passed using,

► Stack (Page 80)

► Queue

► Binary Search Tree

► AVL Tree

Question No: 9 ( Marks: 1 ) - Please choose one

Consider the following sequence of push operations in a stack:

stack.push(’7’); stack.push(’8’); stack.push(’9’); stack.push(’10’); stack.push(’11’); stack.push(’12’);

►7 8 9 10 11 12

►9 8 11 10 7 12

►9 10 8 11 12 7

►9 10 8 12 7 11

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

Consider the following function:

void test_a(int n)

{

cout << n<< " ";

if (n>0)

test_a(n-2);

}

What is printed by the call test_a(4)?

►420

►024

►02

►24

Question No: 12 ( Marks: 1 ) - Please choose one

Queue follows,

► Last in First out

► First inLast out

► First inFirst out(Page 87)

► None of these

Question No: 13 ( Marks: 1 ) - Please choose one

isa binary tree where every node has a value, every node's leftsubtree contains only values lessthan or equal to the

node's value, and every node's right subtree contains only values thatare greater then or equal?

►Strictly Binary Tree

►Binary Search tree            Click here fordetail

►AVL tree

►All of these

Question No: 14 ( Marks: 1 ) - Please choose one

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

►Trees are recursively defined multi-dimensional data structures            Click here for detail

►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: 15 ( Marks: 1 ) - Please choose one

Below is a binary search tree. If we delete the value 50 using the algorithm we discussed, what value will be in the

root of the remaining tree?

► 50

► 60

► 70

► 80

Question No: 16 ( Marks: 1 ) - Please choose one

Is a data structure that can grow easily dynamically at run time without having to copyexisting elements?

► Array

► List

► Both of these

► None of these

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

Which one of the following statement is NOT correct .

► In linked list the elements are necessarily to be contiguous                Click here for detail

► In linked list the elements may locate at far positions in the memory

► In linked list each element also has the address of the element next to it

► In an array the elements are contiguous

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

In a program a reference variable, sayx, can be declared as

► int &x ;                                Click here fordetail

► int *x ;

► int x ;

► None of the given options

Question No: 3 ( Marks: 1 ) - Please choose one

Linked lists are collections of data items "lined up in a row" , insertions and deletions can be made only at the front and the back of a linked list.

► True

► False                                      Click here fordetail

Question No: 4 ( Marks: 1 ) - Please choose one

A Linear DataStructure is the data structure in which data elements are arranged in a sequence or a linear list. Which of the following is Non Linear Data Structure?

► Arrays

► LinkLists

► Binary Search Trees                                      Click here for detail

► None of these

Question No: 5 (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: 6 ( Marks: 1 ) - Please choose one

Which one of the following statements is correct?

►                   size is fixed once it is created                       Click here fordetail

►   Link List size is fixed once it is created.

►Binary Search Tree size is   fixed once it is created

►   AVL Tree size is fixed once it is created

Question No: 7 ( Marks: 1 ) - Please choose one

Which one of the following is correct about pointers?

►They always point to   different memory locations

►They may point to a single   memory location

►The address of two pointer variables is same

►   None of these

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

Which of the following abstract data types are NOT used by Integer Abstract Data type group?

►

►Int

►float                                            Click here for detail

►long

Question No: 9 ( Marks: 1 ) - Please choose one

The operation for adding an entry to a stack is traditionally called :

►add

►append

►insert

►push(Page 53)

Question No: 10 ( Marks: 1 ) - Please choose one

The operation for removing an entry from a stack is traditionally called:

►delete

►peek

►pop(Page 53)

►remove

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

We can add elements in QUEUE From               

►Front

►Rear (Page 91)

►From Both Rare and Front

►None of these

Question No: 12 ( Marks: 1 ) - Please choose one

The difference between abinary tree and a binary search tree is that ,a binary search tree has

►two children per node whereas abinary tree can have none, one, or two children per node

Click here for detail

►   in binary search tree nodes are inserted based on the values they contain

►in binary tree nodes are inserted based on the values they contain

►              of these

Question No: 13 ( Marks: 1 ) - Please choose one

Suppose n is the number ofnodes in a complete Binary Tree then maximum steps required for a search operation are,

►   Log2 (n+1)-1 (Page 139)

►Log   2 (n+1)

►Log   2 (n) – 1

►Log   2 (n)

Question No: 14 ( Marks: 1 ) - Please choose one

The following is a segment of a C program. int pqr(BinaryNode t)

{ if (t == null )

return -1;

else

return 1+max(pqr(t.left),pqr(t.right)) }

Identify, what the above program intend(s) to do?

►Compute the height of a   binary tree using an in-order traversal

►Compute the height of a   binary tree using a pre-order traversal

►Compute the depth ofa binary tree using a pre-order traversal

►Compute the depth ofa      binary tree using a post-order traversal

Question No: 15 ( 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?

►3 65+*7 5 8 +-*

►3 657 5 8+* + -*

►3 5 6+*7 8 5 +-*

►3 5 6 * + 7 8 5 + * -

Question No: 16 ( Marks: 1 ) - Please choose one

An array is a group of consecutive related memory locations.

► TrueClick here for detail

► False

Question No: 17

( Marks: 1 )

Is this a correct statement? Give answer in Yes or No.

A node cannot bedeleted, when the node to be deleted has both left and right subtrees.

False ---- No, it can be deleted.

Question No: 18 ( Marks: 1 )

Deleting a leaf node in binary search tree involves setting            pointer/s of that node’s parentas null.

1

2

3

4

Select the one FALSE statement about binary trees:

a. Every binary tree has at least one node.

b. Every non-empty tree has exactly one root node.

c. Every node has at most two children.

d. Every non-root node has exactly one parent.

Below is a binary search tree. If we delete the value 50 using the algorithm we discussed, what value will be in the root of the remaining tree?

► 50

► 60

► 70

► 80

A tree is an AVL tree if

► Any one node fulfills the AVLcondition

► At least half of the nodes fulfill the AVL condition

► All the nodes fulfill the AVL condition

► None of the given options

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

► True

► False

Consider thefollowing pseudo code declare a stack of characters while ( there are more characters in the word to read )

{

read a character

push the character on the stack

}

while ( the stack is not empty )

{

pop a character off the stack write the character to the screen

}

What is written to the screen for the input"apples"?

► selpa

► selppa

► apples

► aaappppplleess

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

We can add elements in QUEUE From               

► Front

► Rear

► From Both Rare and Front

► None of these

Consider thefollowing tree.

How many descendants does the root have?

► 5

► 6

► 7

► 8

Which of the following statement regarding binary tree is NOT correct.

► A binary tree can contain at least 2L Nodes at level L.

► Acomplete binary tree of depth d is a binary tree that contains 2L Nodes at each level L between 0 and d, both inclusive.

► The total number ofnodes (Tn ) in a complete binary tree of depth d is 2 d+1- 1 .

► The height ofthe complete binary tree can be written as h = log 2 (Tn+1)-1 where Tn is Total number of

Nodes.

The following are statements related to queues.

1.  The last item to beadded to a queue is the first itemto be removed

2.  A queue is a structure in which both ends are not used

3.  The last element hasn’t to wait until all elements preceding it on the queue are removed

4.  A queue is said to be a last-in-first-out list or LIFO data structure. Which of the above is/are related to normal queues?

► (iii) and (ii) only

► (i), (ii) and (iv) only

► (ii) and (iv) only

► None of the given options

The_             method of list data structure removes the element residing at the current position.

► Add

► next

► remove

► find

The depth of a binary tree is

Select correct option:

Total number of nodes in the tree Number of leaf nodes in the tree Number of non-leaf nodes in the tree Maximum level of a leaf*

In which traversal method, the recursive calls can be used to traverse a binary tree ? Select correct option:

In preorder traversal only

In inorder traversal only

In postorder traversal only

All of the given options*

Which of the following statement is false? Select correct option:

Arrays are dense lists and static data structure

data elements in linked list need not be stored in adjecent space in memory

pointers store the next data element of a list*

linked lists are collectionof the nodes that contain information part and next pointer

Which of the following statement related to deleting nodes from a binary search tree is NOT

correct ?

Select correct option:

Thenode to be deleted has no children; the node can be deleted without any adjustment. Delete the leaf node and set reference from its parent to null reference.

Thenode to be deleted has two sub-trees. The method to be used is to replace the node beingdeleted by the rightmost child of its left sub-tree.

Thenode to be deleted has two sub-trees. The method to be used is to replace thenode being deleted by the leftmost child of its right sub-tree.

The node to be deleted has no children; the node can be deleted with very few adjustments to the tree.* (not sure)

Which one of the following calling method does not change the original valueof the argument in the calling function?

Select correct option:

Call by passing reference of the argument Call by passing the address of the argument Call by passing the value of the argument*

None of the given options

In-order traversal method traverses the data in

Select correct option:

Non sorted order Random order Sorted order* None of the given

The depth ofa complete binary tree is given by

Select correct option: Dn = n log2n

Dn = n log2n+1

Dn = log2n

Dn = log2(n+1)-1*

If we write functions for recursive and non recursive in ordertraversal method of BST, what will be the difference between its functions prototypes?

Select correct option:

Different return types Different function names* Different arguments list Nothing will be different

In a program a reference variable, say x, can be declared as

Select correct option:

int &x ;*

int *x ;

int x ;

None of the given options

Which one is not the property of binary tree? Select correct option:

Every node in binary tree should have maximum two children.

Only one node should havetwo parents.*

Sibling nodes should have same parent. None of given options.

1. Here is a piece of codefrom inset method of BST, to search the correct position of newly created node.

while( *info != *(p->getInfo()) && q != NULL ) { p = q;

if( *info < *(p->getInfo()) ) q = p->getLeft();

else q = p->getRight(); }

If there are 8 levels in a tree then, how many times the while loop will be executed. Select correct option:

4

8 *

10

16

During in-order traversal using recursive calls, if we found anode is NULL. It means this node will satisfy following condition.

Select correct option:

It will not have left child

It will not have right child

It will not have both left and right children

None of given options *

During deletion of node from BST, if we found this node don’t have in-order successor and predecessor.

It means this node is                     . Select correct option:

Left most node in the binary search tree Right most node in binary search tree Root node * (not sure)

None of given options

Longest path from root node to farthest leaf node is called

Select correct option: Level Length Depth * Node level

of tree

Binary search algorithm cannot be applied to       _ Select correct option:

sorted linked list * sorted binary trees sorted linear array None of given options

Deleting a

node in BST is a

case

Select correct option: Root, simplest

Left child, simplest Right child, simplest Leaf, simplest *

Which one is not the property of binary tree? Select correct option:

Every node in binary tree should have maximum two children.

Only one node should have two parents. * Sibling nodes should have same parent. Noneof given options.

In-order traversal method traverses the data in

Select correct option:

Non sorted order Random order Sorted order* None of the given

In which traversal method, the recursive calls can be used to traverse a binary tree ? Select correct option:

In preorder traversal only

In inorder traversal only

In postorder traversal only

All of the given options *

Question # 5 of 10 ( Start time: 02:07:23 AM ) Total Marks: 1

Which one is the correct function call for the following function of calculating cube? int cube(int& num) { . . . }

Select correct option: cube(&num) cube(&&num)

cube(*num)

cube(num) *

Question # 6 of 10 ( Start time: 02:08:02 AM ) Total Marks: 1

The depth ofa complete binary tree is given by

Select correct option: Dn = n log2n

Dn = n log2n+1

Dn = log2n

Dn = log2(n+1)-1 *

Question # 7 of 10 ( Start time: 02:08:41 AM ) Total Marks: 1

1. Here is a piece of codefrom inset method of BST, to search the correct position of newly created node. while( *info != *(p->getInfo()) && q != NULL ) { p = q; if( *info < *(p-

>getInfo()) ) q = p->getLeft(); else q = p->getRight(); } If there are 8 levels in a tree then, how many times the while loop will be executed.

Select correct option:

4

8 *

10

16

Question # 8 of 10 ( Start time: 02:09:22 AM ) Total Marks: 1

If we write functions for recursive and non recursive inorder traversal method of BST, what will be the difference between its functions prototypes?

Select correct option:

Different return types Different function names * Different arguments list Nothing will be different

Question # 9 of 10 ( Start time: 02:09:43 AM ) Total Marks: 1

When converting binary tree into extended binary tree, all the original nodes in binary tree are

Select correct option:

Internal nodes on extended tree* External nodes on extended tree Vanished on extended tree

None of above

(dont know)

Question # 10 of 10 ( Start time: 02:10:07 AM )               Total Marks: 1

A binary tree whose every node has either zero or two children is called

Select correct option: Complete binary tree

Binary search tree Strictly binary tree * None of above

Quiz Start Time: 09:51 PM Time Left          66

sec(s)

Question # 4 of 10 ( Start time: 09:52:58 PM )  Total Marks: 1

Leaf node of binary search tree contains

Select correct option:

One Null pointer Three Null pointers Two Null pointers* All of the given