Question $1$

Imagine we have a circular doubly$-$linked list with a sentinel node. The linked list node is a struct with three fields: word, a string, and two pointers named forw and back. The C$\_$D$\_$List class has two data members: a pointer to the first node, named head, and a counter named cnt$.$

Write a member function of the C$\_$D$\_$List class that checks if the list is a palindrome sentence. You may assume that all words are in lower case. See a calling statement below:

bool isPal $=$ list.checkPal$()$;

For instance, the function returns true if the list contains:

SENTINEL, "king", "are", "you", "glad", "you", "are", "king".

Question $2$

The purpose of the following algorithm is to display a queue:

loop $(!$que.isEmpty$())$

item $=$ que.pop$()$

print $($item$)$

end loop

Now the queue is empty. The following algorithm intends to solve the "empty after printing the queue" problem, but it is incorrect. Why? How would you fix it$?$

loop $(!$que.isEmpty$())$

item $=$ que.pop$()$

print $($item$)$

que.push$($item$)$

end loop

Question $3$

What is wrong with the following recursive algorithm?

algorithm getScore $()$

read$($ score $)$

if$($ score $<0||$ score $>100)$

print$\_$Instructions$()$

getScore$()$

end if

return score

end getScore

Question $4$

A classmate wrote the following implementation of one of the stack functions and asks your opinion$/$advice about it$.$ What advice would you give to your classmate? Justify your answer. Hint: Are any advantages$/$disadvantages compared to your implementation of the same function? Which one of the stack functions is guess?

template

bool Stack::guess$($T &item$)$

$\{$

StackNode $*$temp;

if $($length $==0)$

return false;

item $=$ top$->$value;

temp $=$ top$->$next;

delete top;

top $=$ temp;

length$--$;

return true;

$\}$