(۲۵ دى ۱۳۹۳ ۰۲:۴۵ ب.ظ)ziba.O نوشته شده توسط: (25 دى ۱۳۹۳ ۰۲:۱۰ ب.ظ)tm.viper نوشته شده توسط: ۴۳ اشتباست...اگه میگفت کدوم گزینه نمیشه ۱ میشد
چرا؟ ترتیب فرزنداشو تاثیر نمیدی؟ مثلا بین بچه های گره یک اول ۴ گسرش داده میشه بعد ۵؟
توی صورت سوال حرفی از ترتیب نزده
گزینه ۱ از اونجایی غلطه که بعد از ۶ با وجود گره ۲ بازگشت به عقب دادیم و رفتیم سراغ ۷
ترتیبم بخوایم اثر بدیم بعد از ۴ حتما باید ۲ انتخاب شه که تو گزینه ها نیست
در مورد سوال ۳۷
ما یه زیربرنامه ای به اسم heapify داریم
کارش اینه که یه گره موقع درج یا حذف با والد خودش چک میشه که با توجه به نوع هیپ(مینیمم یا ماکسیمم بودن) گره رو به بالا هدایت میکنه که از مرتبه logn هست
حالا تو این سوال گزینه ۱ از اونجا که معلوم نیست کجا هست نیاز هست کل درخت پیمایش بشه از مرتبه n
گزینه ۲ همون طور که تو پاسخنامه هست کافیه ۵ بار زیربرنامه heapify رو اجرا یا اصلا همون extract min رو داشته باشیم که مرتبش logn
گزینه ۳ نیاز هست n/2 عناصر رو extract کنیم یا به قولی n/2 * logn میشه مرتبه زمانیش
گزینه آخرم به دلیل درستی گزینه ۲ رد میشه
سوال ۴۲ هم با توجه به این که هر ۳ حالت اضافه-کم-بی اثر ممکن هست رخ بده
تنها گرینه مردد ۲ میشه جواب باشه
Aurora، در تاریخ ۲۵ دى ۱۳۹۳ ۰۵:۲۲ ب.ظ برای این مطلب یک پانوشت گذاشته است:
لطفا اینجا سوال نپرسید و سوال جواب ندید. برای سوال ها بخش دیگه ای هست!
خواهش می کنم رعایت کنید.
؟
