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

سوال درمورد 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]
حالا اگه اینو از بالا و از سمت چپ به راست به طور سطری پیمایش کنید، همون جوابی که برای سنجش هست بدست میاد
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال ۲۶ پوران، ساختمان داده، علوم کامپیوتر ۸۹ ... مرتبه اجرایی poldasht ۴ ۸۲۵ ۱۵ مهر ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: poldasht
  حل تشریحی صحیح سوال ۴۸ ساختمان داده مهندسی کامپیوتر سراسری سال ۹۳ GentleGhost ۰ ۸۶۲ ۰۸ اسفند ۱۳۹۲ ۱۲:۱۹ ق.ظ
آخرین ارسال: GentleGhost
  سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی Morris ۴ ۱,۲۶۸ ۱۶ بهمن ۱۳۹۲ ۰۱:۲۲ ب.ظ
آخرین ارسال: mahsalove
  سوال ۳۷ ساختمان ۹۲ آی تی sahar-it88 ۲۰ ۳,۳۶۳ ۱۵ بهمن ۱۳۹۲ ۰۶:۵۳ ب.ظ
آخرین ارسال: saminmir
  ساختمان It92 fulgent ۱۲ ۲,۴۴۱ ۱۴ بهمن ۱۳۹۲ ۰۶:۳۰ ب.ظ
آخرین ارسال: maryam.raz
  سوال ساختمان داده : تست ۴۹ مهندسی ۹۲ Morris ۱۲ ۲,۶۲۴ ۰۹ بهمن ۱۳۹۲ ۱۲:۰۱ ق.ظ
آخرین ارسال: izadan11
  مرتبه زمانی ساختمان داده ۹۰ mhma_1367 ۲ ۸۸۸ ۰۷ بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ
آخرین ارسال: mhma_1367
  سوال ۵۵ کنکور ۹۰، داده ساختار مناسب برای درج و حذف و جستجو m-behdad ۲ ۸۰۵ ۰۶ بهمن ۱۳۹۲ ۱۰:۵۶ ق.ظ
آخرین ارسال: Ada Lovelace
  سوال ۳۹و ۴۲ ساختمان داده (it سال ۹۲) *afsoon* ۳ ۱,۱۱۷ ۰۱ بهمن ۱۳۹۲ ۱۱:۱۷ ب.ظ
آخرین ارسال: Riemann
  سوال کامپیوتر ۸۷ - ساختمان داده(درخت) برای ذخیره n عنصر tayebe68 ۵ ۱,۱۸۲ ۲۶ دى ۱۳۹۲ ۱۲:۱۶ ب.ظ
آخرین ارسال: Donna

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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