Distinguish between the following:

Linear and Non-linear data structures

Infix and Postfix expressions

Polynomial and Exponential order of complexity

Breadth first search and Depth first search

Describe the data structure to represent:

Sparse Matrix

Priority Queue

Threaded Link

An algebraic expression of the form

anx^n ... a1x a0

Give formal definitions for complexity measures ohm and Big oh. Illustrate them, taking bubble sort algorithm as an example.

Calculate the time complexity function for the following code

Func (int

If(n
return;
else
Func Func


What advantage do we get if we make a queue circular Suggest two strategies for finding a circular queue to he empty or full with their advantages and disadvantages.

Represent the following graph by an adjacency list. For what purpose is the adjacency list better than the adjacency matrix representation

<img src='./qimages/13484-3b.jpg'>

Find the shortest paths from the vertex 1 to all the remaining vertices in the following weighted digraph. Give all the steps.

<img src='./qimages/13484-4a.jpg'>

A particular binary search tree has the following known about it

Pre-order traversal yields 30, 10, 20.

Post-order traversal yields 20, 10, 30, 88.

Draw this tree.

Prove that the quick sort takes O(N log2 time to sort N elements on the average.

Draw the heap structure that results from insertion of the following elements in the given order into an initially empty heap:

40 80 35 90 45 50 70

Also show the result after deletion of the root of this heap.

What are the properties of a hashing function Write the difference between collision and overflow. Why do they arise? Explain the consequences, if any.

Discuss various approaches to resolve overflows, giving examples.

Why do you require tree balancing Compare the complexity of searching an unbalanced binary search tree with a balanced one. What is the complexity of balancing by AVL method?

Write the procedure to reverse a single linked list without creating an extra linked list.

8. Write short notes on any four of the following:

Garbage Collection

Symbol Table

AVL Trees and its applications

Abstract Data Types

B-Tree