سوال 3
حل تشریحی سوال شماره 3 حل مسئله
کنکور دکتری مهندسی فناوری اطلاعات (IT) 1404
3.
فرض کنید می خواهید یک داده ساختار طراحی کنید که همزمان بتواند عملیات زیر را پشتیبانی کند:
- افزودن عدد صحیح x به داده ساختار
- حذف و بازگرداندن بزرگ ترین مقدار ذخیره شده (عملیات Remove Max)
- محاسبه و بازگرداندن مجموع تمام اعداد ذخیره شده (Sum)، بدون حذف هیچ کدام
این داده ساختار باید با استفاده از سه پشته (Stacks) پیاده سازی شود و همچنین هیچ صف یا آرایه ای نباید مستقیماً استفاده شود. اگر تعداد کل اعداد n باشد، پیچیدگی زمانی عملیات Sum در بدترین حالت چیست؟
1)
O(nlogn)
2)
O(logn)
3)
O(n)
4)
O(1)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،