M.Sc. (Semester (CBCS) Examination Nov/Dec-2018
Computer Science
DATA STRUCTURES
Time 2½ Hours Max. Marks: 70
Instructions: All questions are compulsory.
Figures to the right indicate full marks.
Q.1 Multiple choice questions. (Each carry one marks) 14
Which of these best describes an array?
A data structure that shows a hierarchical behavior
Container of objects of similar types
Container of objects of mixed types
All of the mentioned
In a stack, if a user tries to remove an element from empty stack it is called
Underflow Empty collection
Overflow Garbage collection
A normal queue, if implemented using an array of size MAX_SIZE, gets full
when
Rear MAX_SIZE 1 Front (rear+1)mod MAZ_SIZE
Front rear 1 Rear front
In linked list each node contain minimum of two fields. One field is data field to
store the data second field is?
Pointer to character Pointer to integer
Pointer to node Node
Consider a small circular linked list. How to detect the presence of cycles in
this list effectively?
Keep one node as head and traverse another temp node till the end to
check if its next points to head
Have fast and slow pointers with the fast pointer advancing two nodes at a
time and slow pointer advancing by one node at a time
Cannot determine, you have to pre-define if the list contains cycles
None of the mentioned
What must be the ideal size of array if the height of tree is
2I 1 I 1
I 2I
The null left pointer pointing to predecessor and full right pointer pointing to
successor. How many types of threaded tree are possible with this
conversation?
inorder, postorder, preorder traversals inorder
postorder preorder
What is the worst case complexity of selection sort?
O(nlogn) O(logn)

What is the worst case complexity of bubble sort?
O(nlogn) O(logn)

Page 2 of 2
SLR-VG-209
10) What is the best case complexity of QuickSort?
O(nlogn) O(logn) 8

11) How can jump search be improved?
Start searching from the end
Begin from the kth item, where k is the step size
Cannot be improved
Step size should be other than sqrt(n)
12) A connected planer graph having 6 vertices, 7 edges contains regions.
15 3
1 11
13) The Depth First Search traversal of a graph will result into?
Linked List Tree
Graph with back edges None of the mentioned
14) Which of the following are the uses of matrices?
In solving linear equations Image processing
Graph theory All of the mentioned
Q.2 Answer the following. (Any four) 08
Define linked list.
Differentiate the term arrays and linked list
What is postfix notations?
What is Abstract Data Type?
Define an Dequeue.
White notes on. (Any two) 06
Write Applications of Stack.
Explain Non-primitive data types.
Explain Circular Queues.
Q.3 Answer the following. (Any two) 08
Explain types of binary tree.
Explain traversing of binary tree.
Explain linked representation of graph.
Answer the following. (Any one) 06
Translate infix into postfix and prefix notation

Explain tree traversal algorithm.
Q.4 Answer the following. (Any two) 10
Explain linked representation of queue in memory.
Explain dequeue.
Write operations on queues.
Answer the following. (Any one) 04
What is the maximum number of edges in a bipartite planer graph with N
vertices?
Explain sparse matrices with suitable example.
d
Q.5 Answer the following. (Any two) 14
Explain single and multidimensional array with suitable example.
Explain Dynamic programming with example.
What is searching algorithm? Explain their complexity.