DATA STRUCTURES AND ALGORITHMS 2007 - B.E CSE

PART A-(10 X 2=20 marks)

1.When will you say an algorithm efficient? Give the notations for time complexity.

2.What is a ‘top-down’ design? Is ‘C’ language a top down design? Justify your answer.

3.Why is linked list used for polynomial arithmetic?

4.Write the role of stack in function call.

5.What is the minimum number of nodes in an AVL tree of height 5?

6.What is the use of sentinel value in binary heap?

7.Which is the best way of choosing the pivot element in quick sort?

8.Merge sort is better than insertion sort. Why?

9.Define a graph. How it differs from tree?

10.What is minimum spanning tree? Name any two algorithms used to find MST.

PART B-(5 X 16=80 marks)

11.(a).(i).Given two lists L1 and L2, write the routines to compute L1 n L2 using basic operations.

(ii).Write the routines for inserting and deleting elements from a queue. Check for the conditions Q-empty and Q-full.

(Or)

11.(b).(i).How would you implement a stack of queues? Write routines for creation and inserting of elements into it.

(ii).Write routines to insert heterogeneous data into the list.

12.(a).(i).Write the routines to insert and remove a node from Binary Search Tree.

(ii).A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a binary tree.

(Or)

12.(b).(i).Show the resulting of inserting 2,1,4,5,9,3,6,7 into an empty AVL tree.

(ii).Write the procedure to implement single and double rotations while inserting nodes in an AVL tree.

13.(a).Explain with suitable examples the basic heap operations and algorithms for the same.

(Or)

13.(b).How will you resolve the collisions, while inserting elements into the hash table using separate chaining and linear probing? Write the routines for inserting, searching and removing elements from the hash table using the above mentioned techniques.

14.(a).(i).Write the routine for sorting n elements in increasing order using heap sort.

(ii).Sort 3,1,4,1,5,9,2,6 in decreasing order using heap sort.

(Or)

14.(b).(i).Explain with example about the insertion sort.

(ii).What is external sorting? Discuss the algorithms with proper examples.

15.(a).(i).Discuss and write the program to perform topological sorting.

(ii).What is single source shortest path problem? Discuss Dijikstra’s single source shortest path algorithm with an example.

(Or)

15.(b).(i).Write an algorithm to find the minimum cost spanning tree of an undirected, weighted graph.

(ii).Find the MST for the following graph.