====== هفته بازار ======

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



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

  * [[سوال ۲|سوال بعد]]