Anna University - Data Structure and Algorithm (DSA) - 2011 Nov / Dec Question Paper

B.E / B.Tech DEGREE EXAMINATION NOVEMBER / December 2011

Common to B.E.(EEE/EIE/ICE)

Third Semester

DATA STRUCTURES AND ALGORITHMS

(Regulation 2010)

Time: Three hours

Maximum: 100 marks

Answer ALL questions

PART A - (10*2=2O marks)

1. Define Abstract Data Type.
2. Mention the advantages of representing stacks using linked lists than arrays.
3 State the properties of a binary tree.
4. Draw a directed tree representation of the formula (a + b * c)+ ((d * e ÷ f) * g).
5. In an AVL tree, at what condition the balancing is to be done?
6. What is collision hashing?
7. What do you mean by depth-first traversal?
8. What is mean by topological sorting?
9 Write lown the best,average and worst case complexity of Quick and Merge sort.
IO.State the various asymptotic relations used for denoting Time complexity.

PART B    (5x16 = 80 marks)

11. (a) Explain operations of Doubly linked List in detail with routine of add, delete node from DLL.

Or

(b) Write an algorithm for covert infix expression to postfix expresion with an example of 

(A + (B * C - (D/E^F)* G)*H).

12. (a) (i) Illustrate the construction of tree of a binary tree given its in order and postorder traversal.
in-order:     H D I  J E K B A L F M C N G O
Post-order: H I D J K E B L M F N O G C A

(ii) To find inorder, preorder and postorder for a given tree (6)

Or

(b) Narrate the operation of Binary search tree on searching a node, Insertion node and deletion of a node from binary tree with example.

13. (a) Discuss about AVL Trees

Or

(b) (i) Briefly explain the hash function in detail (6)

(ii) Narrate B-Tree operations. (10)

14. (a)Explain the followiag with algorithm
(i)DFS (4
(ii)BFS (4)
(iii)Kruskal algorithm with example. (8)

Or

(b) Explain Single source path algorithm with an example. Does the algorithm work for paths of negative values? Explain.

15. (a) Explain the following with algorithm
(i) Finduig Maximum and Minimum. (8)
(ii) Binary Search. (8)

Or

(b) Explain how the traveling salesman problem can be solved using greedy algorithm.

Anna University - Data Structure and Algorithm (DSA) - Nov / Dec 2006 - Question Paper

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2006.

Third Semester

Electrical and Electronics Engineering

DATA STRUCTURES AND ALGORITHMS

(Common to Electronics and Instrumentation / Instrumentation and Control Engineering)

(Regulation 2004)

Time : Three hours

Maximum: 100 marks
Answer ALL questions.

PART A — (10 x 2 = 20 marks)

1. What is the purpose of the do-while statement? How does it differ from the
while statement.

2. What is recursion? What advantages is there in its use?

3. State the different application of stack.

4. What is the significance of priority queue?

5. What are the disadvantages of sequential representation of tree over the linked representation?

6. What is the use of threaded binary tree?

7. When is the need of external sort? Give example.

8. Define address calculation sort.

9. What are strongly connected graph? Give example.

10. State any two application of depth first traversal.

PARTB—(5 x 16=80 marks)

11. (a) (i) Name the four storage class specifications are included in C. Explain them with suitable example. (8)

(ii) Write a for ioop that will read the charter type array called text and write the characters backwards into another charter type array called back_text. Assume that the text contains 80 characters. (8)

Or

(b) (i) Write a C program that reads several different names and addresses into the computer, rearrange the names into alphabetic order, and then write out the alphabetize list. Make use of structure variable within the program. (10)

(ii) State the difference between call-by-value and call-by-reference? Give a suitable example. (6)

12. (a) Compare the following with suitable example. (2 x 8 = 16)
(j) Linked list and array
(ii) Singly linked list and Doubly linked list.

Or

(b) i) What are the advantages of circular linked list? Write down the various primitive operations performed on circular linked list. Write the algorithm for insertion of element in the circular linked list. (8)

(ii) Write a C program to perform the following operation on a queue
(1) Insert
(2) Delete and

(3) Display. (8)

13. (a) (i) Write a note on expression tree with suitable example. (6)

