A.1

1), 2)

f2 w: n (C), b: 1 (A)
f3 w: n (C), b: n (C) 
f4 w: lg n (B), b: lg n (B)
f1 w: n^2 (E), b: n^2 (E) 
f5 w: n (C), b: n (C)

A.2

3) Actually all three solutions are correct for this particular tree,
but perfect is the most precise description. In general, heaps correspond
to complete trees. Such trees may be perfect or full, but not
necessarily. In case of ambiguities such as here, more information is 
sent to the students during the exam.

4) min priority queue

5) 4 9 8 100 12 14 13

6) 4 9 8 10 12 14 13 100

7) 8 9 13 10 12 14 100


A.3

8) 12 3 1 \ 2 \\ 11 7 5 4 \\ 6 \\ 9 8 \\ 10 \\ \ 13 \ 14 \ 15 \\

9) 2 1 4 6 5 8 10 9 7 11 3 15 14 13 12

10) 12 3 1 \ 2 \\ 11 7 5 4 \\ 6 \\ 9 \ 10 \\ \ 13 \ 14 \ 15 \\

11) 1 \ 3 2 \\ 12 11 7 5 4 \\ 6 \\ 9 8 \\ 10 \\ \ 13 \ 14 \ 15 \\ 


A.4

12)  A C B I G F E H D

13) A B G D F H I E C 

14) A B C D E G I F H 

Part B:

B.1.

15) yes

16) no

17) yes

18) yes

19) no

20) no


B.2.

use: 
"read" for "read and print"
"insert" for "read and insert"
"remove" for "remove and print"

21) yes:

X Y U V W ---> X U W V Y

print(X) insert(Y) print(U) insert(V) print(W)  remove(V) remove(Y)

22)

no:

X Y U V W ---/---> Y U W X V

insert(X) print(Y) print(U) insert(V) print(W) print(X) print(V)

However print(X) can only be printed after V.

B.3.

23)

double evaluate(const vector<double> &p, double x) {
   double sum = 0.0;

   for (int i = 0; i <= p.size(); i++) {
      double term = p[i];
      
      for (int j = 0; j < i; j++) {
         term *= x;
      }

      sum += term;
   }
   return sum;
}


24)

double evaluate(const vector<double> &p, double x) {
   double sum = 0.0;
   double xi = 1.0;  // Initialized to x^0

   for (int i = 0; i <= p.size(); i++) {
      
      sum += p[i] * xi;

      xi *= x;
   }
   return sum;
}