**Important RGPV Question**

Table of Contents

Toggle** CS-303 Data Structure**

**III SEM, CSE**

**UNIT-1 : ****CLASSIFICATION OF DATA STRUCTURE**

**Q.1) **Explain different non primitive data structures and the operations associated with them.

**(RGPV December 2013)**

**Q.2) ** How does the tree Data Structure differ from other Data Structure.

**(RGPV June 2013)**

**Q.3) **Define data structure and differentiate between linear and nonlinear Data Structure.

**(RGPV June 2012)**

**Q.4) **What are the goals of data structure.

**(RGPV June 2014)**

**Q.5) **How is data structure different from data types.

**(RGPV June 2013)**

**Q.6) **Describe about abstract data types.

**(RGPV June 2012)**

**Q.7) **Describe the difference between an abstract data type specification and implementation.

**(RGPV June 2010 December 2014)**

**Q.8) **An abstract data type for a 24 hour clock has operations to set the time read the time and advance the time by 1 second. Provide a specification for the Abstract data type.

**Q.9)**Explain abstract data type with example.

**(RGPV November 2018)**

**Q.10)**Discuss common operations on data structures in brief.

**OR**

write name of data structure operations.

**(RGPV June 2015)**

**Q.11)** Enlist different operations which are normally performed on any Linear array write an algorithm for insertion operation.

**(RGPV December 2014)**

**Q.12)**Explain various algorithm used in data structure also differentiate single and multiple dimensional array with suitable example.

**(RGPV December 2016)**

**Q.13) **What is an array differentiate between one dimensional and two dimensional arrays.

**(RGPV June 2015)**

**Q.14) **Explain the representation of one dimensional and two dimensional array in memory.

**OR**

explain memory addressing schemes for two dimensional arrays with suitable example,

**(RGPV June 2013)**

**Q.15)**Write a program which read to matrix and then print a matrix which is addition of these two Matrix.

**(RGPV June 2015)**

**Q.16)**Write a program in C to search and display the position of an element in one dimensional array.

**Q.17)**What do you understand by single linked list explain.

**OR**

how to declare a structure of a linked list.

**(RGPV June 2015)**

**Q.18)**How can a linked list be implemented using arrays.

**Q.19)**Explain the method of implementing link list using dynamic allocations or discuss the dynamic representation of linked list.

**(RGPV December 2015)**

**Q.20)**Discuss the algorithm of for insertion at a specified position in a linked list.

**Q.21)**Write a program in C/C++ to create a linked list of 10 elements and to traverse the list.

**(RGPV December 2014)**

**Q.22)**Discuss the advantages and disadvantages of doubly linked list give an example to demonstrate insertion and deletion operations in DLL stored in array form.

**(RGPV Feb 2010)**

**Q.23)**What is two way header list explain the operation of inserting an element at the front middle and at the rare in a double linked list.

**Q.24)**Compare array implementation with linked list implementation right function to insert a node in doubly linked list after a note having element (ΞΌ).

**Q.25)**Differentiate between linked list and doubly linked list or compare singly linked list or two way header list .

**(RGPV December 2016)**

**UNIT 2 : ****STACKS AND QUEUES**

**Q.1)** Explain stack and write algorithms for PUSH and POP operations.

**(RGPV Dec 2003,2007) **

**OR**

Write algorithm for operations on a stack.

**(RGPV June 2007)**

**Q.2) **What is meant by stack? What are various operations that can be applied on a stack.

**OR**

Write short note on stack.

**(RGPV November 2018)**

**Q.3) **How do you represent a stack in C.

**OR**

Describe different ways stack representation.

**(RGPV June 2008)**

**Q.4) **What is stack and how it is implemented using array? list few applications of stack.

**(RGPV June 2016)**

**Q.5) **Define police notation. what are the different ways to express an expression.

**OR **

Define the following

(1) fixed notation (2) Polish notation

(3)Reverse polish notation.

**(RGPV June 2013)**

