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 by row, then what is the address of matrix element
A[i,j] for row and 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?

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 *
ESFSG

12. Write an algorithm to perform various operations (insert, delete and display) for simple
queue.

13. Write algorithms between insert and delete in circular queue. Write an algorithm for
insert and delete operations for circular queue.

14. Convert the following expression from infix to postfix. A + B – C * D * E S F S G

Write algorithms (i) to implement 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.

15. Write a ‘C’ program to implement stack using linked list.

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.

5. Write a short note on threaded binary tree

6. Write an algorithm for binary search method and discuss its efficiency

7. 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

8. Explain Depth First Search and Breadth First Search in graphs with an example.

9. Explain and differentiate BFS and DFS graph traversal method with suitable graph

10. Draw a binary expression tree for the following and perform preorder traversal for the
same: (A + B $ C) + (D + E * F)

11. Construct a binary search tree for the following and perform inorder and postorder
traversals: 5 9 4 8 2 1 3 7 6

12. Write ‘C’ functions for: inserting a node, postorder traversal and counting total number
of nodes for binary search tree.

13. 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

14. Write Kruskal’s algorithm for minimum spanning tree with an example.

15. Write a non-recursive algorithm for Preorder traversal of a binary tree.

16. 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
17. 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 hashing. Classify hashing. Explain clustering, secondary clustering, rehashing and
double hashing.

4. Define the terms: File, Record, Database, Key

5. Discuss various rehashing techniques.

6. Discuss importance of hashing. Also discuss one of the method of hashing with an
example.

7. Discuss the structure of sequential and indexed file organization.

8. 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?