List of important Questions : Data Structure

Unit -1

1. What does abstract data type means? Briefly explain linear and non linear data structures.
2. What is data structure? Explain different types of data structures with applications.
3. Derive the formula to calculate address A[i, j] of 2-D array, for a Row-major order storage
representation. A 2-D array defined as A[r, c] where 1 ≤ r ≤ 4, 5≤ c ≤ 8, requires 2 bytes of
memory for each element. If the array is stored in Row-major order form, calculate the
address of A[3,7] given the Base address as 2000.
4. Define data structure. List out types of Data Structure and explain them in
brief./Differentiate the following terms:
a. Primitive and Non Primitive Data structure
b. Linear and Non Linear Data structure.

5. What is a sparse matrix? Explain memory representation of a sparse matrix.

6. Discuss best case, average case and worst case time analysis with example.
7. What does abstract data type means?
8. A two dimensional array is stored row by row, then what is the address of matrix element
A[i,j] for n row and m column matrix? How array representation of polynomial
2x2+5xy+y2 can be done?
9. Which data structure is used in a time sharing single central processing unit and one main
memory computer system where many users share the system simultaneously? How users
are added for use of the system?
10.

Unit-2
1. Explain PUSH and POP operation of the stack with algorithm.
2. Write an algorithm to convert infix to postfix expression and explain it with example.
3. Write a Program to perform insert and delete operations on a circular Queue.
4. Compare Simple Queue vs Circular Queue. Write an algorithm/program to implement
insert/delete operation into a CircularQueue using array representation of Queue
5. Explain following:
(i) DQUEUE (ii) Priority Queue(iii) Circular Queue

6. Define recursion. What care should be taken in writing recursive function? Give a recursive
solution for the problem of “Towers of Hanoi”.
7. What is recursion? Write a C program for GCD using recursion / Write a C Program for
Factorial Number Using Recursion.
8. Write an algorithm to insert and delete a node in Doubly Linked List.
9. Differentiate between stack & queue. Also explain priority queue with example.
10. Write a program to search an element in a linked list.
11. What is prefix notation? Convert the following infix expression into prefix. A + B – C * D
*E$F$G
12. Write an algorithm to perform various operations (insert,delete and display) for simple
queue.
13. Write differences between simple queue and circular queue. Write an algorithm for insert
and delete operations for circular queue.
14. Convert the following infix expression into postfix. A + B – C * D * E $ F $ G
15. Write algorithm(s) to perform INSERT_FIRST (to insert a node at the first position) and
REVERSE_TRAVERSE (to display the data in nodes in reverse order) operations in
doubly linked list.
16. Write a „C‟ program to implement stack using linked list. 14.Enlist and briefly explain
 various applications of stack.
17. Write „C‟ functions to implement INSERT_FIRST (to insert a node at the first position),
DELETE_FIRST (to delete a node from the first position), DELETE_LAST (delete a node
from the last position) and TRAVERSE (to display the data in nodes) operations in circular
linked list.
18. Discuss and compare array and linked list.
19. Convert the following infix expression to postfix form using Stack. (( A – (B + C)) × D) /
(E + F)
20. What is a priority queue? Discuss the array implementation of priority queue. 18.Write C
code to insert a node at the end of a doubly link list.
21. Write an algorithm to merge two simple link lists having initial address L1 and L2
respectively. Also write algorithm to display the list.
22. Write algorithm OR code for DELETE and DISPLAY functions of Circular Link List.
23. Write C code for the following operations for a simple link list.
a. Reverse : to reverse the link list
b. Max: : to find the largest element from the link list.
24. Convert infix expression into Prefix/Postfix format showing stack status after every step in
tabular form.
c. (A + B) * C – D ^ E ^ (F * G)
d. (A+B)*D+E/(F+G*D)+C
e. A/B$C+D*E/F-G+H
f. a – b / c * d + e * f / g
g. (( A –( B +C))* D) $ ( E +F ) etc.
25. Write an algorithm for evaluation of postfix expression and evaluate the following
expressions showing every status of stack in tabular form.
h. 5 4 6 + * 4 9 3 / + *
i. 7 5 2 + * 4 1 1 + / -
j. 2 $ 3 + 5 * 2 $ 2 – 6 / 6 etc.
26. Enlist and briefly explain various applications of stack.
27. Compare Linked List and Array.
28. Write „C‟ functions / C Program (1) insert a node at the end (2) delete a node from the
beginning (3) insert a node at the beginning (4) delete a node at the end of a Singly Linked
List /Doubly linked list/ / Circular Linked list.
29. Write an advantage of link list, doubly link list and circular link list. (ii) Explain – Why
doubly linked lists are much more efficient with respect to deletions than singly linked
lists?