**Q.6) **Write an algorithm to convert infix to postfix expression. explain with an example.

**(RGPV December 2010)**

**Q.7) **A+(B*C-(D/E^F) *G) *H. Give postfix form.

**Q.8) **Convert the following infix expression to postfix form using stack.

A+BC*ac+(P*Q+R)*S, follow usual precedence rule and assume that the expression is legal.

**Q.9) **Explain how the evaluation of postfix expression take place using a stack?

**OR**

Write an algorithm for evaluation of postfix expression with example.

**(RGPV December 2015)**

**Q.10) **Convert the following infix expression to the prefix expression also show all steps.

(1) A^B*C-D+E/F/(G+H) n (2) (A+B) *(C^(D-E) +F) -G

**(RGPV Dec 2016, Nov)**

**Q.11) **Explain the concept of recursion with example.

**Q.12) **Describe Tower of Hanoi problem.

**(RGPV December 2016)**

**OR **

Write an algorithm for Tower of Hanoi problem also explain with the example.

**(RGPV June 2015)**

**OR**

Discuss Tower of Hanoi problem.

**(RGPV December 2015) **

**OR**

Write a recurrence relationship that describe the number of ring moves as a function of and made by the following algorithm that solves the towers of Hanoi problem using 4 Spikes.

**(RGPV June 2016)**

**Q.13) **What do you mean by direct and indirect recursion? write a recursive C function for Tower of Hanoi problem

**(RGPV December 2014)**

**Q.14) **What is recursion? How does it differ from iteration? Write an algorithm to generate first ten Fibonacci numbers recursively.

**(RGPV Dec 2010,2011)**

**Q.15) **Differentiate between the iteration and recursion.

**(RGPV June 2015)**

**Q.16) **Explain recursive algorithm.

**Q.17) **Convert the following expressions into postfix and prefix form-

(i) (A+B)*C/D+Eβ FβG

(ii) B*(-C)*D+AβD

**(RGPV Dec 2013)**

**Q.18) **What are the disadvantages of representing a stack or Queue by link list.

**Q.19) **Show how to implement a queue using two stacks. Analysisn ruing time of the queue operations – n (1) Show that for a sequence of n queue operations, implementation takes a worst case ruing time of O(n). n (ii) If there are a maximum of k elements in the queue at a particular time, what is the worst case ruing time of perform one queue operation.

**Q.20) **Write a short note on circular queue.

**OR**

What is the circular queue? How do you represent it.

**Q.21) **Write a C procedure which implements circular queue.

**OR**

Write an algorithm for insertion and deletion operation on circular queues.

**(RGPV December 2014)**

**Q.22) **How queues can be represented by Circular List? Write algorithms for primitive operations of queues represented by Circular List.

**OR**

Explain the dynamic implementation of circular Queue.

**(RGPV June 2013)**

**Q.23) **What is D-queue? List various classes of D-queue. Explain it’s insertion and deletion operations with the help of examples.

**(RGPV Feb 2010)**

**Q.24) **Discuss the comparison between stacks and queues.

**(RGPV Dec 2015)**

**Q.26) **For a double ended circular queue (i.e. Deque) implementedn using an array, give algorithms for-n (i) Is DQEmpty-returns true if deque is empty. n (ii) Is DQFull-return true if deque is fulln (iii) InsertFront-insert an element is the front of deque. Then algorithms should also check error conditions if applicable.

**(RGPV June 2010)**

**Q.27) **Write short note on D-queue and priority queue.

**(RGPV November 2018)**

**Q.28) **Define Multiqueue.

**(RGPV Dec 2015)**

**UNIT 3 : ****TREE**

**Q.1) **Prove that a tree with k nodes has exactly (k-1) edges or branches.

**(RGPV June 2014)**

**Q.2) **Define tree. Prove that a binary tree with n nodes has exactly (n-1) edges or branches.

**(RGPV Feb 2010, Dec. 2014)**

**Q.3) **What is a binary search tree? Construct a binary search tree for the given array –

