1.Consider a student database of SY COMP class (at least 10 records).

Database contains different

fields of every student like Roll No, Name and SGPA.(array of objects of class) a) Design a roll call list,
arrange list of students according to roll numbers in ascending order (Use Bubble Sort) b) Arrange
list of students alphabetically. (Use Insertion sort) c) Arrange list of students to find out first ten
toppers from a class. (Use Quick sort) d) Search students according to SGPA. If more than one
student having same SGPA, then print list of all students having same SGPA. e) Search a particular
student according to name using binary search without recursion

#include <iostream>

#include <string.h>

using namespace std;

typedef struct student

int roll_num;

char name[20];

float marks;

} stud;

void create(stud s[20], int n);

void display(stud s[20], int n);

void bubble_sort(stud s[20], int n);

void insertionSort(stud s[20], int n);

void quick_sort(stud s[20], int, int);

int partition(stud s[20], int, int);

void search(stud s[20], int n, int key);

int bsearch(stud s[20], char x[20], int low, int high);

int main()

stud s[20];

int ch, n, key, result;

char x[20];

do

cout << "\n 1) Create Student Database ";

cout << "\n 2) Display Student Records ";

cout << "\n 3) Bubble Sort ";

cout << "\n 4) Insertion Sort ";

cout << "\n 5) Quick Sort ";

cout << "\n 6) Linear search ";

cout << "\n 7) Binary search ";

cout << "\n 8) Exit ";

cout << "\n Enetr Your Choice:=";

cin >> ch;

switch (ch)

case 1:

cout << "\n Enter The Number Of Records:=";

cin >> n;

create(s, n);

break;

case 2:

display(s, n);

break;

case 3:

bubble_sort(s, n);

break;

case 4:

insertionSort(s, n);

break;

case 5:

quick_sort(s, 0, n - 1);

cout << "\n"

<< "\t"

<< "Roll No"

 << "\t"

<< " Name"

<< "\t"

<< "Marks";

for (int i = n - 1; i >= n - 10; i--)

cout << "\n";

cout << "\t " << s[i].roll_num << "\t " << s[i].name << "\t " << s[i].marks;

break;

case 6:

cout << "\n Enter the marks which u want to search:=";

cin >> key;

search(s, n, key);

break;

case 7:

cout << "\n Enter the name of student which u want to search:=";

cin >> x;

insertionSort(s, n);

result = bsearch(s, x, 0, (n - 1));

if (result == -1)

cout << " \n Student name you want to search for is not present ! \n";

else

cout << " \n The student is present :\t" << s[result].name;

break;

case 8:
 return 0;

default:

cout << "\n Invalid choice !! Please enter your choice again." << endl;

} while (ch != 8);

void create(stud s[20], int n)

int i;

for (i = 0; i < n; i++)

cout << "\n Enter the roll number:=";

cin >> s[i].roll_num;

cout << "\n Enter the Name:=";

cin >> s[i].name;

cout << "\n Enter the marks:=";

cin >> s[i].marks;

void display(stud s[20], int n)

int i;

cout << "\n"

<< "\t"

<< "Roll No"

<< "\t"

<< " Name"

<< "\t"

<< "Marks";

