$($a$)$ Which of the following abstract data types can be efficiently implemented using a

singly or doubly linked list?

$$ Symbol table

Queue

$$ Stack

Priority Queue

$($b$)$ Which of the following claims about the heap are true?

A heap always corresponds to a perfect liglree.

$$ A heap is usually implemented using an array.

In a maximum$-$oriented heap, the order of the elements is always clearly

defined.

In a maximum$-$oriented heap, the largest element always corresponds to the

root of the corresponding ligtree.

$($c$)$ Which of the following statements about symbol tables are true?

$$ There is no data structure that guarantees logarithmic runtime $($in the worst

case$)$ for searching, inserting and deleting a value.

$$ Key types must fulfill an ordering relation so that they abe used as keys

for a binary search tree.

$$ The average number of operations to search for a key in a hash table is

constant.

$$ The search in a binary search tree requires $O(n)$ comparisons in the worst

case.

$($d$)$ Which of the following trees are good chand black trees?

a$)$

b$)$

c$)$

d$)$