GOVERNMENT OF KARNATAKA

DEPARTMENT OF COLLEGIATE AND TECHNICAL EDUCATION

GOVERNMENT ENGINEERING COLLEGE

(Affiliated to Visvesvaraya Technological University, Belagavi & Approved by AICTE, New Delhi)
Hyderabad Road, Yaramarus Camp,
RAICHUR – 584135
Ph. No:08532-200624,Fax:08532-251151,E-mail:ppl.gecr123@gmail.com

Department of Computer Science and Engineering

Data Structure
Laboratory Manual
[BCSL305]
III SEMESTER – B. E
Academic Year – 2023-2024

Student Name:

USN:

Section: Batch:
 PREFACE

Data Structure is a branch of Computer Science. The study of data structure allows us to understand
the organization of data and the management of the data flow in order to increase the efficiency of any
process or program. Data Structure is a particular way of storing and organizing data in the memory of
the computer so that these data can easily be retrieved and efficiently utilized in the future when
required. The data can be managed in various ways, like the logical or mathematical model for a
specific organization of data is known as a data structure.

The scope of a particular data model depends on two factors:

1. First, it must be loaded enough into the structure to reflect the definite correlation of the data
with a real-world object.
2. Second, the formation should be so straightforward that one can adapt to process the data
efficiently whenever necessary.

Some examples of Data Structures are Arrays, Linked Lists, Stack, Queue, Trees, etc. Data Structures
are widely used in almost every aspect of Computer Science, i.e., Compiler Design, Operating
Systems, Graphics, Artificial Intelligence, and many more.

Data Structures are the main part of many Computer Science Algorithms as they allow the
programmers to manage the data in an effective way. It plays a crucial role in improving the
performance of a program or software, as the main objective of the software is to store and retrieve the
user's data as fast as possible.
 Institute Vision

To be center of Excellence of Higher Learning and Research in Engineering Imparting Ethical,

Environmental and Economical aspects of the Society.

Institute Mission

Commitment in preparing Globally competent Engineers in response to Rapid Technological growth

through dynamic process of Teaching-Learning, Research and Professional Experiences for the
Betterment of the Community.

Department Vision

To become a Center of Excellence in the computer science and information technology discipline with
a strong research and teaching environment that produces highly qualified and motivated graduates.

Department Mission

 To provide quality education to meet the need of profession and society.

 Provide a learning ambience to enhance innovations, problem solving skills, leadership
qualities, team-spirit and ethical responsibilities.
 To develop human potential to its fullest extent so that intellectually capable and optimistic
leaders can emerge in a range of professions
 Program Outcomes (As Specified by NBA)
PO1 Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.

PO2 Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of mathematics,
natural sciences, and engineering sciences

PO3 Design/development of solutions: Design solutions for complex engineering problems and
design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
considerations

PO4 Conduct investigations of complex problems: Use research-based knowledge and research
methods including design of experiments, analysis and interpretation of data, and synthesis of
the information to provide valid conclusions.

PO5 Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering activities
with an understanding of the limitations.
PO6 The engineer and society: Apply reasoning informed by the contextual knowledge to assess
societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to
the professional engineering practice

PO7 Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and need
for sustainable development

PO8 Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of the engineering practice

PO9 Individual and team work: Function effectively as an individual, and as a member or leader in
diverse teams, and in multidisciplinary settings.
PO10 Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and write
effective reports and design documentation, make effective presentations, and give and receive
clear instructions.
PO11 Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member and
leader in a team, to manage projects and in multidisciplinary environments.

PO12 Life-long learning: Recognize the need for, and have the preparation and ability to engage in
independent and life-long learning in the broadest context of technological change.
 PEO (Program Educational Objectives)

 PEO1: Proficiency to work in multidisciplinary domains, technological advancements through

continuous learning process.

 PEO2: Graduate with moral and ethical values

 PEO3: Explore the research possibilities, innovative practices and entrepreneurship.

PSO (Program Specific Outcomes)

 Understand, analyse and realise the concepts in the field of analog and digital signal
processing, communication, networking and semiconductor technology by applying modern
design tools.
 Ability to enrich the design in electronics through optimization, better efficiency and
innovative ideas
 Enabling the graduates with excellent technical and soft skills, lifelong learning, leadership
qualities, ethics and societal responsibilities.
 Data Structure Laboratory
