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

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

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

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

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

6 سوال

67.

فرض کنید یک درخت دودویی جستجو بر روی n عدد حقیقی متمایز با ارتفاع O(log n) در اختیار داریم. چه تعداد از پرسمان های زیر را بدون پیش پردازش و اطلاعات اضافی میتوان

در O(log n) پاسخ داد؟ (در هر گره صرفا یک کلید و دو اشاره گر فرزندان نگه داشته شده است؟)

محاسبه کوچکترین عدد
محاسبه میانه
تعیین انکه ایا عدد داده شده x در درخت وجود دارد
محاسبه مرتبه عدد x داده شده در بین n عدد ذخیره شده در درخت

صفر

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

68.

مسئله -k مجموع بدین شکل تعریف میشود: مجموعه A از n عدد حقیقی و عدد k داده شده است. ایا k عضو از مجموعه A وجود دارند که جمع انها صفر شود. چه تعداد از گزاره‌های زیر درست است؟

مسئله 1- مجموع در زمان O(1) قابل حل است.
مسئله 2- مجموع در زمان O(n) قابل حل است.
مسئله 3- مجموع در زمان $O (n^{2})$ قابل حل است.

صفر

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

69.

مسئله جستجوی عنصر x در ارایه A شامل n عنصر را در نظر بگیرید. فرض کنید اطلاع داریم که توزیع ورودی به این صورت است که احتمال حضور عنصر x در نیمه دوم ارایه سه برابر احتمال حضور ان در نیمه اول است. همچنین برای هر نیمه، احتمال حضور در هر خانه یکسان است. تعداد مقایسه‌های الگوریتم جسجتوی خطی برای یافتن عنصر x در ارایه بطور متوسط چقدر است؟( فرض کنید طول ارایه A زوج است و عدد x در ارایه وجود دارد. ضمننا جستجوی خطی از ابتدای ارایه شروع میشود.)

$\frac{5}{8} n$

$\frac{3}{4} n$

$\frac{n}{2}$

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

70.

ارایه A شامل n عنصر داده شده است. عنصری از ارایه که حداقل $\frac{n}{3}$ بار تکرار شده باشد را یک عضو پرتکرار می نامیم. میخواهیم در ارایه A یک عضو پرتکرار را در صورت وجود پیدا کنیم. برای اینکار از یک روش مستقیم و غلبه به این صورت استفاده میکنیم: ابتدا ارایه را به سه قیمت با اندازه برابر تقسیم میکنیم و در هر کدام از قسمت ها بطور بازگشتی در صورت وجود یک عضو پرتکرار را پیدا میکنیم. سپس میزان تکرار هر کدام از این سه عضو پرتکرار را در ارایه اصلی جستجو میکنیم و در صورتی که میزان تکرار هر عضو حداقل $\frac{n}{3}$ بود ان عضو را به عنوان عضو پرتکرار برمیگردانیم. کدام گزاره در خصوص این الگوریتم درست است؟ ( فرض کنید n توانی از 3 است.)

زمان اجرا O(n log n) است، اما الگوریتم لزوما درست کار نمیکند.

زمان اجرا O(n log n) است و الگوریتم درست کار میکند.

زمان اجرا O(n) است، اما الگوریتم لزوما درست کار نمیکند.

زمان اجرا O(n) است و الگوریتم درست کار میکند.

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

71.

ارایه نامتناهی A را در نظر بگیرید. فرض کنید در n خانه اول این ارایه n عدد صحیح متناهی بصورت مرتب شده (صعودی) قرار گرفته اند و بقیه خانه‌های ارایه را با $\infty$ پر شده است. به ازای عدد x داده شده میخواهیم بررسی کنیم ایا عدد x در ارایه وجود دارد یا خیر. با چه مرتبه زمانی می توان به این پرسش پاسخ داد؟ (با فرض ان که مقدار n را از قبل نمیدانیم.)

$O (n)$

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

$O (lo g n)$

$O (1)$

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

72.

فرض کنید G یک گراف بدون جهت و بدون وزن با n راس و m یال باشد. مسئله زیر را در نظر بگیرید:

به ازای دو راس u و v داده شده و پارامتر ورودی k، ایا تعداد کوتاه ترین مسیرها بین u و v حداقل k است؟

کدام گزینه درموزد این مسئله درست است؟

می توان الگوریتمی با زمان اجرای چندجمله ای برای این مسئله ارائه داد، اما زمان اجرای این الگوریتم نمی تواند برحسب n و m خطی باشد.

می توان الگوریتمی با زمان اجرای O(m+n) برای این مسئله ارائه داد.

این یک مسئله ان‌پی-تمام است

این یک مسئله ان‌پی-سخت است

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