14, 10, 17, 12, 11, 20, 18, 25, 8, 22, 23.

**Q.4) **Write recursive algorithm for various type of traversal.

**OR**

Write the recursive inorder, preorder and postorder tree traversal algorithms.

**(RGPV Dec 2013)**

**Q.5) **Explain the operation of AVL tree.

**(RGPV Dec 2010) **

**OR**

Explain AVL with suitable example.n In an AVL Tree at what condition the balancing is to be done .

**Q.6) **What is the difference between an AVL tree and a binary tree.

**(RGPV Dec 2016)**

**Q.7) **In what way is a Avial tree better than a binary tree?

**(RGPV Dec 2016)**

**Q.8)** Determine and explain if the following binary tree is –

(i)Heap

(ii) BST

(iii)Height balanced tree complete binary tree full binary tree.

**(RGPV June 2010)**

**Q.9) **Explain how the balance is restored when an insertion into a balanced tree puts are node out of balance?

**(RGPV Dec 2010) **

**OR**

What is height balancing in a tree? Explain it by taking an example and also write the algorithm for inserting and element.

**OR**

Explain the AVL tree insert method.

**Q.10) **Insert 44 47 and 48 into the following AVL tree sequentially. Show the result for this insertion. Also compute the balance factor for the nodes of the resulting AVL tree.

**(RGPV June 2010)**

**Q.11) **The following data to be inserted in an AVL tree in the following order-

20, 25, 30, 40, 45, 60, 55, 57

Show the tree every time balancing is required.

**(RGPV June 2014)**

**Q.12) **Construct an AVL search tree by inserting the following elements in the fall order of their occurrence 64, 1, 44, 26, 13, 110, 98, 85

**(RGPV June 2015)**

**Q.13)** Construct the AVL tree for the following set of elements

13, 5, 1, 7, 8, 98, 67, 26, 33, 12, 6, 7, 8

**(RGPV Dec 2015)**

**Q.14) **The following data are to be inserted in an APL tree in the following order-

20 40 50 57 56 55 52

Show the tree every time balancing is required.

**(RGPV June 2011)**

**Q.15)** Following notes are inserted into MP3 in order-

5, 16, 20, 40, 5, 10, 18, 30, 40, 12, 1

Construct AVL tree.

**Q.16)** Following notes are inserted into empty tree in order-

5, 10, 20, 40, 2, 9, 18, 30, 45, 12, 3

Construct AVL tree.

**(RGPV June 2012)**

**Q.17)** Construct AVL search tree by inserting the following elements in order of their occurrence.

68, 5, 38, 24, 18, 116, 92, 82, 48

**Q.18)** Construct a heap tree for following notes-

5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1

**Q.19)** What are the applications of trees?

**(RGPV Dec 2014,2015) **

**Q.20)** What are the properties of multiway search tree? Create a 5 way search tree of the following data 50, 72, 96, 94, 107, 26, 12, 11, 92, 10, 25, 51, 16, 17, 95.

**(RGPV Dec 2014)**

**Q.21)** Define B-Tree of order m? When is it preferred to use B-Trees.

**(RGPV June 2016)**

**Q.22) **Write an algorithm to search a key in a B-Tree. What is the worst case of searching in a B-Tree? List the possible situations that can occur while inserting a key in a B-Tree.

**(RGPV June 2016)**

**Q.23) **Discuss the algorithm used for insertion of a node into a B-Tree.

**Q.24)** Construct B tree of order 5 for the list of elements. 2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21.

**(RGPV Nov 2018)**

**Q.25)** What is B+ tree ? Compare it with B-tree. Insert the following entries into an initially empty B-tree of order 5-

a, g, f, b, k, c, h, n, j, d, r, i, s, x, e, l, m, t, u, v.

**(RGPV June 2009, Dec 2014)**

**Q.26) **Following nodes are inserted into empty tree in order-

5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1

Construct (i) Binary search tree (ii) AVL tree.

**(****RGPV Dec 2010, 2011, 2014)**