Course Code: BCSL305
Programming Experiments
1. Develop a Program in C for the following:
a) Declare a calendar as an array of 7 elements (A dynamically Created array) to represent 7
days of a week. Each Element of the array is a structure having three fields. The first field is
the name of the Day (A dynamically allocated String), The second field is the date of the Day
(A integer), the third field is the description of the activity for a particular day (A dynamically
allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data from
the keyboard and to print weeks activity details report on screen.

2. Develop a Program in C for the following operations on Strings.

a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with
REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR
Support the program with functions for each of the above operations. Don't use Built-in
functions

3. Develop 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 how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit
Support the program with appropriate functions for each of the above operations
4. Develop 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.
5. Develop a Program in C for the following Stack Applications a. Evaluation of Suffix
expression with single digit operands and operators: +, -, *, /, %, ^ b. Solving Tower of Hanoi
problem with n disks
 6. Develop a menu driven Program in C for the following operations on Circular QUEUE of
Characters (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
7. Develop a menu driven Program in C for the following operations on Singly Linked List
(SLL) of Student Data with the fields: USN, Name, Programme, 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
8. Develop 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, PhNo
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
9. Develop a Program in C for the following operationson Singly Circular Linked List (SCLL) with
header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in
POLYSUM(x,y,z) Support the program with appropriate functions for each of the above
operations.

10. 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
11. Develop 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 DFS/BFS method

12. Given a File of N employee records with a set K of Keys (4-digit) which uniquely determine the
records in file F. Assume that file F is maintained in 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.
1. Develop a Program in C for the following:
a) Declare a calendar as an array of 7 elements (A dynamically Created array) to represent 7 days of a
week. Each Element of the array is a structure having three fields. The first field is the name of the
Day (A dynamically allocated String), The second field is the date of the Day (A integer), the third
field is the description of the activity for a particular day (A dynamically allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data from the
keyboard and to print weeks activity details report on screen.

Theory:
In C, dynamically created arrays are arrays whose size is determined at runtime rather than being fixed
at compile-time. This is achieved using pointers and dynamic memory allocation functions such as
malloc, calloc, and realloc from the C standard library. Here are brief details on how to create
dynamically allocated arrays in C:

1. malloc (Memory Allocation): This function is used to allocate a block of memory of a specified size in
bytes. It returns a pointer to the first byte of the block. You can use this to create dynamic arrays.
int* dynamicArray;
int size = 10;
dynamicArray = (int*)malloc(size * sizeof(int));
2. calloc (Contiguous Allocation): This function allocates memory for an array of elements, each of a
specified size. It initializes all the elements to zero.
int* dynamicArray;
int size = 10;
dynamicArray = (int*)calloc(size, sizeof(int));
3. realloc (Reallocate Memory): This function is used when you want to change the size of an existing
dynamically allocated array. It can make the array larger or smaller as needed.
int* dynamicArray;
int newSize = 20;
dynamicArray = (int*)realloc(dynamicArray, newSize * sizeof(int));
4. Dynamically allocated memory should be explicitly released when it's no longer needed using the free
function to prevent memory leaks.
free(dynamicArray);
dynamicArray = NULL; // Set the pointer to NULL after freeing the memory.

Dynamically created arrays are useful when you need to work with data structures of variable sizes,
such as lists, queues, or when the size of the array is not known until runtime. However, managing
dynamic memory can be error-prone, so it's important to handle allocation and deallocation properly to
avoid memory leaks and other issues.
Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Day {
char *name;
int date;
char *activity;
};
void create(struct Day calendar[]) {
for (int i = 0; i < 7; i++) {
calendar[i].name = (char *)malloc(20 * sizeof(char));
calendar[i].activity = (char *)malloc(100 * sizeof(char));
calendar[i].date = 0;
}
}
void read(struct Day calendar[]) {
for (int i = 0; i < 7; i++) {
printf("Enter the name of day %d: ", i + 1);
scanf("%s", calendar[i].name);
printf("Enter the date of day %d: ", i + 1);
scanf("%d", &calendar[i].date);
printf("Enter the activity for day %d: ", i + 1);
getchar();
fgets(calendar[i].activity, 100, stdin);
calendar[i].activity[strcspn(calendar[i].activity, "\n")] = '\0'; // Remove the trailing newline
}
}
void display(struct Day calendar[]) {
printf("Weekly Activity Details:\n");
for (int i = 0; i < 7; i++) {
printf("Day %d: %s\n", i + 1, calendar[i].name);
printf("Date: %d\n", calendar[i].date);
printf("Activity: %s\n", calendar[i].activity);
printf("\n");
}
}
int main() {
struct Day calendar[7];
create(calendar);
read(calendar);
display(calendar);
for (int i = 0; i < 7; i++) {
free(calendar[i].name);
free(calendar[i].activity);
}
return 0;
}
Output:

Enter the name of day 1: Monday

Enter the date of day 1: 20
Enter the activity for day 1: study
Enter the name of day 2: Tuesday
Enter the date of day 2: 21
Enter the activity for day 2: work
Enter the name of day 3: Wednsday
Enter the date of day 3: 22
Enter the activity for day 3: Study
Enter the name of day 4: Thursday
Enter the date of day 4: 23
Enter the activity for day 4: Work
Enter the name of day 5: Friday
Enter the date of day 5: 24
Enter the activity for day 5: Stduy
Enter the name of day 6: Saturday
Enter the date of day 6: 25
Enter the activity for day 6: Work
Enter the name of day 7: Sunday
Enter the date of day 7: 26
Enter the activity for day 7: Study
Weekly Activity Details:
Day 1: Monday
Date: 20
Activity: study

Day 2: Tuesday
Date: 21
Activity: work

Day 3: Wednsday
Date: 22
Activity: Study

Day 4: Thursday
Date: 23
Activity: Work

Day 5: Friday
Date: 24
Activity: Stusy

Day 6: Saturday
Date: 25
Activity: Work
Day 7: Sunday
Date: 26
Activity: Study
2. Develop a Program in C for the following operations on Strings.
a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with REP if
PAT exists in STR. Report suitable messages in case PAT does not exist in STR Support the program
with functions for each of the above operations. Don't use Built-in functions.

Theory:
Pattern matching operations on strings involve searching for a specific pattern or substring within a
larger string. These operations are commonly used in text processing, data extraction, and searching
algorithms. Here's a brief overview of common pattern matching techniques:

Exact Match: This is the simplest form of pattern matching. It checks if a string exactly matches a
given pattern. For example, checking if a string "abc" matches the pattern "abc."

Substring Search: Substring search involves finding the first occurrence of a substring within a larger
string. Common methods for substring search include:

Brute Force: Iterate through the larger string and compare substrings of the same length with the
pattern. This method is simple but not very efficient.

KMP Algorithm (Knuth-Morris-Pratt): A more efficient algorithm that avoids unnecessary character
comparisons by precomputing a "failure" or "partial match" function.

Boyer-Moore Algorithm: Another efficient algorithm that uses a "bad character" heuristic and a
"good suffix" heuristic to skip characters during the search.

Regular Expressions: Regular expressions (regex) are a powerful tool for pattern matching. They
allow you to specify complex patterns using special symbols and operators. For example, you can use
regular expressions to search for email addresses, phone numbers, or specific text patterns in a
document.

Wildcard Matching: Wildcard characters like '' and '?' can be used to match patterns with variable
characters. For instance, "ap" would match "apple" and "apricot."
Program:
#include <stdio.h>
#include <string.h>

// Function to perform pattern matching and replace

void findAndReplace(char *mainStr, const char *pattern, const char *replacement)
{
int mainLen = strlen(mainStr);
int patternLen = strlen(pattern);
int replacementLen = strlen(replacement);
char result[1000];
int resultIndex = 0;
int i = 0;
while (i < mainLen) {
int j = 0;
int match = 1;
while (j < patternLen) {
if (mainStr[i + j] != pattern[j]) {
match = 0;
break;
}
j++;
}

if (match) {
for (int k = 0; k < replacementLen; k++) {
result[resultIndex] = replacement[k];
resultIndex++;
}
i += patternLen;
} else {
resultIndex++;
i++;
}
}
result[resultIndex] = '\0';
if (resultIndex == 0) {
printf("Pattern not found in the main string.\n");
} else {
printf("Result after replacement: %s\n", result);
}
}

void main()
{
char mainStr[1000];
char pattern[100];
char replacement[100];
printf("Enter the main string: ");
scanf("%s",mainStr);
 printf("Enter the pattern to search: ");
scanf("%s",pattern);
printf("Enter the replacement string: ");
scanf("%s",replacement);
findAndReplace(mainStr, pattern, replacement);

Output:
Enter the main string: aabccc
Enter the pattern to search: abc
Enter the replacement string: ddd
Result after replacement: adddcc
3. Develop 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 how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack f. Exit Support the program with appropriate functions for each of the
above operations

Theory:
Stack operations refer to the basic operations that can be performed on a stack data structure. A stack
is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning that the last
element added to the stack is the first one to be removed. Stack operations typically include the
following:

Push: The push operation is used to add an element to the top of the stack. This operation increases
the size of the stack by one and places the new element at the top.

Pop: The pop operation removes the top element from the stack. After this operation, the size of the
stack is reduced by one, and the removed element is returned or discarded.

Peek (or Top): The peek operation allows you to inspect the element at the top of the stack without
removing it. It provides access to the top element's value.

IsEmpty: This operation checks whether the stack is empty or not. It returns a Boolean value
indicating whether there are any elements in the stack.

IsFull (for fixed-size stacks): In some implementations of a stack with a fixed size, there may be an "is
full" operation to check if the stack has reached its maximum capacity.

Stacks are often used for managing function calls and local variables in programming (the call stack),
parsing expressions, undo functionality in applications, and solving various algorithmic problems. The
simplicity of these operations and the LIFO behavior make stacks a fundamental data structure in
computer science and software development.
Program:
#include<stdio.h>
#include<stdlib.h>
#define MAX 4
int stack[MAX], item; int ch, top = -1, count = 0, status = 0;

void push(int stack[], int item)

{
if (top == (MAX-1))
printf("\n\nStack is Overflow");
else {
stack[++top] = item;
status++;
}
}

int pop(int stack[])

{
int ret;
if(top == -1)
printf("\n\nStack is Underflow");
else {
ret = stack[top--];
status--;
printf("\nPopped element is %d", ret);
}
return ret;
}
void palindrome(int stack[])
{
int i, temp;
temp = status;
for(i=0; i<temp; i++) {
if(stack[i] == pop(stack))
count++;
}
if(temp==count)
printf("\nStack contents are Palindrome");
else
printf("\nStack contents are not palindrome");
}
void display(int stack[])
{
int i;
printf("\nThe stack contents are:\n");
if(top == -1)
printf("\nStack is Empty");
else {
for(i=top; i>=0; i--)
printf("%d\n", stack[i]);
printf("\n");
}
}
void main()
{
for(;;) {
printf("\n\n----MAIN MENU----\n");
printf("\n1. PUSH");
printf("\n2. POP ");
printf("\n3. PALINDROME ");
printf("\n4. DISPLAY ");
printf("\n5. Exit");
printf("\nEnter Your Choice: ");
scanf("%d", &ch);
switch(ch) {
case 1:
printf("\nEnter an element to be pushed: ");
scanf("%d", &item);
push(stack, item);
break;
case 2:
item=pop(stack);
break;
case 3:
palindrome(stack);
break;
case 4:
display(stack);
break;
default:
exit(0);
}
}

}
Output:
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 1
Enter an element to be pushed: 10
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 4
The stack contents are:
10
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 1
Enter an element to be pushed: 20
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 4
The stack contents are:
20
10
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 1
Enter an element to be pushed: 30
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 4
The stack contents are:
30
20
10
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 2
Popped element is 30
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 3
Popped element is 20
Popped element is 10
Stack contents are not palindrome
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 2
Stack is Underflow
----MAIN MENU----
1. PUSH
2. POP
3. PALINDROME
4. DISPLAY
5. Exit
Enter Your Choice: 5
4. Develop 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

Theory:
Converting an infix expression to a postfix expression using stacks is a common algorithm used in
computer science, particularly in compilers and calculators. The postfix notation (also known as
Reverse Polish Notation, RPN) eliminates the need for parentheses and is easier to evaluate
algorithmically. The algorithm to convert an infix expression to postfix expression typically follows
these steps:

1. Create an empty stack to hold operators and an output (postfix) queue to store the postfix expression.
2. Scan the infix expression from left to right, one character at a time.
 For each character, do the following:
 If it is an operand (a digit or a variable), add it to the output queue.
 If it is an open parenthesis '(', push it onto the stack.
 If it is a close parenthesis ')', pop operators from the stack and add them to the output queue until
an open parenthesis is encountered on the stack. Pop and discard the open parenthesis.
 If it is an operator, then:
 While the stack is not empty and the operator at the top of the stack has higher or equal
precedence compared to the current operator, pop the operator from the stack and add it to the
output queue.
 Push the current operator onto the stack.
3. After scanning the entire expression, pop any remaining operators from the stack and add them to the
output queue.
4. The elements in the output queue now form the postfix expression.

Here's an example to illustrate the process:

Infix Expression: 3 + (4 * 5) / 6
Start with an empty stack and an empty output queue.
Scan the expression from left to right.
Output Queue: 3
Stack: +
Output Queue: 3 4
Stack: + (
Output Queue: 3 4 5
Stack: + (*
Output Queue: 3 4 5 *
Stack: +
Output Queue: 3 4 5 * 6
Stack: + /
Pop the remaining operators from the stack and add them to the output queue.
Output Queue: 3 4 5 * 6 / +
The resulting postfix expression is 3 4 5 * 6 / +, which is much easier to evaluate using a stack-based
algorithm. You can now use a stack to evaluate the postfix expression and obtain the result.
Program:
#include<stdio.h>
#include<string.h>

int F(char symbol)

{
switch(symbol) {
case '+':
case '-':
return 2;
case '*':
case '/':
return 4;
case '^':
case '$':
return 5;
case '(':
return 0;
case '#':
return -1;
default:
return 8;
}
}
int G(char symbol)
{
switch(symbol) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 3;
case '^':
case '$':
return 6;
case '(':
return 9;
case ')':
return 0;
default:
return 7;
}
}
 void infix_postfix(char infix[], char postfix[])
{
int top, j, i;
char s[30], symbol;
top = -1;
s[++top] = '#';
j = 0;
for(i=0; i < strlen(infix); i++) {
symbol = infix[i];
while(F(s[top]) > G(symbol)) {
postfix[j] = s[top--];
j++;
}
if(F(s[top]) != G(symbol))
s[++top] = symbol;
else
top--;
}
while(s[top] != '#') {
postfix[j++] = s[top--];
}
postfix[j] = '\0';
}
void main()
{
char infix[20], postfix[20];
printf("\nEnter a valid infix expression\n");
scanf(“%s”,infix);
infix_postfix(infix,postfix);
printf("\nThe infix expression is:\n");
printf ("%s",infix);
printf("\nThe postfix expression is:\n");
printf ("%s",postfix);
}

Output:
5. Develop a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks

Theory:

Evaluating a postfix (suffix) expression using stacks is a straightforward and efficient process. Postfix
notation (also known as Reverse Polish Notation, RPN) is designed to eliminate the need for
parentheses and make expression evaluation more straightforward. Here's a brief overview of how to
evaluate a postfix expression using a stack:
1. Create an empty stack to hold operands.
2. Scan the postfix expression from left to right.
3. For each element (operand or operator), do the following:
4. If it's an operand (a number or variable), push it onto the stack.
5. If it's an operator, pop the required number of operands from the stack (typically two for binary
operators and one for unary operators), perform the operation, and push the result back onto the stack.
6. Continue this process until you have scanned the entire postfix expression.
7. After scanning the entire expression, the result should be the only element left on the stack

Here's an example to illustrate the process:

Postfix Expression: 3 4 5 * 6 / +

1. Start with an empty stack.

2. Scan the expression from left to right.
3. Operand 3: Push it onto the stack.
Stack: 3
4. Operand 4: Push it onto the stack.
Stack: 3 4

5. Operand 5: Push it onto the stack.

Stack: 3 4 5
6. Operator *: Pop the top two operands (4 and 5), perform the operation (4 * 5), and push the
result (20) back onto the stack.
Stack: 3 20
7. Operand 6: Push it onto the stack.
Stack: 3 20 6
8. Operator /: Pop the top two operands (20 and 6), perform the operation (20 / 6), and push the
result (3.33...) back onto the stack.
Stack: 3 3.33...
9. Operator +: Pop the top two operands (3 and 3.33...), perform the operation (3 + 3.33...), and
push the result (6.33...) back onto the stack.
Stack: 6.33...
10. The result is the only element left on the stack, which is 6.33
Program:
#include<stdio.h>
#include<math.h>
#include<string.h>
double compute(char symbol, double op1, double op2)
{
switch(symbol) {
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
case '$':
case '^': return pow(op1,op2);
default: return 0;
}
}
void main()
{
double s[20], res, op1, op2;
int top, i;
char postfix[20], symbol;
printf("\nEnter the postfix expression:\n");
scanf(“%s”, postfix);
top=-1;
for(i=0; i<strlen(postfix); i++) {
symbol = postfix[i];
if(isdigit(symbol))
s[++top] = symbol - '0';
else {
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1, op2);
s[++top] = res;
}
}
res = s[top--];
printf("\nThe result is : %f\n", res);
}
Output:
5b. Solving Tower of Hanoi problem with n disks.

Theory:
The Tower of Hanoi is a classic problem in computer science and mathematics that involves a
set of three rods and a number of disks of different sizes, which can slide onto any rod. The
puzzle starts with the disks in a neat stack in ascending order of size on one rod, the source rod,
with the smallest disk at the top.

The objective of the puzzle is to move the entire stack to another rod, obeying the following
rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a smaller disk.
The Tower of Hanoi puzzle has a recursive solution that can be defined as follows:

Algorithm for Solving the Tower of Hanoi:

1. If there's only one disk (base case), move it from the source rod to the target rod
directly.
2. For a stack of more than one disk, follow these steps:
 Move the top n-1 disks from the source rod to the auxiliary rod using the
target rod as the auxiliary rod.
 Move the largest (nth) disk from the source rod to the target rod.
 Move the n-1 disks from the auxiliary rod to the target rod using the source
rod as the auxiliary rod.
Here's a step-by-step example for solving the Tower of Hanoi with three disks:
1. Move Disk 1 from Source to Target.
2. Move Disk 2 from Source to Auxiliary.
3. Move Disk 1 from Target to Auxiliary.
4. Move Disk 3 from Source to Target.
5. Move Disk 1 from Auxiliary to Source.
6. Move Disk 2 from Auxiliary to Target.
7. Move Disk 1 from Source to Target.
Following these steps will successfully move the entire stack from the source rod to the target
rod. The number of moves required to solve the Tower of Hanoi puzzle with n disks is 2^n - 1,
making it an interesting problem for demonstrating the power of recursion in solving complex
problems.
Program:
#include<stdio.h>
void tower(int n, int source, int temp,int destination)
{
if(n == 0)
return;
tower(n-1, source, destination, temp);
printf("\nMove disc %d from %c to %c", n, source, destination);
tower(n-1, temp, source, destination);
}
void main()
{
int n;
printf("\nEnter the number of discs: \n");
scanf("%d", &n);
tower(n, 'A', 'B', 'C');
printf("\n\nTotal Number of moves are: %d", (int)pow(2,n)-1);
}

Output:
6. 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 and Deletion at End of SLL
d. Perform Insertion and Deletion at Front of SLL
e. Demonstrate how this SLL can be used as STACK and QUEUE
f. Exit

Theory:
Queue operations are the fundamental operations that can be performed on a queue data structure. A
queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning that the
first element added to the queue is the first one to be removed. Here are the basic queue operations:

Enqueue (Insertion): This operation is used to add (enqueue) an element at the rear (end) of the
queue. It increases the size of the queue by one and places the new element at the rear.

Dequeue (Deletion): The dequeue operation removes (dequeues) the element at the front of the queue.
After this operation, the size of the queue is reduced by one, and the element at the front is removed.

Front (or Peek): The front operation allows you to examine the element at the front of the queue
without removing it. It provides access to the value of the front element.

IsEmpty: This operation checks whether the queue is empty or not. It returns a Boolean value
indicating whether there are any elements in the queue.

IsFull (for fixed-size queues): In some implementations of a queue with a fixed size, there may be an
"is full" operation to check if the queue has reached its maximum capacity.

Queue operations are used in various applications, such as scheduling processes in operating systems
(process queues), managing tasks in a printer's print queue, and in data structures like the breadth-first
search (BFS) algorithm for graphs. Queues are a fundamental data structure for managing elements in
a sequential manner and are widely used in computer science and software development.

Program:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
int usn;
char name[20];
char branch[20];
int semester;
char phone[20];
} STUDENT;
struct node {
int usn;
 char name[20];
char branch[20];
int semester;
char phone[20];
struct node *next;
};
typedef struct node*NODE;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL) {
printf("out of memory\n");
exit(0);
}
return x;
}
NODE insert_front(STUDENT item,NODE first)
{
NODE temp;
temp=getnode();
temp->usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;
strcpy(temp->phone,item.phone);
temp->next=NULL;
if(first==NULL)
return temp;
temp->next=first;
return temp;
}
NODE insert_rear(STUDENT item,NODE first)
{
NODE temp,cur;
temp=getnode();
temp->usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;
strcpy(temp->phone,item.phone);
temp->next=NULL;
if(first==NULL)
return temp;
 cur=first;
while(cur->next!=NULL) {
cur=cur->next;
}
cur->next=temp;
return first;
}
NODE delete_front(NODE first)
{
NODE temp;
if(first==NULL) {
printf("student list is empty\n");
return NULL;
}
temp=first;
temp=temp->next;
printf("delete student record:USN=%d\n",first->usn);
free(first);
return temp;
}
NODE delete_rear(NODE first)
{
NODE cur,prev;
if(first==NULL) {
printf("student list is empty cannot delete\n");
return first;
}
if(first->next==NULL) {
printf("delete student record:USN=%d\n",first->usn);
free(first);
return NULL;
}
prev=NULL;
cur=first;
while(cur->next!=NULL) {
prev=cur;
cur=cur->next;
}
printf("delete student record:USN=%d\n",cur->usn);
free(cur);
prev->next=NULL;
return first;
}
void display(NODE first)
{
NODE cur;
int count=0;
if(first==NULL) {
printf("student list is empty\n");
return;
}
cur=first;
while(cur!=NULL) {
printf("%d\t%s\t%s\t%d\t%s\t\n",cur->usn,cur->name,cur->branch,cur-
>semester,cur-
>phone);
cur=cur->next;
count++;
}
printf("number of students=%d\n",count);
}
void main()
{
NODE first;
int choice;
STUDENT item;
first=NULL;
for(;;) {

printf("1.insert_front\n2.insert_rear\n3.delete_front\n4.delete_rear\n5.display\n6.exit\n"
);
printf("Enter the choice\n");
scanf("%d",&choice);
switch(choice) {
case 1:
printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);
first=insert_front(item,first);
break;
case 2:
 printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);
first=insert_rear(item,first);
break;
case 3:
first=delete_front(first);
break;
case 4:
first=delete_rear(first);
break;
case 5:
display(first);
break;
default:
exit(0);
}
}
}
Output:
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 1
Enter the character item to be inserted: A
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 1
Enter the character item to be inserted: B
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 3
Contents of Queue is:
AB
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 1
Enter the character item to be inserted: C
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 3
Contents of Queue is:
ABC
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 2
Deleted item is: A
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 2
Deleted item is: B
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 2
Deleted item is: C
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 2
Queue is Empty
1. Insert
2. Delete
3. Display
4. Exit
Enter the choice: 4
7. Develop a menu driven Program in C for the following operations on Singly Linked List (SLL) of
Student Data with the fields: USN, Name, Programme, 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

