MIDTERM EXAMINATION SUMMER 2007 CS301 - DATA STRUCTURES (Session - 1 )

[admin]

   MIDTERM  EXAMINATION
SUMMER 2007
CS301 - DATA STRUCTURES (Session - 1 )
   
Marks: 50
Time: 120min


   StudentID/LoginID:   ______________________________
Student Name:   ______________________________
Center Name/Code:   ______________________________
Exam Date:   Wednesday, August 15, 2007


Please read the following instructions carefully before attempting any question:
1.   Mobile Phones are strictly prohibited in the examination center.
2.   Dev C++ or any other software is not allowed.
3.   The duration of this examination is 90 Mins.
4.   This examination is closed book, closed notes, closed neighbors; any one found cheating will get no grade.
5.   Unless stated otherwise, all questions carry a single mark.
6.   Do not ask any questions about the contents of this examination from anyone.
a.   If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.
b.   If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.
7.   Most, but not all, of the examination consists of multiple-choice questions. Choose only one choice as your answer.
a.   If you believe that two (or more) of the choices are the correct ones for a particular question, choose the best one.
On the other hand, if you believe that all of the choices provided for a particular question are the wrong ones, select the one that appears to you as being the least wrong.


For Teacher's use only
Question   1   2   3   4   5   6   7   8   9                 Total
Marks                                 


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


When we say the order of a tree is M, we mean that every non-leaf node must have M subtrees.
      
   ?
   True

   ?
   False



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

The time complexity of an ordered list of inserting/deleting a data item to/from the list is O(length_of_list*length_of_list)
      
   ?
   True

   ?
   False



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

An unbalanced tree is one whose root has many more left descendents than right descendents
      
   ?
   True

   ?
   False



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

Stack and queue data structures are needed to convert the infix notations to post fix notations.
      
   ?
   True


   ?
   False



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

A sequential search of the elements is faster than the binary search of an ordered set of elements in an array.
      
   ?
   True

   ?
   False



Question No: 6    ( Marks: 10 )

Convert the infix expression (A - B) * C + D to postfix. Show the trace of the algorithm, i.e., the stack, the infix expression and postfix expression.


Question No: 7    ( Marks: 10 )

Given two sorted lists, L1 and L2, Write the following routine to compute L1 ? L2 using only the basic list operations.

List intersection(List list1, List list2){
// Write the complete code to compute L1 ? L2 here.
}



Question No: 8    ( Marks: 10 )

Consider a binary search tree (BST) that is initially empty. Draw the tree that will result if the following numbers are inserted in the order given: 35, 28, 13, 43, 30, 89, 38, 16, 12, 40


Question No: 9    ( Marks: 10 )

Consider the following binary tree:

(a) Starting from the root node, perform an In-order traversal of the binary tree below and write the letters in the nodes that will result during the visitations.

(b) Write the nodes if a Pre-order traversal is performed starting with node O.