Data Structure (Sem-III) Model Answer Paper Dec 2022

Q1)

A) Linear and Non Linear Data Structures

B) Advantage of Circular Queue over Linear Queue.

Here are the advantages of circular queue over linear queue:

 Efficient use of memory: In a circular queue, when the rear pointer reaches the end of the queue, it wraps
around to the beginning, which allows for efficient use of memory compared to a linear queue.

 Easier for insertion-deletion: In the circular queue, if the queue is not fully occupied, then the elements
can be inserted easily in the vacant locations. But in the case of a linear queue, insertion is not possible
once the rear pointer reaches the last index even if there are empty locations present in the queue.

 Better performance: Circular queue offers better performance in situations where data is frequently
added and removed from the queue as compared to a linear queue.

 Simplified implementation: Implementing a circular queue is simpler as compared to a linear queue as it

requires less complexity and fewer conditional statements.

 Improved flexibility: With a circular queue, the front and rear pointers can move in either direction,
allowing for greater flexibility in implementing queue operations.

 Reduced overhead: Since a circular queue requires a fixed amount of memory, it reduces the overhead
of memory allocation and de allocation as compared to a dynamic data structure like a linked list-based
linear queue.
Function to insert element in circular queue

void insert (int item)

{
if(front == 0 && rear == (MAX - 1))
{
printf ("\nQueue is full");
}
else if(front == -1 && rear == -1)
{
front = 0 ;
rear = 0 ;
}
else if(rear == (MAX-1))
{
rear = 0 ;
}
else
{
rear++;
}
q[rear] = item ;

C) Deletion in binary search tree

Binary search tree (BST)

 A Binary Search Tree (BST) is a special type of tree where the value of the left child node’s always
less than the parent node and the value of the right child node is greater than the parent node.
 Commonly performed operations on binary search trees are searching, insertion, and deletion.
 Here, we see Delete operation in detail.

Delete Operation

 In a binary search tree, the Delete function is used to delete the specified node.
 But, delete a node from a binary search tree in such a way, that the property of the binary search tree
doesn't violate.
 To achieve this there are three methods for deleting a node from a binary search tree are used.

Method - 1: Deletion of A Node Having No Child (Leaf Node)

Method - 2: Deletion of A Node Having Only One Child Node

Method - 3: Deletion of A Node Having Two Children Nodes

 It is a quite complex method case compared to the other two methods.

 In this, the node which is to be deleted is replaced with its in-order successor or predecessor
recursively until the node to be deleted is replaced on the leaf of the tree.
 After this, replace the node with NULL and free the allocated space. Consider the following example
where the node with two child nodes whose value = 60 is deleted from the BST:

In-order Traversal Sequence of the following Tree is 15, 25, 30, 60, 65, 75, 85, 90, 95.
A node with two children can be deleted from the BST in the following two ways:
Way 1:

 Visit the right sub-tree of the deleting node.

 Take the least value node called the in-order successor node.
 Replace the deleting node with its in-order successor node.
 In this way take the node with value 65 which is the least valued in-order successor node of node 60
that is to be deleted.

Way 2:

 Visit the left sub-tree of the deleting node.

 Take the greatest value node called the in-order predecessor node.
 Replace the deleting node with its in-order predecessor node.
 In this way take the node with value 30 which is the greatest valued in-order predecessor node of the
node 60 that is to be deleted.

D) C function to search an element from DLL

void search_element()
{
int data,i=1;
struct node* temp;
printf("\nEnter data to search");
scanf("\n%d",&data);
temp = head;
while(temp != NULL) // Start traversing from head node
{
if(temp -> data == data)
{
printf("\nElement found at position %d",i);
break;
}
else
{
i=i+1;
temp = temp -> next;
}
}
if(temp==0)
printf("\n Element %d is not found in the list\n",data);
}

Q.2

A) Construct AVL Tree for following67, 34, 90, 22, 45, 11, 2, 78, 38, 122
B) Postfix Evaluation

Algorithm

1) Add ) to postfix expression.

2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
ii) B-> Next to Top element
iii) Evaluate B operator A
push B operator A onto Stack
5) Set result = pop
6) END

9 6 7 * 2 / - Following are the steps to solve the postfix expression

Q3.

A)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head,*tail;
int count = 1 ;
void createList(int n);
void insertEnd();
void del_from_beg();
void displayList();
void countEvenOdd();

int main()
{
int n, i;
printf("Enter total no of nodes\t");
scanf("%d",&n);
for (i=0; i<=n ; i++)
{
count++ ;
}

createList(n);
printf("\nThe nodes are\n");
displayList();

insertEnd();
printf("\nThe nodes are\n");
displayList();

del_from_beg();
printf("\nThe nodes after deleting first node\n");
displayList();
displayList();
countEvenOdd();

void createList(int n)
{
struct node *newnode;
int i;
head=0;

for(i=0;i<n;i++)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter new node");
scanf("%d",&newnode->data);
newnode->next=0;
if(head==0)
{
head=tail=newnode;
tail->next=head;
}
else
{
tail->next=newnode;
tail=newnode;
tail->next=head;
}
}
}

void insertEnd()
{
//Create new node
struct node *newNode, *temp;
newNode = (struct node*)malloc(sizeof(struct node));
printf("\n Enter data to insert at end\n");
scanf("%d",&newNode->data);
tail->next=newNode;
tail=newNode;
tail->next=head;
}

