Answer any $4$ Questions each question is $15$ Marks

Qn$1.$

$($a$)$ i$.$ What is a linear list?

ii$.$ Distinguish between linear list and circular linked list.

$($b$)$ With the aid of diagrams

i$.$ Write an algorithm to delete the Kth element in the list.

ii$.$ Write an algorithm to insert an element $Y$ immediately after the $K$ th element.

$($c$)$ Using the Stack and the Queue structures explain the LIFO and FIFO principle in data management.

$($d$).$ Explain the statement "the time taken by an algorithm grows with the size of the input" $[15$marks$]$

$Q2.$

$($a$).$ What are the advantages of the data structure Queue? What type of data structure would you recommend for storing data?.

$($b$)$ With the help of diagrams explain the Heap data structure. Use that same diagram to explain

i$.$ max $-$ heap

ii$.$ min $-$ heap

$($c$).$ Draw a complete binary tree with exactly $7$ nodes. Put different values in each node. Then draw an array with $7$ elements and show where each of the $7$ node value would be placed in the array $($using the usual array representation of a complete binary tree$).$

$($d$).$ Distinguish between the worst$-$case and the average$-$case running time and the factors that affect the running time of an algorithm.

$[15$marks$]$