**Q.27)** Write short note on Red Black tree.

**(RGPV Nov 2018)**

**UNIT-4 : ****GRAPHS**

**Q.1) ** Define weekly coected graph.

**(RGPV Dec 2015)**

**Q.2) **What do you mean by graph and multi graph.

**(RGPV June 2014) **

**Q.3) **Define graph. Explain three commonly used graph representation methods with example.

**(RGPV Dec 2014)**

**Q.4) **Explain sequential representations of graphs.

**(RGPV Dec 2016)**

**Q.5) **What do you understand about graph? How the graphs are represented in the memory?

**(RGPV June 2016)**

**Q.6) **Write a C function to create the adjacency list representation of a graph given its adjacency Matrix representation.

**(RGPV June 2016)**

**Q.7) ** For following graph find-

(i) In degree and out degree of each vertex

(ii) Strongly coected component

(iii) Adjacency matrix.

**(RGPV June 2014)**

**Q.8) **Consider graph (G)

(i) Find adjacency matrix (A) of graph G.

(ii) Find path matrix (P) of G.

**(RGPV June 2014)**

**Q.9)** For the graph given below, find its-

(i) Adjacency matrix

(ii) Path matrix.

** (RGPV Dec 2008, 2014)**

**Q.10) **Find the adjacency matrix, in-degree and out-degree for the give graph.

**(RGPV June 2013)**

**Q.11) **Obtain the adjacency-matrix, adjacency list and adjacency multilist representations of the following graph.

**(RGPV Dec 2013)**

**Q.12) **Is it possible to coect a graph into tree if yes how?

**(RGPV June 2014) **

**OR**

Differentiate between a tree and a graph is it possible to coect a graph into tree? if yes how?

**(RGPV Dec 2014)**

**Q.13) **Prove that the number of edges in n-vertex complete graph in n(n-1)/2 by mathematical induction.

**(RGPV June 11) **

**OR**

Prove that the maximum number of edges possible in a single graph of a node is n(n-1)/2.

**(RGPV Dec 2014)**

**Q.14) **Describe depth first search or breadth first search method of traversing a graph.

**OR**

Explain the graph traversal techniques with example.

**(RGPV June 2013)**

**Q.15) **Discuss breadth first search algorithm with example.

**(RGPV Dec 2015) **

**OR**

Write the algorithm for breadth first traversals and explain with example.

**(RGPV Dec 2013) **

**Q.16) **Highlight the difference between breadth first search and depth.

**(RGPV June 2015) **

**OR**

Differentiate between depth first search (DFS) and breadth first search.

**(RGPV Nov 2018)**

**Q.17) ** Differentiate between DFS and BFS. Give DFS spaing tree and BFS spaing tree of the given graph.

**(RGPV Dec 2008, June 2009) **

**OR**

Differentiate between DFS and BFSn Give DFS spaing tree of the given graph-

**(RGPV Dec 2014)**

**Q.18) **In what order are the vertices visited using DFS starting from vertex A in the following undirected graph? Where a choice exists alphabetical order. What if you use BFS?

**(RGPV June 2010)**

**Q.19) **From the given graph G. Find the minimum path P from A to Y using Breadth First Search (BFS).

**(RGPV June 2015)**

**Q.20) **Explain spaing tree and a minimum cost spaing tree.

**[RGPV June 2005 (IV-Sem), 2006(IV-Sem), Dec. 2011]**

**OR**

Explain minimum cost spaing tree.

**(RGPV Dec 2012)**

**Q.21) **Define spaing tree.

**(RGPV Dec 2015)**

**Q.22)**Describe the routine for minimum cost spaing tree using a suitable example with graphical representation.

**(RGPV Dec 2016)**

**Q.23) **Explain the Kruskal algorithm with example.

**(RGPV Dec 2011) **

**Q.24) **Find the minimum cost spaing tree of the given graph using Kruskal’s algorithm.

**(RGPV Feb 2010, June 2014)**

