M.C.A. (Semester II) (CBCS) Examination Nov/Dec-2018
Science
DATA STRUCTURES
Time: 2½ Hours Max. Marks: 70
Instructions: Question No. 1 and 2 are compulsory.
Attempt any 3 questions from Q. no. 3 to Q. no. 7
Figures to the right indicate full marks.
Q.1 Choose the correct alternatives. 10
Which of these best describes an array?
A data structure that shows a hierarchical behavior
Array contains elements only of the same type
Container of objects of mixed types
All of the above
Assuming int is of 4 bytes, what is the size of int arr[15]
15 19
11 60
Which of the following applications may use a stack?
A parentheses balancing program
Tracking of local variables at run time
Compiler Syntax Analyzer
All of the above
What is the time complexity to count the number of elements in the
linked list?

O(log None of the above
What are the advantages of priority queues?
Easy to implement
Process with different priority can be efficiently handled
Applications with differing requirements
All of the above
What is the time complexity of pre-order traversal in the iterative
fashion?

O(log O(n log
Which of the following data structure cant store the non-homogeneous
data elements?
Arrays Records
Pointers None
Which of the following sorting techniques is slowest? Z
Quick sort Heap sort
Shell sort Bubble sort
Page 2 of 2
SLR-SN-8
What is a weight balance tree?
A binary tree that stores the sizes of sub trees in nodes
A binary tree with an additional attribute of weight
A height balanced binary tree
A normal binary tree
10) Which of the following properties is associated with a queue?
First In Last Out
First In First Out
Last In First Out
None of the above
State whether true or false 04
In a queue, elements are both inserted and deleted from one end.
Traversal in a graph is visiting each node at least once.
In a Binary Tree, a node may have a degree greater than 2.
The Quick Sort Algorithm works by partitioning the array to be sorted,
then recursively sorting each partition.
Q.2 Write a short notes on the following 08
Queue
Merge sort
Answer the following 06
Discuss sparse matrices
Write an example for infix to prefix conversion.
Q.3 Answer the following 14
What is algorithm? Discuss complexity of algorithm with example.
Explain linked list representation of push and pop operations for the stack.
Q.4 Answer the following 14
Write an algorithm to insert and delete an element from one dimensional
array with suitable example.
Explain Depth First Search algorithm with suitable example.
Q.5 Answer the following. 14
Construct a Binary tree from given series and show the results of pre-order
and post-order traversing at the constructed binary tree.
Series 39, 43, 83, 66, 10, 91, 26, 55, 72, 100, 12, 60
Explain Branch and Bound technique with suitable example.
Q.6 Answer the following. 14
What is quick sort? To sort the given data using quick sort technique:
23, 15, 19, 45, 90, 10 and 50
Discuss binary search algorithm with suitable example.
Q.7 Answer the following. 14
Explain Binary tree indexing
Discuss Doubly linked list with example.