سوال 41
حل تشریحی سوال شماره 41 دروس مشترک
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1400
41.
مسئله درخت دودویی جستجوی (د. د.ج) بهینه با n عدد را در نظر بگیرید. در مسئله در د.ج بهینه nعدد به همراه تعداد دفعاتی که پرسمان خواهند شد داده میشود. هدف ساخت یک د.د.ج است به گونهای که مجموع حاصل ضرب پرسمان اعداد در عمق آنها در د.د.ج کمینه شود. الگوریتم حریصانه زیر را در نظر بگیرید. عدد با بیشترین پرسمان را در ریشه درخت قرار میدهیم بر اساس ریشه مشخص شده اعداد باقی مانده بر اساس خاصیت د.د.ج در یکی از زیر درختهای چپ یا راست قرار میگیرند به صورت بازگشتی زیر درخت چپ و راست را میسازیم کوچکترین که این الگوریتم حریصانه درست کار نمیکند کدام است؟
1)
3
2)
4
3)
5
4)
به ازای هر n همیشه درست کار میکند.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،