Theory:
A singly linked list is a fundamental data structure in computer science and consists of a sequence of
elements, called nodes, where each node contains both data and a reference (or link) to the next node
in the sequence. The last node typically has a reference to NULL or is considered the end of the list.
Singly linked lists have several characteristics and operations:

Characteristics of a Singly Linked List:

 Nodes: Each node in a singly linked list has two components:
 Data: The value or information stored in the node.
 Next Pointer/Link: A reference to the next node in the sequence.
 Head: The first node of the list is called the head. It serves as the starting point for traversing
the list.
 Tail: The last node in the list. Its "next" reference points to NULL, indicating the end of the
list.
 Traversal: To traverse a singly linked list, you start at the head and follow the "next" pointers
from node to node until you reach the end (where the "next" pointer is NULL).
Common Operations on a Singly Linked List:
Insertion:
 Insert at the Beginning: Add a new node at the beginning of the list. Update the "next" pointer
of the new node to point to the current head, and update the head to point to the new node.
 Insert at the End: Add a new node at the end of the list. Update the "next" pointer of the
current tail to point to the new node and then update the tail to point to the new node.
Deletion: To delete a node from a singly linked list, update the "next" pointer of the preceding node to
skip the node to be deleted.
Search: To find a specific element in the list, you start at the head and traverse the list while
comparing the data of each node with the target value.
Traversal: You can traverse the list by starting at the head and following the "next" pointers until you
reach the end of the list. This is used to perform operations on all elements in the list.
Length: You can find the length of the list by traversing it and counting the number of nodes
encountered.
Reversal: To reverse a singly linked list, you need to change the direction of the "next" pointers. This
operation can be done iteratively or recursively.
Singly linked lists are efficient for insertions and deletions at the beginning of the list (O(1) time
complexity) but less efficient for random access (O(n) time complexity). They are commonly used in
various data structures, such as stacks and queues, and can serve as building blocks for more complex
data structures like linked lists with additional features or as part of graph representations.
Program:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
int usn;
char name[20];
char branch[20];
int semester;
char phone[20];
} STUDENT;
struct node {
int usn;
char name[20];
char branch[20];
int semester;
char phone[20];
struct node *next;
};
typedef struct node*NODE;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL) {
printf("out of memory\n");
exit(0);
}
return x;
}
NODE insert_front(STUDENT item,NODE first)
{
NODE temp;
temp=getnode();
temp->usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;
strcpy(temp->phone,item.phone);
temp->next=NULL;
if(first==NULL)
return temp;
temp->next=first;
return temp;
}
NODE insert_rear(STUDENT item,NODE first)
{
NODE temp,cur;
temp=getnode();
temp->usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;
strcpy(temp->phone,item.phone);
temp->next=NULL;
if(first==NULL)
return temp;
cur=first;
while(cur->next!=NULL) {
cur=cur->next;
}
cur->next=temp;
return first;
}
NODE delete_front(NODE first)
{
NODE temp;
if(first==NULL) {
printf("student list is empty\n");
return NULL;
}
temp=first;
temp=temp->next;
printf("delete student record:USN=%d\n",first->usn);
free(first);
return temp;
}
NODE delete_rear(NODE first)
{
NODE cur,prev;
if(first==NULL) {
printf("student list is empty cannot delete\n");
return first;
}
if(first->next==NULL) {
printf("delete student record:USN=%d\n",first->usn);
free(first);
return NULL;
 }
prev=NULL;
cur=first;
while(cur->next!=NULL) {
prev=cur;
cur=cur->next;
}
printf("delete student record:USN=%d\n",cur->usn);
free(cur);
prev->next=NULL;
return first;
}
void display(NODE first)
{
NODE cur;
int count=0;
if(first==NULL) {
printf("student list is empty\n");
return;
}
cur=first;
while(cur!=NULL) {
printf("%d\t%s\t%s\t%d\t%s\t\n",cur->usn,cur->name,cur->branch,cur->semester,cur-
>phone);
cur=cur->next;
count++;
}
printf("number of students=%d\n",count);
}
void main()
{
NODE first;
int choice;
STUDENT item;
first=NULL;
for(;;) {
printf("1.insert_front\n2.insert_rear\n3.delete_front\n4.delete_rear\n5.display\n6.exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);
switch(choice) {
case 1:
printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
 scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);
first=insert_front(item,first);
break;
case 2:
printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);
first=insert_rear(item,first);
break;
case 3:
first=delete_front(first);
break;
case 4:
first=delete_rear(first);
break;
case 5:
display(first);
break;
default:
exit(0);
}
}
}

