Andhra University BE/B.Tech Data Structures Previous Paper 2007
First question is compulsory.
Answer any FOUR from the remaining questions.
Answer ALL parts of any question at one place.
1.(a) Enumerate the elements of 3-D array A in row-major order.
(b) What is meant by ‘Stack-overflow’?
(c) Why are header nodes included in linked lists?
(d) What is the time complexity of quicksort algorithm in (i) average case and in (ii) worst case?
(e) Define an almost complete binary tree.
(f) When does the interpolation search perform better than the binary search algorithm?
(g) Write the significance of transitive closure in the context of graphs.
2. (a) define an abstract data type and discuss its role in application program development withspecific reference to an application of ADT stack. (10)
(b) Explain why stack is essential to simulate recursion with iteration using a simple example.(4)
3. Write a C program to implement a circular queue using arrays and discuss its advantages over Linear queue. (14)
4. (a) what is a doubly linked list? Explain its advantages and disadvantages when compared to a singlylinked lists. (6)
(b) A sorted list of integers is represented as a singly linked list with header node. Write C function to (i) insert a integer x into it
(ii) Delete an integer y from the list. (2*4=8)
5. (a) Represent the given infix expression using a binary tree and find the postfix and prefix equivalents of the given expression by traversing the tree :
(b)Write the node structure of a right-in-threaded binary tree and explain how does it support in order traversal of binary tree. (6)
6. (a) discuss various approaches to searching for a record in a sorted list of records and compare them.
(b) Write a C function for binary search and explain why its applicability is limited to arrays-based sorted lists. (7)
7. Write an algorithm for heap sort and apply it to sort the given list of integers:
8. (a) What is a spanning tree? (2)
(b) Find the depth-first spanning tree starting with vertex ‘B’ for the graph below.(3)
(c) Find the minimal spanning tree using Kruskal’s algorithm. (5)
(d) Find the cost of the minimal spanning tree. (2)
(e) Write an application for minimal spanning tree. (2)http://www.stepinau.com/2013/09/26/andhra-university-beb-tech-data-structures-previous-paper-2007/IT 2.1 Previous PapersCSE,CSE Previous Papers,Data Structures Previous Papers