M.Sc Computer Science Sample Paper for 2nd year Data Structure and AlgorithmItsMyAcademy.com

# M.Sc Computer Science Sample Paper for 2nd year Data Structure and Algorithm

MASTER OF COMPUTER SCIENCE, SEMESTER- II, YEAR-1

DATA STRUCTURE AND ALGORITHM

Time: 3 Hours                                                                                                            Total Marks: 60

Note:

1. 1.       Attempt any FIVE questions.
2. 2.       Each question carries equal marks

Q 1     a.  Write an algorithm to transform an infix expression into a prefix expression. What is

the time complexity of the algorithm?

b. The order of nodes of a Binary Tree in Preorder and Inorder traversal are as follows:

Preorder:      A  B  C  D  E  F  G  H  I  J  K  L  M  N

Inorder:        A  D  J  M  H  K  F  C  I  N  L  G  E  B

Draw the corresponding Binary Tree.

Q 2      Define Binary Tree and how binary tree is represented in Memory? Give POST-ORDER traversal algorithm of a Binary tree.

### Q 3      a.   What is the difference between stack and queue?

b. Assuming a queue representation through circular array, write a algorithm for addition and deletion of an element into queue.

Q 4      How Linked list is represented into memory? Give algorithm for the following:

(a)         Inserting an item after given node.

(b)         Insertion of an item in a sorted linked list.

Q 5      Define Arrays and how Linear Arrays is represented into memory. Explain various operations on array with help of algorithms?

Q 6      (a) Why Binary Tree is called the simplest form of tree?

(b) Explain Kruskal’s algorithm.

Q 7      What is Big O notation? Explain its significance in quantitative analysis of data structure?

Q 8      Write short notes on the following:

(b)         Sparse Matrices

Q 9      Write short notes on the following:

(a)         Insertion sort

(b)         Application of Binary trees

Note: Above M.Sc Computer Science Sample Paper for 2nd year Data Structure and Algorithm has been prepared after reviewing few universities sample papers. We are not sure whether same or similar question papers pattern does your university has or not. We are just trying to help you by providing the possibilities. We always suggest you to go thoroughly with textbooks, teacher’s notes and the syllabus for better preparation of your coming examination.

All the Best!!