Data Structure (2130702)

BE | Semester 3 
  Winter - 2014|01/01/2015
Total Marks 70

Q1 (a) What is data structure? Explain linear and non-linear data structure with example.

  (b) Discuss best case, average case and worst case time analysis with example.

  (c) Explain PUSH and POP operation of the stack with algorithm.

Q2 (a) Write an algorithm to perform insert and delete operation on single queue.

  (b) (a) Convert the following infix expression to postfix prefix form.

OR

  (b) Define the following term : Path, Cycle, Degree of vertex, Sibling, Height Balanced Tree, Strictly binary tree, in degree

Q3 (a) Explain delete operation in doubly link list.

  (b) What is the difference between queue & Dqueue . Explain insertion operation in Dqueue.

OR

Q3 (a) Write an algorithm to reverse a given single link list.

  (b) Create a binary search tree by inserting following nodes in sequence.

Q4 (a) Write an algorithm to perform traversal of Binary search tree

  (b) Explain AVL tree with the help of an example also show insertion and deletion with the help of an example.

OR

Q4 (a) Write a short note on :spanning tree , threaded binary tree

  (b) Explain the basic two techniques for Collision-resolution in Hashing with example. Also explain primary clustering.

Q5 (a) Compare and contrast Prim’s and Kruskal’s algorithm with the help of an example

  (b) Explain various multiple key access file organization in brief with advantages and disadvantages of each method.

OR

Q5 (a) What do you mean by Hashing? Explain any FOUR hashing techniques

  (b) Explain and differentiate BFS and DFS graph traversal method with suitable graph.