2007 Anna University B.E Computer Science CS 1151-DATA STRUCTURES Question paper
Third Semester
Computer Science and Engineering
CS 1151-DATA STRUCTURES
Answer all the questions:
------------------------------------------------------------------------------------------------------------
PART A-(10 X 2=20 marks)
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.
------------------------------------------------------------------------------------------------------------
(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.
(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.
(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.
(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.
(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.
No comments:
Post a Comment