DSA Practical Exam pdf - 17 jan 2024
DSA PRACTICAL PDF :
Practical 1
Aim: Write a C++ program to
1.1) Traverse the elements in array
Program: -
#include<iostream>
using namespace std;
int main(){
int arr[100],n,a;
cout <<"Enter the size of array: ";
cin>>n;
cout <<"Enter the element of array: ";
for(int i =0; i<n; i++){
cin >> a;
arr[i] = a;
}
cout <<"the element of array : "<< endl;
for(int j = 0; j< n; j++){
cout << arr[j]<< endl;
}
return 0;
}
Output:
1.2) insert the elements in array
Program:
#include<iostream>
using namespace std;
int main() {
int arr[100], n, a, item, pos;
cout << "Enter the size of array: ";
cin >> n;
cout << "Enter the elements of array: ";
for(int i = 0; i < n; i++) {
cin >> a;
arr[i] = a;
}
cout << "The elements of array: " << endl;
for(int j = 0; j < n; j++) {
cout << arr[j] << endl;
}
cout << "Enter the item to be inserted into the array: ";
cin >> item;
cout << "Enter the position of insertion in array: ";
cin >> pos;
for (int size = n - 1; size >= pos - 1; size--) {
arr[size + 1] = arr[size];
}
arr[pos - 1] = item;
cout << "New Array is :" << endl;
for(int j = 0; j <= n; j++) {
cout << arr[j] << endl;
}
return 0;
}
Output:
1.3) delete the element from array
Program:
#include<iostream>
using namespace std;
int main() {
int arr[100], n, a, item, pos;
cout << "Enter the size of array: ";
cin >> n;
cout << "Enter the elements of array: ";
for(int i = 0; i < n; i++) {
cin >> a;
arr[i] = a;
}
cout << "The elements of array: " << endl;
for(int j = 0; j < n; j++) {
cout << arr[j] << endl;
}
cout << "Enter the position of deleation of element: "<< endl;
cin >> pos;
item=arr[n];
for(int j = pos;j<=arr[n]-1;j++){
arr[j]=arr[j+1];
}
cout << "The elements of new array: " << endl;
for(int j = 0; j < n - 1; j++) {
cout << arr[j] << endl;
}
return 0;
}
Output:
Practical 2
Aim: Write a C++ program that perform the following:
2.1) Search for a key element in a list of elements using linear search
Program:
#include <iostream>
using namespace std;
int main()
{
int array[10], size, item, item1, loc = 0, loc1 = 0, beg, end, mid;
cout << "ENTER THE SIZE OF ARRAY:";
cin >> size;
cout << "ENTER THE ELEMENTS FOR ARRAY:";
for (int i = 0; i < size; i++){
cin >> array[i];
}
cout << "THE ELEMENTS OF ARRAY:";
for (int i = 0; i < array[size]; i++)
{
cout << array[i] << endl;
}
cout << "ENTER THE ELEMENT YOU WANT TO SEARCH:";
cin >> item;
array[size + 1] = item;
while (array[loc] != item)
{
loc = loc + 1;
}
if (loc == array[size] + 1)
{
cout << "ITEM IS NOT IN ARRAY:" << endl;
}
else
{
cout << "THE LOCATION IS:" << loc;
}
return 0;
}
Output:
2.2) Search for a key element in a list of sorted elements using binary search.
Program:
#include <iostream>
using namespace std;
int main() {
int beg, end, array[20], size, item, loc, i, mid;
cout << "ENTER THE SIZE OF ARRAY:";
cin >> size;
cout << "ENTER THE VALUES OF ARRAY:";
for (i = 0; i < size; i++) {
cin >> array[i];
}
cout << "VALUES OF ARRAY:" << endl;
for (i = 0; i < size; i++) {
cout << array[i] << endl;
}
beg = 0;
end = size - 1;
mid = (beg + end) / 2;
cout << "ENTER THE ELEMENT YOU WANT TO SEARCH:";
cin >> item;
while (beg <= end && array[mid] != item) {
if (item < array[mid]) {
end = mid - 1;
} else {
beg = mid + 1;
}
mid = (beg + end) / 2;
}
if (item == array[mid]) {
loc = mid;
cout << "THE LOCATION IS:" << loc;
} else {
loc = -1; // Set loc to a value that indicates the element is not found
cout << "ELEMENT NOT FOUND";
}
return 0;
}
Output:
Practical 3
Aim: Write a program to implement Sorting Algorithm
3.1)Bubble Sort
Program:
#include <iostream>
using namespace std;
int main() {
int array[20], size, i, j, k, ptr, temp;
cout << "ENTER THE SIZE OF ARRAY:";
cin >> size;
cout << "ENTER THE ELEMENTS OF ARRAY:";
for (i = 0; i < size; i++) {
cin >> array[i];
}
cout << "THE ARRAY VALUES ARE:" << endl;
for (i = 0; i < size; i++) {
cout << array[i] << endl;
}
for (k = 0; k < size - 1; k++) {
for (ptr = 0; ptr < size - k - 1; ptr++) {
if (array[ptr] > array[ptr + 1]) {
temp = array[ptr];
array[ptr] = array[ptr + 1];
array[ptr + 1] = temp;
}
}
}
cout << "THE BUBBLED ARRAY IS:" << endl;
for (i = 0; i < size; i++) {
cout << array[i] << endl;
}
return 0;
}
Output:
3.2) Selection Sort
Program :
#include <iostream>
using namespace std;
int main()
{
int array1[20];
int size, i, j, temp, min, loc;
cout << "ENTER THE SIZE OF ARRAY:" << endl;
cin >> size;
cout << "ENTER THE ELEMENTS FOR ARRAY:";
for (i = 0; i < size; i++){
cin >> array1[i];
}
cout << "THE ELEMENTS ARE:" << endl;
for (i = 0; i < size; i++){
cout << array1[i] << " "<< endl;
}
cout << "NOW WE PERFORM SELECTION SORTING:";
int k;
for (k = 0; k < size - 1; k++){
min = array1[k];
loc = k;
for (j = k + 1; j < size; j++)
{
if (min > array1[j])
{
min = array1[j];
loc = j;
}
}
temp = array1[k];
array1[k] = array1[loc];
array1[loc] = temp;
}
cout << endl
<< "NEW ARRAY:";
for (i = 0; i < size; i++){
cout << " " << array1[i];
}
return 0;
}
Output:
3.3) Insertion Sort
Program:
#include <iostream>
using namespace std;
int main()
{
int array1[20];
int i, size, ptr, temp;
cout << "ENTER THE SIZE OF ARRAY:";
cin >> size;
cout << "ENTER THE ELEMENTS OF ARRAY:" << endl;
for (i = 0; i < size; i++){
cin >> array1[i];
}
cout << "THE ELEMENTS ARE:" << endl;
for (i = 0; i < size; i++){
cout << array1[i] << endl;
}
cout << "NOW WE PERFORM INSERTION SORTING" << endl;
array1[0] = -1;
for (int k = 2; k < size; k++){
temp = array1[k];
ptr = k - 1;
while (temp < array1[ptr]){
array1[ptr + 1] = array1[ptr];
ptr = ptr - 1;
}
array1[ptr + 1] = temp;
}
cout << "THE NEW ARRAY IS :" << endl;
for (i = 0; i < size; i++){
cout << array1[i] << endl;
}
return 0;
}
Output:
Practical 4
Aim: Write a program to perform
4.1) Traversal of Matrix
Program:
#include <iostream>
using namespace std;
int main(){
int array1[3][2], j;
cout << "ENTER ELEMENTS:";
for (int i = 0; i < 3; i++){
for (j = 0; j < 2; j++){
cin >> array1[i][j];
}
}
cout << "THE ELEMENTS ARE:" << endl;
for (int i = 0; i < 3; i++){
for (int j = 0; j < 2; j++){
cout << "NUMBER [" << i << "][" << j << "]:" << array1[i][j] << endl;
}
}
return 0;
}
Output:
4.2) addition of Matrix
Program:
#include <iostream>
using namespace std;
int main(){
int r, c, a[100][100], b[100][100], sum[100][100], i, j;
cout << "Enter number of rows (between 1 and 100): ";
cin >> r;
cout << "Enter number of columns (between 1 and 100): ";
cin >> c;
cout << endl
<< "Enter elements of 1st matrix: " << endl;
for (i = 0; i < r; ++i){
for (j = 0; j < c; ++j){
cout << "Enter element a" << i + 1 << j + 1 << " : ";
cin >> a[i][j];
}
}
cout << endl
<< "Enter elements of 2nd matrix: " << endl;
for (i = 0; i < r; ++i){
for (j = 0; j < c; ++j){
cout << "Enter element b" << i + 1 << j + 1 << " : ";
cin >> b[i][j];
}
}
for (i = 0; i < r; ++i){
for (j = 0; j < c; ++j){
sum[i][j] = a[i][j] + b[i][j];
}
}
cout << endl
<< "Sum of two matrix is: " << endl;
for (i = 0; i < r; ++i){
for (j = 0; j < c; ++j)
{
cout << sum[i][j] << " ";
if (j == c - 1){
cout << endl;
}
}
}
}
Output:
4.3) multiplication of Matrix
Prgram:
#include <iostream>
using namespace std;
int main(){
int a[10][10], b[10][10], mult[10][10], r1, c1, r2, c2, i, j, k;
cout << "Enter rows and columns for first matrix: ";
cin >> r1 >> c1;
cout << "Enter rows and columns for second matrix: ";
cin >> r2 >> c2;
while (c1 != r2){
cout << "Error! column of first matrix not equal to row of second.";
cout << "Enter rows and columns for first matrix: ";
cin >> r1 >> c1;
cout << "Enter rows and columns for second matrix: ";
cin >> r2 >> c2;
}
cout << endl
<< "Enter elements of matrix 1:" << endl;
for (i = 0; i < r1; ++i){
for (j = 0; j < c1; ++j){
cout << "Enter element a" << i + 1 << j + 1 << " : ";
cin >> a[i][j];
}
}
cout << endl
<< "Enter elements of matrix 2:" << endl;
for (i = 0; i < r2; ++i){
for (j = 0; j < c2; ++j)
{
cout << "Enter element b" << i + 1 << j + 1 << " : ";
cin >> b[i][j];
}
}
for (i = 0; i < r1; ++i){
for (j = 0; j < c2; ++j)
{
mult[i][j] = 0;
}
}
for (i = 0; i < r1; ++i){
for (j = 0; j < c2; ++j){
for (k = 0; k < c1; ++k)
{
mult[i][j] += a[i][k] * b[k][j];
}
}
}
cout << endl
<< "Output Matrix: " << endl;
for (i = 0; i < r1; ++i){
for (j = 0; j < c2; ++j){
cout << " " << mult[i][j];
if (j == c2 - 1){
cout << endl;
}
}
}
return 0;
}
Output:
Practical 5:-
Write a C++ program that uses functions to perform the following:
5.1) Create a singly linked list of integers.
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int INFO[10];
int LINK[10];
int START=3;
INFO[3]=45;LINK[3]=2;
INFO[2]=67;LINK[2]=5;
INFO[5]=75;LINK[5]=4;
INFO[4]=80;LINK[4]=7;
INFO[7]=90;LINK[7]=0;
int PTR=START;
cout<<"TRAVERSAl LIST:"<<endl;
while(PTR!=0)
{
cout<<INFO[PTR]<<" ";
PTR=LINK[PTR];
}
getch();
}
OUTPUT:-
5.2) Delete a given integer from the above linked list.
#include <iostream>
using namespace std;
int main() {
int INFO[10];
int LINK[10];
int START = 3;
INFO[3] = 40;
LINK[3] = 2;
INFO[2] = 66;
LINK[2] = 5;
INFO[5] = 25;
LINK[5] = 4;
INFO[4] = 83;
LINK[4] = 7;
INFO[7] = 60;
LINK[7] = 0;
int deleteValue;
cout << "Enter the value to delete: ";
cin >> deleteValue;
int PREV = 0; // To keep track of the previous node
int PTR = START;
// Find the node to delete
while (PTR != 0 && INFO[PTR] != deleteValue) {
PREV = PTR;
PTR = LINK[PTR];
}
if (PTR == 0) {
cout << "Value not found in the list." << endl;
} else {
// Update pointers to skip the node to be deleted
LINK[PREV] = LINK[PTR];
// Optional: You can also clear the values in the deleted node if needed
INFO[PTR] = 0;
LINK[PTR] = 0;
cout << "Value " << deleteValue << " deleted from the list." << endl;
// Print the updated list
cout << "TRAVERSAL LIST:" << endl;
PTR = START;
while (PTR != 0) {
cout << INFO[PTR] << " ";
PTR = LINK[PTR];
}
}
return 0;
}
OUTPUT :
5.3) Display the contents of the above list after deletion.
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int INFO[10];
int LINK[10];
int START=3;
int ITEM,locp,locd,AVAIL;
INFO[3]=45;LINK[3]=2;
INFO[2]=67;LINK[2]=5;
INFO[5]=75;LINK[5]=4;
INFO[4]=80;LINK[4]=7;
INFO[7]=90;LINK[7]=0;
int PTR=START;
cout<<"TRAVERSAl LIST:"<<endl;
while(PTR!=0) {
cout<<INFO[PTR]<<" ";
PTR=LINK[PTR];
}
cout<<endl<<"NOW WE FIND THE LOCATION OF ITEM:"<<endl;
cout<<"INSERT ONE ITEM YOU WANT DELETE:"<<endl;
cin>>ITEM;
if(START==0)
{
locd=0;
locp=0;
cout<<"LOCATION is:"<<locd<<locp<<endl;
}
if(INFO[START]==ITEM)
{
locd=START;
locp=0;
cout<<"LOCATION is:"<<locd<<endl;
}
int save=START;
PTR=LINK[START];
while(PTR!=0)
{
if(INFO[PTR]==ITEM)
{
locd=PTR;
locp=save;
cout<<"LOCATION is:"<<locd<<endl;
}
save=PTR;
PTR=LINK[PTR];
}
cout<<"NOW WE PERFORM DELETION:"<<endl;
if(locd==0)
{
cout<<"ITEM IS NOT IN THE LIST:"<<endl;
}
if(locp==0) {
START=LINK[START];
}
Else {
LINK[locp]=LINK[locd];
}
LINK[locd]=AVAIL;
AVAIL=locd;
cout<<"DELETED NODE:"<<AVAIL<<endl;
cout<<"NEW LINKED LIST:"<<endl;
PTR=START;
while(PTR!=0)
{
cout<<INFO[PTR]<<" ";
PTR=LINK[PTR]; }
getch(); }
OUTPUT:-
5.4 )Sorting the linked list
#include <iostream>
using namespace std;
void swapNodes(int INFO[], int LINK[], int a, int b) {
int tempInfo = INFO[a];
INFO[a] = INFO[b];
INFO[b] = tempInfo;
int tempLink = LINK[a];
LINK[a] = LINK[b];
LINK[b] = tempLink;
}
void bubbleSort(int INFO[], int LINK[], int start) {
int n = 0;
int current = start;
// Count the number of elements in the linked list
while (current != 0) {
n++;
current = LINK[current];
}
// Perform bubble sort
for (int i = 0; i < n - 1; i++) {
for (int j = start; j < n - i - 1; j++) {
if (INFO[j] > INFO[LINK[j]]) {
swapNodes(INFO, LINK, j, LINK[j]);
}
}
}
}
int main() {
int INFO[10];
int LINK[10];
int START = 3;
INFO[3] = 40;
LINK[3] = 2;
INFO[2] = 66;
LINK[2] = 5;
INFO[5] = 25;
LINK[5] = 4;
INFO[4] = 83;
LINK[4] = 7;
INFO[7] = 60;
LINK[7] = 0;
// Sorting the linked list using bubble sort
bubbleSort(INFO, LINK, START);
// Traversing the sorted list
int PTR = START;
cout << "TRAVERSAL OF SORTED LIST:" << endl;
while (PTR != 0) {
cout << INFO[PTR] << " ";
PTR = LINK[PTR];
}
return 0;
}
OUTPUT:
5.5) reverse the elements of Linked list
#include <iostream>
using namespace std;
int main() {
int INFO[10];
int LINK[10];
int START = 3;
INFO[3] = 40;
LINK[3] = 2;
INFO[2] = 66;
LINK[2] = 5;
INFO[5] = 25;
LINK[5] = 4;
INFO[4] = 83;
LINK[4] = 7;
INFO[7] = 60;
LINK[7] = 0;
// Traverse and print the original list
int PTR = START;
cout << "Original List:" << endl;
while (PTR != 0) {
cout << INFO[PTR] << " ";
PTR = LINK[PTR];
}
// Reverse the list
int prev = 0;
int current = START;
int next;
while (current != 0) {
next = LINK[current];
LINK[current] = prev;
prev = current;
current = next;
}
// Update the new start after reversing
START = prev;
// Print the reversed list
cout << "\nReversed List:" << endl;
PTR = START;
while (PTR != 0) {
cout << INFO[PTR] << " ";
PTR = LINK[PTR];
}
return 0;
}
OUTPUT :
5.6) search the element in a given linked list
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int INFO[10];
int LINK[10];
int START=3;
int loc,ITEM,PTR;
INFO[3]=45;LINK[3]=2;
INFO[2]=67;LINK[2]=5;
INFO[5]=75;LINK[5]=4;
INFO[4]=80;LINK[4]=7;
INFO[7]=90;LINK[7]=0;
PTR=START;
cout<<"TRAVERSAl LIST:"<<endl;
while(PTR!=0)
{
cout<<INFO[PTR]<<" ";
PTR=LINK[PTR];
}
cout<<"NOW WE PERFORM SEARCHING:"<<endl;
cout<<"ENTER ELEMENT YOU WANT TO SEARCH:"<<endl;
cin>>ITEM;
PTR=START;
while(PTR!=0)
{
if(ITEM>INFO[PTR])
{
PTR=LINK[PTR];
}
else if(ITEM==INFO[PTR])
{
loc=PTR;
cout<<"THE LOCATION IS :"<<loc<<endl;
}
else
{
loc=0;
cout<<"LOCATION IS:"<<loc;
} }
loc=0;
cout<<"THE LOCATION IS :"<<loc;
getch(); }
OUTPUT:-
Practical 6
Aim: Write a program to implement Stack
6.1) PUSH
6.2) POP
6.3) DISPLAY Operations
Program:
#include<iostream>
using namespace std;
int stack[10];
int n = 9 , top = -1;
void push(int val){
if (top >= n -1){
cout<<"Stack over flow"<< endl;
}else{
top++;
stack[top] = val;
}
}
void pop(){
if (top <= -1){
cout << "Stack Unserflow" << endl;
}else
{
cout << "the poped element is :" << stack[top] << endl;
top--;
}
}
void dispaly(){
if (top >= 0){
cout << "Stack element are:"<< endl;
for (int i = top; i >= 0; i--){
cout<< stack[i] << " " << endl;
}
}else{
cout << "Stack is empty";
}
}
int main()
{
int ch, val;
cout << "1) Push"<< endl;
cout << "2) pop"<< endl;
cout << "3) Display"<< endl;
cout << "4) Exit"<< endl;
do
{
cout << "Enter Choice: ";
cin >> ch;
switch (ch){
case 1:
cout << "Enter the value in stack: ";
cin >> val;
push(val);
break;
case 2:
pop();
break;
case 3:
dispaly();
break;
case 4:
cout<< "Exiting...";
break;
default:
cout << "Invalid choice";
break;
}
} while (ch!=4);
return 0;
}
Output:
Practical 7
Aim: Write a C++ program that uses functions to perform the following:
7.1) Create a queue of integers.
7.2) Delete a given integer from the above queue.
7.3) Display the contents of the above queue after deletion.
Program:
#include <iostream>
using namespace std;
int QUEUE[10];
int n = 10, front = -1, rear = -1;
int item;
void insert(int item){
if (rear == n - 1){
cout << "Overflow:" << endl;
}
else{
front = 0;
rear = rear + 1;
QUEUE[rear] = item;
}
}
void deletion(){
if (front == -1){
cout << "UNDERFLOW:" << endl;
}else{
item = QUEUE[front];
cout << "DELETED ELEMENT IS:" << item << endl;
front = front + 1;
}
}
void display(){
cout << "THE QUEUE ELEMENTS ARE:" << endl;
for (int i = 1; i <= rear; i++){
cout << " " << QUEUE[i] << endl;
}
}
int main(){
cout << "ENTER 1 FOR ADD THE ELEMENT:" << endl;
cout << "ENTER 2 FOR DELETE THE ELEMENT:" << endl;
cout << "ENTER 3 FOR DISPLAY THE ELEMENT:" << endl;
cout << "ENTER 4 FOR EXIT:" << endl;
int choice;
do{
cout << "ENTER THE OPERATION YOU WANT TO PERFORM:" << endl;
cin >> choice;
switch (choice){
case 1:
cout<< "Enter the item you want to insert: ";
cin >> item;
insert(item);
break;
case 2:
deletion();
break;
case 3:
display();
break;
case 4:
cout << "Exiting..." << endl;
break;
default:
cout << "YOU HAVE ENTERED INVALID NUMBER:" << endl;
}
} while (choice != 4);
return 0;
}
Output:
Practical 8
Aim: write a program to implement Tree Traversal Algorithm
8.1) In-order
8.2) Post-order
8.3) Pre-order
Program:
#include <iostream>
using namespace std;
struct node {
int data;
struct node *lchild;
struct node *rChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->lchild = NULL;
tempNode->rChild = NULL;
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
if(data < parent->data) {
current = current->lchild;
if(current == NULL) {
parent->lchild = tempNode;
return;
}
}
else {
current = current->rChild;
if(current == NULL) {
parent->rChild = tempNode;
return;
}
}
}
}
}
void pre_order_traversal(struct node* root){
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->lchild);
pre_order_traversal(root->rChild);
}
}
void inorder_traversal(struct node* root){
if(root != NULL) {
inorder_traversal(root->lchild);
printf("%d ",root->data);
inorder_traversal(root->rChild);
}
}
void post_order_traversal(struct node* root){
if(root != NULL) {
post_order_traversal(root->lchild);
post_order_traversal(root->rChild);
printf("%d ", root->data);
}
}
int main(){
int i, size;
int array[100];
cout<< "How many element you want to add:";
cin >> size;
cout << "Enter the element of tree:"<< endl;
for(int i = 0; i < size; i++){
cin >> array[i];
}
for(i = 0; i < size; i++)
insert(array[i]);
printf("Preorder traversal: ");
pre_order_traversal(root);
printf("\nInorder traversal: ");
inorder_traversal(root);
printf("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
Output:
Practical 9
Aim: write a program to implement graph using Adjacency Matrix.
Program:
#include <iostream>
#include <vector>
class Graph {
private:
int num_vertices;
std::vector<std::vector<int>> adj_matrix;
public:
Graph(int vertices) : num_vertices(vertices), adj_matrix(vertices, std::vector<int>(vertices, 0)) {}
void addEdge(int start, int end) {
adj_matrix[start][end] = 1;
}
void display() {
std::cout << "Adjacency Matrix:" << std::endl;
for (const auto& row : adj_matrix) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
};
int main() {
int num_vertices, start, end;
std::cout << "Enter the number of vertices: ";
std::cin >> num_vertices;
Graph graph(num_vertices);
bool a = true;
for (int i = 0; i < num_vertices; ++i) {
std::cout << "Enter the start vertex: ";
std::cin >> start;
std::cout << "Enter the end vertex: ";
std::cin >> end;
graph.addEdge(start, end);
}
graph.display();
return 0;
}
Output:
Comments
Post a Comment