Code: CT11                                                           Subject: DATA STRUCTURE THROUGH C

Flowchart: Alternate Process: MARCH 2010Time: 3 Hours                                                                                                     Max. Marks: 100



·      Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.  Marks are indicated against each question.

·      Parts of a question should be answered at the same place.



Q.1                                                                                                                                  (7 × 4 = 28)

             a.  What is the condition that a circular queue is full if the queue is implemented using arrays?


             b.  Explain boundary tag method.  


             c.  Discuss algorithm for deletion of a node having two children from binary search tree.


             d.  An array is defined as A[2:8, -4:1, 6:10] requires 4 words per memory cell. Find the location of the [5, -1, 8] if the array is implemented in row major order. The base address is given as 200.


             e.  Define B tree, B+ Tree.  Among the two which one is better and why?


             f.   What do you mean by complete threaded binary tree? How null pointers are replaced in it?


             g. Explain heap sorting algorithm.


Q.2       a.  Define binary tree. Prove that maximum number of nodes in a binary tree of height h can be 2h - 1   


             b.  What is spanning tree?  What is a minimum spanning tree? Work out the Kruskal’s algorithm to find the minimum spanning tree of the following graph:                                                          (8+10)



  Q.3     a.  Write an algorithm for quick sort. Compare its complexities for worst case, average case and best case. Sort the following using quick sort

                            5, 4, 2, 8, 7, 9, 1, 3


             b.  Discuss different ways of collision resolution with open addressing.                          (10+8)


  Q.4     a.  What is priority queue? How priority queue can be represented in memory?                      


             b.  Convert the following infix expression into postfix using stack:                                            

                  A + ( B * C - ( D / E ↑ F) * G) * H


             c.  Write an algorithm to evaluate a postfix expression using stack. Explain the steps of the algorithm.    (6+4+8)


  Q.5     a.  What is AVL tree? Why height balancing is required? For the given sequence, create AVL tree (show each step with all rotations)

                                     H, I, J, B, A, E, C, F, D                                                                                


             b.  Explain single source shortest path algorithm. Find the shortest path for the following graph taking ‘v0’ as starting node.                                                                                                                        (9+9)




  Q.6     a.  What do you mean by buddy system memory allocator? What are its drawbacks?             


             b.  Explain first fit and best fit approaches of memory management. Write an algorithm for best fit approach.


             c.  What is scheduling problem?


             d.  Write a program to reverse a singly linked list without using any more memory. (5+5+4+4 = 18)


  Q.7     a.  What do you mean by Huffman trees?  Write the algorithm for the same. Draw Huffman tree for the set of weights {1, 2, 3, 3, 4}                                                                                                      


             b.  Explain in detail depth first traversal algorithm of a graph.                                         (10+8)