(ii) Write a C program to perform following operations in a binary tree.
(1) To search for particular information
(2) To compute number of nodes in a tree. (10)

Or

(b) (i) Write a C pseudo code to create, insert and delete a node recursively in Binary search tree. (10)

(ii) Draw the complete undirected graphs with five vertices. Prove that the number of edges in an n vertices complete graph is n (n -1)/2. (6)

14. (a) (i) Devise an algorithm for an insertion sort. (6)
(ii) What are different types of sorting techniques? Write an algorithm for shell sort and explain it with example. (10)

Or

(b) (i) Write notes on interpolation search with suitable example. (9)

(ii) Why do we say quick sort is an unstable sorting method? Write an algorithm to prove the same. (7)

15. (a) (i) Devise a round robin algorithm. Explain it in detail with a suitable example. (8)

(ii) State the array and the linked representation of graphs with example. (8)

Or

(b) (i) What are the different graph traversal methods? Explain them with example. (8)

(ii) Give an algorithm to find a shortest path in a graph. Explain it with a suitable example. (8)

Anna University - Data Structure and Algorithm (DSA) - May / June 2007 Question Paper

B.E./B.Tech. DEGREE EXAMINATION, MAY/JUNE 2007.

Third Semester

Electrical and Electronics Engineering

DATA STRUCTURES AND ALGORITHMS

(Common to Electronics and Instrumentation Engineering / Instrumentation and Control Engineering)

(Regulations 2004)

Time: Three hours

Maximum: 100 marks

Answer ALL questions.

PARTA—(10x2 =20 marks)

1. Write code for generating fibonacci sequence recursively.

2. How do you access the  address where the element of a matrix, whose index is given, is stored?

3. Justify queue as ADT.

4. Write simple code to traverse through DLL.

5. Construct a binary tree for the following Infix expression: A + B * C/D.

6. Perform post order traversal for the following binary tree:

7. Give examples of sorting techniques that is not based on Divide and Conquer algorithmic technique.

8. What is the best case and worst case complexity of merge sort?
9. What are spanning forests? Discuss.
10. What is an adjacency matrix used for? Discuss.

PARTB—(5x 16=80 marks)

11. (a) How do you implement union, structures and arrays in C? Explain with suitable examples. (6 + 4 + 6)

Or

(b) (i) Write algorithm for reversing the elements of an array (one dimensional). (6)

(ii) Write a C program to find the product of a matrix A and its transpose. (10)

12. (a) (i) Write algorithms for insertion and deletion of nodes in a
(1) Stack (5)
(2) Circular List (5)

(ii) What is a priority queue? State the advantages with reference to implementation. (6)

Or

(b) Define a header node in Doubly Linked List. How do you merge two Doubly Linked Lists into a sing1e one? Compare with Circular Linked List. Write suitable algorithms.

13. (a) What is threaded binary tree? How do you represent binary tree using list? Write algorithms for finding the Kth element. 

Or

(b) (i) Develop a ‘C’ program to implement a binary tree. Discuss how evaluation of expressions are handled using a binary tree structure.  (10)

(ii) What are the applications of binary tree data structure? Explain. (6)

14. (a) Explain algorithms for bubble sort and selection sort. Which one of these outperforms? Why? Discuss.

Or

(b) Describe with suitable algorithms for indexed sequential search, binary search and interpolation search schemes.

15. (a) Describe BFS and DFS methods for graphs with suitable algorithms. How efficiencies are computed?

Or

(b) Write algorithm for finding minimum spanning tree and explain applications. Illustrate the algorithm with typical data of your own.

Anna University - Data structures and algorithms - APRIL/MAY 2010 Question Paper

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010

Third Semester

Electrical and Electronics Engineering

EE2204 — DATA STRUCTURES AND ALGORITHMS

(Common to Electronics and Instrumentation Engineering and Instrumentation and

Control Engineering)

(Regulation 2008)

Time: Three hours Maximum: 100 Marks

Answer ALL Questions
PART A — (10 × 2 = 20 Marks)

