Heaps

Single correct

• A82, 90, 101
• B82, 11, 93
• C131, 11, 93
• D131, 111, 90

Single correct

• A53
• B52
• C27
• D1

Single correct

• ABoth Extract-Max(A) and Insert(A,key) run in $O(1)$.
• BBoth Extract-Max(A) and Insert(A,key) run in $O(\log(n))$.
• CExtract-Max(A) runs in $O(1)$ whereas Insert(A,key) runs in $O(n)$.
• DExtract-Max(A) runs in $O(1)$ whereas Insert(A,key) runs in $O(\log(n))$.

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• AI, II and III
• BI, II and IV
• CI, III and IV
• DII, III and IV

Numerical answer

Single correct

• A$O(1)$
• B$O(d)$ but not $O(1)$
• C$O(2^d)$ but not $O(d)$
• D$O(d\,2^d)$ but not $O(2^d)$

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• A40, 30, 20, 10, 15, 16, 17, 8, 4, 35
• B40, 35, 20, 10, 30, 16, 17, 8, 4, 15
• C40, 30, 20, 10, 35, 16, 17, 8, 4, 15
• D40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Single correct

• A$\Theta(1)$
• B$\Theta(\sqrt{\log n})$
• C$\Theta\left(\dfrac{\log n}{\log \log n}\right)$
• D$\Theta(\log n)$

Answer key coming soon