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

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

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

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

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

7 سوال
92.

چند مورد از مسائل ان‌پی-سخت زیر هنگامی که ورودی یک درخت بدون وزن است. در زمان چند جمله‌ای قابل حل هستند؟

  • پیدا کردن طولانی ترین مسیر
  • محاسبه کمینه رنگ مورد نیاز برای رنگ امیزی راسی بطوری که رئوس مجاور همرنگ نباشند
  • پیدا کردن بزرگترین مجموعه مستقل (مجموعه رئوسی که بین هر دو راس یالی وجود نداشته باشد)
1)

0

2)

1

3)

2

4)

3

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

گراف همبند و وزن‌دار G را در نظر بگیرید. درخت پوشای کمینه G لزوما یکتا نیست و G میتواند چندین درخت پوشای کمینه داشته باشد. فرض کنید T یک درخت پوشای کمینه دلخواه از G باشد. کدام یک از گزاره‌های زیر درست هستند؟

الف) حتما یک اجرا از الگوریتم پریم وجود دارد که T را تولید کند

ب) حتما یک اجرا از الگوریتم کروسکال وجود دارد که T را تولید کند

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

1)

الف درست، ب درست

2)

الف درست، ب نادرست

3)

الف نادرست، ب درست

4)

الف نادرست، ب نادرست

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

فرض کنید در کدگذاری هافمن، طول کد همه کاراکترها یکسان شده است. با فرض انکه تعداد کاراکترها 32 میباشد، چندتا از گزاره‌های زیر همیشه درست است؟

  • تعداد تکرار همه کاراکترها یکسان است
  • اختلاف تکرار هر دو کاراکتر حداکثر یک است
  • اختلاف تکرار هر دو کاراکتر حداکثر دو است
  • به ازای هر عدد ثابت c میتوان مثالی زد که دو کاراکتر وجود داشته باشند که اختلاف تکرارشان حداقل c باشد
1)

0

2)

1

3)

2

4)

3

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

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

1)

{1,2,5}

2)

{1,4,7}

3)

{1,5,10}

4)

{1,7,10)

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

فرض کنید در الگوریتم مرتب سازی سریع پس از عمل بخش بندی (Partition) ارایه (3,1,2,4,5,8,7,6,9) بدست امده است. چند عدد از بین 9 عدد در ارایه ممکن است محور این بخش بندی قرار گرفته باشند؟

1)

2

2)

3

3)

4

4)

5

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

فرض کنید برای درهم سازی از روش زنجیره‌ای با یک جدول به اندازه m استفاده شده است. تابع درهم ساز رکورد با کلید k را به خانه k mod m نگاشت میکند. اگر بدانیم کلید رکوردها، زیرمجموعه است، به ازای کدام m، هزینه جستجو در بدترین حالت کمتر است؟

1)

7

2)

9

3)

11

4)

12

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

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

1)

دنباله از n عدد برابر

2)

دنباله از n عدد فیبوناچی پشت سرهم

3)

دنباله

4)

دنباله

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