مبانی و ساختارهای داده در مهندسی کامپیوتر: روش جایگذاری برای حل روابط بازگشتی - کوییز

1. جایگذاری تابع بازگشتی در خود تابع
2. جایگذاری مقادیر ثابت پایه (base case)
3. جایگذاری مقادیر پارامتر ها در تابع
4. جایگذاری خروجی تابع در ورودی آن

گزینه صحیح: 1

توضیح: در روش جایگذاری، ما به طور مداوم تابع بازگشتی را در عبارات خود جایگزین می کنیم تا زمانی که به مقادیر ثابت پایه برسیم و بتوانیم یک الگوی کلی استخراج کنیم.

1. T(n) = T(n-1) + c
2. T(n) = T(n/2) + c
3. T(n) = 2T(n/2) + cn
4. T(n) = T(n-1) + n

گزینه صحیح: 4

توضیح: رابطه T(n) = T(n-1) + n با هر بار تکرار، یک مقدار خطی n به پیچیدگی اضافه می کند که منجر به پیچیدگی O(n^2) می شود، در حالی که سایر روابط پیچیدگی کمتری دارند.

1. صف (Queue)
2. پشته (Stack)
3. لیست پیوندی (Linked List)
4. درخت (Tree)

گزینه صحیح: 2

توضیح: پشته به دلیل ماهیت LIFO (Last-In, First-Out) خود، برای نگهداری فراخوانی های توابع بازگشتی و مقادیر میانی که باید به ترتیب معکوس بازیابی شوند، بسیار مناسب است.

1. زمانی که تعداد سطوح بازگشتی کم باشد.
2. زمانی که فرمول پیچیدگی نهایی به راحتی قابل استخراج باشد.
3. زمانی که روابط بازگشتی بسیار پیچیده و با چندین جمله باشند.
4. زمانی که مقادیر پایه (base cases) به سادگی قابل محاسبه باشند.

گزینه صحیح: 3

توضیح: وقتی رابطه بازگشتی شامل چندین جمله یا عبارات پیچیده باشد، استخراج یک الگوی کلی و قابل محاسبه با روش جایگذاری دشوار و زمان بر می شود.

1. این روش همواره پیچیدگی زمانی را به صورت دقیق محاسبه می کند.
2. این روش ممکن است نیاز به حدس زدن فرم کلی داشته باشد.
3. این روش برای روابط بازگشتی خطی مناسب نیست.
4. این روش نیازی به تعریف مقادیر پایه ندارد.

گزینه صحیح: 2

توضیح: اغلب در روش جایگذاری، پس از چند مرحله جایگذاری، نیاز داریم فرم کلی پیچیدگی را حدس بزنیم و سپس آن را با استقراء اثبات کنیم.

1. تحلیل حافظه (Space Complexity)
2. تحلیل زمانی (Time Complexity)
3. تحلیل انرژی (Energy Complexity)
4. تحلیل کارایی سخت افزار (Hardware Efficiency)

گزینه صحیح: 2

توضیح: هدف اصلی روش جایگذاری، تعیین نرخ رشد تعداد عملیات انجام شده توسط الگوریتم با افزایش اندازه ورودی است که همان تحلیل زمانی است.

1. T(n) = T(n-1) + c
2. T(n) = T(n-1) + T(n-2)
3. T(n) = 2T(n-1) + c
4. T(n) = T(n/2) + c

گزینه صحیح: 3

توضیح: رابطه T(n) = 2T(n-1) + c با هر مرحله، تعداد فراخوانی ها را دو برابر می کند که منجر به رشد نمایی $O(2^n)$ می شود. این مشابه فیبوناچی با دو فراخوانی است.