پرلایک
صفحه اصلی
تست لایک
کنکور دکتری
دکتری مهندسی و علم کامپیوتر
طراحی الگوریتم

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

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

درباره آزمونساختمان داده(10 سوال)طراحی الگوریتم(10 سوال)سیستم‌های عامل پیشرفته(15 سوال)پایگاه داده پیشرفته(10 سوال)

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

10 سوال
11.

در درخت میانوندی داده شده، مقدار هر برگ می‌تواند صفر یا یک باشد. ماکزیمم خروجی این عبارت کدام است؟

1)

2

2)

3

3)

4

4)

6

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

می‌دانیم ترتیب شروع و پایان فعالیت‌های H و G و F و E و D و C و B و A از چپ به راست به‌صورت است. در اینجا زمان شروع و زمان پایان فعالیت X می‌باشد. می‌خواهیم این فعالیت‌ها را در تعدادی اتاق که در اختیار داریم انجام دهیم. یک فعالیت در یک اتاق قابل انجام است، اگر در تمام مدت آن فعالیت اتاق به‌طور کامل در اختیارش باشد. حداقل تعداد اتاق‌های مورد نیاز برای انجام همه فعالیت‌ها کدام است؟

1)

3

2)

4

3)

5

4)

6

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

اعداد صحیح بین 1 تا 1398 به عنوان ورودی داده شده است. کدام تابع در هم‌ساز، اعداد داده شده را به‌طور یکنواخت بین 10 خانه جدول درهم‌سازی توزیع می‌کند؟(یک توزیع یکنواخت است، اگر تفاضل تعداد اعداد نگاشت شده به هر دو خانه از جدول حداکثر 1 باشد.)

1)

2)

3)

4)

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

آرایه داده شده است. می‌توانیم هر بار دو خانه دلخواه از این آرایه را باهم جابه‌جا کنیم. با حداقل چند جابه‌جایی می‌توان این آرایه را به یک هرم بیشینه تبدیل کرد؟

1)

0

2)

1

3)

2

4)

3

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

فرض کنید در گراف وزن‌دار و جهت‌دار G با n رأس، تنها وزن یال‌های خارج شده از رأس s ممکن است منفی باشند. (البته می‌دانیم گراف دور منفی ندارد.) بزرگ‌ترین که به ازای آن الگوریتم دایکسترا روی هر گراف رأسی با فرض‌های گفته شده کوتاه‌ترین مسیر از به بقیه رئوس را درست محاسبه می‌کند، کدام است؟

1)

2

2)

3

3)

4

4)

به ازای هر n همیشه درست کار می‌کند.

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

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

1)

2)

5

3)

2

4)

1

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

اگر مسئله X عضو کلاس NP-Complete به مسئله Y عضو کلاس P در زمان جمله‌ای تبدیل شود، کدام گزینه نادرست است؟

1)

NP=P

2)

NP-Complete=P

3)

NP-Hard=NP

4)

مسئله 3-SAT در زمان چند جمله‌ای حل می‌شود.

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

زمان اجرای الگوریتمی به‌صورت است. مرتبه زمانی اجرای این الگوریتم کدام است؟

1)

O(n)

2)

3)

O(logn)

4)

O(nlogn)

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

فرض کنید G یک گراف وزن‌دار و جهت‌دار با n رأس و m یال است. با فرض اینکه فاصله کوتاهترین مسیر برای هر دو رأس را در یک ماتریس در اختیار داریم، مطلع شده‌ایم که وزن تنها یک یال تغییر پیدا کرده است. می‌خواهیم به ازای دو رأس مشخص s و t طول کوتاهترین مسیر بین این دو رأس را به روز کنیم. این کار را در چه زمانی می‌توان انجام داد؟

1)

O(n)

2)

O(n+m)

3)

O(1)

4)

O(nlogn+m)

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

دو هرم کمینه در اختیار داریم که هر یک شامل n عدد است. می‌خواهیم یک هرم کمینه برای همه این 2n عدد بسازیم. با چه مرتبه زمانی می‌توان این کار را انجام داد؟ (فرض کنید هرم‌های کمینه با آرایه پیاده‌سازی شده‌اند.)

1)

O(n)

2)

O(nlogn)

3)

4)

O(nloglogn)

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