for (i = 0; i < n; i++)

 {

cout << "\n";

cout << "\t " << s[i].roll_num << "\t " << s[i].name << "\t " << s[i].marks;

// bubble sort to sort in ascending order on roll number

void bubble_sort(stud s[20], int n)

int i, j;

stud temp;

for (i = 1; i < n; i++)

for (j = 0; j < n; j++)

if (s[j].roll_num > s[j + 1].roll_num)

temp = s[j];

s[j] = s[j + 1];

s[j + 1] = temp;

// insertion sort to sort on names in ascending order

void insertionSort(stud s[20], int n)

int i, j;

stud key;

for (i = 1; i < n; i++)

key = s[i];

j = i - 1;
 /* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && strcmp(s[j].name, key.name) > 0)

s[j + 1] = s[j];

j = j - 1;

s[j + 1] = key;

// Quick sort to sort on marks

void quick_sort(stud s[20], int l, int u)

int j;

if (l < u)

j = partition(s, l, u);

quick_sort(s, l, j - 1);

quick_sort(s, j + 1, u);

int partition(stud s[20], int l, int u)

int i, j;

stud temp, v;

v = s[l];

i = l;

j = u + 1;

do
 {

do

i++;

while (s[i].marks < v.marks && i <= u);

do

j--;

while (v.marks < s[j].marks);

if (i < j)

temp = s[i];

s[i] = s[j];

s[j] = temp;

} while (i < j);

s[l] = s[j];

s[j] = v;

return (j);

// linear search for marks if more than one student having same marks print all of them

void search(stud s[20], int n, int key)

int i;

cout << "\n"

<< "\t"

<< "Roll No"

<< "\t"

<< " Name"

<< "\t"

<< "Marks";

for (i = 0; i < n; i++)

 {

if (key == s[i].marks)

cout << "\n\t " << s[i].roll_num << "\t " << s[i].name << "\t " << s[i].marks;

int bsearch(stud s[20], char x[20], int low, int high)

int mid;

while (low <= high)

mid = (low + high) / 2;

if (strcmp(x, s[mid].name) == 0)

return mid;

else if (strcmp(x, s[mid].name) < 0)

high = mid - 1;

else

low = mid + 1;

-1;

}
2. Department of Computer Engineering has student's club named ‘COMET’. Students of Second,
third and final year of department can be granted membership on request. Similarly one may cancel
the membership of club. First node is reserved for president of club and last node is reserved for
secretary of club. Write program to maintain club member‘s information using singly linked list.
Store student MIS Registration No. and Name. Write functions to a) Add and delete the members as
well as president or even secretary. b) Compute total number of members of club c) Display
members d) Display list in reverse order using recursion e) Two linked lists exists for two divisions.
Concatenate two lists.

#include<iostream>

#include<string.h>

using namespace std;

struct node

int prn, rollno;

char name[50];

struct node *next;

};

class info

node

*s = NULL,

*head1 = NULL, *temp1 = NULL, *head2 = NULL, *temp2 = NULL, *head = NULL, *temp = NULL;

int b, c, i, j, ct;

char a[20];

public:

node *create();

void insertp();

void insertm();

void delm();

void delp();

void dels();
 void display();

void count();

void reverse();

void rev(node *p);

void concat();

};

node *info::create()

node *p = new (struct node);

cout << "enter name of student ";

cin >> a;

strcpy(p->name, a);

cout << "\n enter prn no. of student \n";

cin >> b;

p->prn = b;

cout << "enter student rollno";

cin >> c;

p->rollno = c;

p->next = NULL;

return p;

void info::insertm()

node *p = create();

if (head == NULL)

head = p;

else

temp = head;
 while (temp->next != NULL)

temp = temp->next;

temp->next = p;

void info::insertp()

node *p = create();

if (head == NULL)

head = p;

else

temp = head;

head = p;

head->next = temp->next;

void info::display()

if (head == NULL)

cout << "linklist is empty";

else

temp = head;

cout << " prn rolln0 NAME \n";

 while (temp->next != NULL)

cout << " \n"

<< temp->prn << " " << temp->rollno << " " << temp->name;

temp = temp->next;

cout << " " << temp->prn << " " << temp->rollno << " " << temp->name;

void info::delm()

int m, f = 0;

cout << "\n enter the prn no. of student whose data you want to delete";

cin >> m;

temp = head;

while (temp->next != NULL)

if (temp->prn == m)

s->next = temp->next;

delete (temp);

f = 1;

s = temp;

temp = temp->next;

if (f == 0)

cout << "\n sorry memeber not deleted ";

}
}

void info::delp()

temp = head;

head = head->next;

delete (temp);

void info::dels()

temp = head;

while (temp->next != NULL)

s = temp;

temp = temp->next;

s->next = NULL;

delete (temp);

void info::count()

temp = head;

ct = 0;

while (temp->next != NULL)

temp = temp->next;

ct++;

ct++;

cout << " Count of members is:" << ct;

}
void info::reverse()

rev(head);

void info::rev(node *temp)

if (temp == NULL)

return;

else

rev(temp->next);

cout << " " << temp->prn << " " << temp->rollno << " " << temp->name;

void info::concat()

int k, j;

cout << "enter no. of members in list1";

cin >> k;

head = NULL;

for (i = 0; i < k; i++)

insertm();

head1 = head;

head = NULL;

cout << "enter no. of members in list2";

cin >> j;

for (i = 0; i < j; i++)

 {

insertm();

head2 = head;

head = NULL;

temp1 = head1;

while (temp1->next != NULL)

temp1 = temp1->next;

temp1->next = head2;

temp2 = head1;

cout << " prn rolln0 NAME \n";

while (temp2->next != NULL)

cout << "\n " << temp2->prn << "temp2 = temp2->next;" << temp2->rollno << "" << temp2-
>name << "\n ";

cout << "\n " << temp2->prn << " " << temp2->rollno << " " << temp2->name << "\n";

int main()

info s;

int i;

char ch;

do

cout << "\n choice the options";

cout << "\n 1. To insert president ";

cout << "\n 2. To insert member ";

cout << "\n 3. To insert secretary ";

cout << "\n 4. To delete president ";

cout << "\n 5. To delete member ";

cout << "\n 6. To delete secretary ";

cout << "\n 7. To display data ";

cout << "\n 8. Count of members";

cout << "\n 9. To display reverse of string ";

cout << "\n 10.To concatenate two strings ";

cin >> i;

switch (i)

case 1:

s.insertp();

break;

case 2:

s.insertm();

break;

case 3:

s.insertm();

break;

case 4:

s.delp();

break;

case 5:

s.delm();

break;

case 6:

s.dels();

break;

case 7:

s.display();
 break;

case 8:

s.count();

break;

case 9:

s.reverse();

break;

case 10:

s.concat();

break;

default:

cout << "\n unknown choice";

cout << "\n do you want to continue enter y/Y \n";

cin >> ch;

} while (ch == 'y' || ch == 'Y');

return 0;

3. Implement Stack using a linked list. Use this stack to perform evaluation of a postfix
expression#include<iostream>

#include<stdlib.h>

#include<string.h>

#include<ctype.h>

struct node

int data;

struct node *next;

};

struct node *top = NULL;

/* create a new node with the given data */

struct node *createNode(int data)

struct node *ptr = (struct node *)malloc(sizeof(struct node));

ptr->data = data;

ptr->next = NULL;

return ptr;

/* push the input data into the stack */

void push(int data)

struct node *ptr = createNode(data);

if (ptr == NULL)

std::cout << "Memory allocation error!" << std::endl;

exit(EXIT_FAILURE);

if (top == NULL)

top = ptr;

return;

ptr->next = top;

top = ptr;
}

