Practise Numericals

Here are few examples that will help you to prepare for any Data Structure Examination

Sorting Based Example

Bubble sort is used to sort the series. Each pass (iteration) of bubble sort will work as follows:

Take an array of numbers ” 5 1 4 2 8“, after first pass the sequence will be “1 4 2 5 8”

Explanation as follows: Sequence of First Pass can be found as follows

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5).

Question: Apply Bubble sort on the following sequence to sort

write only the state of an array after each pass (make sure that algorithms behaves in adaptive manner)

Solution : the sorting is shown in following steps (click for video explanation)

Array	3	5	8	4	1	6	12	9
1st Pass	3	5	4	1	6	8	9	12
2^nd Pass	3	4	1	5	6	8	9	12
3^rd Pass	3	1	4	5	6	8	9	12
4^th Pass	1	3	4	5	6	8	9	12
5^th Pass	1	3	4	5	6	8	9	12
6^th Pass
7^th Pass

Note : Since algorithm is adaptive, therefore it exits after 5th pass once the array becomes sorted. For non-adaptive algorithm it will iterate all 7 passes in which pass 6 and pass 7 will have same ordering of data as pass 5.

Question: Apply selection sort on the following sequence to arrange the numbers in ascending order.

10	17	6	2	20
2	17	6	10	20
2	6	17	10	20
2	6	10	17	20
2	6	10	17	20
2	6	10	17	20

Problems on Linked List

Question : Consider the following list1 and list2 as shown below. Combine the two list as shown, make sure that the cost of combining the two list should be constant [i.e. 0(1)].

Solution Following are the key statements (main logic) to get the desired list.

cur = Last1->next; ( curr now point to node with data value 3)
Last1->next = Last2->next; ( node value 9 in list1 will point to node value 33 in list 2)
Last2->next = cur; (last node of list 2 now connect to first node of list 1, hence making circular list)

Alternatively, we can also use the following

Node *next1 = last1->next; Node *next2 = last2->next;
last1->next = next2; last2->next = next1;

Question : Write the logic to combine the two given list as shown below. Also comment on the cost of operations performed

Solution

last1= Start;
while(last1 ->next!=NULL) { last1 = last1->next; }
last1->next = head; head->prev = last1;

Note : the time complexity is O(n) due to while loop that goes n-times, where n is the number of nodes in first list.

Problems on Stack

Question : Consider the following stack, where STACK is allocated N=6 memory cells

STACK: AAA , DDD, EEE, FFF, GGG ( this is present status of stack, AAA is the top element)

Describe the stack as the following operations take place:

PUSH(KKK), POP( ), PUSH(LLL), PUSH(SSS), POP( ), PUSH(TTT)

Solution The first element in the sequence represent Top element

Operation	STACK	Comment (if any)
	AAA , DDD, EEE, FFF, GGG
PUSH(KKK)	KKK, AAA , DDD, EEE, FFF, GGG
POP( )	AAA , DDD, EEE, FFF, GGG
PUSH(LLL)	LLL, AAA , DDD, EEE, FFF, GGG
PUSH(SSS)	LLL, AAA , DDD, EEE, FFF, GGG	OVERFLOW
POP( )	AAA , DDD, EEE, FFF, GGG
PUSH(TTT)	TTT, AAA , DDD, EEE, FFF, GGG

Question: Convert the following INFIX expressions to their PREFIX equivalents

Q1 – (A * B) + (C / D) – (D + E)
Q2 – (A – B) + D / ((E + F) * G)
Q3 – (A – 2 * (B + C) / D * E) + F

Step by step execution and status of STACK is as follows

Solution -1 (click for video explanation)

Using Method-1 (*(A B) + (C / D) – (D + E)**
Char	Stack	Expression
)	), )
E	), )	E
+	), ), +	E
D	), ), +	ED
(	)	ED +
–	), –	ED +
)	), -, )	ED +
D	), -, )	ED + D
/	), -, ), /	ED + D
C	), -, ), /	ED + DC
(	), –	ED + DC /
+	), -, +	ED + DC /
)	), -, +, )	ED + DC /
B	), -, +, )	ED + DC / B
*	), -, +, ), *	ED + DC / B
A	), -, +, ), *	ED + DC / BA
(	), -, +	ED + DC / BA *
(		*– + A B / C D + D E** (on reversing)

Solution –2

Using Method-1((A – B) + D / ((E + F) * G)
Char	Stack	Expression
)	), )
G	), )	G
*	), ), *	G
)	), ), *, )	G
F	), ), *, )	GF
+	), ), *, ), +	GF
E	), ), *, ), +	GFE
(	), ), *	GFE +
(	)	GFE + *
/	), /	GFE + *
D	), /	GFE + * D
+	), +	GFE + * D /
)	), +, )	GFE + * D /
B	), +, )	GFE + * D / B
–	), +, ), –	GFE + * D / B
A	), +, ), –	GFE + * D / BA
(	), +	GFE + * D / BA –
(		GFE + * D / BA – +
Ans	on reversing	*+ – A B / D + E F G**

Solution –3

*((A – 2 (B + C) / D * E) + F**
Char	Stack	Expression
F	)	F
+	), +	F
)	), +, )	F
E	), +, )	FE
*	), +, ), *	FE
D	), +, ), *	FED
/	), +, ), *, /	FED
)	), +, ), *, /, )	FED
C	), +, ), *, /, )	FEDC
+	), +, ), *, /, ), +	FEDC
B	), +, ), *, /, ), +	FEDCB
(	), +, ), *, /	FEDCB +
*	), +, ), , /,	FEDCB +
2	), +, ), , /,	FEDCB + 2
–	), +, ), –	FEDCB + 2 * / *
A	), +, ), –	FEDCB + 2 * / * A
(	), +	FEDCB + 2 * / * A –
(		*+ – A / * 2 + BCDEF**

Question : Evaluate the PREFIX expressions [ – + * A B / C D + D E ] using stack

[assume A=2, B=3, C=2, D=4, E=3, F=2, G=3]

Solution-1:– step by step using STACK (click for video explanation)

*[- + A B / C D + D E] è – + * 2 3 / 2 4 + 4 3**
Char	Stack	Operation
3	3
4	3, 4
+	7	4 + 3 = 7
4	7, 4
2	7, 4, 2
/	7, 0	2 / 4 = 0
3	7, 0, 3
2	7, 0, 3, 2
*	7, 0, 6	2*3=6
+	7, 6	6+0
–	-1	6-7=-1

Solution-2 step by step using STACK

*[+ – A B / D + E F G] è + – 2 3 / 4 * + 3 2 3**
Char	Stack	operation
3	3
2	3, 2
3	3, 2, 3
+	3, 5	3 + 2 = 5
*	15	5 * 3 = 15
4	15, 4
/	0	4 / 15 = 0
3	0, 3
2	0, 3, 2
–	0, -1	2 – 3 = -1
+	-1	-1 + 0 = -1

Question : Convert the following INFIX expressions to their POSTFIX equivalents

Evaluate the POSTFIX expression 2 3 * 2 4 / + 4 3 + –

Problems on Queues

Question : Demomstrate the ENQUEUE/DEQUEUE operations on a Circular queue with size (N = 5). Show the status of Rear & Front after every operation

Question : Demomstrate the ENQUEUE/DEQUEUE operations on a Circular queue with size (N = 5). Show the status of Rear & Front after every operation