M.Sc. (Semester (CBCS) Examination Oct/Nov-2017
Computer Science
DATA STRUCTURES
Day Date: Saturday, 18-11-2017 Max. Marks: 70
Time: 10.30 AM to 01.00 PM
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 correct alternatives. 10
Omega notation is used to denote
Lower bounds Upper Bounds
Upper and Lower Bounds None of the above
refer to the kind if data the variable may hold in
programming language.
Abstract Data Type Data Structure
Data Object Data Type
The step count is the maximum number of steps that
can be executed for the given parameter.
Best Case Worst Case
Average case None of the above
a tree means visiting all its nodes to get the complete tree
information.
Searching Traversing
Sorting None of the above
Sorting is done on data which is stored in called as
External Sorting.
Main Memory Auxiliary Memory
Register None of the above
When each array element is another array, it is called a
1D array 2D array
3D array Multidimensional array
is a finite ordered set of homogenous elements.
Tree Graph
List Array
A step by step procedure to solve a problem is called as
Data structure
Problem Solver
Algorithm
Procedural language
If non-zero elements are less in count, then such matrix is called
Identify Matrix Row Matrix
Triangular Matrix Sparse Matrix
Page 2 of 2
SLR-MG-288
10) In we traverse the tree level wise from left to right
starting from the root.
Depth First Traversal Breadth First Traversal
Left to right Traversal L level wise Traversal
State True or False. 04
In the prefix form, the operator precedes the two operand.
The stack operators in Last in first out.
An array is static data structure.
The Tree is linear data structure.
Q.2 Write short notes of the following. 08
Linear Data structure.
Complexity of an algorithm.
Answer the following:- 06
Discuss the advantages and disadvantages of sequential search.
Define the term Backtracking?
Q.3 Answer the following.
Define term Singly inked List? State and explain in detail the various
operations on Singly Linked list with suitable example?
07
Define Array? Discuss the different ways of representing two-dimensional
Arrays in memory with suitable examples?
07
Q.4 Answer the following.
Define the term Stack? Explain in detail insertion and deletion operation in
stack with suitable example?
07
What do you mean by Binary Tree? Construct a Binary tree from given
series and show the results of Pre-order, /in-order and Post-order
traversing Binary tree.
Series 13, 16, 10, 10, 12, 6
07
Q.5 Answer the following.
Define the term Sorting? Perform insertion Sort and Show the result in
passes on following series.
Series 19, 20, 10, 13, 39
07
Define Algorithm. Discuss the characteristics of an algorithm. 07
Q.6 Answer the following.
Discuss Breadth and Depth First search as a classical tree traversing
algorithm with suitable example?
07
Write down the counting sort algorithm? Sort the series 2 9 2 1 8 using
counting sort algorithm.
07
Q.7 Answer the following.
State the algorithm for conversion of Infix into Prefix string? Apply the
same on given infix expression show its conversion into postfix string?
Infix Expression c
07
State the algorithm of Binary Search and Linear Search and also show
the results of the both of the search on given series to find the number 61
in it.
Series 35, 98, 13, 89, 55, 13, 61, 10, 19, 61