BSc.-Data Structures-Mumbai-November 2018 - Grad Plus

# BSc.-Data Structures-Mumbai-November 2018

## 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) Multiple Choice Questions

1) Which of the following is not the type of queue?
A. Ordinary queue
B. Single-ended queue
C. Circular queue
D. Priority queue

2) What is the best case for linear search?
A. a) O(nlogn)
B. b) O(logn)
C. c) O(n)
D. d) O(1)

3) What data structure can be used to check if syntax has balanced parenthesis?
A. queue
B. tree
C. list
D. Stack

4) After each iteration in bubble sort
A. At least one element is at its sorted position.
B. One less comparison is made in the next iteration.
C. Both A & B are true.
D. Neither A or B are true.

5) Which of the following algorithm cannot be designed without recursion −
A. Tower of Hanoi
B. Fibonacci Series
C. Tree Traversal
D. None of the above

B) Fill in the blanks

( data in memory, leaf, NULL, Space complexity, self-referential)

1) A tree node with no children is called a _______ node.

2) A data structure that points to an object of the same type, as itself is
known as a __________ data structure.

3) After creating a linked list’s head pointer, one should make sure it
points to _______ before using it in any operations.

4) _______________refers to the amount of storage the algorithm
consumes.

5) A data structure is a logical method of representing ________

1) Define array.

2) Define Iterator.

4) Define binary tree.

5) Define List.

Q. 2) Attempt the following (Any THREE)(Each of 5Marks) (15M)

a) How to implement Multi Arrays ADT in data structure.

b) What is a python set? Demonstrate union, intersection and addition operations
on set with example.

c) Define Algorithm. List and explain different cases of Algorithm analysis.

d) Write a short note on Big O notation.

e) How to use List for maintaining sorted list.

f) Sort the given set of numbers using bubble sorting:
12, 5, 2, 15, 10, 3, 5

Q. 3) Attempt the following (Any THREE) (Each of 5Marks) (15M)

a) Define Linked list. Write a short note on Linked list iterators.

b) Write a python code to implement stack operations using python list.

c) Evaluate following postfix expression:
1) 5 6 3-+10 5-12 2-8+/*
2) 3 23 + 3 21 – * 4 7 + /

d) Convert following infix expression to postfix:
i) A+(B*C-(D/E-F)*G)*H          ii) A * (B + C * D) + E/78

e) How priority queue is implemented by using heap and tree.

f) Write a short note on a single link list.

Q. 4) Attempt the following (Any THREE) (Each of 5Marks) (15M)

a) Define recursive function? List and explain its different properties.

b) Explain Hashing linear probing.

c) List and explain properties of Binary tree.

d) Sort the given set of numbers using quick sorting technique:
1, 14, 5, 8, 9, 65, 2, 21

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

f) For a given binary tree perform inorder, preorder, and postorder traversal:

Q. 5) Attempt the following (Any THREE) (Each of 5Marks) (15M)

a) Represent the following expressions using tree
i) (A+B*C)-D/5 ii) A+(B*C-D)/(F*E)+3

b) Differentiate between linear and binary search with example.

c) Write an algorithm to convert infix into postfix.

d) Write a python code to find execution time required to check whether a number is
Armstrong number or not.

e) Write short note on Doubly link list.

Scroll to Top