Data Structures & Algorithms - May 2014

Electronics & Telecom Engineering (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.

Answer any one question from Q1 and Q2

1 (a) Sort the following numbers using Bubble Sort. Show all steps and discuss the time complexity. 20 5 18 7 21 6(6 marks) 1 (b) Explain the term Data Structure and its operations.(6 marks) 2 (a) What is a String? Explain the usage of string functions strcmp and strlen.(6 marks) 2 (b) Explain in detail: Index Sequential Search and Local and Global Variables.(6 marks)

Answer any one question from Q3 and Q4

3 (a) Write an algorithm with appropriate illustrations to perform the following operations on Singly Linked list (SLL). Delete a node (Start, end, intermediate).(6 marks) 3 (b) What is the disadvantage of Linear Queue? Suggest suitable method to overcome.(6 marks)

Answer any one question from Q4 and Q5

4 (a) Complete following missing expression in the table.

Answer any one question from Q5 and Q6

5 (a) Using the following data, draw a Binary Search Tree. Show all steps. 10 60 40 28 14 50 5(4 marks) 5 (b) What is a AVL Tree ? Explain with a suitable example RR and LL rotation.(4 marks) 5 (c) Define the following terms with respect to Trees:
i) Root
ii) Subtree
iii) Level of node
iv) Depth of Tree
v) Sibling(5 marks) 6 (a) Define Binary Tree. What are its types? Explain with suitable figures.(3 marks) 6 (b) Write a C function to search element in binary search tree.(4 marks) 6 (c) Write inorder, preorder and postorder traversals for the following tree. (6 marks)

Answer any one question from Q7 and Q8

7 (a) Write an algorithm for BFS Traversal of Graph.(4 marks) 7 (b) Write an algorithm to find in-degree and out-degree of a vertex with a suitable example.(4 marks) 7 (c) Write Kruskal's algorithm for the given graph hence find minimum spanning tree. (5 marks) 8 (a) What is a minimum spanning tree? Explain with suitable example Prism algorithm.(4 marks) 8 (b) Represent the following graph using adjacency matrix and adjacency list. (5 marks) 8 (c) Explain the term topological sorting a suitable example.(4 marks)