زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۱۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال درمورد min heap ساختمان داده IT 86

ارسال:
  

netsupport پرسیده:

سوال درمورد min heap ساختمان داده IT 86

به یک Min Heap خال گره هایی با کلیدهای به ترتیب ار چپ به راست ۴۵و۵۵و۴۰و۲۲و۷۵و۷۰و۴۵و۵۰و۲ اضافه شده است. Min Heap حاصل کدام گزینه است؟
جواب کتاب طراحی الگوریتم پوران و کلید سوال گزینه ۱ واینه: ۲،۲۲،۴۵،۴۰،۷۵،۷۰،۴۵،۵۵،۵۰
اما من اینو با تابع Heapify بدست آوردم شدگزینه ۳ و این: ۲،۲۲،۴۰،۴۵،۷۵،۷۰،۴۵،۵۰،۵۵
حالا کدوم درسته؟ تکلیف چیه؟!!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

amir2930 پاسخ داده:

RE: سوال درمورد min heap ساختمان داده IT 86

اول هر node رو به هیپ اضافه کن ودر هر مرحله heapify کن میشه گزینه یک
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Lantern پاسخ داده:

سوال درمورد min heap ساختمان داده IT 86

اگه اشتباه نکنم صورت صحیح سوال باید ترتیب کلیدها از راست به چپ باشه چون اگه از چپ به راست باشه هیچ کدوم از گزینه های شما جواب نمیتونه باشه.
با ترتیب از راست به چپ کلید های ۴۵و۵۵و۴۰و۲۲و۷۵و۷۰و۴۵و۵۰و۲ میشه به ترتیب با نودها عمل درج رو انجام بدیم و پس از هر درج بررسی کنیم که خاصیت Min Heap برقرارباشد که در اینصورت همان ترتیب گفته شده در پوران یعنی ۲،۲۲،۴۵،۴۰،۷۵،۷۰،۴۵،۵۵،۵۰ (از چپ به راست) صحیح است.البته اگه ابتدا با نودها درخت کامل را ایجاد کنیم و بعد بخواهیم Heapify را انجام دهیم تا تبدیل به Min Heap شود پاسخ شما (گزینه ۳)صحیح است.
از نوع طرح سوال که گفته گره‌ها به ترتیب به Min Heap اضافه شده میشه گفت منظور طراح این بوده که از ابتدا خاصیت Min Heap بودن حفظ شود و با اضافه شدن هر نود جدید این خاصیت از بین نرود و به همین خاطر گزینه ۱ را صحیح دانسته است.
در حال که اگر از Heapify بخواهیم استفاده کنیم این کار را روی یک Heap انجام می دهیم که خاصیت Heap بودن آن نقض شده و می خواهیم آن را تبدیل به Min Heap کنیم.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: سوال درمورد min heap ساختمان داده IT 86

همون ۱ درسته‌، میدونم کجای کار اشتباه میکنید‌، منم اول مثل شما حل میکردم و جواب غلط در میومد . برای این سوال راحت ترین کار اینه که بیای تک تک گره های جدید رو به درخت وارد کنی و به ازای هر درج که میکنی تغییرات لازم رو همونجا بدی‌، اما اگه بیای همه گره‌ها رو با هم در یه درخت درج کنی و بعد بخوای با روال هیپیفای اونو درست کنی احتمال اشتباه کردنت زیاده .
نقل قول این ارسال در یک پاسخ

ارسال:
  

csharpisatechnology پاسخ داده:

RE: سوال درمورد min heap ساختمان داده IT 86

(۲۶ دى ۱۳۹۰ ۰۸:۳۸ ب.ظ)Masoud05 نوشته شده توسط:  همون ۱ درسته‌، میدونم کجای کار اشتباه میکنید‌، منم اول مثل شما حل میکردم و جواب غلط در میومد . برای این سوال راحت ترین کار اینه که بیای تک تک گره های جدید رو به درخت وارد کنی و به ازای هر درج که میکنی تغییرات لازم رو همونجا بدی‌، اما اگه بیای همه گره‌ها رو با هم در یه درخت درج کنی و بعد بخوای با روال هیپیفای اونو درست کنی احتمال اشتباه کردنت زیاده .

به روش شما باید جواب بشه این :
(از چپ به راست بخوانید)
۲-۴۵-۲۲-۵۰-۷۵-۴۵-۴۰-۷۰-۵۵
گزینه ی فوق هم توی گزینه ها نیست.
مگه اینکه بیاید هیپ رو کمی تغییر بدید به شرطی که minHeap باقی بمونه و فرض کنید اون هم معادل همون هیپ قبلی هست(نه مساویش)،بعدش بیاید پیمایش کنید.
در هر صورت سوالش خیلی ابهام داره.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

پشتکار پاسخ داده:

سوال درمورد min heap ساختمان داده IT 86

اگر میخوای راحت این تستها رو حل کنید از روی کتاب مقسمی ساختمان داده رو بخونید. خیلی تمیز و زیبا و قشنگ توضیح داده
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

سوال درمورد min heap ساختمان داده IT 86

Lantern راست می گه، باید از راست باشه صورت سوال.
داده ها رو به صورت درخت کامل وارد می کنی و یکی یکی سطر ها رو می سازی.
در هر مرحله گره ای که درج می شه با والد خودش مقایسه میشه اگه ازش کوچکتر باشه با والدش جابجا میشه و بقیه ی گره های موجود هم با والد خودشون بعد از هر تغییر مقایسه میشن و باید به صورت minHeap با والد خودشون جابجا بشن.
خوب وقتی همه چیز تموم شد شکل درخت به صورت زیر در میاد :
[تصویر:  141855_1_1379088121.png]
حالا اگه اینو از بالا و از سمت چپ به راست به طور سطری پیمایش کنید، همون جوابی که برای سنجش هست بدست میاد
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۱,۲۹۰ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۹۶۵ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۱۸۴ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۳,۹۶۱ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۶,۱۲۰ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۷,۲۲۹ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۶۱۵ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
Question فرادرس برای ساختمان داده marvelous ۷ ۵,۷۰۵ ۱۰ مرداد ۱۳۹۸ ۰۹:۳۷ ب.ظ
آخرین ارسال: marvelous
  معرفی منبع خوب برای ساختمان داده alireza9819 ۴ ۵,۱۶۶ ۱۰ مرداد ۱۳۹۸ ۰۲:۵۸ ب.ظ
آخرین ارسال: marvelous
  [دانلود] جزوه و ویس جلسه نکته تست ساختمان داده والگوریتم استاد یوسفی زمستان ٩٣ software94 ۲۳ ۲۶,۲۴۰ ۰۲ فروردین ۱۳۹۸ ۱۲:۳۲ ق.ظ
آخرین ارسال: honiehs

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close