Output:
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
1
USN :
10
name :
John
branch :
CSE
semester:
3
phone :
98765980
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
5
10 John CSE 3 98765980
numbrt of students=1
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
2
USN :
12
name :
David
branch :
ECE
semester:
5
phone :
98098873
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
5
10 John CSE 3 98765980
12 David ECE 5 98098873
number of students=2
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
3
delete student record:USN=10
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice
5
12 David ECE 5 98098873
number of students=1
1.insert_front
2.insert_rear
3.delete_front
4.delete_rear
5.display
6.exit
Enter the choice 6
8. Develop 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, PhNo
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

Theory:
A doubly linked list is a linear data structure that extends the concept of a singly linked list. In a
doubly linked list, each node contains two references (or links): one to the next node in the sequence
(as in a singly linked list), and one to the previous node. This additional backward link allows for more
flexible traversal and operations, as it provides bidirectional access to elements in the list. Here are the
key characteristics and operations associated with a doubly linked list:

Characteristics of a Doubly Linked List:

 Nodes: Each node in a doubly linked list has three components:
 Data: The value or information stored in the node.
 Next Pointer/Link: A reference to the next node in the sequence.
 Previous Pointer/Link: A reference to the previous node in the sequence.
 Head and Tail: Similar to a singly linked list, a doubly linked list has a head (the first node)
