Search This Blog

IT2201 DATA STRUCTURES AND ALGORITHMS ANNA UNIVERSITY QUESTION PAPER

Saturday, September 24, 2011 ·

ANNA UNIVERSITY QUESTION PAPER FOR IT2201 DATA STRUCTURES AND ALGORITHMS

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2010
Third Semester
Information Technology
IT 2201 — DATA STRUCTURES AND ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 Marks
PART A — (10 × 2 = 20 Marks)
2. Clearly distinguish between linked lists and arrays. Mention their relative
3. What is meant by depth and height of a tree?
4. Discuss the application of trees.
5. What are the important factors to be considered in designing the hash
function?
6. What is a disjoint set? Define the ADT for a disjoint set.
7. What is Euler circuit?
8. What are the two ways of representing a graph? Give examples.
9. Define NP-complete problems.
10. What is meant by backtracking?
PART B — (5 × 16 = 80 Marks)
11. (a) (i) Derive an ADT to perform insertion and deletion in a singly linked
list. (8)
(ii) Explain cursor implementation of linked lists. Write the
essential operations. (8)
Or
(b) (i) Write an ADT to implement stack of size N using an array. The
elements in the stack are to be integers. The operations to be
supported are PUSH, POP and DISPLAY. Take into account the
exceptions of stack overflow and stack underflow. (8)
(ii) A circular queue has a size of 5 and has 3 elements 10, 20 and 40
where F = 2 and R = 4. After inserting 50 and 60, what is the value
of F and R. Trying to insert 30 at this stage what happens? Delete
2 elements from the queue and insert 70, 80 & 90. Show the
sequence of steps with necessary diagrams with the value of F & R.
(8)
12. (a) (i) Write an ADT to construct an AVL tree. (8)
(ii) Suppose the following sequences list nodes of a binary tree T in
preorder and inorder, respectively :
Preorder : A, B, D, C, E, G, F, H, J
Inorder : D, B, A, E, G, C, H, F, J
Draw the diagram of the tree. (8)
Or
(b) (i) Write an ADT for performing insert and delete operations in a
Binary Search Tree. (8)
(ii) Describe in detail the binary heaps. Construct a min heap tree for
the following :
5, 2, 6,7, 1, 3, 8, 9, 4 (8)
13. (a) (i) Formulate an ADT to implement separate chaining hashing
scheme. (8)
(ii) Show the result of inserting the keys 2, 3, 5, 7, 11, 13, 15, 6, 4 into
an initially empty extendible hashing data structure with M = 3. (8)
Or
(b) (i) Formulate an ADT to perform for the Union and find operations of
disjoint sets. (8)
(ii) Describe about Union-by-rank and Find with path compression
with code. (8)
14. (a) (i) Write routines to find shortest path using Dijkstra’s algorithm. (8)
(ii) Find all articulation points in the below graph. Show the depth first
spanning tree and the values of DFN and Low for each vertex. (8)
Or
(b) (i) Write the pseudo code to find a minimum spanning tree using
Kruskal’s algorithm. (8)
(ii) Find the topological ordering of the below graph. (8)
15. (a) (i) Discuss the running time of Divide-and-Conquer merge sort
algorithm. (8)
(ii) Explain the concept of greedy algorithm with Huffman codes
example. (8)
Or
(b) Explain the Dynamic Programming with an example. (16)