/* pop the top element from the stack */

int pop()

int data;

struct node *temp;

if (top == NULL)

return -1;

data = top->data;

temp = top;

top = top->next;

free(temp);

return data;

int main()

char str[100];

int i, data = -1, operand1, operand2, result;

/* i/p postfix expr from the user */

std::cout << "Enter your postfix expression: ";

fgets(str, 100, stdin);

for (i = 0; i < strlen(str); i++)

if (isdigit(str[i]))

data = (data == -1) ? 0 : data;

data = (data * 10) + (str[i] - '0');

 continue;

if (data != -1)

push(data);

if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')

operand2 = pop();

operand1 = pop();

if (operand1 == -1 || operand2 == -1)

break;

switch (str[i])

case '+':

result = operand1 + operand2;

push(result);

break;

case '-':

result = operand1 - operand2;

push(result);

break;

case '*':

result = operand1 * operand2;

push(result);

break;

case '/':

result = operand1 / operand2;

 push(result);

break;

data = -1;

if (top != NULL && top->next == NULL)

std::cout << "Output: " << top->data << std::endl;

else

std::cout << "You've entered a wrong expression." << std::endl;

return 0;

4. Queues are frequently used in computer programming, and a typical example is the creation of a
job queue by an operating system. If the operating system does not use priorities, then the jobs are
processed in the order they enter the system. Write C++ program for simulating job queue. Write
functions to add job and delete job from queue

