Data Structure (2130702)

BE | Semester 3 
  Winter - 2016|01/02/2017
Total Marks 70

Q1
Explain the following terms in brief

  (1) Primitive data structure.

  (2) Non-primitive data structure.

  (3) Linear data structure.

  (4) Non-linear data structure.

  (5) Recursion.

  (6) Time complexity of an algorithm.

  (7) Double-ended queue.

  (8) Priority queue.

  (9) Circular linked list.

  (10) Complete binary tree.

  (11) 2-3 tree.

  (12) Minimum spanning tree.

  (13) Degree of vertex.

  (14) Hash collision.

Q2 (a) Write a pseudo-code for PUSH and POP operations of stack.

  (b) What is prefix notation? Convert the following infix expression into prefix.

  (c) Write an algorithm to perform various operations (insert, delete and display) for simple queue.

OR

Q3 (a) Convert the following infix expression into postfix.

  (b) Write algorithm(s) to perform INSERT_FIRST (to insert a node at the first position) and REVERSE_TRAVERSE (to display the data in nodes in reverse order) operations in doubly linked list.

  (c) Write a ‘C’ program to implement stack using linked list.

OR

Q3 (a)

  (b) Discuss various rehashing techniques.

  (c) Write ‘C’ functions to implement INSERT_FIRST (to insert a node at the first position), DELETE_FIRST (to delete a node from the first position), DELETE_LAST (delete a node from the last position) and TRAVERSE (to display the data in nodes) operations in circular linked list.

Q4 (a) Write an algorithm for Binary search method.

  (b)

  (c) Sort the following numbers using

OR

Q4 (a) Write a ‘C’ function for Selection sort.

  (b) Write an algorithm for Quick sort.

  (c) Explain Depth First Search and Breadth First Search in graphs with an example.

Q5 (a) Draw a binary expression tree for the following and perform preorder traversal for the same:

  (b) Construct a binary search tree for the following and perform inorder and postorder traversals:

  (c) Write ‘C’ functions for: inserting a node, postorder traversal and counting total number of nodes for binary search tree.

OR

Q5 (a) Explain AVL trees.

  (b) Construct a binary search tree from the following traversals:

  (c) Write Kruskal’s algorithm for minimum spanning tree with an example.