and a tail (the last node). The head's previous pointer is NULL, and the tail's next pointer is NULL.
Traversal: You can traverse a doubly linked list both forward and backward. This makes it easier to
perform operations in both directions.

Common Operations on a Doubly Linked List:

Insertion:
 Insert at the Beginning: Add a new node at the beginning of the list. Update the "next"
pointer of the new node to point to the current head, update the "previous" pointer of the current head
to point to the new node, and update the head to point to the new node.
 Insert at the End: Add a new node at the end of the list. Update the "next" pointer of the
current tail to point to the new node, update the "previous" pointer of the new node to point to the
current tail, and update the tail to point to the new node.

Deletion: To delete a node from a doubly linked list, update the "next" pointer of the preceding node
to skip the node to be deleted and update the "previous" pointer of the following node to skip the node.
Search: You can search for an element in the list by starting at either the head or the tail and traversing
the list in the desired direction while comparing the data of each node with the target value.

Traversal: You can traverse the list in both directions, either starting from the head and following the
"next" pointers or starting from the tail and following the "previous" pointers.
Length: To find the length of the list, you can traverse it while counting the number of nodes
encountered.
Reversal: Reversing a doubly linked list is relatively straightforward. You swap the "next" and
"previous" pointers for each node in the list.

Doubly linked lists offer more flexibility for certain operations like reverse traversal and bidirectional
navigation, but they come at the cost of increased memory usage due to the additional "previous"
pointers. They are commonly used in various applications and data structures, such as text editors,
music playlists, and certain types of caches, where elements need to be efficiently traversed in both
directions.

Program:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node {
int ssn;
char name[20],department[20],designation[20],phone[20];
float salary;
struct node *llink;
struct node *rlink;
};
typedef struct node *NODE;
struct node *item;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL) {
printf("out of memory\n");
exit(0);
}
return x;
}
void read()
{
item=getnode();
printf("ssn:");
scanf("%d",&item->ssn);
printf("name:");
scanf("%s",item->name);
printf("department:");
scanf("%s",item->department);
printf("designation:");
 scanf("%s",item->designation);
printf("salary:");
scanf("%f",&item->salary);
printf("phone:");
scanf("%s",item->phone);
item->llink=item->rlink=NULL;
}
NODE insert_front(NODE first)
{
read();
if(first==NULL) return item;
item->rlink=first;
first->llink=item;
return item;
}
NODE insert_rear(NODE first)
{
NODE cur;
read();
if(first==NULL) return item;
cur=first;
while(cur->rlink!=NULL) {
cur=cur->rlink;
}
cur->rlink=item;
item->llink=cur;
return first;
}
NODE delete_front(NODE first)
{
NODE second;
if(first==NULL) {
printf("employee list is empty\n");
return NULL;
}
if(first->rlink==NULL) {
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
return NULL;
}
second=first->rlink;
second->llink=NULL;
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
 return second;
}
NODE delete_rear(NODE first)
{
NODE cur,prev;
if(first==NULL) {
printf("list is empty cannot delete\n");
return first;
}
if(first->rlink==NULL) {
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
return NULL;
}
prev=NULL;
cur=first;
while(cur->rlink!=NULL) {
prev=cur;
cur=cur->rlink;
}
printf("employee details deleted:ssn:=%d\n",cur->ssn);
free(cur);
prev->rlink=NULL;
return first;
}
void display(NODE first)
{
NODE temp,cur;
int count=0;
if(first==NULL) {
printf("employee list is empty\n");
return;
}
cur=first;
while(cur!=NULL) {
printf("%d %f %s %s %s %s\n",cur->ssn,cur->salary,cur->name,cur->department,
cur->designation,cur->phone);
cur=cur->rlink;
count++;
}
printf("number of employees=%d\n",count);
}
void main()
{
 NODE first;
int choice;
first=NULL;
for(;;) {
printf("1:insert_front\n2:insert_rear\n");
printf("3:delete_front\n4:delete_rear\n");
printf("5:display\n6:exit\n");
printf("enter the choice\n");
scanf("%d",&choice);
switch(choice) {
case 1:
first=insert_front(first);
break;
case 2:
first=insert_rear(first);
break;
case 3:
first=delete_front(first);
break;
case 4:
first=delete_rear(first);
break;
case 5:
display(first);
break;
default:
exit(0);
}
}
}