#include<iostream>

#define MAX 10

using namespace std;

struct queue

int data[MAX];

int front, rear;

};

class Queue

struct queue q;
public:

Queue() { q.front = q.rear = -1; }

int isempty();

int isfull();

void enqueue(int);

int delqueue();

void display();

};

int Queue::isempty()

return (q.front == q.rear) ? 1 : 0;

int Queue::isfull()

return (q.rear == MAX - 1) ? 1 : 0;

void Queue::enqueue(int x)

q.data[++q.rear] = x;

int Queue::delqueue()

return q.data[++q.front];

void Queue::display()

int i;

cout << "\n";

for (i = q.front + 1; i <= q.rear; i++)

cout << q.data[i] << " ";

}

int main()

Queue obj;

int ch, x;

do

cout << "\n 1. insert job\n 2.delete job\n 3.display\n 4.Exit\n Enter your choice:";

cin >> ch;

switch (ch)

case 1:

if (!obj.isfull())

cout << "\n Enter data:";

cin >> x;

obj.enqueue(x);

else

cout << "Queue is overflow";

break;

case 2:

if (!obj.isempty())

cout << "\n Deleted Element=" << obj.delqueue();

else

cout << "\n Queue is underflow";

cout << "\nremaining jobs :";

obj.display();
 break;

case 3:

if (!obj.isempty())

cout << "\n Queue contains:";

obj.display();

else

break;

cout << "\n Queue is empty";

case 4:

cout << "\n Exit";

} while (ch != 4);

return 0;

5. A double-ended queue(deque) is a linear list in which additions and deletions may be made at
either end. Obtain a data representation mapping a deque into a one-dimensional array. Write C++
program to simulate deque with functions to add and delete elements from either end of the deque.

#include<iostream>

using namespace std;

#define SIZE 5

class dequeue

int a[10], front, rear;

public:
 dequeue();

void add_at_beg(int);

void add_at_end(int);

void delete_fr_front();

void delete_fr_rear();

void display();

};

dequeue::dequeue()

front = -1;

rear = -1;

void dequeue::add_at_beg(int item)

if (front == -1)

front++;

rear++;

a[rear] = item;

else if (rear >= SIZE - 1)

cout << "\nInsertion is not possible, overflow!!!";

else

for (int i = rear; i >= front; i--)

a[i + 1] = a[i];
 }

a[front] = item;

rear++;

void dequeue::add_at_end(int item)

if (front == -1)

front++;

rear++;

a[rear] = item;

else if (rear >= SIZE - 1)

cout << "\nInsertion is not possible, overflow!!!";

else

a[++rear] = item;

void dequeue::display()

if (front == -1)

cout << "\nDequeue is empty";

return;

}
 for (int i = front; i <= rear; i++)

cout << a[i] << " ";

void dequeue::delete_fr_front()

if (front == -1)

cout << "Deletion is not possible: Dequeue is empty";

return;

if (front == rear)

cout << "The deleted element is " << a[front];

front = rear = -1;

else

cout << "The deleted element is " << a[front];

front = front + 1;

void dequeue::delete_fr_rear()

if (front == -1)

{
 cout << "Deletion is not possible: Dequeue is empty";

return;

if (front == rear)

cout << "The deleted element is " << a[rear];

front = rear = -1;

else

cout << "The deleted element is " << a[rear];

rear = rear - 1;

int main()

int c, item;

dequeue d1;

do

cout << "\n\n****DEQUEUE OPERATION****\n";

cout << "1-Insert at beginning";

cout << "\n2-Insert at end";

cout << "\n3-Display";

cout << "\n4-Deletion from front";

cout << "\n5-Deletion from rear";

cout << "\n6-Exit";

cout << "\nEnter your choice<1-6>: ";

 cin >> c;

switch (c)

case 1:

cout << "Enter the element to be inserted: ";

cin >> item;

d1.add_at_beg(item);

break;

case 2:

cout << "Enter the element to be inserted: ";

cin >> item;

d1.add_at_end(item);

break;

case 3:

d1.display();

break;

case 4:

d1.delete_fr_front();

break;

case 5:

d1.delete_fr_rear();

break;

case 6:

cout << "Exiting the program.\n";

break;

default:

cout << "Invalid choice";

break;

} while (c != 6);
 return 0;

