Pre University Exam
B.Tech(CS)-III
Semester
Data Structure
Using C(ECS-302)
1.Attempt any four parts.
(a). Define abstract data type. Write a program to sort 100
complex numbers into ascending number of their absolute values. Given absolute
value (X+iY)=(X2+Y2)1/2
(b). Write a C function to concatenate two circularly linked lists
pointed by list1 and list2 in such a way that circular list pointed by list1 is
appended to the circular list pointed by list2.
(c) .describe the asymptotic notation. Explain what you understand
by worst case complexity of an algorithm.
(d).Explain the linked list representation of a polynomial? WAP
for addition of polynomial.
(e).What are sparse
matrices? Explain hoe they are represented?
(f).Calculate the address of A[10][20] of the given matrix
A[50][50],having float values in row major and column major order.
2. Attempt any four parts.
(a).Write the algorithm to evaluate a postfix expression using a
stack. And evaluate the following: 5,6,2,+,*,12,4,1,-,-,*
(b).Write down the algorithm for the insertion and deletion
operation performed on the DeQueue.
(c). What is the advantage of circular queue representation over
simple queue representation, when arrays are used?
(d). Describe priority queues and explain the insertion and deletion
operation in them through program.
(e). Explain tower of Hanoi problem and give the solution to the
problem where the no. of disks is 4.
(f). Write the algorithm to convert the infix expression to
postfix expression.
3. Attempt any two parts.
(a). What is a binary tree? How is it represented in the memory?
Write an algorithm to delete and insert a nodes from threaded binary tree.
(b). Show that the maximum no. of nodes in a binary tree of height
h is 2(h-1)+1.
(c). Describe Huffman algorithm and its application and draw tree
for the following symbols frequency of occurrence in a message is stated along
with the symbol below: A: 15, B: 6, C: 7,D: 12, E: 25,F: 4,H: 1,I: 15
(d).WAP to create and insert elements in a binary search tree.
4. Attempt any two parts.
(a). Discuss sdjacency list representation of graph. Explain DFS
of the graph.
(b). Discuss Prim’s and Kruskal’s algorithm for finding the
minimum cost spanning tree.Compare them and explain with example.
(c). Write the dijikstra algorithm for all pair shortest path.
Explain with example.
5. Attempt any two parts.
(a). Define multi-way search tree. Define AVL tree. Show the steps
to build an AVL tree for following : A Z
B Y C
X D U E
(b). How the choice of pivot element affect the running time of
quick sort. Write the algorithm for the heap sort. Sort the following using
merge sort method. 75 10 70
80 90 100 40
(c).
1. Explain the term Garbage
collection and compaction.
2. What is hashing? Discuss various collision resolution
strategies foe hash table.
No comments:
Post a Comment