BSc.-Data Structures-Mumbai-April 2018
MUMBAI UNIVERSITY
Subject: Data Structures
Semester: 2
[Total Time: 2 ¼]
[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 appreciate
4 Mixing of sub-questions is not allowed.
____________________________________________________________________________________________________________________________
Q. 1) Attempt All ( Each of 5 Marks)(15M)
a) Multiple Choice Questions
1) _________________ level is where the model becomes compatible executable code.
i) Abstract level
ii) Implementation level
iii) Application level
iv) All of the above
2) Which one of the below is not a divide and conquer approach?
i) Insertion Sort
ii) Merge Sort
c) Shell Sort
d) Heap Sort
3) Which of the following is true about the ch characteristics of abstract data types?
a) it exports a type b) exports a set of operations.
i) True, False
ii) False, True
iii) True, True
iv) False, False
4) To represent the hierarchical relationship between elements, which data structure is suitable?
i) Dequeue
ii) Priority
iii) Tree
iv) Graph
5) What is the worst-case time complexity of a linear search algorithm?
i) O (1)
ii) O (n)
iii) O (log n )iv) O (n2)
B) Fill in the blanks.
( greater than, FIFO, end, postorder, a precondition )
1) The assertion given in the beginning segment in an algorithm is called __________.
2) In _________ traversal, the root node is visited last.
3) New nodes are added at the ____________ of the list.
4) A queue, in other words, is called a __________ llist.
5) The lower limit is modified when the key is _____________ the m middle elementsin the array in a binary search method.
C) Short Answers.
1) Define data structure.
2) Define priority queue.
3) Define hash Function.
4) Define 2D array.
5) Define tree.
Q. 2) Attempt the following ( Any THREE) ( Each of 5 Marks) (15M)
1) Write short note on Map ADT.
2) What is python set? List and explain any five functions of set.
3) If x is an algorithm and n is the size of input data, then explain the factors which decide the efficiency of x.
4) Write a short note on Big O notation.
5) define ADT. Explain Bags ADT.
6) Sort the given set of numbers using insertion sorting.
10, 50, 20, 15, 10, 30, 45
Show step-by-step process.
Q. 3) Attempt the following ( Any THREE) ( Each of 5 Marks) (15M)
i) DEfine linked list. How linked list is implemented.
ii) Write a python code to implement queue operations using python list.
iii) Write an algorithm to convert postfix into infix.
iv) Convert following infix expression to postfix.
a) A+(B* C= (D/F)*G) * H-B b) A* (B + C * D ) + E
e) What is difference between a queue and priority queue. Explain with example.
f) What short note on circular liked list traversal.
Q. 4) Attempt the following ( Any THREE) ( Each of 5 Marks) (15M)
1) What is recursive function? List and e explain the properties of recursion.
2) What is rehashing? Explain with example.
3) Why a collision occurs in Hashable? Explain any one of the methods to solve it.
4) Sort the given set of numbers using merge sorting technique.
12, 1, 5, 88, 79, 75, 42, 31
5) Define search tree. Explain B-search tree with example.
6) for a given binary tree perform inorder, preorder, and postorder traversal.
Q. 5) Attempt the following ( Any THREE) ( Each of 5 Marks) (15M)
a) What is difference between time and space complexity.
b) Wha is List> Explain usage of the list.
c) What is an expression tree? Represent expression 3 + (( 5+ 9) *) using expression tree.
d) Convert abc+de-fg+h/* postfix to infix.
f) Write short notes on heaps and heapsort.