BSc.-Data Structures-Mumbai-April 2019
MUMBAI UNIVERSITY
Subject: Data Structures
Semester: 2
(Total Time: 2 ½ Hours)
[Total Marks: 75]
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 5Marks) (15M)
a) Select appropriate option from following.
1) Python array is —
a) Built-in data type b) Additional data type
c) Abstract data type d) Both a&c
2 What is the worst case for linear search?
a) O(nlogn) b) O(logn)
c) O(n) d) O(1)
3 Process of inserting an element in stack is called ____________
a) Create b) Push
c) Evaluation d) Pop
4) The type of expression in which the operator succeeds its operands is?
a) Infix Expression b) Prefix Expression
c) Postfix Expression d) None of the mentioned
5) In the linked list each node contains a minimum of two fields. One field is a data field to store the data second field is?
a) Pointer to character b) Pointer to integer
c) Pointer to node d) Node
B) Fill in the blanks
1) An —— is object providing mechanism for general traversal.
2) Queue is called as ——- type of structure.
3) Binary search works only with ——– collection.
4) In a stack, if a user tries to remove an element from empty stack it is called _________
5) In ——- linked list last node pints to first node.
C) Short Answers.
1) State any application where a stack can be used.
2) With reference to Date ADT, what will be the output of statement d=Date( ) ?
3) The type of expression in which operator succeeds its operands is?
4) What is a hash table?
5) What is a full binary tree?
Q. 2) Attempt the following (Any THREE)(Each of 5Marks) (15M)
a) What is ADT? Explain the types of operation on ADT.
b) How to implement array as an ADT?
c) Write a note on SET ADT.
d) What is binary search? Explain with example.
e) Write a program to accept city name from user & display message whether that name exists in a predefined list?
f) Arrange this list 5,10,44,20,15 in ascending order by using selection sort. Write down step by step process.
Q. 3) Attempt the following (Any THREE) (Each of 5Marks) (15M)
a) What is a linked list? Explain types of linked lists
b) Write a program to implement stack using python list with required
functionality.
c) What is doubly linked list? Define a function to append node in doubly linked
list.
d) How stack can be used to check parenthesis balancing?
e) What is postfix notation? Convert the following expressions to postfix.
1) (a+b)/c 2) a/b*c-d+e 3) a – b/(a+b) 4) a * b *c +d – e
f) Explain the concept of priority queue.
Q. 4) Attempt the following (Any THREE) (Each of 5Marks) (15M)
a) What is recursion? State its properties.
b) With example explain clustering in hashing.
c) Discuss the steps in quick sort.
d) With respect to tree structure define following terms:
Root, path, depth, width, height
e) Define a recursive function to calculate nth term of Fibonacci series. Test this
function to print 10 terms of series.
f) For a given binary tree perform in order, preorder, and postorder traversal.
Q. 5) Attempt the following (Any THREE) (Each of 5Marks) (15M)
a) Write a program to read 10 numbers and arrange them in descending order
using bubble sort.
b) What is list traversal? Explain algorithm for traversing singly linked list.
c) Write a note on recursive call tree working with runtime stack .
d) Build an expression tree for following expressions:
1) a-(b*c+d) 2) (a-c*d)+x/y
e) What is binary search tree? With example explain insertion of node in this tree.