Data Structures

Define data structure. Distinguish between linear and non linear data structures and list the various operations that can be performed on data structure.

Classify the different types of queues. Illustrate the difference between a queues and linked lists with an example

Consider an array A[1: n] Given a position, write an algorithm to insert an element in the array. If the position is empty, the element is inserted easily. If the position is already occupied the element should be inserted with the minimum number of shifts.

Give the postfix and prefix forms of the expression.
(i) A + B* (C - D) / (P - R)
(ii) - A B+ C+D

Describe about stack ADT and discuss its application for push and pop operations on an stack using a linked list.

Create an expression tree for the expression.a*(b+c)-((d+e*f)*g).

Simulate the result of inserting 3,1,4,6,2,8,9 into an initially empty AVL Tree.

Illustrate the steps in the construction of a heap of records with the following key values: 12,33,67,8,7,80,5,23.

Consider the binary search tree given below and the result of in-order, pre-order, and post-order traversals.

Discuss the common collision resolution strategies used in closed hashing system.

Explain the working of Dijkstra's algorithm with the help of an example graph.

Formulate the minimum spanning tree for the following graph (Using Prim's Algorithm).

Compare working of binary search and linear search technique with example.

Write Short notes on:
i. Polynomial Manipulation
ii. Red Black Tree
iii. Hashing

Sort the sequence 96, 31, 27,42,76,6,10,4 using shell sort and radix sort and prepare the required steps.