Important RGPV Question
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 —
