Practical Exam Flashcards
gi3. BST of integers, pre-order and post-order
Pre-order traversal in BST
Data Left Right
int preOrder(){
}
explain what is adjency matrix
what are some characteristics of adjacency matrix
how to build adjacency matrix
how to accept graph as an adjacency matrix
applications of adjacency matrix
some advantages and disadvantages of adjacency matrix
Implement DFS in C and accept graph as an adjacency matrix
include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
// Globally declared visited array
int vis[100];
// Graph structure to store number of vertices and edges and adjacency matrix
struct Graph {
int V;
int E;
int** Adj;
};
// Function to create and initialize the adjacency matrix for the graph
struct Graph* createGraph(int vertices) {
struct Graph* G = (struct Graph*)malloc(sizeof(struct Graph));
if (!G) {
printf(“Memory Error\n”);
return NULL;
}
G->V = vertices;
G->E = 0;
G->Adj = (int**)malloc(G->V * sizeof(int*));
for (int k = 0; k < G->V; k++) {
G->Adj[k] = (int*)malloc(G->V * sizeof(int));
for (int v = 0; v < G->V; v++) {
G->Adj[k][v] = 0; // Initialize adjacency matrix to 0
}
}
return G; }
// Function to add an edge to the graph
void addEdge(struct Graph* G, int u, int v) {
if (u >= 0 && u < G->V && v >= 0 && v < G->V) {
G->Adj[u][v] = 1;
G->Adj[v][u] = 1; // Undirected graph
G->E++;
} else {
printf(“Invalid vertices!\n”);
}
}
// DFS function to print DFS traversal of graph
void DFS(struct Graph* G, int u) {
vis[u] = 1;
printf(“%d “, u);
for (int v = 0; v < G->V; v++) {
if (!vis[v] && G->Adj[u][v]) {
DFS(G, v);
}
}
}
// Function for DFS traversal
void DFStraversal(struct Graph* G) {
for (int i = 0; i < G->V; i++) {
vis[i] = 0; // Reset visited array
}
for (int i = 0; i < G->V; i++) {
if (!vis[i]) {
DFS(G, i);
}
}
}
// Function to display the adjacency matrix
void displayAdjacencyMatrix(struct Graph* G) {
printf(“Adjacency Matrix:\n”);
for (int i = 0; i < G->V; i++) {
for (int j = 0; j < G->V; j++) {
printf(“%d “, G->Adj[i][j]);
}
printf(“\n”);
}
}
// Function to free the graph memory
void freeGraph(struct Graph* G) {
for (int i = 0; i < G->V; i++) {
free(G->Adj[i]);
}
free(G->Adj);
free(G);
}
// Driver code with menu
int main() {
struct Graph* G = createGraph(7);
int choice, u, v;
while (1) {
printf("\nMenu:\n");
printf("1. Add Edge\n");
printf("2. Display Adjacency Matrix\n");
printf("3. Perform DFS Traversal\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter vertices to add an edge (u v): ");
scanf("%d %d", &u, &v);
addEdge(G, u, v);
break;
case 2:
displayAdjacencyMatrix(G);
break;
case 3:
printf("DFS Traversal: ");
DFStraversal(G);
printf("\n");
break;
case 4:
freeGraph(G);
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0; }
doubly linked list, create insert and display operation
include<stdio.h></stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n");
printf("5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);</stdlib.h>
if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf(“\nNode inserted\n”);
}
}
void insertion_last()
{
struct node ptr,temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf(“\nOVERFLOW”);
}
else
{
printf(“\nEnter value”);
scanf(“%d”,&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}
}
printf("\nnode inserted\n");
} void insertion_specified() { struct node *ptr,*temp; int item,loc,i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) {
printf("\n OVERFLOW"); } else {
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n"); } } void deletion_beginning() {
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf(“\n UNDERFLOW”);
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf(“\nnode deleted\n”);
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf(“\nnode deleted\n”);
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf(“\n Enter the data after which the node is to be deleted : “);
scanf(“%d”, &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf(“\nCan’t delete\n”);
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf(“\nnode deleted\n”);
}
}
void display()
{
struct node *ptr;
printf(“\n printing values…\n”);
ptr = head;
while(ptr != NULL)
{
printf(“%d\n”,ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf(“\nEmpty List\n”);
}
else
{
printf(“\nEnter item which you want to search?\n”);
scanf(“%d”,&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf(“\nitem found at location %d “,i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf(“\nItem not found\n”);
}
}
}
WAP in C to implement dynamic implementation of queue of integers with following operation
initialize()
push()
pop()
isempty()
display()
include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
// Node structure for linked list
struct Node {
int data;
struct Node* next;
};
// Queue structure
struct Queue {
struct Node* front;
struct Node* rear;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to initialize the queue
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = NULL;
queue->rear = NULL;
return queue;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}
// Function to insert an element into the queue (enqueue)
void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}
// Function to remove an element from the queue (dequeue)
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf(“Queue is empty. Cannot dequeue.\n”);
return -1; // Return -1 to indicate queue is empty
}
struct Node* temp = queue->front;
int data = temp->data;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return data;
}
// Function to display the queue
void display(struct Queue* queue) {
if (isEmpty(queue)) {
printf(“Queue is empty.\n”);
return;
}
struct Node* temp = queue->front;
printf(“Queue elements: “);
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
// Main function with menu
int main() {
struct Queue* queue = createQueue();
int choice, data;
while (1) {
printf("\nMenu:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Check if empty\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to enqueue: ");
scanf("%d", &data);
enqueue(queue, data);
break;
case 2:
data = dequeue(queue);
if (data != -1) {
printf("Dequeued: %d\n", data);
}
break;
case 3:
display(queue);
break;
case 4:
if (isEmpty(queue)) {
printf("Queue is empty.\n");
} else {
printf("Queue is not empty.\n");
}
break;
case 5:
printf("Exiting...\n");
free(queue);
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0; }
WAP to implement static queue and perform this operations: init(),
insert(),
display(),
isfull()
include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
typedef struct {
int items[MAX];
int front;
int rear;
} StaticQueue;
// Function to initialize the queue
void init(StaticQueue *q) {
q->front = -1;
q->rear = -1;
printf(“Queue initialized.\n”);
}
// Function to check if the queue is full
int isfull(StaticQueue *q) {
return (q->rear + 1) % MAX == q->front;
}
// Function to insert an element into the queue
void insert(StaticQueue *q, int value) {
if (isfull(q)) {
printf(“Queue is full. Cannot insert %d.\n”, value);
return;
}
if (q->front == -1) { // If queue is empty
q->front = 0;
}
q->rear = (q->rear + 1) % MAX;
q->items[q->rear] = value;
printf(“Inserted %d into the queue.\n”, value);
}
// Function to display the elements of the queue
void display(StaticQueue *q) {
if (q->front == -1) {
printf(“Queue is empty.\n”);
return;
}
printf(“Queue elements: “);
int i = q->front;
while (1) {
printf(“%d “, q->items[i]);
if (i == q->rear) {
break;
}
i = (i + 1) % MAX;
}
printf(“\n”);
}
// Main function to drive the menu
int main() {
StaticQueue q;
int choice, value;
while (1) {
printf("\nMenu:\n");
printf("1. Initialize Queue\n");
printf("2. Insert Element\n");
printf("3. Display Queue\n");
printf("4. Check if Queue is Full\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
init(&q);
break;
case 2:
printf("Enter value to insert: ");
scanf("%d", &value);
insert(&q, value);
break;
case 3:
display(&q);
break;
case 4:
if (isfull(&q)) {
printf("Queue is full.\n");
} else {
printf("Queue is not full.\n");
}
break;
case 5:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0; }
Explain above program
StaticQueue Structure: This structure holds the queue items, the front index, and the rear index.
init(): Initializes the queue by setting the front and rear indices to -1.
isfull(): Checks if the queue is full.
insert(): Inserts an element into the queue if it is not full.
display(): Displays the elements in the queue.
Menu-driven Interface: The main() function provides a menu for the user to interact with the queue.
How to Compile and Run:
Copy the code into a file named static_queue.c.
Open a terminal and navigate to the directory where the file is saved.
Compile the code using gcc static_queue.c -o static_queue.
Run the program using ./static_queue.
You can then follow the on-screen menu to perform operations on the static queue.
