Jawaharlal Nehru Technological University, Hyderabad MCA-I Semester Supplementary Examinations July 2010 DATA STRUCTURES Question paper

Code No: 21003


Time: 3hours Max.Marks:60

Answer any Five questions
All questions carry equal Marks

1.a) Define ADT and Sparse matrix.
b) Write a 'C' program that implement complex numbers, using structures with real and complex parts. Write routines to add, multiply and negate such numbers.

2. Write an algorithm to perform
i) append an element to the end of a Singly Linked List
ii) Return the number of elements in a Singly Linked List
iii) Delete 'n' the element from a Doubly Linked List.

3.a) What is Stack and what are its applications?
b) Write an algorithm to transform a String from prefix to postfix. Carefully state any assumptions you make regarding the input.

4. What is a priority queue? What are the primitive operations applied to a queue?
Write 'C' routines for those operations.

5. Assume the following list of keys:
16,38,54,80,22,65,55,48,64,95,5,100,58,25,36
Use pivot as the middle element of the list. Explain clearly step-by-step how to sort the list using quick sort.

6. Consider the following list
2,10,17,45,49,55,68,85,92,98,110.
Explain step-by-step how many comparisons are required to find item '98' in list using binary search.

7.a) Define and differentiate Binary Tree and Binary Search Tree.
b) Write clearly the Heap-Sort-algorithm.
8.a) What are the operations that are performed on Binary Search Tree? Write a function "Search" that searches the Binary Search Tree for a given item.
b) Write an algorithm that implements the bubble-sort.