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 for detail
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 Click here for detail
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. Last Node 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 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



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
A Compound 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 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: 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 by using arrays or linked lists
► A list is a sequence of one 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 in Last out
► First in First out(Page 87)
► 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 Click here for detail
►AVL tree
►All of these




Question No: 14 ( 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 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 copy existing 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, say x, can be declared as
► int &x ; Click here for detail
► 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 for detail






Question No: 4 ( Marks: 1 ) - Please choose one
A Linear Data Structure 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 for detail
► 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 a binary tree and a binary search tree is that ,a binary search tree has
►two children per node whereas a binary 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 of nodes 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 of a binary tree using a pre-order traversal
►Compute the depth of a 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 be deleted, 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 parent as 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 AVL condition
► 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 x is not an value.
► True
► False








Consider the following 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 the following 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.
► 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.
► The total number of nodes (Tn ) in a complete binary tree of depth d is 2 d+1- 1 .
► The height of the 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 be added to a queue is the first item to 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 collection of 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:
The node 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.
The node to be deleted has two sub-trees. The method to be used is to replace the node being deleted by the rightmost child of its left sub-tree.
The node to be deleted has two sub-trees. The method to be used is to replace the node 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 value of 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 of a 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 order 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








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 have two parents.*



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






1. Here is a piece of code from 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 a node 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. None of 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 of a 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 code from 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