6. A book consists of chapters, chapters consist of sections and sections consist of subsections.
Construct a tree and print the nodes. Find the time and space requirements of your method.

#include<iostream>

#include<cstdlib>

#include<string.h>

using namespace std;

/*

* Node Declaration

*/

struct node

char label[10];

int ch_count;

struct node *child[10];

} *root;

/*

* Class Declaration

*/

class BST

public : void create_tree();

void display(node *r1);

BST()

root = NULL;
 }

};

void BST::create_tree()

int tbooks, tchapters, i, j, k;

root = new node();

cout << "Enter name of book";

cin >> root->label;

cout << "Enter no. of chapters in book";

cin >> tchapters;

root->ch_count = tchapters;

for (i = 0; i < tchapters; i++)

root->child[i] = new node;

cout << "Enter Chapter name\n";

cin >> root->child[i]->label;

cout << "Enter no. of sections in Chapter: " << root->child[i]->label;

cin >> root->child[i]->ch_count;

for (j = 0; j < root->child[i]->ch_count; j++)

root->child[i]->child[j] = new node;

cout << "Enter Section " << j + 1 << "name\n";

cin >> root->child[i]->child[j]->label;

// cout<<"Enter no. of subsections in "<child[i]->child[j]->label;

// cin>>r1->child[i]->ch_count;

void BST::display(node *r1)

int i, j, k, tchapters;
 if (r1 != NULL)

cout << "\n-----Book Hierarchy---";

cout << "\n Book title : "<<r1->label;

tchapters = r1 -> ch_count;

for (i = 0; i < tchapters; i++)

cout << "\n Chapter "<<i+1;

cout<<" "<<r1->child[i]->label;

cout << "\n Sections ";

for (j = 0; j < r1->child[i]->ch_count;j++)

// cin>>r1->child[i]->child[j]->label;

cout << "\n "<<r1->child[i]->child[j]->label;

/*

* Main Contains Menu

*/

int main()

int choice;

BST bst;

while (1)

cout << " ---------------- " << endl;

cout << "Book Tree Creation" << endl;

cout << " ---------------- " << endl;

cout << "1.Create" << endl;

 cout << "2.Display" << endl;

cout << "3.Quit" << endl;

cout << "Enter your choice : ";

cin >> choice;

switch (choice)

case 1:

bst.create_tree();

case 2:

bst.display(root);

break;

case 3:

exit(1);

default:

cout << "Wrong choice" << endl;

7. Beginning with an empty binary search tree, Construct binary search tree by inserting the values
in the order given. After constructing a binary tree - i. Insert new node ii. Find number of nodes in
longest path iii. Minimum data value found in the tree iv. Change a tree so that the roles of the left
and right pointers are swapped at every node v. Search a value

#include<iostream>

using namespace std;

struct node

int data;

node *L;

node *R;

};
node *root, *temp;

int count, key;

class bst

public:

void create();

void insert(node *, node *);

void disin(node *);

void dispre(node *);

void dispost(node *);

void search(node *, int);

int height(node *);

void mirror(node *);

void min(node *);

bst()

root = NULL;

count = 0;

};

void bst::create()

char ans;

do

temp = new node;

cout << "Enter the data : ";

cin >> temp->data;

temp->L = NULL;

temp->R = NULL;

if (root == NULL)
 {

root = temp;

else

insert(root, temp);

cout << "Do you want to insert more value : " << endl;

cin >> ans;

count++;

cout << endl;

} while (ans == 'y');

cout << "The Total no.of nodes are:" << count;

void bst::insert(node *root, node *temp)

if (temp->data > root->data)

if (root->R == NULL)

root->R = temp;

else

insert(root->R, temp);

else

if (root->L == NULL)

root->L = temp;

else

insert(root->L, temp);
 }

void bst::disin(node *root)

if (root != NULL)

disin(root

->L);

cout << root

->data

<< "\t ";

disin(root -> R);

count++;

