# RGPV Previous Exam Papers BE

# Data Structure and Algorithms

**Note:Attempt any 5 questions.**

**All question Carry equal marks.**

**UNIT-I**

Q.1.(a) What is recursion ? Solve Tower of Hanoi problem by using recursion.?

(b) What is the procedure for calculating the address of any two-dimensional array ? Explain with the help of an example.?

(b) What is the procedure for calculating the address of any two-dimensional array ? Explain with the help of an example.?

**OR**

Q.2.(a) Explain briefly an array, structure and array of structures. If an array B[11][8] is stored

as column wise and B[2][2] is stored at 1024 and B[3][3] at 1084,find the addresses of B[5][3] and B[1][1].?

(b) Write an algorithm to find the VALUE of an Arithmetic expression P into postfix notations

P = (3 ? 2 * 5)/(3 * 2 -3) + 5.

as column wise and B[2][2] is stored at 1024 and B[3][3] at 1084,find the addresses of B[5][3] and B[1][1].?

(b) Write an algorithm to find the VALUE of an Arithmetic expression P into postfix notations

P = (3 ? 2 * 5)/(3 * 2 -3) + 5.

**UNIT-II**

Q.3.(a) Draw the picture representation of a polynomial function P(x) using linked list :

P(x) = 2×8 -5×7 – 3s2 + 4

(b) Write an algorithm to delete the First Node N from a linked list which contain the given

ITEM of information.?

P(x) = 2×8 -5×7 – 3s2 + 4

(b) Write an algorithm to delete the First Node N from a linked list which contain the given

ITEM of information.?

**OR**

Q.4.(a) Explain the memory representation of a doubly linked list.?

(b) Explain the following :

(i) To represent linked list using array

(ii) Sparse matrices.

(b) Explain the following :

(i) To represent linked list using array

(ii) Sparse matrices.

**UNIT-IIII**

Q.5.(a) Explain the memory representation of a binary tree with suitable example.?

(b) What are basic differences between complete binary tree and almost complete binary tree ?Construct the binary tree with general tree.?

(b) What are basic differences between complete binary tree and almost complete binary tree ?Construct the binary tree with general tree.?

**OR**

Q.6.(a) Show that maximum number of nodes in a binary tree of height ‘h’ is 2h+1 -1 ,h>=0.

(b) Construct a Binary Tree T with Nine Nodes and the Inorder and Preorder Traversal of T

yields the following sequence of nodes :

IN-ORDER : E,A,C,K,F,H,D,B,G

PRE-ORDER : F,A,E,K,C,D,H,G,B

(b) Construct a Binary Tree T with Nine Nodes and the Inorder and Preorder Traversal of T

yields the following sequence of nodes :

IN-ORDER : E,A,C,K,F,H,D,B,G

PRE-ORDER : F,A,E,K,C,D,H,G,B

**UNIT-IV**

Q.7.(a) Write the procedure for shell sort. Explain with suitable example.?

(b) Write the algorithm for Merge Sort and also prove that the worst case complexity is

O(n logn).?

(b) Write the algorithm for Merge Sort and also prove that the worst case complexity is

O(n logn).?

**OR**

Q.8.(a) Explain Hasing Procedure. Give four advantages of a chained hash table over open

addressing.?

(b) What are the differences between Sequential Search and Binary Search ? Write an algorithm for binary search on linear array.?

addressing.?

(b) What are the differences between Sequential Search and Binary Search ? Write an algorithm for binary search on linear array.?

**UNIT-V**

Q.9.(a) What is minimum Cost Spanning Tree ? An undirected graph G is given below. Convert into the Minimum Cost Spanning Tree by using Kruskal’s Algorithm.?

(b) Write an Algorithm to insert the element into the B-tree.?

(b) Write an Algorithm to insert the element into the B-tree.?

**OR**

Q.10.(a) Write the Algorithm for Breadth First Graph Traversals.Also prove the time complexity

is :

is :

T(n,e) = T(n2)

(b) Construct the AVL search-tree from the given set of item values 😕

H,I,J,B,A,E,C,F

(b) Construct the AVL search-tree from the given set of item values 😕

H,I,J,B,A,E,C,F