Anna University, Chennai
Third Semester
B.E Electrical and Electronics Engineering
EE 2204 — DATA STRUCTURES AND ALGORITHMS
April/May 2010
(R-2008)
Semester : III
Department : EEE
Subject Code: EE2204
Subject Name: EE2204 — DATA STRUCTURES AND ALGORITHMS
Year: April/May 2010
Type: PDF (Type Version)
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 x 2 = 20 Marks)
1. List out the areas in which data structures are applied extensively.
2. Convert the expression ((A+B)*C(DE)^(F +G)) to equivalent Prefix and Postfix 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. (12)
(ii) Explain with a pseudo code how a linear queue could be converted into a circular queue. (4)
Or
(b) (i) What is a stack ADT? Write in detail about any three applications of stack. (11)
(ii) With a pseudo code explain how a node can inserted at a user specified position of a doubly linked list. (5)
12. (a) (i) Discuss the various representations of a binary tree in memory with suitable example. (8)
(ii) What are the basic operations that can be performed on a binary tree? Explain each of them in detail with suitable example. (8)
Or
(b) (i) Give an algorithm to convert a general tree to binary tree. (8)
(ii) With an example, explain the algorithms of inorder and postorder traversals on a binary search tree. (8)
13. (a) What is an AVL tree? Explain the rotations of an AVL tree. (16)
Or
(b) (i) Explain the binary heap in detail. (8)
(ii)What is hashing?Explain any two methods to overcome collision problem of hashing. (8)
14. (a) (i) Explain Dijkstra's algorithm and solve the single source shortest path problem with an example. (12)
(ii) Illustrate with an example, the linked list representation of graph. (4)
Or
(b) (i) Write the procedures to perform the BFS and DFS search of a graph. (8)
(ii) Explain Prim's algorithm to construct a minimum spanning tree from an undirected graph. (8)
15. (a) (i) With an example, explain how will you measure the efficiency of an algorithm. (8)
(ii) Analyze the linear search algorithm with an example. (8)
Or
(b) Explain how the travelling salesman problem can be solved using greedy algorithm. (16)
Third Semester
B.E Electrical and Electronics Engineering
EE 2204 — DATA STRUCTURES AND ALGORITHMS
April/May 2010
(R-2008)
Semester : III
Department : EEE
Subject Code: EE2204
Subject Name: EE2204 — DATA STRUCTURES AND ALGORITHMS
Year: April/May 2010
Type: PDF (Type Version)
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 x 2 = 20 Marks)
1. List out the areas in which data structures are applied extensively.
2. Convert the expression ((A+B)*C(DE)^(F +G)) to equivalent Prefix and Postfix 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. (12)
(ii) Explain with a pseudo code how a linear queue could be converted into a circular queue. (4)
Or
(b) (i) What is a stack ADT? Write in detail about any three applications of stack. (11)
(ii) With a pseudo code explain how a node can inserted at a user specified position of a doubly linked list. (5)
12. (a) (i) Discuss the various representations of a binary tree in memory with suitable example. (8)
(ii) What are the basic operations that can be performed on a binary tree? Explain each of them in detail with suitable example. (8)
Or
(b) (i) Give an algorithm to convert a general tree to binary tree. (8)
(ii) With an example, explain the algorithms of inorder and postorder traversals on a binary search tree. (8)
13. (a) What is an AVL tree? Explain the rotations of an AVL tree. (16)
Or
(b) (i) Explain the binary heap in detail. (8)
(ii)What is hashing?Explain any two methods to overcome collision problem of hashing. (8)
14. (a) (i) Explain Dijkstra's algorithm and solve the single source shortest path problem with an example. (12)
(ii) Illustrate with an example, the linked list representation of graph. (4)
Or
(b) (i) Write the procedures to perform the BFS and DFS search of a graph. (8)
(ii) Explain Prim's algorithm to construct a minimum spanning tree from an undirected graph. (8)
15. (a) (i) With an example, explain how will you measure the efficiency of an algorithm. (8)
(ii) Analyze the linear search algorithm with an example. (8)
Or
(b) Explain how the travelling salesman problem can be solved using greedy algorithm. (16)
0 comments:
Pen down your valuable important comments below