M.Sc. (Semester (CBCS) Examination Mar/Apr-2018
Computer 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 correct alternatives.
10
A binary search tree whose left sub-tree and right sub-tree differ in height by at most 1 unit is called
AVL tree
Red-black tree
Lemma tree
None of the above
Stack is also called as
Last in first out
First in last out
Last in last out
First in first out
is not the component of data structure.
Operations
Storage Structures
Algorithms
None of above
Inserting an item into the stack when stack is not full is called operation and deletion of item form the stack, when stack is not empty is called operation.
push, pop
pop, push
insert, delete
delete, insert
is very useful in situation when data have to stored and then retrieved in reverse order.
Stack
Queue
List
Link list
What of the following is non-liner data structure?
Stacks
List
Strings
Trees
Which data structure is used in breadth first search of a graph to hold nodes?
Stack
Queue
Tree
Array
Which of the following data structure is linear type?
Graph
Trees
Binary tree
Stack
In search start at the beginning of the list and check every element in the list.
Linear search
Binary search
Hash Search
Binary Tree search
10) Which of the following is not the internal sort?
Insertion sort
Bubble sort
Merge Sort
Heap Sort
Page 2 of 2
SLR-UG-268

State following statements are True or False.
04
Binary search is used for searching in a sorted array.
In the infix form, the operator precedes the two operands.
The queue operated in First in first out.
The degree of root node is always zero.
Q.2

Write short notes on the following.
08
Dynamic programming
Complexity of algorithm

Answer the following.
06
Enlist any five basic operations to process data in data structure. Explain any one with example.
Enlist any four derived data types and explain any one.
Q.3
Answer the following.
14

State the steps to implement push and pop operations of a stack.

Illustrate and write the procedure to insert and delete a data in a queue with an example.
Q.4
Answer the following.
14

Convert the following infix to postfix notation

Write an algorithm to delete a node from linked list.
Q.5
Answer the following.
14

List the steps for sorting the following numbers using insertion sort. 6 12, 21, 36

Write an algorithm for merge sort. State the complexity to short numbers.
Q.6
Answer the following.
14

Write an algorithm to convert infix to postfix using stack.

Construct a binary tree, given the preorder sequence. a b c e i f j d g h k l
Q.7
Answer the following.
14

Write an algorithm to implement Breadth first search.

What is binary tree? Write algorithm to construct a binary search tree.