Data Structures and Applications Previous year questions

In this post, you will get the previous year questions of Data Structures and Applications. DSA 21CS32 3rd semester previous year questions.

Data Structures and Applications Previous year questions

MODULE 1

1. Define data structures. Give its classifications

2. Define structures with examples.

3. Define pointers. Give advantages and disadvantages of pointers.

4. Write a program to (i) reverse a string, and (ii) concatenate two strings (iii) Compare Strings.

5. Explain dynamic memory allocation in detail.

6. Differentiate between structures and unions.

7. Explain with examples: i) insertion and ii) deletion in an array.

8. What is Sparse Matrix | Give the Triplet form of given Matrix.

9. Differentiate between Structures and Unions with example.

10. How would you represent polynomial using array of structures and also write a function.

11. Explain different types of structure declaration with examples

12. Define pointers. How to declare and initialize pointers, explain with example

MODULE 2

1. Define stack. Implement push and pop functions for stack using arrays.

2. Define queues. Implement Qinsert and Qdelete function for queues using arrays.

3. Define recursion. Write recursive program for i) Factorial of a number , ii) tower of Hanoi

4. Write the postfix form of the following expression :  4$2*3-3+8/4/4(1+1)

((((a/b) – c) + ((d*e)) – a * c))     ii) A – B | (C * D $ E)

5. Write an algorithm to evaluate a postfix expression. Evaluate the following postfix expression abc +*de/-  where a = 5, b = 6,c = 2, d = 12, e = 4.

6. Write a function to evaluate Postfix expression.

7. evaluate for the given postix expression. ABC – D *+E$F+ and assume A = 6, B = 3, C = 2, D = 5, E = 1 and F = 7.

8. With a neat diagram explain ONE-WAY list representation of a priority queue.

9. Write a C program demonstrating the various stack operations, including cases for overflow and underflow of STACKS.

10. Explain with suitable example disadvantages of ordinary queue and how it is solved using circular queue.

11. Define stack. Give ‘C’ implementation of PUSH and POP functions. Include check for empty and full conditions of stacks.

12. Define stack. Give the implementation of push, pop and display functions. Include check for empty and full conditions.

13. What is the advantage of circular queue over ordinary queue? Write a C program to simulate the working of circular queue of integers using array. Provide the following operations: Insert, Delete, Display

14. Write a note on Dequeue and priority queue.

MODULE 3

14. What is a linked list? Explain the different types of linked lists with a neat diagram.

1. Write the following functions for singly linked list: (1) Reverse the list (ii) Concatenate two lists.

2. Write functions insert_front and delete_front using doubly linked list.

3. Write an algorithm to add two polynomials.

4. Define sparse matrix. Give sparse matrix representation of linked list for given matrix.

7. Write a note on header linked list. Explain the widely used header lists with diagrams.

8. List out any 2 differences between doubly linked lists and singly linked list.

9. Illustrate with examples how to insert a node at the beginning, INSERT a node at intermediate position, DELETE a node with a given value.

12. Write a note on Doubly Linked lists and also write functions to insert at front and delete at front using D.L.L

15. Write a C function to insert a node at front and delete a node from the rear end in a circular linked list.

16. Write a C function for the concatenation of two doubly linked lists.

17. Describe the doubly linked lists with advantages and disadvantages. Write a C function to delete a node from a circular doubly linked list with header node.

19. Write a C function to add two-polynomials represented as circular list with header node.

MODULE 4

10. With suitable example define the following (i) Binary tree (ii) Fall binary tree (ii) Almost complete B.T (iv) Strict Binary tree (v) Level of B.T

2. Given inorder sequence: DJGBHEAFKIC and postorder sequence: JGDHEBKIFCA. Construct binary tree and give preorder traversal.

3. Explain threaded binary tree in detail. 

4. Write a function to insert an item into an ordered binary search tree (duplicate items are not allowed)

5. Write a short note on threaded binary trees and state the rules to constrict a threaded binary tree.

6. With separate functions illustrate recursive search and iterative search of a binary search tree.

7. Consider the following tree T in (Fig.7(a)) write the preorder, inorder, postorder for the tree T. Also find the depth of TREE in (Fig.7(a)).

(Fig.7(a))

8. Write functions to illustrate “copying of binary trees”, and “testing equality of binary trees”.

9. Define complete binary tree. Illustrate with examples

11. Create expression tree for the Postfix expression given below.

AB/C*D*E+ and traverse the resulting expression tree using inorder and preorder traversals.

12. Write a note on Threaded Binary tree for a given Binary tree in Fig.Q12(a), Insert ‘r’ as a right child of ‘S’ in a Threaded Binary tree and write the function to insert

Fig.Q12(a)

13. Define BST Write a function to insert an item into BST.

14. Show that for any non-empty b-tree T. if n₀ is the number of leaf nodes and n₂ is the number of nodes of degree 2 than n₀ = n₂₊₁

15. Write “C” functions to illustrate copying of binary tree.

16. What is a tree? With suitable example, define:

• Binary tree 
• Level of the binary tree
• Complete binary tree
• Degree of the tree

17. Write the ‘C’ routines to traverse the tree using:

• Pre-order traversal
• Post-order traversal.

18. For the given data, draw a binary search tree and show the array and linked representation of the same: 100, 85, 45, 55, 110, 20, 70, 65.

19. What is the advantage of the threaded binary tree over binary tree? Explain the construction of threaded binary tree for 10, 20, 30, 40 and 50.

20. Define expression tree. For a tree given in Fig.Q20(a) traverse the tree using in-order, preorder and post-order traversals.

Fig.Q20(a)

21. Construct a binary search tree by using the following in-order and preorder traversals:

• Inorder : BCAEDGHFI 
• Preorder: ABCDEFGHI

MODULE 5

1. Define graph. Give adjacency matrix and adjacency linked list for given weighted graph in Fig.Q1(a).

Fig.Q1(a)

2. Write an algorithm for breadth first search and depth first search.

3. Write an algorithm for Radix sort.

4. Explain Hashing in detail.

5. State and explain WARSHALLS algorithm with an example.

6. Write an algorithm for insertion sort. Apply insertion sort, showing the various passes to sort the array A, where A = [77, 33, 44, 11, 88, 22, 66, 55].

7. Write a short note on hashing. Explain any 3 popular HASH functions.

8. What do you understand by the term file organization? Briefly summarize any 3 widely file organization techniques.

9. Define graph. Give adjacency matrix and adjacency lists for the graph given below Fig Q9(a) :

Fig Q9(a)

10. Write an algorithm for DFS, show BFS and DFS traversals for the graph given in Q.No.9(a).

11. Write a note on Hashing functions.

12. What is collision? What are the methods to resolve collision? Explain linear probing with an example. 

13. Suppose 9 cards are punched as follows 348, 143, 361, 423, 538, 128, 321, 543, 366. Apply Radix sort to sort them in 3 phases and give its complexity.

14. Define graph. For the given graph, show the adjacency matrix and adjacency list representation of the graph Ref. (Fig.14(a))

Fig.14(a)

15. What are the methods used for traversing a graph? Explain any one with example and write C function for the same.

16. Write a C function for insertion sort. Sort the following list using insertion sort: 50, 30, 10, 70, 40, 20, 60

17. What is collision? What are the methods to resolve collision? Explain linear probing with example.

18. Explain in detail about static and dynamic hashing.

19. Briefly explain basic operations that can be performed on a file. Explain indexed sequential file organization.