| ۲۱ |
در الگوریتم “Merge Sort”، پیچیدگی زمان در بدترین حالت برابر است با |
A) O(n log n) <br> B) O(n²) <br> C) O(n) <br> D) O(log n) |
A |
تقسیم به دو زیرآرایهٔ تقریباً برابر → رابطه T(n)=2T(n/2)+O(n) → O(n log n). |
| ۲۲ |
کدام تکنیک تقسیموحل (divide‑and‑conquer) برای یافتن بزرگترین زیرآرایهٔ با مجموع بیشینه (Maximum Subarray) استفاده میشود؟ |
A) Kadane’s algorithm <br> B) الگوریتم پیشرو‑پسگرد (forward‑backward) <br> C) ترکیبی از دو نیمه <br> D) الگوریتم شطرنج |
C |
حل برای دو نیمه، سپس ترکیب (cross‑mid) که O(n) زمان میگیرد. |
| ۲۳ |
در الگوریتم “KMP” برای جستجوی الگو، پیشپردازش الگو (پیشوند‑پسوند) چه زمانی انجام میشود؟ |
A) هر بار قبل از مقایسه جدید <br> B) فقط یکبار قبل از شروع جستجو <br> C) پس از هر تطبیق موفق <br> D) هرگز |
B |
پیشپردازش (محاسبهٔ LPS) یکبار قبل از اسکن متن انجام میشود. |
| ۲۴ |
زمان متوسط برای جستجوی عنصر در یک جدول هش با زنجیر کردن که طول متوسط زنجیره ≤ 3 باشد، چقدر است؟ |
A) O(1) <br> B) O(log n) <br> C) O(3) <br> D) O(n) |
A |
متوسط ثابت → O(1). |
| ۲۵ |
در الگوریتم “Dijkstra” با استفاده از صف اولویت دودویی (binary heap) هزینه کل زمان برای گرافی با V راس و E یال چیست؟ |
A) O(V log V + E) <br> B) O((V+E) log V) <br> C) O(V²) <br> D) O(E log V) |
B |
هر استخراج min O(log V) و هر به‑روزرسانی O(log V) → مجموع (V+E) log V. |
| ۲۶ |
در الگوریتم “Floyd‑Warshall” برای یافتن کوتاه ترین مسیرهای تمامبهتمام، حافظهٔ مصرفی چقدر است؟ |
A) O(V) <br> B) O(V log V) <br> C) O(V²) <br> D) O(V³) |
**C |
نیاز به ماتریس فاصله V×V. |
| ۲۷ |
برای حل مسألهٔ “Travelling Salesman Problem” (TSP) به صورت Exact با n شهر، زمان اجرای حالت‑دینامیک زیر چه مقدار است؟ |
A) O(2ⁿ·n) <br> B) O(n log n) <br> C) O(n²) <br> D) O(n!) |
A |
DP بر پایهٔ زیرمجموعهها: O(2ⁿ·n). |
| ۲۸ |
در الگوریتم “Rabin‑Karp” برای جستجوی الگو، تابع هش پایهٔ چه ویژگیای باید داشته باشد تا تصادفیسازی بهخوبی انجام شود؟ |
A) وابستگی به طول الگو <br> B) استفاده از عدد اول بزرگ <br> C) عدم وجود تصادم <br> D) وابستگی خطی به جدول ASCII |
B |
انتخاب مدول (پران) یک عدد اول بزرگ (مثلاً ۱٬۰۰۰٬۰۰۳) کمک میکند تصادم کم شود. |
| ۲۹ |
در الگوریتم “Prim” برای درخت پوشای کمینه (MST)، استفاده از heap دودویی باعث میشود زمان کلی برابر باشد با |
A) O(E log V) <br> B) O(V log E) <br> C) O(V²) <br> D) O(E + V log V) |
A |
در هر قدم استخراج کمینه O(log V) و به‑روزرسانی حداکثر E بار. |
| ۳۰ |
در حل مسألهٔ “Longest Common Subsequence” (LCS) با دو رشتهٔ طول n و m، زمان و حافظهٔ مورد نیاز کدام است؟ |
A) O(n + m) زمان، O(min(n,m)) حافظه <br> B) O(n·m) زمان، O(n·m) حافظه <br> C) O(n·m) زمان، O(min(n,m)) حافظه <br> D) O(n log m) زمان، O(m) حافظه |
C |
DP جدول n·m → زمان O(nm). با بهینهسازی دو سطر میتوان حافظه O(min(n,m)) را داشت. |
| ۳۱ |
کدام روش برای حل مسألهٔ “Subset Sum” (جمع زیرمجموعه) به صورت تقریبی (FPTAS) استفاده میشود؟ |
A) الگوریتم حریصانه <br> B) دینامیک برنامهریزی با مقیاسبندی مقادیر <br> C) روش بازگشتی <br> D) بهینهسازی خطی |
B |
مقیاسبندی عددها (تقریب) بهمنظور کاهش حالتها؛ زمان پلینومیک در 1/ε. |
| ۳۲ |
در الگوریتم “Karatsuba” برای ضرب اعداد بزرگ، پیچیدگی زمان برابر است با |
A) O(n²) <br> B) O(n^{log₂3}) <br> C) O(n log n) <br> D) O(n) |
B |
T(n)=3T(n/2)+O(n) → n^{log₂3} ≈ n^{1.585}. |
| ۳۳ |
زمان متوسط برای پیدا کردن یک ریشهٔ نامستقیم (non‑leaf) در Heap‑Sort چیست؟ |
A) O(1) <br> B) O(log n) <br> C) O(n) <br> D) O(n log n) |
A |
دسترسی به ریشه (المان اول) O(1). |
| ۳۴ |
در الگوریتم «BFS» برای گراف بدون وزن، چه اطلاعاتی برای بازسازی مسیر کوتاهترین از منبع به مقصد نیاز است؟ |
A) فاصلهٔ هر گره <br> B) پیشنویس (predecessor) برای هر گره <br> C) مرتبهٔ بازدید <br> D) همه موارد |
D |
برای بازسازی مسیر نیاز به پیشنویس (parent) و همچنین فاصله (سطح) برای صحت. |
| ۳۵ |
در روش «Backtracking» برای مسألهٔ N‑Queens، پرش (prune) بر پایهٔ چه معیاری انجام میشود؟ |
A) سطرهای خالی <br> B) ستونهای اشغال شده <br> C) قطرهای اصلی و فرعی <br> D) همه موارد |
D |
هر سه (ستون، قطر اصلی، قطر فرعی) برای حذف حالتهای ناسازگار استفاده میشود. |
| ۳۶ |
در الگوریتم «A*** (A star) برای مسیریابی، تابع هزینهی هورستیک (heuristic) باید چه ویژگیهایی داشته باشد؟ |
A) همگرا (consistent) <br> B) دقیق (admissible) <br> C) همزمان هم دقیق و هم همگرا <br> D) هیچکدام |
C |
برای تضمین پیدا کردن مسیر بهینه، هورستیک باید هم admissible (بهاصل کمتر) و هم consistent باشد. |
| ۳۷ |
پیچیدگی زمان الگوریتم «Counting Sort» برای اعداد در بازهٔ [0, k] چیست؟ |
A) O(n log n) <br> B) O(n + k) <br> C) O(k log k) <br> D) O(n²) |
B |
زمان خطی نسبت به ورودی و دامنه: O(n + k). |
| ۳۸ |
در الگوریتم «Topological Sort» (Kahn) برای گراف جهتدار بدون دور، اگر گراف دارای چندین ترتیب ترکیبی باشد، نتایج خروجی چگونه خواهد بود؟ |
A) همیشه یک ترتیب یکتا <br> B) ممکن است هر ترتیب معتبر باشد <br> C) فقط ترتیب معکوس BFS <br> D) None |
B |
الگوریتم هر راس با درجهٔ ورودی صفر را میتواند به ترتیب دلخواه انتخاب کند؛ بنابراین ممکن است چندین خروجی معتبر تولید شود. |
| ۳۹ |
الگوریتم «Patience Sorting» برای پیدا کردن طول LIS (Longest Increasing Subsequence) چه زمان تعدیلپذیری دارد؟ |
A) O(n log n) <br> B) O(n²) <br> C) O(log n) <br> D) O(n) |
A |
ساخت دستهها با جستجوی باینری O(log n) برای هر عنصر → O(n log n). |
| ۴۰ |
در الگوریتم «Binary Search» روی آرایهٔ مرتب، اگر بهطور تصادفی یک عنصر موجود را جستجو کنید، آیا زمان متوسط متفاوت از بدترین حالت است؟ |
A) بله، متوسط O(log n) و بدترین O(n) <br> B) بله، متوسط O(1) <br> C) خیر، هر دو O(log n) <br> D) خیر، هر دو O(n) |
C |
Binary Search در تمام موارد زمان log n دارد؛ حتی در بدترین حالت. |