DATA STRUCTURES & APPLICATIONS III-SEM

Data Structures and Applications-Module-wise

Practice Questions

Module-1
1. Explain the concept of dynamic memory allocation and describe the various dynamic memory
allocation functions in C, along with their syntax and suitable examples.
2. Explain self-referential structure with syntax example.
3. Define data structure. Explain classification and need of Data structures.
4. What is Stack? Write a c program to implement stack using an array checking all necessary conditions
and to perform the following operations: push (), pop () and display.
5. Assume you are implementing a stack using a dynamic array. When the stack is full, it should
automatically double its size. Write a C program to demonstrate this concept.
6. Write a Program to
i. Evaluate a postfix Expression (Note: Postfix=Reverse Polish Notation and Prefix= Polish
Notation).
And Trace the algorithm for the expression: ABC + * CBA - + * where A=1, B=2, C=3.
623+-382/+*2$3+
ii. Reverse a string and check for palindrome or not using STACK.
iii. A teacher wants to store and later expand the list of student marks in memory as the class size
increases. Write a C program that dynamically allocates memory for 5 student marks and resize
the memory when the teacher enters a new class size.
iv. Write a C program that uses a stack to check whether an input expression containing parentheses
() and curly braces {} is [Link] program should read an expression, use stack operations
to match each opening and closing bracket, and display whether the expression is “Balanced”
or “Not Balanced.”

7. Explain how two stacks can be efficiently implemented within a single array without wasting space.
Write functions to perform push and pop operations for both stacks and demonstrate how overflow and
underflow conditions are handled.
OR
In a memory-constrained embedded system, you are required to maintain two different stacks—one for
user actions and another for system actions—using a single shared memory block (array). Design and
implement the system so that both stacks can grow dynamically from opposite ends of the array without
overlapping. Include suitable push and pop operations for both stacks.

8. Write a Program to Convert Infix to Postfix Expression. Convert the following infix expression to
postfix expression using STACK by showing the steps clearly:
i. A+B*C-D/E
ii. (A+B) ^ (C*D)
iii. ((M+(N-O)*P)^Q+R)
iv. A^B^C-D+E+F/G
v. (A+B)*(C$(D-E)+F)-G

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 1

 DATA STRUCTURES & APPLICATIONS III-SEM

Module-2

1. What is Queue? List its types. Mention the limitations of Linear Queue. Also explain the insert, delete and
display operations on Queue with appropriate examples.

2. What are the disadvantages of Linear Queue? Write C functions for Insertion, Deletion and display of
elements in a circular queue. Trace and show (diagrammatically) the representation of the queue of size 3
for the conditions:
i. Insert 3 elements
ii. Delete 2 elements
iii. Insert 3 elements.
iv. Delete 1 element
3. What is double ended queue? List and Write a C functions to perform operations on Double ended queue.
4. Consider the following sequence of operations on an empty stack.
Push(54);push(52);pop();push(55);push(62);S=pop();

Consider the following sequence of operations on an empty queue.

enqueue(21);enqueue(24);dequeue();enqueue(28);enqueue(32);Q=dequeue();

Find the value of S+Q.

5. The initial configuration of circular queue as follows

a - - b c
What is the status of states of queue contents after the following sequence of steps?
enqueue(x), dequeuer(),enqueuer(y), dequeuer(), enqueue(z), dequeuer().

6. Write a program to implement priority Queue using circular array.

7. Design and implement a C program that dynamically manages a circular queue with automatic
resizing. When the queue becomes full, it should automatically double its capacity while preserving the
correct circular order of elements.
8. What is Recursive function? Write a recursive C program to find
i. Factorial of a number
ii. Sum of N natural numbers.
iii. Ackermann Function
iv. Fibonacci series
v. GCD of two numbers
vi. Solve tower of Hanoi problem, solve the same problem for three disks. Calculate the number of
moves required also write recursive call list.

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 2

DATA STRUCTURES & APPLICATIONS III-SEM

Module-3
1. Write a C program to perform following operations on Singly Linked List.
i. Create ii. beginsert (); [Link]();
iv. randominsert(); v. begin_delete(); vi. last_delete();
vii. random_delete(); viii. void search();
2. Write a C program to perform following operations on Circular Singly Linked List.
ii. Create ii. beginsert (); [Link]();
v. randominsert(); v. begin_delete(); vi. last_delete();
vii. random_delete(); viii. void search();
3. Write a C program to perform following operations on Doubly Linked List.
i. Create ii. beginsert (); [Link]();
vi. randominsert(); v. begin_delete(); vi. last_delete();
vii. random_delete(); viii. void search();
4. Write a C function to insert a node in a doubly linked list by position. Your program should take position
as input from user.
5. Differentiate between doubly Linked List and singly Linked List. Develop a ‘C’ routine to insert a node
before a given key node in a doubly linked list.
6. Write a C program to perform following operations on Circular Doubly Linked List.
i. beginsert (); ii. lastinsert ();
iii. begin_delete(); iv. last_delete();
7. Write a Program to implement Stack Operations using Linked List.
8. Write a Program to implement Queue Operations using Linked List.
Lab Programs 6 & 7
9. Design, Develop and Implement a menu driven Program in C for the following operations on Singly
Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo.
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit
[Link], Develop and Implement a menu driven Program in C for the following operations on Doubly
Linked List (DLL) of Employee Data with the fields: SSN, Name, Dept,Designation, Sal, Ph. No.
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue
f. Exit.

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 3

 DATA STRUCTURES & APPLICATIONS III-SEM

