Birla Institute of Technology (BIT Mesra) 2006 MS Software Engineering Data Structure & Algorith(closed book) - Question Paper

Birla Institute of Technology and Science, Pilani
Distance Learning Programmes Division
MS Software Engineering in Collaboration with Wipro Technologies
Second Semester 2005 – 2006
Mid semester
Regular
Course No. : SEWPZC415
Course Name : Data Structure & Algorithms
Nature of examination : Closed Book Exam
weightage : 40 %
Duration : 2Hours

Date : February 12, 2006 (AN)

Note: Attempt all ques.. begin every ans from a fresh page
All diagrams must be prepared with pen only. Avoid blank space and block pages

Q1a) discuss “Big-Oh” Notation and Bring out application(s) of “Big-Oh” Notation
4 (2+2)
Q1b) Show that 2n3 + 4n2 log n is O(n3)
Indicate steps of reduction clearly 4

Q2a) discuss the principle of operation of stack and provide applications of stack
4(2+2)
Q2b) Write an algorithm to display contents of a provided queue in the reverse order,
using a stack data structure. 4

Q3a) discuss the subsequent terms with respect to Tree data structure 4
I) path
II) depth
III) height
IV) complete binary tree

Q3b) Construct Binary Tree for the expression ((3+1)*3 )/((9-5)+2))-((3*(7-4))+6)) and
write pre-order and post-order traversal for the Tree. (Hint do not consider
parenthesis as nodes) 4

Q4a) discuss Separate Chaining method of handling collision in hashing with an
example 4
Q4b) What is Heap Data Structure provide an example and comment on its performance 4 (1+2+1)
Q5a) Write an algorithm for Bucket sort and also calculate its running time 4(3+1)

Q5b) Create a binary search tree for a provided elements showing details of every element insertion 4
100, 150, 110, 200, 50, 40
(Order of insertion should be from left to right that is element 100 first, 150
second etc)
**********************

Earning:   Approval pending.