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

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

چند گزاره از گزاره های زیر درست است؟

• هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلیدها مرتب سازی می کند، باید در بدترین حالت حداقل $\left[\log \left(n!\right)\right]$ مقایسه کلیدها را انجام دهد.
• اگر m تعداد برگ ها در یک درخت دودویی و d عمق آن باشد آنگاه $d\ge \left[\log m\right]$.
• الگوریتم مرتب سازی شمارشی یک الگوریتم مبتنی بر مقایسه است که در بدترین وضعیت از مرتبه O(n) است.

هر الگوریتم قطعی که بتواند بزرگ ترین کلید دوم (دومین بزرگترین کلید) را در هر ورودی ممکن، تنها با مقایسه کلیدها بیابد. باید در بدترین حالت، حداقل چند مقایسه انجام دهد؟ (تعداد عناصر برابر n است.)

فرض کنید یک ساختار داده جدید به نام لیست اولویت دار پویا (Dynamic Priority List) دارید. این ساختار داده از لیستی از گره ها تشکیل شده است که هر گره دارای یک مقدار کلید و یک اولویت است. عمل های زیر، بر روی این ساختار داده تعریف شده اند:

• $insert(x,p)$: افزودن یک عنصر با کلید x و الویت p به لیست
• $DeleteMax\left(\right)$: حذف گره ای که دارای بیشترین اولویت است. اگر چند گره دارای اولویت یکسان باشند. اولین گره از سمت چپ حذف می شود.
• $FindMedian()$: یافتن مقدار میانه از بین تمامی کلیدهای موجود در لیست
• $IncreasePriority(x,k)$: افزایش اولویت عنصر با کلید x به اندازه k

هر کدام از این عملیات باید در کمترین پیچیدگی زمانی ممکن انجام شوند. حال، کدام یک از روش های زیر مناسب ترین ساختار داده ترکیبی برای پیاده سازی لیست اولویت دار پویا است، به گونه ای که همه عملیات با پیچیدگی بهینه انجام شوند؟

در دو الگوریتم مرتب سازی سریع (Quick Sort) و مرتب سازی ادغامی (Merge Sort)، تعداد مقایسه ها و جابه جایی ها متفاوت است. کدام گزاره زیر، درباره این تفاوت ها درست است؟

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