MODEL PAPER
FIRST SEMESTER, M. Sc INFORMATION TECHNOLOGY

Paper - III (MIT - 103): Data Structure and Algorithm

1. Question

Explain Abstract Data Types with any example.
2. Question


1. Convert Infix expression to prefix.
2. Evaluate the prefix expression.
3. Question


1. What do you mean by queue? What are the practical applications of queue?
2. Compare different implementations of queue. Write a function to delete elements in circular queue.

   OR
   Write functions for
   

   1. Finding size.
   2. Checking empty.
   3. Checking full.
   for the implementation of a queue in a circular array with index values to indicate emptiness.
4. Question

Compare array implementation with linked list implementation. Write function to insert a node in doubly linked list after a node having element N. What is the difference between "P=NULL" and "P is undefined"?
5. Question


1. Write algorithm for any of the following sorting methods: -
• Merge Sort
• Quick Sort
• Radix Sort
2. Compare above three methods of sorting for ideal, worst and average cases.
6. Question

Describe the following in brief: -
1. Hash Table.
2. Priority queue.
7. Question


1. Write a recursive algorithm to print Fibonacci numbers.
2. Write a short note on Optimal Binary Search Tree.
8. Question

What do you mean by graph? How are graphs represented in C.
Describe Travelling Salesman's problem.