Solution: Attempt Any Five Out of Six. Each Question Carries 6 Marks

SOLUTION
Brought to you by
Data Structures Using C
Section – A
Attempt any five out of six.
Each question carries 6 marks.
Soln. 1:
(a)
Graphs are a non-primitive non-linear data structure
where a set of elements are connect by edges. Each
item/element is called a node or a vertex.
Formal Definition: A graph G can be defined as a pair
(V,E), where V is a set of vertices, and E is a set of edges
between the vertices E ⊆ {(u,v) | u, v ∈ V}. If the graph is
undirected, the adjacency relation defined by the edges
is symmetric, or E ⊆ {{u,v} | u, v ∈ V} (sets of vertices
rather than ordered pairs). If the graph does not
allow self-loops, adjacency is irreflexive.
Applications of graph:
1) Used in development of AI in finding shortest path
in games, GPS systems, etc.
2) Google uses graphs to search for web pages,
where pages on the internet are linked to each
other using hyperlinks.
3) On ecommerce websites, relationship graphs are
used to show recommendations.
(b)
int fact(int n)
{
If(n == 1 || n == 0)
return 1;
return (n*fact(n-1));
}
Soln. 2:
A(-2:2, 2:22)
B(1:8, -5:5, -10:5)
(i) First dimension of A has 2-(-2) = 4 elements and
second dimension has 22-2 = 20 elements. Total
number of elements in A = 4*20 = 80 elements
First dimension of B has 8-1 = 7 elements,