Output:
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
1
ssn:100
name:John
department:Sales
designation:Manager
salary:10000
phone:9876530
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
2
ssn:200
name:Smith
department:HR
designation:Manager
salary:2000
phone:987543
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
5
100 10000.000000 John Sales Manager 9876530
200 2000.000000 Smith HR Manager 987543
number of employees=2
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
1
ssn:50
name:Mary
department:Reception
designation:Receptionist
salary:1000
phone:9847564
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
5
50 1000.000000 Mary Reception Receptionist 9847564
100 10000.000000 John Sales Manager 9876530
200 2000.000000 Smith HR Manager 987543
number of employees=3
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
3
employee details deleted:ssn:=50
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
4
employee details deleted:ssn:=200
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice
5
100 10000.000000 John Sales Manager 9876530
number of employees=1
1:insert_front
2:insert_rear
3:delete_front
4:delete_rear
5:display
6:exit
enter the choice 6
9. Develop a Program in C for the following operations on Singly Circular Linked List (SCLL)
with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result
in POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations
Theory:
A singly circular linked list is a variation of a singly linked list where the last node's "next" pointer
points back to the first node, forming a closed loop. This type of list is often used in situations where
elements need to be traversed in a circular manner.

To add two polynomials using a singly circular linked list, you can create a circular linked list to
represent each polynomial, where each node in the list contains a term with a coefficient and an
exponent. Then, you can traverse both lists and add corresponding terms based on their exponents.
Here's a step-by-step process to add two polynomials using a singly circular linked list:

1. Create two circular linked lists to represent the two polynomials, say poly1 and poly2.
Initialize pointers to the current node in both lists (current1 and current2) to the head nodes.
2. Initialize a new circular linked list to store the result, say resultPoly. Initialize a pointer to the
current node in the result list (currentResult) to the head node.
3. While both current1 and current2 are not at the end of their respective lists (you can determine
this when the "next" pointer of current1 or current2 points to the head node):

a. If the exponent of the term at current1 is equal to the exponent of the term at current2, add the
coefficients of both terms, create a new term with the sum, and insert it into resultPoly. Move both
current1 and current2 to the next node in their respective lists.
b. If the exponent of the term at current1 is greater than the exponent of the term at current2, insert the
term from poly1 into resultPoly and move current1 to the next node.
c. If the exponent of the term at current2 is greater than the exponent of the term at current1, insert the
term from poly2 into resultPoly and move current2 to the next node.

4. Repeat the above steps until you have processed all terms in both polynomials.
5. After processing the entire lists, you may have some remaining terms in either poly1 or poly2.
Insert these remaining terms into resultPoly.
6. The resultPoly will now contain the sum of the two polynomials. You can traverse it to print or
display the result.

It's important to note that you need to ensure that the linked lists are circular, meaning that the "next"
pointer of the last node points back to the head node. This allows you to loop through the lists
repeatedly if necessary.

This approach efficiently adds two polynomials by comparing the exponents of corresponding terms
and adding their coefficients, taking advantage of the linked list structure to represent the terms.
Program:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node
{
int coef;
int x,y,z;
struct node *link;
};
typedef struct node *NODE;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
return x;
}
NODE readpoly()
{
NODE temp,head,cur;
char ch;
head=getnode();
head->coef=-1;
head->x=-1;
head->y=-1;
head->z=-1;
head->link=head;
do
{
temp=getnode();
printf("\nEnter the coefficient and exponent in decreasing order\n");
scanf("%d%d%d%d",&temp->coef,&temp->x,&temp->y,&temp->z );
cur=head;
while(cur->link!=head)
cur=cur->link;
cur->link=temp;
temp->link=head;
printf("\nDo you want to enter more coefficients(y/n)");
getchar();
scanf("%c",&ch);
} while(ch =='y' || ch == 'Y');
return head;
}
int compare(NODE a,NODE b)
{
if(a->x > b->x)
return 1;
else if(a->x < b->x)
return -1;
else if(a->y > b->y)
return 1;
else if(a->y < b->y)
return -1;
else if(a->z > b->z)
return 1;
else if(a->z < b->z)
return -1;
return 0;
}
void attach(int cf,int x1,int y1, int z1, NODE *ptr)
{
NODE temp;
temp=getnode();
temp->coef=cf;
temp->x=x1;
temp->y=y1;
temp->z=z1;
(*ptr)->link=temp;
*ptr=temp;
}
NODE addpoly(NODE a,NODE b)
{
NODE starta,c ,lastc;
int sum,done=0;
starta=a;
a=a->link;
b=b->link;
c=getnode(); // create list C to store A+B
c->coef=-1;
c->x=-1;
c->y=-1;
c->z=-1;
lastc=c;
do{
switch(compare(a,b))
{
case -1: attach(b->coef,b->x,b->y,b->z,&lastc);
b=b->link;
 break;
case 0: if(starta==a)
done=1;
else{
sum=a->coef+b->coef;
if(sum)
attach(sum,a->x, a->y,a->z,&lastc);
a=a->link;b=b->link;
}
break;
case 1: if(starta==a)
done=1;
attach(a->coef,a->x, a->y,a->z,&lastc);
a=a->link;
break;
}
}while(!done);
lastc->link=c;
return c;
}
void print(NODE ptr)
{
NODE cur;
cur=ptr->link;
while(cur!=ptr)
{
printf("%d*x^%d*y^%d*z^%d",cur->coef,cur->x, cur->y, cur->z);
cur=cur->link;
if (cur!=ptr)
printf(" + ");
}
}
void evaluate(NODE ptr)
{
int res=0;
int x,y,z, ex,ey,ez,cof;
NODE cur;
printf("\nEnter the values of x, y,z");
scanf("%d", &x);
scanf("%d", &y);
scanf("%d", &z);
cur=ptr->link;
while(cur!=ptr)
{
ex=cur->x;
ey=cur->y;
ez=cur->z;
cof=cur->coef;
res+=cof*pow(x,ex)*pow(y,ey)*pow(z,ez);
cur=cur->link;
}
printf("\nresult: %d",res);
}
void main(void)
{
int i, ch;
NODE a=NULL,b,c;
while(1)
{
printf("\n1: Represent first polynomial A");
printf("\n2: Represent Second polynomial B");
printf("\n3: Display the polynomial A");
printf("\n4: Display the polynomial B");
printf("\n5: Add A & B polynomials");
printf("\n6: Evaluate polynomial C");
printf("\n7: Exit");
printf("\n Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the elements of the polynomial A");
a=readpoly();
break;
case 2:printf("\nEnter the elements of the polynomial B");
b= readpoly();
break;
case 3: print(a);
break;
case 4:print(b);
break;
case 5: c=addpoly(a,b);
printf("\nThe sum of two polynomials is: ");
print(c);
printf("\n");
break;
case 6:evaluate(c);
break;
case 7: return;
default: printf("\nInvalid choice!\n");
}
}
}
Output:
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 1
Enter the elements of the polynomial A
Enter the coefficient and exponent in decreasing order
2222
Do you want to enter more coefficients(y/n)y
Enter the coefficient and exponent in decreasing order
3111
Do you want to enter more coefficients(y/n)y
Enter the coefficient and exponent in decreasing order
5000
Do you want to enter more coefficients(y/n)n
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 3
2*x^2*y^2*z^2 + 3*x^1*y^1*z^1 + 5*x^0*y^0*z^0
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 2
Enter the elements of the polynomial B
Enter the coefficient and exponent in decreasing order
3222
Do you want to enter more coefficients(y/n)y
Enter the coefficient and exponent in decreasing order
6000
Do you want to enter more coefficients(y/n)n
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 4
3*x^2*y^2*z^2 + 6*x^0*y^0*z^0
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 5
The sum of two polynomials is: 5*x^2*y^2*z^2 + 3*x^1*y^1*z^1 + 11*x^0*y^0*z^0
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 6
Enter the values of x, y,z 2 3 4
result: 2963
1: Represent first polynomial A
2: Represent Second polynomial B
3: Display the polynomial A
4: Display the polynomial B
5: Add A & B polynomials
6: Evaluate polynomial C
7: Exit
Enter your choice: 7
10. 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