1. List out the areas in which data structures are applied extensively.
2. Convert the expression ((A+B)*C-(D-E)^(F +G)) to equivalent Prefix and
Post fix notations.
3. How many different trees are possible with 10 nodes?
4. What is an almost complete binary tree?
5. In an AVL tree, at what condition the balancing is to be done?
6. What is the bucket size, when the overlapping and collision occur at same
time?
7. Define graph.
8. What is a minimum spanning tree?
9. Define NP hard and NP complete.
10. What is meant by dynamic programming?

PART B — (5 × 16 = 80 Marks)

11. (a) (i) What is a linked list? Explain with suitable program segments any
four operations of a linked list. (Marks 12)
(ii) Explain with a pseudo code how a linear queue could be converted
into a circular queue. (Marks 4)
Or
(b) (i) What is a stack ADT? Write in detail about any three applications
of stack. (Marks 11)
(ii) With a pseudo code explain how a node can inserted at a user
specified position of a doubly linked list. (Marks 5)
12. (a) (i) Discuss the various representations of a binary tree in memory with
suitable example. (Marks 8)
(ii) What are the basic operations that can be performed on a binary
tree? Explain each of them in detail with suitable example. (Marks 8)
Or
(b) (i) Give an algorithm to convert a general tree to binary tree. (Marks 8)
(ii) With an example, explain the algorithms of in order and post order
traversals on a binary search tree. (Marks 8)
13. (a) What is an AVL tree? Explain the rotations of an AVL tree. (Marks 16)
Or
(b) (i) Explain the binary heap in detail. (Marks 8)
(ii) What is hashing? Explain any two methods to overcome collision
problem of hashing. (Marks 8)
14. (a) (i) Explain Dijkstra's algorithm and solve the single source shortest
path problem with an example. (Marks 12)
(ii) Illustrate with an example, the linked list representation of graph.
(Marks 4)
Or
(b) (i) Write the procedures to perform the BFS and DFS search of a
graph. (Marks 8)
(ii) Explain Prim's algorithm to construct a minimum spanning tree
from an undirected graph. (Marks 8)
15. (a) (i) With an example, explain how will you measure the efficiency of an
algorithm. (Marks 8)
(ii) Analyze the linear search algorithm with an example. (Marks 8)
Or
(b) Explain how the travelling salesman problem can be solved using greedy
algorithm. (Marks 16) 

DATA STRUCTURES AND ALGORITHMS DECEMBER 2009 Question Paper

	ANNA UNIVERSITY COIMBATORE
B.E./B.Tech. DEGREE EXAMINATION:DECEMBER 2009
	REGULATION-2008
	THIRD SEMESTER
   (COMMON TO EEE/EIE/ICE)
080300003-DATA STRUCTURES AND ALGORITHMS
Time : 3 hours            Maximum : 100 marks

	Answer ALL questions.

	PART A — (20 * 2 = 40 marks)

1. What are the advantage of modularity?
2. What are the two basic operation on array?
3. Give any two example for linked list
4. What is circularly linked list?
5. Differentiate LIFO and FIFO and give typical examples of it.
6. What is a tree?why it is used.
7. What is the need for non-linear data structure?
8. What are the operation on the binary tree?
9. What is the majar drawback of sepsrste chaining hashing?
10.What is a balance factor for any node in AVL tree?
11.What is heap?
12.What is linear probing?
13.Define the following:
   (i)Graph (ii)cycle
14.What is Biconnectivity?
15.Give any tow typical application of graphs.
16.where is Huffman coding is used?
17.What is principle of divide and conquer algorithms?
18.What do you mean by best fit in Bin packing?
19.What is the principle of randomized algorithms?
20.List out any two examples for NP complete problems.

PART B — (5 * 12 = 60 marks)

21.Explain the operation of a linked list.Also compara linked list and Array
22.Explain the various traversals in binary tree with example.
23.What is AVL tree? Also write suitable rotation algorithm.
24.Expain the shortest path algorithm with diagram.
25.Expain the kruskal's algorithm with diagram.
26.Expain the concept of stack and briefed on its two functions.
27.What is hashing?list out the various techniques of hashing.
28.Write short noteson folloeing:(i)B-tree(ii)Dynamic programming

Data Structure and Algorithm - Unit 1 Question Paper