حل تشریحی سوال شماره 34 دروس مشترک (ساختمانهای گسسته، ساختمان دادهها، طراحی الگوریتم، مهندسی نرمافزار، شبکههای کامپیوتری)
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1404
فرض کنید یک صف (Queue) داریم که با استفاده از یک لیست پیوندی با عناصر یکتا پیاده سازی شده است. این صف دو عملیات اصلی enqueue (افزودن به انتهای صف) و dequeue (حذف از انتهای صف) را پشتیبانی می کند. حال میخواهیم تابعی به این صف اضافه کنیم که میانه (Median) عناصر موجود در صف را در زمان بهینه برگرداند کدام روش زیر مناسب است؟
پیمایش کل صف در هر بار فراخوانی تابع میانه برای پیدا کردن مقدار میانه
استفاده از یک لیست پیوندی دوم برای کپی کردن عناصر صف و مرتب کردن آنها هر بار که به میانه نیاز داریم.
استفاده از دو صف دیگر برای نگهداری عناصر کوچک تر و بزرگتر از میانه و به روزرسانی آنها هنگام هر عملیات enqueue و dequeue
استفاده از یک ساختار داده کمکی مرتب مانند درخت جست و جوی دودویی متوازن کامل (Balanced BST) برای ذخیره و مدیریت عناصر به طوری که میانه با دسترسی به ریشه درخت قابل دستیابی باشد.