second dimension has 5-(-5) = 10 elements and
third dimension has 5-(-10) = 15 elements. Total
number of elements in B = 7*10*15 = 1050
elements.
(ii) Address of B[2][2][3]= BaseAddress +
((depthindex*col_size+colindex) * row_size +
rowindex) * Element_Size = 400 + ((2*7 +
2)*10+3)*4 = 1052
Soln. 3:
(a) Step 1: Add ‘)’ at the end of P.
Step 2: Scan P from left to right and repeat steps 3
and 4 for each element of P until ‘)’ in
encountered.
Step 3: If and operand is encountered, Push it onto
the STACK.
Step 4: If an operator is encountered, then
(a)Remove two elements from STACK where A is
TOP element and B is next to TOP element. (b)
Evaluate (B (operator) A). (c) Place result back
onto the STACK. e
Step 5: set VALUE := TOP element on STACK.
Step 6: Return.
(b) ab+cd+*f^
a = 3, b = 4, c = 2, d = 2, f = 1.
ab+cd+*f^)
3,4,+,2,2,+,*,f,^
SYMBOL STACK
3 3
4 3, 4
+ 7
2 7, 2
2 7, 2, 2
+ 7, 4
* 28
1 28, 1
^ 28
28 is the answer.
Soln. 4:
It is better than a normal queue because in this we can
effectively utilize the memory space. If we have a normal
queue and have deleted some elements from there then
empty space is created there and even if the queue has
empty cells then also we cannot insert any new element
because the insertion has to be done from one side only
(i.e. rear or tail) and deletion has to be done from
another side (i.e. front or head).But in case of circular
queue the front and rear are adjacent to each other.
Applications of queue:
1) When a resource is shared among multiple consumers.
Examples include CPU scheduling, Disk Scheduling.
2) When data is transferred asynchronously (data not
necessarily received at same rate as sent) between two
processes. Examples include IO Buffers, pipes, file IO, etc.
#define MAX 50
int queue_array[MAX];
int rear = - 1;
int front = - 1;
void main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /*End of while*/
} /*End of main()*/
Soln. 5:
23, 11, 37, 28, 15, 19, 55.9
Pass 1:
11, 23, 37, 28, 15, 19, 55.9
Pass 2:
11, 23, 37, 28, 15, 19, 55.9
Pass 3:
11, 23, 28, 37, 15, 19, 55.9
Pass 4:
11, 23, 28, 15, 37, 19, 55.9 -> 11, 15, 23, 28, 37, 19, 55.9
Pass 5:
11, 15, 23, 28, 19, 37, 55.9 -> 11, 15, 19, 23, 28, 37, 55.9
Pass 6:
11, 15, 19, 23, 28, 37, 55.9
Pass 7:
11, 15, 19, 23, 28, 37, 55.9
Soln. 6:
(a)
#include <stdio.h>
int main()
{
int m, n, p, q, c, d, k, sum = 0;
int first[10][10], second[10][10], multiply[10][10];
printf("Enter the number of rows and columns of

first matrix\n");
scanf("%d%d", &m, &n);
printf("Enter the elements of first matrix\n");
for (c = 0; c < m; c++)

for (d = 0; d < n; d++)
scanf("%d", &first[c][d]);
printf("Enter the number of rows and columns of

second matrix\n");
scanf("%d%d", &p, &q);
if (n != p)
printf("Matrices with entered orders can't be
multiplied with each other.\n");
else
{
printf("Enter the elements of second matrix\n");
for (c = 0; c < p; c++)

for (d = 0; d < q; d++)
scanf("%d", &second[c][d]);
for (c = 0; c < m; c++) {

for (d = 0; d < q; d++) {
for (k = 0; k < p; k++) {
sum = sum + first[c][k]*second[k][d];
}
multiply[c][d] = sum;
sum = 0;
}
}
printf("Product of entered matrices:-\n");
for (c = 0; c < m; c++) {

for (d = 0; d < q; d++)
printf("%d\t", multiply[c][d]);
printf("\n");
}
}
return 0;
}
Section – B
Attempt only two out of three.
Each question carries 10 marks.
Soln. 7:
(i) No.
(ii) No.
(iii) (9, (8, 6, 5), (7, 4))
(iv) Node 6
(v) Yes.
Soln. 8:
(a) A, C, D, F, K, _, _, _
A, C, D, F, _, _, _, _
A, C, D, _, _, _, _, _
A, C, _, _, _, _, _, _
A, C, R, _, _, _, _, _
A, C, R, L, _, _, _, _
A, C, R, L, S, _, _, _
A, C, R, L, S, P, _, _
A, C, R, L, S, _, _, _
(b) void del_beg()
{
struct node *temp;
temp = start;
start = start->next;
free(temp);
printf("nThe Element deleted Successfully ");
}
Soln. 9:
J, R, D, G, T, E, M, H, P, A, F, Q
(i)
(ii) Inorder: A, D, E, F, G, H, J, M, P, Q, R, T
Preorder: J, D, A, G, E, F, H, R, M, P, Q, T
Postorder: A, E, F, H, G, D, M, P, Q, T, R, J
Section – C
(Compulsory)
(a) (i) An algorithm is analyzed on the basis of its
space and time complexity.
(ii)
(b)
V1  V2, V3, V1
V2  V4, V5, V1
V3  V6, V7
V4  V8, V2
V5 V8, V2
V6 V8, V3
V7 V8, V3
V8  V4, V5, V6, V7
BFS Algorithm:
Step 1 − Visit the adjacent unvisited vertex. Mark it

as visited. Display it. Insert it in a queue.
Step 2 − If no adjacent vertex is found, remove the

first vertex from the queue.
Step3 − Repeat Rule 1 and Rule 2 until the queue
is empty.
CURRENT = V7
QUEUE = V3, V8
OUTPUT = V7
CURRENT = V3
QUEUE = V8, V1, V6
OUTPUT = V7, V3
CURRENT = V8
QUEUE = V1, V6, V4, V5
OUTPUT = V7, V3, V8
CURRENT = V1
QUEUE = V6, V4, V5, V2
OUTPUT = V7, V3, V8, V1
CURRENT = V6
QUEUE = V4, V5, V2
OUTPUT = V7, V3, V8, V1, V6
CURRENT = V4
QUEUE = V5, V2
OUTPUT = V7, V3, V8, V1, V6, V4
CURRENT = V5
QUEUE = V2
OUTPUT = V7, V3, V8, V1, V6, V4, V5
CURRENT = V2
QUEUE =
OUTPUT = V7, V3, V8, V1, V6, V4, V5, V2
--------x--------

Solution: Attempt Any Five Out of Six. Each Question Carries 6 Marks

Uploaded by

Copyright:

Available Formats

Solution: Attempt Any Five Out of Six. Each Question Carries 6 Marks

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Solution: Attempt Any Five Out of Six. Each Question Carries 6 Marks

Uploaded by

Copyright:

Available Formats

SOLUTION

Data Structures Using C

First dimension of B has 8-1 = 7 elements,

printf("Enter the number of rows and columns of

for (c = 0; c < m; c++)

printf("Enter the number of rows and columns of

for (c = 0; c < p; c++)

for (c = 0; c < m; c++) {

printf("Product of entered matrices:-\n");

for (c = 0; c < m; c++) {

Step 1 − Visit the adjacent unvisited vertex. Mark it

Step 2 − If no adjacent vertex is found, remove the

You might also like