Data Structure (2130702)

BE | Semester 3 
  Summer - 2016|06/09/2016
Total Marks 70

Q1
Short Question

  (1) Define primitive data structure.

  (2) Explain space and time complexity.

  (3) What is the time complexity of Quicksort algorithm in the worst case?

  (4) List the applications of Stack.

  (5) Define graph.

  (6) Explain degree of a vertex in a graph.

  (7) List the applications of Graphs.

  (8) List the applications of Binary trees.

  (9) Define B-Tree.

  (10) Describe the time complexity of Binary search algorithm.

  (11) What is hash collision?

  (12) Write ‘C’ structure of Binary tree.

  (13) Write ‘C’ structure of Singly linked list.

  (14) Define priority queue.

Q2 (a) Write an algorithm for simple queue with ENQUEUE operations.

  (b) Write an algorithm to reverse a string using stack.

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

OR

  (c) Write a program to implement circular queue using array.

Q3 (a) Evaluate the following postfix expression using stack:

  (b) Explain the concept of circular queue. Compare circular queue with simple queue.

  (c) Explain insert and delete operations in AVL trees with suitable examples.

OR

Q3 (a) Explain double ended queue.

  (b) Write ‘C’ functions to implement DELETE_FIRST_NODE and TRAVERSE operations in doubly linked list.

  (c) With a suitable example, explain steps for conversion of a general tree into a binary tree.

Q4 (a) Explain Sequential search method.

  (b) Explain Threaded binary trees with suitable examples.

  (c) Write an algorithm for Selection sort method. Explain each step with an example.

OR

Q4 (a) Explain Depth First Search in graphs with an example.

  (b) Explain Binary search method.

  (c) Write an algorithm for Insertion sort method. Explain each step with an example.

Q5 (a) Explain Breadth First Search in graphs with an example.

  (b) Construct a binary tree from the traversals given below:

  (c) Explain various Hash collision resolution techniques with examples.

OR

Q5 (a) Explain Sequential file organizations and list its advantages and disadvantages.

  (b) Draw a Binary expression tree for the following and perform preorder traversal:

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