# VU CS301 – Data Structures FinalTerm Solved Unsolved Past Papers 2004

Page 1 of

CS301 Data Structures

Final Term Examination – August 2004

Time Allowed: 150 Minutes

Please read the following instructions carefully before attempting any of the questions:

1. This examination is closed book, closed notes, closed neighbors; any one found cheating will get no grade.
2. Attempt all questions. Marks are written adjacent to each question.
3. Do not ask any questions about the contents of this examination from anyone.
1. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.

1. If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.

1. Wriite all steps, missing steps may lead to deduction of marks.
2. You are allowed to use any development environment like Dev C++ etc.

**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.

 Total Marks: 135 Total Questions: 7 Question No. 1 Marks : 15

Consider the following Sort algorithms:

Quicksort, Mergesort, Insertion Sort, Bubble Sort, Selection Sort

(a)  Which is the fastest on an already sorted array?

(b)  Which do roughly the same amount of work regardless of the arrangement of the data values in the array?

(c)  Show the following array as it is sorted in ascending order, step by step, by insertion sort. int[6] Arr = {3,2,7,9,1,6};

Question No. 2                                                                                                             Marks : 10

Consider the following binary tree:

(a)   Starting from the root node A, perform a pre-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 an in-order traversal is performed starting with node A.

Question No. 3                                                                                                             Marks : 25

Consider the following problem: Given N elements in a data structure, find the middle element in sorted order. This is also called the median. Note the elements are not necessarily in sorted order unless the data structure forces them to be. For example, if the numbers are:

34 76  87  12  8  96  83

Then the middle element in sorted order is 76. If the elements had been sorted, 76 would be in the middle.

For each of the following possible data structures assume the N elements are already in the data structure. For each data structure, describe briefly in one or two lines an efficient algorithm to find the middle element in sorted order (do not write code).

1. an unsorted array
2. a sorted linked list – (here the elements are already sorted)
3. a min heap
4. a balanced binary search tree
5. a hash table of size M

Question No. 4                                                                                                             Marks : 20

Using modulo 11 as the hash function “h(x) = x mod 11”, show the contents of the hash table (indexed by 0..10) after the following values are stored in order: 3,14,25,4, 37.

Show (pictorially) the result after each insertion.

(a) Use linear probing to handle collisions.

(b) Use separate chaining to handle collisions.

Page 2 of 3

 Question No. 5 Marks : 30 Consider the following piece of code: [30] class Employee { public: // Constructor functions Employee(); Employee(const string Name, const int Years, const float Salary, const bool Promote = True); string GetName () const; void GetAge (int &Age) const; float GetSalary() const; void Print() const; void SetName(const string Name); void SetAge(const int Age); void SetSalary(const float Pay); void SetPromotable(const bool Promote); private: bool getPromotability() const; string employeeName; int age; float salary; bool promotable; }; // Functions float ComputeAverageSalary (const Employee Workers[], const int NumWorkers) { float Sum = 0.0; for (int i = 0; i < NumWorkers; i++) { // CODE FRAGMENT 1 } return (Sum / NumWorkers); }; // Main program int main( ) { // INITIALIZATION CODE // CODE FRAGMENT 2 return 0;

}

a) Given these definitions above, determine which of the following are valid object creation examples? (Circle Valid or Invalid)

(Valid / Invalid) Employee E2 (“”, 0, 0.0);

(Valid / Invalid) Employee E1 (Mohammed”, 33, (float)40000, True);

(Valid / Invalid) Employee E3 (E1);

(Valid / Invalid) Employee E5 (33, 40000.0, True);

(Valid / Invalid) Employee E4;

b) Assume the Employee objects Amy and Bob have been properly created and initialized. Which of the following are valid object usage examples? (Circle Valid or Invalid)

(Valid / Invalid) int Year = Bob.GetAge(); (Valid / Invalid) Bob.SetPromotable(bool True); (Valid / Invalid) Bob = Amy;

(Valid / Invalid) Bob.SetName (Amy.GetName()); (Valid / Invalid) bool Promote = Bob.getPromotability();

c) Assume the Employee objects Bob and Amy have been properly created and initialized. Which of the following are valid object usage examples? (Circle Valid or Invalid)

(Valid / Invalid) SetSalary(Bob, 35000);

(Valid / Invalid) Print(Bob);

(Valid / Invalid) Bob.SetAge(30);

(Valid / Invalid) Amy.Print();

(Valid / Invalid) Amy.age = 23;

d)  How would you create an array of 30 Employee objects called Staff?

1. You first must create a new class called EmployeeArray

b. Employee Staff[30];

1. You cannot create an array of objects

d. You must write a loop that executes 30 times to create the Employee objects

1. none of the above.

e)  Consider CODE FRAGMENT 1. What code needs to go there?

1. Sum += Employee.GetSalary();

b. Sum = Sum + Staff[i].GetSalary();

1. Sum += Workers[i].salary;

d. Sum = Sum + Workers[i].GetSalary();

1. none of the above.

f) In CODE FRAGMENT 2, how would you call ComputeAverageSalary() given an initialized array of 30 Employee objects called Staff.

1. float Average = ComputeAverageSalary(Staff, 30);

b. float Average = ComputeAverageSalary(Staff);

1. float Average = Staff.ComputeAverageSalary(30);

d. float Average = Staff.ComputeAverageSalary(NumWorkers);

1. none of the above.

 Question No. 6 Marks : 20 The following question applies to a Binary Search Tree (BST). [20]

(a)  Show the result of inserting (in order) 10,8,6,2,4,1,7 into an initially empty BST. Draw the diagram of resultant BST

(b)  Give an order in which the elements should arrive to have the worst case (largest) height, as well as the best case (minimum) height.

(c)  Give a linear time algorithm to determine if a BST is a valid BST.

(d)  Give a linear time algorithm to print all the nodes in a arbitrary tree in level order. That is, all nodes at depth 0 are printed first (the root) followed by nodes of depth 1, then depth 2 and so on.

Question No. 7                                                                                                             Marks : 15

Build an efficient Huffman tree using the algorithm we discussed in class for the following:

the cat in the hat

Show all steps in building the tree. The counts for each character have already been calculated for you. Also note the blank is represented by an underscore ( – ).

Page 3 of 3