**OR**

Find the minimum spaing tree of graph G.

**(RGPV June 2015)**

**Q.25) **Explain Prim’s algorithm for minimum spaing tree with example.

**(RGPV Nov 2018)**

**Q.26) **Explain spaing tree and its components.

**(RGPV Dec 2016) **

**UNIT-5 : ****SORTING AND SEARCHING**

**Q.1) **Write short note on the internal and external sorting.

**(RGPV Dec 2008)**

**OR**

Define the term-

(i) Internal sorting (ii) External sorting.

**(RGPV June 2014) **

**OR**

Differentiate between internal and external sorting.

**(RGPV June 2012, 2015) **

**OR**

Discuss internal and external sorting.

**(RGPV Dec 2015)**

**Q.2) ** Discuss bubble sorting and explain it with example. Also write the algorithm and complexity of the bubble sort.

**OR**

Write bubble sort algorithm and also calculate its efficiency.

**(RGPV June 2010)**

**Q.3) **Write quick sort algorithm. Using quick sort technique set the following array in ascending order. Show all steps- 25, 57, 48, 37, 12, 92, 86, 33, 50, 42

**(RGPV June 2006, Sept 2009)**

**OR**

Explain quick sort algorithm and also write it. Calculate efficiency (or complexity) of quick sort.

**(RGPV Dec 2008)**

**OR**

Discuss the algorithm of quick sort with example.

**(RGPV Dec 2015)**

**Q.4) **Sort the following integers using quick sort β

25, 57, 48, 37, 12, 92, 86, 33

**(RGPV June 2014)**

**Q.5) **What is quick sort? Why is it called partition exchange sort?

**(RGPV Dec 2014)**

**Q.6) **Sort using quick sort algorithm. 36, 25, 32, 5, 8, 65, 38, 47, 95.

**(RGPV Nov 2018)**

**Q.7) **Write short note on heap sort.

**(RGPV Nov 2018)**

**Q.8) **Write an algorithm for selection sort. What is the complexity of n this algorithm?

**(RGPV Dec 2014)**

**Q.9) **Derive the worst case and average case complexity of selection sort algorithm.

**(RGPV June 2015)**

**Q.10) **Describe the complexity of heap sort.

**(RGPV June 2014)**

**Q.11) **Sort the following elements using heap sort-

8. 11, 56, 23, 90, 75, 39, 21, 17, 89, 4

**(RGPV June 2013)**

**Q.12) **How many key comparisons and assignments are required in an insertion sort to sort list of N elements?

**(RGPV June 2013)**

**Q.13) ** Show under what order of input, the insertion sort will have worst-case and best-case situations for sorting the set {142, 543, 123, 65, 453, 879, 572, 434}n** (RGPV June 2016)**

**Q.16) ** What is a stable sorting algorithm? Which of the sortingn algorithm, we have seen are stable and unstable using a suitable example? Prove that counting sort is stable.

**(RGPV Dec 2016) **

**Q.14) **Suppose the elements in the array are-

A=<2, 13, 5, 18, 14, 20> Does this array can be represent in INSERTION SORTING? Justify your answer with all the steps?

**(RGPV Dec 2016)**

**Q.15) **Consider following list of elements as – 50, 40, 20, 70, 15, 35, 20, 60 sort the sequence using merge sort show all steps.

**(RGPV Dec 2016)**

**Q.16) **Compare merge sort and quick sort algorithms in terms of storagen space and time required to execute them.

**(RGPV Dec 2013)**

**Q.17) **Explain how merge sort sorts the following sequence of numbers using a diagram (142, 543, 123, 65, 453, 879, 572, 434 ).

**(RGPV June 2016)**

**Q.18) **Write a short note on complexity of radix sort.

**(RGPV Dec 2008)**

**Q.19) ** What is min heap? Create the min heap for the given data set- 6, 15, 50, 3, 33, 45, 40, 80, 80, 10

**(RGPV Dec 2013)**

**— Best of Luck for Exam —**