Qn$3.$

$($a$).$ Suppose a queue implemented in a circular fashion is in the state shown in the diagram below. Draw a diagram showing the structure after the letters $G$ and $R$ are inserted, three letters are removed, and the letters $D$ and $P$ are inserted.

$($b$)$ What error occurs in part $($a$)$ if the letters G$,$ R$,$ D and $P$ are inserted before any letters are removed?

$($c$)$ Describe how an array could be used to implement a queue in a program written in a highlevel language.

$($d$).$ If the nested paraenthesis representation of a tree is as follows, then what is the graphical representation of the tree?

$(A(B(D))(C(E)(F(H)(I)(G)))(M))$

$($c$).$ From the algorithm below compute the total running time $T(n)$ using the cost and time to execute one statement of the algorithm.

For jlarr$2$ to Length $A$

do key larrA$[j]$

$//$ Insert $A[i]$ into the sorted sequence$/$

$.$

ilarrJ$-1$

While $i>0$ and $A[i]>$ key

Do $A[i+1]larrA[i]$

ilarri$-1$

$A[i+1]larr$ key

$[15$marks$]$