هفته بازار

در هر یک از موارد زیر، درستی یا نادرستی عبارت ذکر شده را مشخّص کنید و دلیل خود را به‌دقّت توضیح دهید.

1. پیدا کردن عنصر بیشینه در یک Min-Heap از زمان $\Omega(\log n)$ است.
2. بنابر قضیه‌ی اصلی، جواب رابطه‌ی بازگشتی $T(n) = 4T(\frac{n}{5}) + \log(n!)$ برابر است با $T(n) = \Theta(n\log n)$.
3. یک Heap با $n$ عنصر را می‌توان در زمان $O(n)$ به‌یک درخت دودویی جستجو تبدیل کرد.
4. عدد ثابتی مانند $n_0 \geq 1$ وجود دارد که برای هر $n \geq n_0$، آرایه‌ای به طول $n$ وجود داردکه روی آن آرایه، الگوریتم Insertion Sort سریع‌تر از Merge Sort عمل می‌کند.
5. برای گراف وزن‌دار $G = (V, E)$، درخت $M$ یک زیردرخت فراگیر کمینه است، اگر و فقط اگربرای هر دو رأس دلخواه $v_1$ و $v_2$، وزن مسیر بین آن دو در $M$، کمینه‌ی وزن مسیرهای بین آن دو در $G$ باشد.
6. یک درخت قرمز-سیاه با ۱۰۲۴ گره، حداقل یک گره‌ی قرمز دارد.
7. عمل درج در درخت قرمز-سیاه دارای خاصیت جابه‌جایی است. بدین معنی که درج عنصر $x$ و سپس عنصر $y$ همان‌ درختی را ایجاد می‌کند که درج $y$ و سپس $x$ می‌سازد.