BSc.-Data Structures-Mumbai-November 2017

MUMBAI UNIVERSITY

Subject:

Semester: 2

[Total Marks: 75]
[Total Time: 2¼]
Please check whether you have got the right question paper
NB: 1 All questions are compulsory.
2 Figures to the right indicate marks.
3 Wustrations, in-depth answers & diagrams will be appreciated.
4. Ming of sub-question is not allowed.
_________________________________________________________________________________________________________________________________________

1) Attempt all (Each of 5 marks) (15M)

A) Select appropriate choice from the following.
i) Array in  python is:
a) Data type
b) Advanced data type
c) Abstract data type
d) None of these

2) Stack is also known as
a) FIFO Structure
b) LIFO Structure
c) Bothe a & b
d) None of these

3) Singly linked list allows traversal in
a) Forward direction
b) Back ward direction
c) Bath a & b
d) None of these

iv) The method which te moves tast element from the python list is
a) Delete ( )
b) Remove ()
c) Pop ( )
d) All a,b, & c

v) The set operation which performs finding common between 2 sets is
a) Union
b) Intersection
c) Subset
d) Superset

B) Fill in the blanks.

1) Full form of  ADT is  ____________

2) The entry point queue called _________ & exit is called as ___________

3) The function which calls itself is _____________ function.

4) When last noad linked list point to first node, the list is called as ____________

5) The depth tree simply number of ____________ in tree.

C) Short answers

i) Define data structure.

ii) State the factors used for algorithm analysis.

iii) Which ADT is used in solving polynomial expressions?

iv) Define tree

v) Define Hashing.

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

a) What is ADT Discuss its advantages

b)   Write a program to read 10  numbers & then search whether  55 exist in that list:

c) Suppote set is implemented by using python list, define is subset (set B) method to decide whether  B is Subset.

d) How array differs from the python list?

e) Write a note on Algorithm analyst.

f) Explain binary search technique with an example.

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

a) Explain prepending operation on singly linked list.

b) Consider ‘stack ‘STK is empty. After performing each of the following operations, draw the status of ‘STK’ with its contents & Top position.
i) STK. push (100)
ii) STK. push (150)
iii) STK. pop ( )
iv) STK. push (200)

c) Write a program to implement queue using python list.

d) Explain the concept of doubly linked list with example.

e) Define se for singly linked list & define function to traverse list.

f) Explain why on should use linked list when list in python is available?

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

a) Explain working of recursive operation

b) Write a note hash unction

c) Explain the procedure of merger sort.

d) with respect to given tree diagram answer following.

i) List path from A to H
ii)  What is the postorder traversal of tree
iii) List all interior nodes
iv)  List all leaf nodes
v) Is it a binary tree? Why?

e) How to construct an expression tree? Give example.

f) Explain indoor traversal with a proper tree diagram.

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

a) Explain efficiency analysis for operation on list such as append & extend.

b) Write a program to read 5 name & display them in alphabetic order.

c) Convert following expression into postfix form
i) ( X * Y)/Z
ii)   A + B* (C – D)/E
iii) H/i*j-k+m

d) What is interactor? Explain its use.

e) State & explain properties of tree.