BSc.-Data Structures-Mumbai-April 2017

MUMBAI UNIVERSITY

Subject: Data Structures

Semester: 2

[Time: 2???????? Hours]
[Marks:75]
Please check whether you have got the right question paper.
N.B:1. All questions are compulsory.
2. Figures to the right indicate marks.
3. Illustrations, in-depth answers, and diagrams will be appreciated.
4. Mixing of sub-questions is not allowed.
____________________________________________________________________________________________________________________________

Q.1 Attempt all (each of 5 marks) (15M)

a) Select the appropriate choice from the following.

i) Stack ADT can be easily implemented by using python:
a) Tipple
b) List
c) Dictionary
d) All a, b &c

ii) The common name of function n2 is
a) Linear
b) Quadratic
c) Exponential
d) None of these

iii) The maximum swap operations are involved in
a) Insertion sort
b) Bubble sort
c) Selection sort
d) Both b & c

iv) Doubly linked list consist of:
a) 2 data items & one address reference.
b) 1 address reference & one data item.
c) 2 address references & one data item.
d) None of these.

v) The binary tree must-have.
a) Every node with 2 siblings
b) Every node with at least 1 sibling
c) Every node with at the most 2 siblings

B) Fill in the blanks.

1) In post order traversal root node is visited ________.

2) The dims ( ) method returns __________ of multidimensional array.

3) The entry/exit point of stack is called _________.

4) The __________ method returns the iterator object.

5) The size of tree is simply ________ in tree

C) Short answers.

1) Define set ADT.

2) As a time efficiency which sorting algorithm is best for python list?

3) Define algorithm.

4) Define recursive Function?

5) Draw expression tree for expression (9+5)*(12-6)

Q. 2 Attempt the following (Any Three) (15M)

a) Write a short note on the abstract data type.

b) Sort the given list of numbers using insertion sort. Show step by step procedure 14, 33,27,57,100,12.

c) Explain different operations on set in python with example.

d) Discuss the cases of algorithms.

e) Write a program to accept one name from user & display whether that name exists in the predefine name list.

f) Explain the applications of array ADT.

Q. 3 Attempt the following (Any Three) (15M)

a) What is a linked list? List & explain types of linked list.

b) Convert the following infix expression into postfix.
i) (a+b*c)-d
ii) (-a+b)-25/5*3+4
iii) (a/b*c)-56+12^2

c) How priority queue is implemented?

d) Define function to put node at the end of the linked list.

e) Explain stack data structure with its application.

f) Define pop function for stack ADT implemented using python list.

Q. 4 Attempt the following (Any Three) (15M)

a) Write a python code to find the factorial of a number using recursive function.

b) What do you mean by hashing linear probing?

c) For a given binary tree perform inorder preorder & post order traversal.

d) What is tail recursion? Give example.

e) Write in brief about hash function.

f) State & explain properties of tree.

Q. 5 Attempt the following (Any Three) (15M)

a) Write a program to get 10 numbers from user. Then search -5 exists in this number list.

b) Explain operations performed on quene ADT.

c) Write a note on runtime stack.

d) Suppose ‘Q’ is empty queue. After performing each of the following operations what will be the status of Q.
i) Q. enqueue (10)
ii) Q. enqueue (200)
iii) Q. isempty ()
iv) Q. dequeue ()
v) Q. dequeue ()

e) Explain post-order traversal with example.