(۲۲ بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط: (21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط: سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد
(۲۲ بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط: (21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط: سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد
دوست عزیز دومی مکس هیپه.در مکس هیپ کوچکترین عنصر در یکی از برگهاس و معلوم نیست کدوم برگ که بخوای با زمان logn پیداش کنی.باید n/2 عناصر که برگ هستند مورد جستجو قرار بگیره و از مرتبه n هستش که قطعا این رو نمی توان ساخت.
اولیش هم که avl فرض میکنیم به ازای هر a و b دلخواه گفته در مرتبه logn هست.a رو ریشه avl فرض میکنیم و b رو فرزند چپ a,حالا باید چند تا از نودها بررسی بشه؟n-1 که از مرتبه n هست.
پس هر ۲ رو نمی توان ساخت.
