Data Structure (2130702)

BE | Semester 3 
  Summer - 2018|05/21/2018
Total Marks 70

Q1 (a) Differentiate between linear and non linear data structures.

  (b) Discuss the variations of a queue.

  (c) Write an algorithm to convert an infix expression to postfix expression.

Q2 (a) Evaluate the following postfix expression using a stack. Show the steps.

  (b) Consider the stack S of characters, where S is allocated 8 memory cells.

  (c) Write a program to implement queue and check for boundary conditions.

OR

  (c) Write a program to implement a circularly linked list.

Q3 (a) List the advantages of a doubly linked list over singly linked list.

  (b) Write an algorithm to swap two nodes, n and n+1, in a singly linked list.

  (c) Perform inorder, postorder and preorder traversals for the following binary tree.

OR

Q3 (a) What is a header node? Explain its importance.

  (b) Write an algorithm to count the number of nodes in a singly circularly linked list.

  (c) What is a binary search tree? Create a binary search tree for the following data.

Q4 (a) Explain the working of the Kruskal’s algorithm.

  (b) Write the algorithm for binary search and find its complexity.

  (c) Insert the following letters into an empty B-tree of order 5:

OR

Q4 (a) Define the following terms with respect to a graph: Node, Edge, Path

  (b) Discuss different representations of a graph.

  (c) Apply Djkstra’s algorithm for the following graph with Node S as the starting node.

Q5 (a) What is the complexity of the quick sort algorithm on sorted data? Justify your answer.

  (b) What is hashing? Explain hash collision and any one collision resolution technique.

  (c) Explain the difference between insertion sort and selection sort with an example. What is the time complexity of these algorithms? How?

OR

Q5 (a) List the qualities of a good hash function.

  (b) Explain two hash functions.

  (c) Apply merge sort algorithm for the following data and show the steps.