Unit-3
1. Create a Binary Search Tree for the following data and do in-order, Preorder and Post-order
traversal of the tree. 40, 60, 15, 4, 30, 70, 65, 10, 95, 25, 34
2. Define the following with example :
a. Strictly binary tree
b. Complete binary tree
c. Binary search tree
d. Binary tree
e. Directed graph
f. Undirected graph
g. Degree of vertex
h. Null graph
i. Multi graph
j. Weighted graph
k. Elementary path
l. Descendent node
m. Path,
n. Cycle,
o. Degree of vertex,
p. Sibling,
q. Height Balanced Tree,

3. How graph can be represented? Write an algorithm for Breadth First Search Traversal of a
Graph. 4.What is an AVL tree? Explain the different types of rotations used to create an
AVL tree with suitable examples.
4. Write a short note on threaded binary tree
5. Write an algorithm for binary search method and discuss its efficiency
6. Define height of the binary tree. Define height balanced tree with its advantages. Construct
a height balanced binary tree (AVL tree) for the following data.
42,06,54,62,88,50,22,32,12,33
7. Explain Depth First Search and Breadth First Search in graphs with an example.
8. Explain and differentiate BFS and DFS graph traversal method with suitable graph
9. Draw a binary expression tree for the following and perform preorder traversal for the
same: (A + B $ C) + (D + E * F)
10. Construct a binary search tree for the following and perform inorder and postorder
traversals: 5 9 4 8 2 1 3 7 6
11. Write „C‟ functions for: inserting a node, postorder traversal and counting total number of
nodes for binary search tree.
12. Construct a binary search tree from the following traversals:
Inorder: 3 4 5 6 7 9 17 20 22
Preorder: 9 4 3 6 5 7 17 22 20
13. Write Kruskal‟s algorithm for minimum spanning tree with an example. 11.Write a non-
recursive algorithm for Preorder traversal of a binary tree.
14. With figure, explain the following terms: (1) Depth of a tree (2) Sibling nodes (3) Strictly
binary tree (4) Ancestor nodes (5) Graph (6) Minimum spanning tree (7) Degree of a vertex
15. Write Prim‟s algorithm for minimum spanning tree with an example

Unit-4
1. What is hashing? Explain hashing functions.
2. Write a short note on inverted key file organization.
3. Define Hash Clash. Explain Primary Clustering, secondary clustering, rehashing and
double hashing.
4. Explain the terms: File, Field, Record, Database, Key
5. Write a short note on indexed file organization.
6. Discuss various rehashing techniques.
7. Discuss importance of hashing. Also discuss one of the method of hashing with an example.
8. Discuss the structure of sequential and indexed file organization.
9. Describe various collision resolution techniques in hashing.

Unit-5
1. Write an algorithm for Binary search method.
2. Write a „C‟ program for Bubble sort.
3. Sort the following numbers using (i) Selection sort (ii) Quick sort: 10 50 0 20 30 10
4. Write a „C‟ function for Selection sort.
5. Write an algorithm for Quick sort.
6. Write a selection sort algorithm and also discuss its efficiency.
7. Apply quick sort on following data:
42 23 74 11 65 58 94 36 99 87
8. What is the time complexity of Quicksort algorithm in the worst case?