Download AKTU B-Tech 3rd Sem 2018-2019 Data Structures Rcs 305 Question Paper

Firstranker's choice

Printed Pages: 02

Paper Id: 110303

--- Content provided by​ FirstRanker.com ---

FirstRanker.com

Sub Code: RCS305

Roll No.

Time: 3 Hours

B. TECH.

--- Content provided by‌ FirstRanker.com ---

(SEM III) THEORY EXAMINATION 2018-19

DATA STRUCTURES

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

Total Marks: 70

SECTION A

--- Content provided by​ FirstRanker.com ---

1. Attempt all questions in brief. 2 x 7 = 14
   1. How the graph can be represented in memory? Explain with suitable example.
   2. Write the syntax to check whether a given circular queue is full or empty?
   3. Draw a binary Tree for the expression: A * B - (C + D) * (P/Q)
   4. Differentiate between overflow and underflow condition in a linked list.
   5. What do you understand by stable and in place sorting?

   --- Content provided by⁠ FirstRanker.com ---

   6. Number of nodes in a complete tree is 100000. Find its depth.
   7. What is Recursion? Give disadvantages of recursion.

SECTION B

1. Attempt any three of the following: 7x3=21
   1. What do you understand by time and space trade off? Define the asymptotic notations. Derive the O-notation for linear search.

   --- Content provided by‍ FirstRanker.com ---

   2. Consider the following infix expression and convert into reverse polish notation using stack. A + (B * C - (D/E^F) * H)
   3. Explain Huffman algorithm. Construct Huffman tree for MAHARASHTRA with its optimal code.
   4. What is a height balanced Tree? Why height balancing of Tree is required? Create an AVL Tree for the following elements: a, z, b, y, c, x, d, w, e, v, f
   5. Write the Floyd Warshall algorithm to compute the all pair shortest path. Apply the algorithm on following graph:
      (Graph Description - Not renderable in HTML, needs image)

   --- Content provided by‌ FirstRanker.com ---

SECTION C

1. Attempt any one part of the following: 7x1=7
   1. Write a program in c to delete a specific element in single linked list. Double linked list takes more space than single linked list for storing one extra address. Under what condition, could a double linked list more beneficial than single linked list.
   2. Suppose multidimensional arrays P and Q are declared as P (-2: 2, 2: 22) and Q (1: 8, -5: 5, -10: 5) stored in column major order
      1. Find the length of each dimension of P and Q
      2. The number of elements in P and Q

      --- Content provided by​ FirstRanker.com ---

      3. Assuming Base address (Q) = 400, W=4, Find the effective indices E1, E2, E3 and address of the element Q [3, 3, 3].
2. Attempt any one part of the following: 7x1=7
   1. Explain Tower of Hanoi problem and write a recursive algorithm to solve it.
   2. Explain how a circular queue can be implemented using arrays. Write all functions for circular queue operations.

   --- Content provided by​ FirstRanker.com ---

3. Attempt any one part of the following: 7x1=7
   1. Write the algorithm for deletion of an element in binary search tree.
   2. Construct the binary tree for the following
      In-order: Q, B, K, C, F, A, G, P, E. DH, R
      Preorder: G, B, Q, A, C, K, F, P, D, E, R, H
      

      --- Content provided by FirstRanker.com ---

      Find the Post Order of the Tree
4. Attempt any one part of the following: 7x1=7
   1. By considering vertex as source vertex, Find the shortest paths to all other vertices in the following graph using Dijkstra's algorithms. Show all the steps.
      (Graph Description - Not renderable in HTML, needs image)
   2. Explain in detail about the graph traversal techniques with suitable examples.

   --- Content provided by​ FirstRanker.com ---

5. Attempt any one part of the following: 7x1=7
   1. Write algorithm for Quick sort. Trace your algorithm on the following data to sort the list: 2, 13, 4, 21, 7, 56, 51, 85, 59, 1, 9, 10. How the choice of pivot element effects the efficiency of algorithm.
   2. Construct a B-tree of order 5 created by inserting the following elements 3, 14, 7, 1, 8, 5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, 19 Also delete elements 6, 23 and 3 from the constructed tree.

--- Content provided by‍ FirstRanker.com ---