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

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

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

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

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

5 سوال

56.

در گراف همبند بدون جهت G=(V,E) شامل n راس، اگر از هر راس BFS را اجرا کنیم، ارتفاع درخت BFS حداکثر 2 میشود. کدام گزینه در خصوص تعداد یال‌های این گراف درست است؟

$∣ E ∣ = Θ (n)$

$∣ E ∣ = Θ (n^{2})$

$∣ E ∣ = Ω (n lo g n)$

برای هر 2/ $n - 1 \leq i \leq n (n - 1)$ میتوان گرافی با i یال مثال زد که این ویژگی را داشته باشد.

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

57.

رشته A شامل n کاراکتر را در نظر بگیرید. میخواهیم این رشته را به یک رشته آینه‌ای تبدیل کنیم. اعمال مجاز، حذف یک کاراکتر یا درج یک کاراکتر در هرجای رشته است. حداقل چند عمل نیاز است تا اینکار انجام شود؟

( $\hat{A}$ رشته آینه‌ای A است و منظور از LCS و ED به ترتیب طول بزرگترین زیردنباله مشترک و فاصله ویرایشی (با فرض عمل‌های حذف، درج و جایگزینی) است)

$n - L CS (A, \hat{A})$

$n - E D (A, \hat{A})$

$L CS (A, \hat{A})$

ED(A,A^)

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

58.

فرض کنید در یک شبکه شار برای محاسبه شار از راس s به راس t از الگوریتم زیر استفاده کنیم.

شار عبوری از همه یال‌ها را صفر قرار میدهیم. در هر مرحله یک مسیر از s به t انتخاب میکنیم که یال‌های مسیر همچنان ظرفیت خالی داشته باشند. شار همه یال‌های این مسیر را به اندازه یکسان افزایش میدهیم طوری که حداقل یک یال مسیر ظرفیتش تکمیل شود. این کار را انقدر ادامه میدهیم تا چنین مسیری یافت نشود.

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

با شار بیشینه برابر است

حداقل به اندازه نصف شار بیشینه است

حداقل به اندازه یک چهارم شار بیشینه است

میتوان شبکه‌ای مثال زد که برای ان خروجی الگوریتم فوق کمتر از 0/0001 شار بیشینه باشد

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

59.

فرض کنید n بازه روی محور اعداد حقیقی داریم. میخواهیم بیشترین تعداد بازه را پیدا کنیم که با یکدیگر هم‌پوشانی نداشته باشند. برای بازه I فرض کنید c(I) برابر تعداد بازه‌هایی است که با I هم پوشانی دارند. برای حل این مسئله از الگوریتم حریصانه زیر استفاده میکنیم. در هر مرحله از بین بازه‌های باقی مانده بازه I را کهc(I) از همه کمتر است انتخاب و تمام بازه‌هایی که با آن همپوشانی دارند حذف میکنیم. اگر چند بازه وجود داشت که تعداد همپوشانی شان کمینه بود یکی را به دلخواه انتخاب میکنیم. کمترین n که الگوریتم حریصانه فوق لزوما جواب بهینه را تولید نمیکند در بین گزینه‌ها کدام است؟

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

60.

گراف وزن دار ، همبند و بدون جهت G با n راس را در نظر بگیرید. میخواهیم درخت پوشای کمینه را با استفاده از الگوریتم کروسکال در چه زمانی قابل پیاده سازی است؟

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

$O (n^{2})$

$O (n lo g n)$

$O (n)$

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