void bst::dispre(node *root)

if (root != NULL)

cout << root

->data

<< "\t ";

dispre(root

->L);

dispre(root

->R);

void bst::dispost(node *root)

if (root != NULL)
 {

dispost(root

->L);

dispost(root

->R);

cout << root

->data<< "\t ";

void bst::search(node *root, int key)

int flag = 0;

cout << "\nEnter your key : " << endl;

cin >> key;

temp = root;

while (temp != NULL)

if (key == temp->data)

cout << "KEY FOUND\n";

flag = 1;

break;

node *parent = temp;

if (key > parent->data)

temp = temp->R;

else

{
 temp = temp->L;

if (flag == 0)

cout << "KEY NOT FOUND " << endl;

int bst::height(node *root)

int hl, hr;

if (root == NULL)

return 0;

else if (root->L == NULL && root->R == NULL)

return 0;

cout << endl;

hr = height(root->R);

hl = height(root->L);

if (hr > hl)

return (1 + hr);

else

return (1 + hl);

}
void bst::min(node *root)

temp = root;

cout << endl;

while (temp->L != NULL)

temp = temp->L;

cout << root->data;

void bst::mirror(node *root)

temp = root;

if (root != NULL)

mirror(root->L);

mirror(root->R);

temp = root->L;

root->L = root->R;

root->R = temp;

int main()

bst t;

int ch;

char ans;

do

cout<<"\n1) Insert new node 2)number of nodes in longest path 3) minimum 4) mirror 5) search
6) inorder 7) preorder 8) postorder"<<endl;
 cin>>ch;

switch (ch)

case 1:

t.create();

break;

case 2:

cout << "\"n Number of nodes in longest path:" << (1 + (t.height(root)));

break;

case 3:

cout << "\nThe min element is:";

t.min(root);

break;

case 4:

t.mirror(root);

cout << "\nThe mirror of tree is: ";

t.disin(root);

break;

case 5:

t.search(root, key);

break;

case 6:

cout << "\n***************INORDER**************" << endl;

t.disin(root);

break;

case 7:

cout << "\n***************PREORDER**************" << endl;

t.dispre(root);

break;

case 8:

cout << "\n*******************POSTORDER**************" << endl;

 t.dispost(root);

break;

cout << "\nDo you want to continue :";

cin >> ans;

} while (ans == 'y');

return 0;

8. Implement graph using adjacency list or matrix and perform DFS or BFS.

#include<bits/stdc++.h>

using namespace std;

class Graph

// Number of vertex

int v;

// Number of edges

int e;

// Adjacency matrix

int **adj;

public:

// To create the initial adjacency matrix

Graph(int v, int e);

// Function to insert a new edge

void addEdge(int start, int e);

// Function to display the BFS traversal

void BFS(int start);

};

// Function to fill the empty adjacency matrix

Graph::Graph(int v, int e)

this->v = v;

this->e = e;

adj = new int *[v];

for (int row = 0; row < v; row++)

adj[row] = new int[v];

for (int column = 0; column < v; column++)

adj[row][column] = 0;

// Function to add an edge to the graph

void Graph::addEdge(int start, int e)

// Considering a bidirectional edge

adj[start][e] = 1;

adj[e][start] = 1;

// Function to perform BFS on the graph

void Graph::BFS(int start)

// Visited vector to so that

// a vertex is not visited more than once

// Initializing the vector to false as no

// vertex is visited at the beginning

vector<bool>visited(v,false);
 vector<int>q;

q.push_back(start);

// Set source as visited

visited[start] = true;

int vis;

while (!q.empty())

vis = q[0];

// Print the current node

cout << vis << " ";

q.erase(q.begin());

// For every adjacent vertex to the current vertex

for (int i = 0; i < v; i++)

if (adj[vis][i] == 1 && (!visited[i]))

// Push the adjacent node to the queue

q.push_back(i);

// Set

visited[i] = true;

// Driver code

int main()

int v = 5, e = 4;

// Create the graph

Graph G(v, e);

 G.addEdge(0, 1);

G.addEdge(0, 2);

G.addEdge(1, 3);

G.BFS(0);