$4.$a

For the "Set" abstract data type, what is the $)$ complexity to add an element and the $)$ complexity to remove an element? Explain your answers.

$[4$ marks$]$

$4.$b

You are given four numbers $(n_1,n_2,n_3,$ and $($:$n_4\}.$ They are added in this order into a stack. Then you remove all four of them from the stack. You then take the same four numbers $($in the original order$)$ and add them to a queue. Then you remove all four of them from the queue. Give one example of four numbers $($i$.$e$.$ with actual values$)$ where the two ordered sequences $($the one removed from the stack and the one removed from the queue$)$ give the same values.

$[4$ marks$]$

$4.$c

Consider the directed graph $G$ shown below:

i$.$ State whether $G$ is non$-$connected, weakly connected, or strongly connected. Explain your answer.

$[2$ marks$]$

ii$.$ How many nodes of $G$ have the same in$-$degree and out$-$degree? Explain your answer.

$[2$ marks$]$

iii. What is the density of $G?$ Explain your answer.

$[2$ marks$]$

iv$.$ Write down the order in which the nodes are visited during depth$-$first traversal, starting at node $0.$ Include the symbol uarr wherever the traversal is forced to back up to a previous node. You can assume that adjacent nodes are selected in increasing order of their value.

$[4$ marks$]$

$4.$d

This question is about the

This question is about the ${?}^r$

i$.$ What is the sequence of nodes visited by the in$-$order traversal?

$[2$ marks$]$

ii$.$ How many values of $"1"$ are there in the array for the "parent vector" representation of this tree?

$[2$ marks$]$

iii. Give a tree with a post$-$order traversal sequence of nodes that is the same as the sequence you have from part $($i$).$

$[3$ marks$]$

$[$Total $25$ marks$]$

$---$End of Paper$---$