Theory:
A Binary Search Tree (BST) is a binary tree data structure that follows a specific order, or property,
making it efficient for searching, insertion, and deletion operations. In a BST, each node has at most
two children: a left child and a right child. The following properties define a binary search tree:

Value Ordering: For every node in the tree:

 All nodes in its left subtree have values less than the node's value.
 All nodes in its right subtree have values greater than the node's value.
This ordering principle makes it easy to search for, insert, and delete elements within the tree.

Common Operations and Characteristics of a Binary Search Tree:

Search: Searching for an element in a BST is efficient. You start at the root node and compare the
target value with the current node's value. If the target is less than the current node, you move to the
left child; if it's greater, you move to the right child. This process continues recursively until you find
the target or reach a null node.

Insertion: Inserting an element into a BST is also efficient. You follow the same process as searching
but insert the new node in place when you reach a null child position.

Deletion: Deleting an element from a BST can be more complex. You must consider different cases,
such as:
 Deleting a leaf node (a node with no children) is straightforward.
 Deleting a node with one child is relatively simple; you replace the node with its child.
 Deleting a node with two children is more involved; you can replace it with the in-order
predecessor or in-order successor, or restructure the tree in a way that maintains the BST property.
Traversal: BSTs support different traversal methods, including in-order, pre-order, and post-order
traversals. These traversals allow you to visit all the nodes in a specific order and are commonly used
for tasks like printing elements in ascending or descending order.

Balanced BSTs: A balanced BST is a tree where the heights of the left and right subtrees of any node
differ by at most one. Balanced BSTs, like AVL trees and Red-Black trees, maintain the tree's balance,
ensuring that search, insertion, and deletion operations are efficient (logarithmic time complexity).

Worst-Case Scenario: In the worst-case scenario, when the tree is highly unbalanced (resembling a
linked list), the time complexity for search, insert, and delete operations can degrade to O(n), where n
is the number of nodes.

