طراحی الگوریتم

حل تشریحی سوالات طراحی الگوریتم - کنکور ارشد مهندسی کامپیوتر 1402

منوی آزمون (درس ها)

درباره آزمون زبان عمومی (انگلیسی)(10 سوال)زبان تخصصی (انگلیسی)(15 سوال)ریاضی عمومی ( 1 و 2 )(7 سوال)آمار و احتمال مهندسی(7 سوال)ریاضیات گسسته(6 سوال)نظریه زبان‌ها و ماشین‌ها(5 سوال)سیگنال‌ها و سیستم‌ها(5 سوال)ساختمان داده‌ها(6 سوال)طراحی الگوریتم(6 سوال)هوش مصنوعی(8 سوال)مدار منطقی(7 سوال)معماری کامپیوتر(7 سوال)الکترونیک دیجیتال(6 سوال)سیستم‌های عامل(7 سوال)شبکه‌های کامپیوتری(6 سوال)پایگاه داده‌ها(7 سوال)

سوالات طراحی الگوریتم

6 سوال

62.

یک ارایه دو بعدی $n \cdot n$ از اعداد داده شده است که هر سطر به صورت صعودی از چپ به راست و هر ستون به صورت صعدی از بالا به پایین مرتب شده است. کمترین پیچیدگی زمانی برای پیدا کردن یک عدد داده شده در این ارایه دوبعدی کدام است؟

$O (n lo g n)$

$O (lo g n)$

$O (n^{2})$

$O (n)$

مشاهده پاسخ ها

63.

یک الگوریتم یک ارایه دو بعدی $n \cdot n$ را به عنوان ورودی دریافت میکند و زمان اجرای ان برحسب n عبارت است از $T (n) = O (n lo g n)$ ، زمان الگوریتم بر حسب اندازه ورودی $m = n^{2}$ کدام است؟

$O (m^{2} lo g m)$

$O (m^{2} lo g^{2} m)$

$O (m lo g m)$

مشاهده پاسخ ها

64.

فرض کنید برای حل یک مسئله باید از بین چهار الگوریتم انتخاب کنید. کدام یک ارجحیت دارد؟

الگوریتم A نمونه‌ای به اندازه n را با حل بازگشتی بیست نمونه با اندازه $\frac{n}{3}$ حل میکند و سپس راه حل های انها را در زمان $O (n^{3})$ ترکیب میکنند.

الگوریتم B نمونه‌ای به اندازه n را با حل بازگشتی هشت نمونه با اندازه $\frac{n}{2}$ حل میکند و سپس راه حل های انها را در زمان $O (n^{3})$ ترکیب میکنند.

الگوریتم C نمونه‌ای به اندازه n را با حل بازگشتی دو نمونه با اندازه $2 \cdot n$ حل میکند و سپس راه حل های انها را در زمان $O (n)$ ترکیب میکنند.

الگوریتم D نمونه‌ای به اندازه n را با حل بازگشتی دو نمونه با اندازه $n - 1$ حل میکند و سپس راه حل های انها را در زمان ثابت ترکیب میکنند.

مشاهده پاسخ ها

65.

فرض کنید $A = [a_{1}, a_{2}, .. \dots\dots, a_{n}]$ ارایه‌ای از اعداد صحیح متمایز باشد و K یک عدد صحیح داده شده باشد. هدف این است که دو عدد متمایز از A را پیدا کنید که مجموع انها دقیقا K باشد، یا گزارش دهید که چنین عناصری وجود ندارد . یک الگوریتم کارا برای حل این مسئله چه زمانی خواهد داشت؟

$O (lo g n)$

$O (n)$

$O (n lo g n)$

$O (n^{2})$

مشاهده پاسخ ها

66.

الگوریتم مرتب سازی ادغام (megesort) را در نظر بگیرید. به جای اینکه ارایه ورودی را به دو قسمت تقریبا مساوی تقسیم کنیم، ان را به m بخش تقسیم میکنیم لزوما مساوی نیستند (m یک ثابت است.) سپس بصورت بازگشتی الگوریتم ادغام اصلاح شده را روی هر قسمت اجرا میکنیم و m ارایه مرتب شده را ادغام میکنیم . زمان اجرای الگوریتم ادغام اصلاح شده در حالتی که m>2 کدام است؟

O(mn)

O(m log n)

O(log log n)

O(n log n)

مشاهده پاسخ ها

67.

کدام یک از روابط بازگشتی زیر را نمی توان مستقیما با قضیه اصلی حل کرد؟

$T (n) = 16 T (\frac{n}{4}) + n$

$T (n) = T (\frac{n}{5}) + 20$

$T (n) = 3 T (\frac{n}{4}) + n lo g n$

$T (n) = 2 T (\frac{n}{2}) + n lo g n$

مشاهده پاسخ ها