MIDTERM EXAMINATION
CS301- Data Structures
Time: 60 min
M a r k s: 38
Question No: 1 ( M a r k s: 1 ) http://vuzs.net
Which one of the following statement is NOT correct .
► In linked list the elements are necessarily to be contiguous
► 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 ( M a r k s: 1 ) http://vuzs.net
In a program a reference variable, say x, can be declared as
► int &x ;
► int *x ;
► int x ;
► None of the given options
Question No: 3 ( M a r k s: 1 ) http://vuzs.net
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
Question No: 4 ( M a r k s: 1 ) http://vuzs.net
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
► None of these
Question No: 5 ( M a r k s: 1 ) http://vuzs.net
A queue where the de-queue operation depends not on FIFO, is called a priority queue
eslaF►
► True
Question No: 6 ( M a r k s: 1 ) http://vuzs.net
Which one of the following statements is correct?
► Array size is fixed once it is created.
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 ( M a r k s: 1 ) http://vuzs.net
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 ( M a r k s: 1 ) http://vuzs.net
Which of the following abstract data types are NOT used by Integer Abstract Data type group?
►short
int►
float►
long►
Question No: 9 ( M a r k s: 1 ) http://vuzs.net
The operation for adding an entry to a stack is traditionally called :
add►
append►
insert►
►push
Question No: 10 ( M a r k s: 1 ) http://vuzs.net
The operation for removing an entry from a stack is traditionally called:
delete►
peek►
► pop
remove►
Question No: 11 ( M a r k s: 1 ) http://vuzs.net
We can add elements in QUEUE From _________
►Front
►Rear
►From Both Rare and Front
►None of these
Question No: 12 ( M a r k s: 1 ) http://vuzs.net
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
► 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
►none of these
Question No: 13 ( M a r k s: 1 ) http://vuzs.net
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
Log► 2(n+1)
Log► 2(n) – 1
Log► 2(n)
Question No: 14 ( M a r k s: 1 ) http://vuzs.net
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 ( M a r k s: 1 ) http://vuzs.net
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 6 5 + * 7 5 8 + - *
► 3 6 5 7 5 8 + * + - *
► 3 5 6 + * 7 8 5 + - *
► 3 5 6 * + 7 8 5 + * -
Question No: 16 ( M a r k s: 1 ) http://vuzs.net
An array is a group of consecutive related memory locations.
► True
► False
Question No: 17 ( M a r k s: 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.
No, it can be deleted.
Question No: 18 ( M a r k s: 1 )
Deleting a leaf node in binary search tree involves setting ______ pointer/s of that nodes parent as null.
1
2
3
4
Question No: 19 ( M a r k s: 2 )
Describe any two uses of priority queues?
Question No: 20 ( M a r k s: 3 )
How we evaluate postfix expressions?
Question No: 21 ( M a r k s: 5 )
Following is the while loop used in level-order traversal:
while( !q.empty() )
{
treeNode = q.dequeue();
cout
if(treeNode->getLeft() != NULL )
q.enqueue( treeNode->getLeft());
if(treeNode->getRight() != NULL )
?
}
What should be the statement to replace the question mark in the loop above:
Question No: 22 ( M a r k s: 10 )
Write a friend function for a Linked List class called mergeLists that takes two non-empty lists, merge these two lists and return the merged list.
Use the following function prototype:
List mergeLists(List x,List y)
