DATA STRUCTURES LABORATORY (1BCSL306)

DATA STRUCTURES LABORATORY

Course Code 1BCSL306 
Scheme 2025
Type of Course PCCL 
Semester 3
Teaching Hours/Week (L:T:P) 0:0:2
CIE Marks 50
Total Hours of Pedagogy L:T:P:SL:TW 0:0:28:2:30 
SEE Marks 50
Credits 1 
Total Marks 100
Examination type (SEE) Practical 
Exam Hours 03

PART – A

FIXED SET OF EXPERIMENTS

1. Develop a Program in C for the following:

a. Define a record (structure) titled Book with the following fields: Book_ID, Title, Author, Price, Availability Status (Available/Issued).

b. Dynamically allocate memory to store the details of N books, where N is entered by the user.

c. Implement the following functions:

i. create() – To allocate memory and read the details of N books and store them in the allocated memory.

ii. display() – To display the details of all books available in the library.

iii. search() – To search for a book using Book ID and display the book details if found.

iv. issueBook() – To issue a book by updating its availability status and display an appropriate message.

v. returnBook() – To return an issued book by updating its availability status and display an appropriate message.

d. Build a menu-driven interface with the following options:

i. Add Book Records.

ii. Display all Book Records.

iii. Search Book by Book ID.

iv. Issue a Book.

v. Return a Book.

vi. Exit.

2. Develop a C program for processing sparse matrices using an appropriate data structure. The program shall accept suitable sparse matrix data, use an appropriate representation, and perform operations such as addition and transpose. Demonstrate the correctness of the solution using suitable test cases.

3. Develop a menu driven Program in C for the following operations on STACK of Integers (Array Implementation of Stack with maximum size MAX >15).

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 at any given point of time.

e. Exit.

 Support structured program with appropriate functions for each of the above operations.

4. Develop a program in C for simulating a Printer Queue using Queue data structure with the following operations:

a. Add a print job to the Printer Queue.

b. Process a print job from the Printer Queue (delete).

c. Display the number of print jobs currently waiting in the Queue.

d. Demonstrate Queue overflow and underflow conditions.

e. Exit.

5. Develop a Program in C for the following operations on Singly Circular Linked List (SCLL) with header nodes.

a. Read the polynomial: degree of the polynomial, terms (coefficient and power).

b. Represent the Polynomial in one variable based on degree.

c. Find the sum of two polynomials POLY1 and POLY2 and store the result in POLYSUM. 

Support the program with appropriate functions for each of the above operations.

6. Develop a Program in C for the following:

a. Create a Binary Tree (createTree) by inserting integer elements as keys entered by the user in level order.

b. Implement the following functions:

i. createTree() – Create a binary tree through key Insertions.

ii. preorder() – Display the elements using Preorder Traversal.

iii. inorder() – Display the elements using Inorder Traversal.

iv. postorder() – Display the elements using Postorder Traversal.

c. Develop a menu-driven interface with the following options:

i. Create Binary Tree.

ii. Display Preorder Traversal.

iii. Display Inorder Traversal.

iv. Display Postorder Traversal.

v. Exit.

PART – B

OPEN ENDED EXPERIMENTS

Open-ended experiments are a type of laboratory activity where the outcome is not predetermined and students are given the freedom to explore, design, and conduct the experiment based on the problem statements as per the concepts defined by the course coordinator. It encourages creativity, critical thinking, and inquiry-based learning.

1. A compiler design team needs a tool to convert arithmetic expressions from infix notation to postfix notation for efficient code generation. The expression contains alphanumeric operands, operators (+, -, *, /, %, ^), and brackets: (, ), {, }, [, ]. Develop a C program that supports the following::

a. Read an infix expression.

b. Validate the expression for correct bracket nesting and syntax.

c. Convert the valid infix expression to postfix notation.

Note: An input expression is valid if:

• Open brackets must be closed by the same type of brackets.

• Open brackets must be closed in the correct order.

• Every close bracket has a corresponding open bracket of the same type.

• Operators must have valid operands on both sides.

2. A University wants to manage student records effectively. Each student record contains USN, Name, Semester (1-8), and Department. Choose suitable data structure (Singly Linked List/ Doubly Linked List/Circular Linked Lists) and develop a menu-driven C program to manage these records with the following operations:

a. Create a list of student records (choose any insertion method: beginning /end).

b. View all student records.

c. Display student records for a given semester.

d. Insert the new student in the list after the given student’s name.

e. Delete a student record (based on USN or Name)

 Note: For CIE Test and SEE, any ONE option from (c) to (e) may be asked along with options (a) &

(b).

3. A manufacturing unit needs a system (repository) to manage machine parts used in assembly. Each part has:

• Part Number (alphanumeric, e.g., "P1001", "BOLT23")

• Part Name (e.g., "Bolt", "Wheel")

• Model Number (e.g., "M2024", "X100")

• Description (e.g., "Stainless steel ")

Develop a C program to implement the following three operations.

a. Add a new part to the inventory/repository

b. Remove an obsolete part (by part number or model number)

c. Search and display part details (by part number or model number)

All three operations happen frequently without any order. Choose suitable data structure that results in the best performance.

4. Develop a C program by selecting suitable data structure to manage hierarchical data/information having keys (numeric). The program shall provide appropriate operations such as insertion of information, traversal (display of all information), quick search for information based on the key. Demonstrate the solution using relevant test cases.

5. Develop a C program to store employee records having fields: emp-no, name, designation, department) using suitable Indexing mechanism. The program shall support record management operations such adding new employee, search for employee details based on emp-no, remove employee record based on emp-no, and display employee records based on department. Demonstrate the correctness of the implementation using appropriate test cases.

6. A transportation department wants to analyse connectivity between cities. Each city has a City Name and cities are interconnected (not necessarily all) with roads. Develop a menu-driven C program with the following operations:

a. Create a graph representing N cities with interconnecting roads.

b. Display the graph representation.

c. Print all cities reachable by road from a given city..

d. Check whether any two given cities are connected via road.

Suggested Learning Resources: 

Text books:

1. Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed, Fundamentals of Data Structures in C, 2nd Ed, Universities Press, 2023

2. Reema Thareja, Data Structures using C, 3rd Ed, Oxford press, 2023.

Reference books / Manuals:

1. A M Tenenbaum, Data Structures using C, PHI, 1989.

2. Seymour Lipschutz, Data Structures Schaum's Outlines, McGraw Hill, 2014.