QP DSA

Every year thousands of students appear for sppu exams, therefore it is very necessary for each and every student to be mentally prepared for the exams and for this case only we study the previous year question papers to get an insight of previous year question papers.

A good analysis of question papers can help you get a better head from others in the same exam as now you would be already prepared for those questions and that would even help you score better.The best advice that we can give you is that try to solve the maximum questions by yourself only rather than depending on solutions based books it would ultimately make your mind more lazy and you will put effort much less and the result would be that you would get less out of the subjects.

These all are as per updated 2015 pattern onwards which are of 50 marks. The question paper is divided into 8 questions of which you have to attempt any four, there is a choice in every question, so among 1st two you have to attempt anyone and so on. The major advantage of this pattern is that it gives you the freedom to choose you among questions but each question comes with 12 to 13 marks per head so getting a question wrong in the subject where the start and final steps matter also count a lot.so we are also uploading a series of a specially designed question bank for better preparation.

Unit I- Introduction to Algorithms & Data Structures
• What is data structure? State its necessity.
• Explain Greedy algorithm with Suitable Example
• Classify and describe different data structure.
• Describe various type of operator which can be performed on data structure.
• Define : i) Linear and Non-linear data structures
ii) Static and Dynamic data structures iii) Persistent and Ephemeral data structures
• Enlist and explain characteristics of algorithm.
• Describe Big ‘O’ Notation used in algorithm. Give Time and Space Complexity of all Sorting and Searching.
• Explain different approach to design an algorithm.
• What do you mean by primitive and non-primitive data structure explain with example.
• What do you mean by linear and non-linear data structure explain with example.
• Explain Time and Space complexity related to algorithm and also state their importance.
• Explain built in and derived data type with example.
• Describe abstract data type.
• Define ADT.
• What is recursive data structure?
• List out the areas in which data structures are applied extensively
• How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example.
• What do you mean by complexity of an algorithm? Explain the meaning of
worst case analysis and best case analysis with an example.
• What is called as a Data Structure? Explain classification of data structure.
• Differentiate between data type and data structures.
• Explain Primary & Secondary Data Structures.
• Explain Time and space complexity with example
• Define Flowchart, Algorithm, and Pseudo code with Example.
• Write difference between static and dynamic data structure.
• Ephemeral and Persistent data structure


Unit II- Linear Data Structures using Sequential Organization
• What is an array?
• Explain an efficient way of storing a sparse matrix in memory. Write a module to find the transpose of a sparse matrix stored in this way.
• With Suitable Example , Describe Polynomial multiplication using array.
• Define the term array. How are two-dimensional arrays represented in memory? Explain how address of an element is calculated in a two dimensional array.
• Explain Array as ADT.
• Define a sparse metrics. Explain the representation of a 4X4 matrix using
linked list.
• Define data type and abstract data type. Comment upon the significance of both.
• Explain concept of 2D Array
• Explain Greedy and Divide Conquer method.
• Write a program to check Palindrome number
• Explain Array as ADT.
• Explain Polynomial as an array of structure with all functions
• Write a program for all string operations with using Library functions
• Write a program for all string operations without using Library functions

Unit III Linked Lists
• What are the disadvantages array implementations of linked list?

• Swap two adjacent elements by adjusting only the pointers (and not the data) using singly linked list.
• What are the advantages of doubly linked list over singly linked list?
• What is a circularly linked list?
• What is linear list?
• How will you delete a node from a linked list?
• What is linear pattern search?
• What is doubly linked list?
• Design and implement an algorithm to search a linear ordered linked list for a given alphabetic key or name.
• Given two sorted lists L1 and L2 write a procedure to compute L1_L2 using only the basic operations
• Write a routine to insert an element in a linked list
• Two linked lists contain information of the same type in ascending order. Write a module to merge them to a single linked list that is sorted.
• Write a complete program in C to create a single linked list. Write
• Functions to do the following operations
o Insert a new node at the end
o Delete the first node
• What are the advantages and disadvantages of linked list?

Unit IV- Stacks