Module-4
1. Explain the following terms with suitable examples: Binary Tree, Full/Complete Binary Tree, Nearly Complete
Binary Tree, Strictly Binary Tree, Expression Tree, Binary Search Tree, Height of a tree, Level of a tree ,
Descendants, degree of tree, Ancestor, path, internal nodes,
2. With suitable example, explain Lemma/Properties of Binary tree.
3. Explain Different ways to represent Binary Tree.
4. Find the following in the tree given:

i. Balance factor of the tree.

ii. Show the depth first traversal (preorder, inorder and postorder) of the tree.
iii. Show the breadth first traversal of the tree.
5. Write c functions for each of the following: Inorder traversal, Preorder traversal, Postorder traversal.
6. What is Binary Search Tree? Write the Inorder traversal, Preorder traversal and Postorder traversal of a given
tree here root is 25.

7. Create a Binary Search Tree (BST) using the following data entered as a sequential set:
i. 14,15,12,23,5,7,7,10,33,80,66
ii. DATASTRUCTURESUSINGC
8. Construct the Expression tree for the following and also write the preorder and postorder traversals for the tree
generated.
i. ( a / ( b + c )) + (((d / e) - f) * g)
ii. (5+6*7)$((5+6)*7))
iii. A+(B-C)*D$(E*F)
iv. (A+B*C)$ ((D+E)*F)
9. Generate binary trees looking into the following tree traversals:
i. Preorder : ABDGCEHIF; Inorder : DGBAHEICF
ii. Postorder : IEJFCGKLHDBA; Inorder : EICFJBGDKHLA.
10. Write an algorithm/function to delete a node from the BST. Also explain the same using appropriate examples.
11. Write the algorithms for the following operations in Binary Search Tree (BST).
i) Smallest node in a BST ii) Add node to BST iii) Search an item in a BST
12. Lab Program-8: Develop a menu driven Program in C for the following operations on Binary Search Tree
(BST) of Integers.
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 4

 DATA STRUCTURES & APPLICATIONS III-SEM

Module-5
1. Define the following with reference to Graph and give one examples for each: Directed graph
(Digraph), undirected graph, self-loop, multigraph, weighted graph, subgraph, connected graph,
disconnected graph, Path, Cycle, Loop, Degree, Out-Degree and In-Degree.
2. Describe the graph storage structures adjacency matrix and adjacency list with example. Give the
comparisons between them.
3. Explain with suitable examples the following operations on graph
a. Vertex insertion
b. Edge Addition
c. Vertex Deletion
d. Edge Deletion
4. Discuss Breadth-first traversal of a graph with suitable example and Program. Give the Breadth-first
traversal for the following graph starting from vertex A.

5. Explain Depth-first traversal of a graph with the help of an algorithm. Give the Depth-first traversal
for the following graph starting from vertex 1.

6. Write Warshall’s algorithm/ Program to find Transitive Closure of a Matrix/ Path Matrix.
Explain the same with suitable example. Find the transitive closure / Path Matrix for the graphs
given below:

(a) (b)

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 5

 DATA STRUCTURES & APPLICATIONS III-SEM

7. Write Floyd’s algorithm/ Program to solve All Pair Shortest Path Problem. Explain the same with
suitable example. Solve the same for the below graphs:

(a) (b)

Lab Programs-9 & 10

8. Design, Develop and Implement a Program in C for the following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using any traversal method
(DFS/BFS).
9. Given a set of N employee records with a set K of Keys (4-digit) which uniquely determine the records.
Assume that the records are available in the memory by a Hash Table (HT) of m memory locations with
L as the set of memory addresses (2-digit) of locations in HT. Let the keys in K and addresses in L are
Integers. Develop a Program in C that uses Hash function H: K →L as H (K) = K mod m (remainder
method), and implement hashing technique to map a given key K to the address space L. Resolve the
collision (if any) using linear probing.

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 6

DATA STRUCTURES & APPLICATIONS III-SEM

Lab Programs
1. Design, Develop and Implement a menu driven Program in C for the following operations on STACK of Integers
(Array Implementation of Stack with maximum size MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate Overflow and Underflow situations on Stack
d. Display the status of Stack
e. Exit
Support the program with appropriate functions for each of the above operations.
2. Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression. Program
should support for both parenthesized and free parenthesized expressions with the operators: +, -, *, /, %
(Remainder), ^ (Power) and alphanumeric operands.
3. Develop and Implement a Program in C for evaluation of Suffix expression with single digit operands and
operators: +, -, *, /, %, ^.
4. Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE
of integers (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations.
5. Design, Develop and Implement a menu driven Program in C for the following operations on Double Ended
QUEUE of integers (Array Implementation of Queue with maximum size MAX)
a. Perform Insertion / Deletion at front of QUEUE
b. Perform Insertion / Deletion at rear of QUEUE
c. Display the status of Circular QUEUE
d. Exit
6. Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List
(SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo.
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit
7. Design, Develop and Implement a menu driven Program in C for the following operations on Doubly Linked List
(DLL) of Employee Data with the fields: SSN, Name, Dept,Designation, Sal, Ph. No.
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue
f. Exit.
8. Develop a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers.
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit
9. Design, Develop and Implement a Program in C for the following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using any traversal method (DFS/BFS).
10. Given a set of N employee records with a set K of Keys (4-digit) which uniquely determine the records. Assume
that the records are available in the memory by a Hash Table (HT) of m memory locations with L as the set of
memory addresses (2-digit) of locations in HT. Let the keys in K and addresses in L are Integers. Develop a
Program in C that uses Hash function H: K →L as H (K) = K mod m (remainder method), and implement hashing
technique to map a given key K to the address space L. Resolve the collision (if any) using linear probing.

ABHISHEK K. L, Assistant Professor, Dept. of AI&ML, BMSIT&M, Bengaluru 7