BITS WILP Data Structures and Algorithms Design Mid-Sem Exam (Regular) 2016-H2

Birla Institute of Technology & Science, Pilani
Work-Integrated Learning Programmes Division
First Semester 2016-2017
EC-2 Regular Mid-Semester Test
Course Title : Data Structures and Algorithms Design
Course No : SS ZG 519
Total : 30 marks
Nature of Exam : Closed Book
Duration : 2 hours
Date : 24/09/2016 (AN)
No. of Pages = 1
No. of Questions = 5
Note:
1. Please follow all the Instructions to Candidates given on the cover page of the answer book.
2. All parts of a question should be answered consecutively. Each answer should start from a fresh
page.
3. Assumptions made if any, should be stated clearly at the beginning of your answer.



3. What is the average case running time for binary search algorithm on a sorted array
of n distinct integers? Justify your answer with a precise argument. (4Marks)

4. (a) Write a pseudocode for all stack operations (push, pop, size, top, isEmpty) when
stacks are implemented using arrays. (5Marks)
(b) Write a pseudocode for deleting a node from a doubly linked list. (2Marks)

5. (a) A certain Professor Amongus claims that if a binary tree which stores elements
in its internal nodes has the following property, then it is a binary search tree.
For every node v, the element stored at the left child of v is less than or equal to
the element stored at v and the element stored in the right child of v is greater
than or equal to the element stored at v.
Is the Professor making a correct claim? (3Marks)
(b) Write a pseudocode for finding a successor of an element k in a binary search
tree. (3Marks)

SS ZG519 (EC-2 Regular Mid-Sem Test) First Semester 2016-2017