• What is the use of stack pointer?
• Explain the implementation of stack using Linked List.
• What is a stack? Write down the procedure for implementing various stack
operations
• Explain the various application of stack?
• What is the difference between a Stack and an Array?
• Convert the following infix expression to post fix notation ((a+2)(b+4)) -1 • Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input : a b + c d +f .
• Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.
• Execute your algorithm to convert an infix expression to a post fix expression with the following infix expression as input A+B-C/DEFG/H . • State the difference between array and linked list. • Define stack and what are the basic operation performed on it explain. • Convert following expression Q into postfix and prefix form. Q=(A+B)C-D/E*(F/G).Show stack representation.
• Write procedure to push element on stack. Also give meaning of stack overflow, stack underflow, top of stack terms.
• Explain four primitive operation stack with diagram.
• Define recursion? Write a ‘C’ Program to find factorial of given number.
• What is recursion? Write a ‘C’ Program to find fibo series of 1st ten numbers.
• Discuss the Polish Notation of arithmetic expression in application of stack.
• Discuss push and pop operation on stack.
• Draw flowchart and Write ‘C’ Program to perform push and pop operation on stack.
• State application of stack.
• State ADT of stack.

Unit V- Queues
• Give the structure of Queue model.
• What are the basic operations of Queue ADT?
• What is Enqueue and Dequeue?
• Give the applications of Queue.
• Define a queue model.
• What is a queue? Write an algorithm to implement queue with example.
• What are circular queues? Write down routines for inserting and deleting
elements from a circular queue implemented using arrays.
• Implement a Queue using a singly linked list L. The operations INSERT and DELETE should still take O (1) time.
• Devise a representation for a list where insertions and deletions can be made at either end. Such a structure is called Deque (Double ended queue). Write
functions for inserting and deleting at either end.
• Distinguish between stack and queue.
• Explain concept of Priority Queue and Circular linked list representation of Queue.
• Write C functions for insertion and deletion of Queue elements using array.
• Explain the concept of Circular Queue with example.
• Write algorithms for basic operations of deque.
• State ADT for queue
• Write procedure, draw flow chart and Write ‘C’ Program for inserting and deleting element in queue.
• Define Circular Queue. Also explain advantages and disadvantages of Circular Queue.
• State application of Queue.
• State difference between Stack and Queue.
• Describe the term front pointer, rear pointer, overflow, underflow related to Queue.
• Explain priority Queue with example and its type.
• Explain concept of Circular Queue with diagram and example.
• What is dQueue? List and describe its different type with diagram and example.
• Write ‘C’ Program to implement insert and delete operation in queue.
• Explain Input Restricted and Output Restricted dQueue.

Unit VI- Sorting & Searching
• Explain Radix sort with example.
• Explain Merge sort with example.
• Write Program for Insertion Sort.
• Write ‘C’ Program for Binary Search.
• Sort The given numbers in ascending order using Radix Sort.(348 14 614 5381 47 986 2432 128).
• Write Algorithm for Insertion Sort and arrange the given numbers in ascending order.(77 33 44 11 88 22 66 55).
• Describe the principle of Selection Sort and demonstrate using one example.
• Write a Program for Bubble Sort in ‘C’ Language.
• Compare Quick and Heap Sort with respect to working principle and time complexity.
• Explain Linear Search Algorithm and state its Limitations.
• Write an Algorithm for insertion sort and arrange the given numbers in ascending order.(45 22 8 34 19).
• Compare Merge and Quick Sort with respect to working principle and time complexity.
• What is Searching and Sorting with respect to working principle and time complexity.
• Explain Merge Sort.State advantages and disadvantages and Sort the following numbers in ascending order using Merge Sort. (15,84,62,08,41,57,33,18,51,32).
• Compare Quick Sort and Radix Sort with respect to working principle and time complexity.
• What is Searching?Explain linear search with example.
• Write and explain procedure for recursive Quick Sort and Justify with an example.
• Write a ‘C’ Program for Selection Sort and arrange the given numbers in ascending order.(16,23,13,09,07,05).
• Write an Algorithm for Bubble Sort.
• Consider a data(53,64,23,66,98,12,76,44,33,10) and write an Algorithm to search (22) using linear search.
• Describe Radix Sort Algorithm and State its complexity.
• Explain the concepts of Sorting Algorithm and efficiencies of Sorting Algorithm.
• Explain Binary Search Algorithm with example.
• Explain Quick Sort.State its advantages and disadvantages and Sort the following numbers in descending order.(11,05,21,03,29,17,02,43).
• Give principle of Insertion Sort with Algorithm.
• Explain Linear and Binary Search algorithm with time complexity and example.
• Explain Internal and external sorting. Define sort stability, efficiency and passes with example
• Apply binary search and explain the steps,
9,17,23,38,45,50,57,76,79,90,100- search 77
• Explain Quick sort and Merge sort with example.