Binary Search Trees are widely used in computer science and various applications due to their
efficiency in search operations. They are commonly employed in databases, language compilers, file
systems, and more. To address the worst-case scenarios and ensure efficient operations, self-balancing
binary search trees like AVL trees and Red-Black trees are often preferred in practice.
Program:
#include <stdio.h>
#include <stdlib.h>
int flag=0;
typedef struct BST {
int data;
struct BST *lchild,*rchild;
} node;
/*FUNCTION PROTOTYPE*/
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main()
{
int choice;
int ans =1;
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
printf("\nProgram For Binary Search Tree ");
do {
printf("\n1.Create");
printf("\n2.Search");
printf("\n3.Recursive Traversals");
printf("\n4.Exit");
printf("\nEnter your choice :");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf("\nEnter The Element ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf("\nWant To enter More Elements?(1/0)");
scanf("%d",&ans);
} while (ans);
break;
 case 2:
printf("\nEnter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &parent);
if(flag==1) {
printf("\nParent of node %d is %d", tmp->data, parent->data);
} else {
printf("\n The %d Element is not Present",key);
}
flag=0;
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf("\nThe Inorder display :");
inorder(root);
printf("\nThe Preorder display : ");
preorder(root);
printf("\nThe Postorder display : ");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*Get new Node */
node *get_node()
{
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*This function is for creating a binary search tree */
void insert(node *root, node *new_node)
{
if (new_node->data < root->data) {
if(root->lchild==NULL)
root->lchild=new_node;
else
insert(root->lchild, new_node);
}
 if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*This function is for searching the node from binary Search Tree*/
node *search(node *root, int key, node **parent)
{
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf("\nThe %d Element is Present", temp->data);
flag=1;
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*This function displays the tree in inorder fashion */
void inorder(node *temp)
{
if (temp != NULL) {
inorder(temp->lchild);
printf("%d\t", temp->data);
inorder(temp->rchild);
}
}
/*This function displays the tree in preorder fashion */
void preorder(node *temp)
{
if (temp != NULL) {
printf("%d\t", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
 /*This function displays the tree in postorder fashion */
void postorder(node *temp)
{
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d\t", temp->data);
}
}
Output:
Program For Binary Search Tree
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :1
Enter The Element 6
Want To enter More Elements?(1/0)1
Enter The Element 9
Want To enter More Elements?(1/0)1
Enter The Element 5
Want To enter More Elements?(1/0)1
Enter The Element 2
Want To enter More Elements?(1/0)1
Enter The Element 8
Want To enter More Elements?(1/0)1
Enter The Element 15
Want To enter More Elements?(1/0)1
Enter The Element 24
Want To enter More Elements?(1/0)1
Enter The Element 14
Want To enter More Elements?(1/0)1
Enter The Element 7
Want To enter More Elements?(1/0)1
Enter The Element 8
Want To enter More Elements?(1/0)1
Enter The Element 5
Want To enter More Elements?(1/0)1
Enter The Element 2
Want To enter More Elements?(1/0)0
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :3
The Inorder display :2 5 6 7 8 9 14 15 24
The Preorder display : 6 5 2 9 8 7 15 14 24
The Postorder display : 2 5 7 8 14 24 15 9 6
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :2
Enter Element to be searched :7
The 7 Element is Present
Parent of node 7 is 8
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :4
11. Develop 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 DFS/BFS method

Theory:
Breadth-First Search (BFS) is a graph traversal algorithm used to explore a graph in a level-wise
manner. It starts at a given source vertex and systematically visits all the vertices reachable from that
source vertex, following the breadth of the graph. Here are the key steps and details of the BFS
algorithm:

BFS Algorithm:

Initialize: Create a queue (FIFO data structure) to store vertices to be processed, and mark all vertices
as unvisited. Set the source vertex as the first vertex to be visited. You can also initialize other data
structures, such as arrays to track visited vertices or to store the traversal order.
1. Explore the Source Vertex:
2. Enqueue the source vertex into the queue.
3. Mark it as visited.
4. Main Loop:
While the queue is not empty:
 Dequeue the front vertex from the queue. This vertex is the current vertex.
 Process (or visit) the current vertex. This can include printing its value or performing a
specific operation.
 Enqueue all unvisited neighbors (adjacent vertices) of the current vertex into the queue and
mark them as visited.
5. Repeat Step 3: Continue the process until the queue is empty.

DFS Algorithm:
1. Initialize: Mark all vertices as unvisited, and select a source vertex to start the traversal. You can also
initialize other data structures, such as arrays to track visited vertices or to store the traversal order.
2. Explore the Source Vertex:
 Mark the source vertex as visited.
 Process (or visit) the source vertex. This can include printing its value or performing a specific
operation.
3. Main Loop:
 For each unvisited neighbor (adjacent vertex) of the current vertex:
 Mark the neighbor as visited.
 Recursively call DFS on the neighbor (go deeper).
 Process (or visit) the neighbor.
4. Repeat Step 3: Continue this process recursively until there are no more unvisited neighbors for the
current vertex.
DFS Traversal Properties:
1. DFS explores the graph in a depth-first manner, which means it goes as deep as possible along one
branch before exploring other branches.
2. DFS can be implemented using either recursion or an explicit stack data structure. The recursive
version leverages the system call stack for backtracking.
Program:
#include<stdio.h>
#include<stdlib.h>
int n,a[10][10],i,j,source,s[10],choice,count;
void bfs(int n,int a[10][10],int source,int s[])
{
int q[10],u;
int front=1,rear=1;
s[source]=1;
q[rear]=source;
while(front<=rear) {
u=q[front];
front=front+1;
for(i=1; i<=n; i++)
if(a[u][i]==1 &&s[i]==0) {
rear=rear+1;
q[rear]=i;
s[i]=1;
}
}
}
void dfs(int n,int a[10][10],int source,int s[])
{
s[source]=1;
for(i=1; i<=n; i++)
if(a[source][i]==1 && s[i]==0)
dfs(n,a,i,s);
}
int main()
{
printf("Enter the number of nodes : \n");
scanf("%d",&n);
printf("\n Enter the adjacency matrix\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
while(1) {
printf("\n\n1.BFS\n 2.DFS\n 3.Exit\n");
printf("\nenter your choice\n");
scanf("%d",&choice);
switch(choice) {
case 1:
printf("\n Enter the source :\n");
scanf("%d",&source);
 for(i=1; i<=n; i++)
s[i]=0;
bfs(n,a,source,s);
for(i=1; i<=n; i++) {
if(s[i]==0)
printf("\n The node %d is not reachable\n",i);
else
printf("\n The node %d is reachable\n",i);
}
break;
case 2:
printf("\nEnter the source vertex :\n");
scanf("%d",&source);
count=0;
for(i=1; i<=n; i++)
s[i]=0;
dfs(n,a,source,s);
for(i=1; i<=n; i++)
if(s[i])
count=count+1;
if(count==n)
printf("\nThe graph is connected.");
else
printf("\nThe graph is not connected.");
break;
case 3:
exit(0);
}
}
}
Output:
Enter the number of nodes :
4
Enter the adjacency matrix
0010
1010
0000
0000
1.BFS
2.DFS
3.Exit
enter your choice
1
Enter the source :
1
The node 1 is reachable
The node 2 is not reachable
The node 3 is reachable
The node 4 is not reachable
1.BFS
2.DFS
3.Exit
enter your choice
2
Enter the source vertex :
1
The graph is not connected.
1.BFS
2.DFS
3.Exit
enter your choice
3
12. Given a File of N employee records with a set K of Keys (4-digit) which uniquely determine the
records in file F. Assume that file F is maintained in 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

Theory:
Linear probing is a collision resolution technique used in open addressing-based hash tables. In a hash
table, collisions occur when two different keys hash to the same index. Linear probing is a method to
handle these collisions by searching for the next available slot in a linear sequence of slots in the hash
table.

Here's how linear probing works:

1. Hash Function: When a key is inserted into the hash table, it is first hashed to an index using a hash
function.
2. Collision Handling: If the calculated index is already occupied by another key (a collision), linear
probing is used to find the next available slot.
3. Linear Probing: Starting from the collision index, the algorithm linearly searches for the next available
(empty) slot by incrementing the index one at a time. If it reaches the end of the table, it wraps around
to the beginning. The probing sequence is generally linear: index, index+1, index+2, ..., and so on.
4. Insertion: Once an empty slot is found, the key is inserted into that slot. If the hash table becomes too
full, it may need to be resized to maintain efficiency.
5. Lookup: When looking up a key, you calculate its index using the hash function. If the key is not
found at that index, you probe linearly until you find the key or an empty slot.
6. Deletion: Deleting a key involves marking the corresponding slot as deleted, which is different from
empty. This is done to distinguish between truly empty slots and slots that were previously occupied
but had their keys removed. During lookups, if a deleted slot is encountered, the search continues to
find the correct key.

Advantages of Linear Probing:

1. Simplicity: Linear probing is relatively simple to implement compared to other collision resolution
techniques like chaining.
2. Space Efficiency: Linear probing can be space-efficient when the load factor (the ratio of the number
of keys to the number of slots in the table) is relatively low. It doesn't require additional data structures
to handle collisions.
Program:
#include<stdio.h>
#define MAX 100
void display(int[]);
void linear_prob(int[],int,int);
void main()
{
int a[MAX],num,key,i;
int ans=1;
printf(" collision handling by linear probing : \n");
for (i=0; i<MAX; i++)
a[i] = -1;
do {
printf("\n Enter the data");
scanf("%4d", &num);
key=num%MAX;
linear_prob(a,key,num);
printf("\n Do you wish to continue ? (1/0) ");
scanf("%d",&ans);
} while(ans);
display(a);
}
void linear_prob(int a[MAX], int key, int num)
{
int flag=0, i;
if(a[key]== -1) {
a[key] = num;
} else {
printf("\nCollision Detected...!!!\n");
for(i=key+1; i<MAX; i++) {
if(a[i]==-1) {
flag = 1;
a[i]=num;
break;
}
}
if(flag==0) {
for(i=0; i<MAX; i++) {
if(a[i]==-1) {
a[i]=num;
break;
}
}
}
 printf("\n Collision avoided successfully");
}
}
void display(int a[MAX])
{
int i,choice;
printf("1.Display ALL\n 2.Filtered Display\n");
scanf("%d",&choice);
if(choice==1) {
printf("\n the hash table is\n");
for(i=0; i<MAX; i++)
printf("\n %d %d ", i, a[i]);
} else {
printf("\n the hash table is\n");
for(i=0; i<MAX; i++)
if(a[i]!=-1)
printf("\n %d %d ", i, a[i]);
}
}
Output:
Enter the data1234
Do you wish to continue ? (1/0) 1
Enter the data2548
Do you wish to continue ? (1/0) 1
Enter the data3256
Do you wish to continue ? (1/0) 1
Enter the data1299
Do you wish to continue ? (1/0) 1
Enter the data1298
Do you wish to continue ? (1/0) 1
Enter the data1398
Collision Detected...!!!
Collision avoided successfully using LINEAR PROBING
Do you wish to continue ? (1/0) 0
1.Display ALL
2.Filtered Display
2
the hash table is
0 1398
34 1234
48 2548
56 3256
98 1298
99 1299
Viva Questions
1. What is a data structure?
2. Why are data structures important in computer science and programming?
3. Differentiate between an array and a linked list.
4. What is an algorithm? How is it related to data structures?
5. Describe the characteristics of a stack and provide examples of real-world scenarios
where stacks are used.
6. Explain the difference between a queue and a stack.
7. What are the main applications of queues in computer science?
8. Define a tree and discuss the different types of trees you know.
9. What is a binary tree, and what are the types of binary trees?
10. Explain the concept of a linked list.
11. What is the difference between singly linked lists and doubly linked lists?
12. Define a hash table and explain the importance of hash functions.
13. Discuss various collision resolution techniques in hash tables.
14. Explain the difference between breadth-first search (BFS) and depth-first search (DFS).
15. What are dynamic data structures, and why are they useful?
16. How do you implement a stack using an array?
17. What are the applications of trees in computer science?
18. How can you search for an element in a binary search tree (BST)?
19. Discuss the difference between a graph and a tree.
20. Explain the concepts of in-order, pre-order, and post-order traversals in a binary tree.
21. Describe the properties of a balanced binary search tree.