Data Structure (2130702)

BE | Semester 3 
  Summer - 2019|06/04/2019
Total Marks 70

Q1 (a) Define Data Structure and differentiate between linear and nonlinear data structures

 Unit : Introduction to Data Structure |  Topic : Types of Data Structures

  (b) Write a pseudocode for PUSH and POP operations of stack

 Unit : Linear Data Structure |  Topic : Operations On Stacks

  (c) Write algorithm for inserting an element in circular queue and deleting a node from a singly linked list.

 Unit : Linear Data Structure |  Topic : Singly Linked List

Q2 (a) Illustrate the working of priority queue with suitable example.

 Unit : Linear Data Structure |  Topic : Priority Queue and array representation of Priority Queue

  (b) Write recursive algorithm to compute factorial of a given number. Which data structure can be used to implement this algorithm?

 Unit : Linear Data Structure |  Topic : Recursion

  (c) Sort the following numbers in ascending order by applying quick sort.

 Unit : Sorting and Searching |  Topic : Quick Sort

OR

  (c) “If no interchanges occurred, then all the elements must be sorted and no further passes are required.” Which sorting technique works on this principal? Apply the same sorting technique on the following data to sort them in ascending order.

 Unit : Sorting and Searching |  Topic : Bubble Sort

Q3 (a) Evaluate the following postfix expression in tabular form showing stack after every step. 7 6 + 4 * 4 10 + - 5 +

 Unit : Linear Data Structure |  Topic : Polish Expression, Reverse Polish Expression and their Compilation

  (b) Write the algorithm for binary search.

 Unit : Sorting and Searching |  Topic : Binary Search

  (c) Explain the working of the Prim’s algorithm with suitable example.

 Unit : Nonlinear Data Structure |  Topic : Minimal spanning Tree

OR

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

 Unit : Linear Data Structure |  Topic : Doubly Linked List

  (b) List out graph traversal techniques & explain any one using suitable example.

 Unit : Nonlinear Data Structure |  Topic : Elementary Graph operations (BFS, DFS)

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

 Unit : Nonlinear Data Structure |  Topic : Shortest path Algorithms

Q4 (a) Explain Sequential search method with suitable example.

 Unit : Sorting and Searching |  Topic : Sequential Search

  (b) Given Inorder and Preorder traversal, find Postorder traversal.
Inorder: Y B K C F A G X E D H Z
Preorder: G B Y A C K F X D E Z H

 Unit : Nonlinear Data Structure |  Topic : Binary Tree Traversal (Inorder, postorder, preorder)

  (c) Explain collision in the context of hashing? Discuss collision resolution techniques.

 Unit : Hashing and File Structures |  Topic : Collision-Resolution Techniques in hashing

OR

  (a) Explain indexing structure for index files.

 Unit : Hashing and File Structures |  Topic : Indexing structure for index files

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

 Unit : Nonlinear Data Structure |  Topic : Binary Tree Traversal (Inorder, postorder, preorder)

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

 Unit : Nonlinear Data Structure |  Topic : AVL Trees

Q5 (a) Define: i) Cyclic Graph ii) Siblings iii) Strictly Binary Tree

 Unit : Nonlinear Data Structure |  Topic : Tree-Definitions and Concepts

  (b) Explain Threaded binary trees with suitable examples.

 Unit : Nonlinear Data Structure |  Topic : Threaded Binary Tree

  (c) Write a C program to reverse a string using stack.

 Unit : Linear Data Structure |  Topic : Applications of Stacks

OR

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

 Unit : Hashing and File Structures |  Topic : Sequencial File Organization

  (b) Write an algorithm for insertion sort.

 Unit : Sorting and Searching

  (c) Discuss different representations of a graph.

 Unit : Nonlinear Data Structure |  Topic : Matrix Representation of Graphs