void del_from_beg()
{
struct node* temp;
temp = head; // bringing temp at starting
head=head->next; //link between head and second node
free(temp); //relese memory
tail->next=head;

void del_from_end()
{
struct node* temp,*prev;
temp=head;
while(temp -> next != head)
{
prev = temp;
temp = temp -> next;
}
prev -> next = head;
free(temp);

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("\nList is empty.");
}
else
{
temp = head;
while(temp -> next != head)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("%d\t", temp->data);
}
printf("Circular Print %d",tail->next->data);
}

void countEvenOdd()
{
struct node *temp;
int count=0,evencount=0,oddcount=0;
temp = head ;
while (temp->next!= head)
{
if(temp->data%2==0)
{
printf("\n%d is Even Number",temp->data);
printf("\tStored at %u",temp);
evencount++;
}
else
{
printf("\n%d is Odd Number",temp->data);
printf("\tStored at %u",temp);
oddcount++;
}
temp = temp->next ;
count++ ;

}
if(temp->data%2==0)
{
printf("\n%d is Even Number",temp->data);
printf("\tStored at %u",temp);
evencount++;
}
else
{
printf("\n%d is Odd Number",temp->data);
printf("\tStored at %u",temp);
oddcount++;
}
count++;
printf("\n");
printf("\nEven COUNT IS %d",evencount);
printf("\nOdd COUNT IS %d",oddcount);
printf("\nCOUNT IS %d",count);

}
B) C program to simulate Queue as linked List
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>

struct node
{
int data;
struct node*next;
};
struct node *front=0,*rear=0;

void enqueue(int n);

void dequeue();
void display();

int main()
{
int i=1,select,item;
while(i)
{
printf("\nMainMenu");
printf("\n1:ENQUEUE");
printf("\n2:DEQUEUE");
printf("\n3:DISPLAY");
printf("\n4:EXIT");

printf("\nEnteryourchoice");
scanf("\n%d",&select);

switch(select)
{
case 1:
printf("\nEnter the data to insert in the Queue from rear:");
scanf("\n%d",&item);
enqueue(item);
break;
case 2:
printf("\nDeletingfromthefront:");
dequeue();
break;
case 3:
printf("\nThelistis:");
display();
break;
case 4:
exit(0);
break;
default:
printf("\nInvalid Choice");
break;
}
printf("\n Do u want to contineu, please enter 1 or 0\n");
scanf("%d", &i);
}
return 0;
}

void enqueue(int n)
{
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=n;
newnode->next=0;
if(front==0&&rear==0)
{
front=rear=newnode;
}
else
{
rear->next=newnode;
rear=newnode;
}
}

void dequeue()
{
struct node *temp;
if(front==0&&rear==0)
{
printf("\nUnderflow");

}
else
{
temp=front;
printf("\nDeleted item is %d",front->data);
front=front->next;
free(temp);
}
}

void display()
{
struct node *temp;
temp=front;
if(front==NULL)
{
printf("\nUnderflow");
}
else
{
while(temp!=NULL)
{
printf("\t%d",temp->data);
temp=temp->next;
}
}}
Q4)

A) Huffman Tree

Step1) Arrange the frequencies in increasing order

Symbol g p r e i
Frequency 17 20 25 33 40

Combine g and P with lowest frequency Now lowest frequencies are 25 and 33
for r and e combine them

Final Codes are

r=00

e=01

g=100

p=101

i=11
B) Discuss various ways to represent graph in Memory

Following are ways to represent graph in Memory

Q.5
 Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for
every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph
is not possible if the graph is not a DAG.


Q.6

Depth-first Search

- The depth-first search algorithm in following graph progresses by expanding the starting node A of
graph and then going deeper and deeper until the goal node is found, or until a node that has no children is
encountered.

- When a dead-end is reached, the algorithm backtracks, returning to the most recent node that has not
been completely explored.

- Depth-first search begins at a starting node A which becomes the current node.

- Then, it examines each node N along a path P which begins at A.

- That is, we process a neighbor of A, then a neighbor of neighbor of A, and so on.

Algorithm for depth-first search-

 Step 1: SET STATUS=1(ready state) for each node in G

 Step 2: Push the starting node A on the stack and set its STATUS=2(waiting state)
 Step 3: Repeat Steps4 and 5 until STACK is empty
 Step 4: Pop the top node N. Process it and set its STATUS=3(processed state)
 Step 5: Push on the stack all the neighbors of node that are in the ready state (whose STATUS=1)
and set their STATUS=2(waiting state) [END OF LOOP]
 Step 6: EXIT

Adjacency list for Graph:

 A: B, C, D
 B: C, E
 C: E
 D: C, F
 E: A
 F: C
 G: D, F, H
 H: C

 Recursive Function:

void Graph::DFSUtil(int v, bool visited[]) {

visited[v] = true;

cout << v << " ";

// Recur for all the vertices adjacent // to this vertexlist<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFSUtil(*i, visited);

// DFS traversal of the vertices reachable from v.

// It uses recursive DFSUtil()

void Graph::DFS(int v)

// Mark all the vertices as not visited

bool *visited = new bool[V];

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

visited[i] = false;

// Call the recursive helper function

// to print DFS traversal

DFSUtil(v, visited);