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

دولتی ۸۲ (heap)

ارسال:
  

tabassomesayna پرسیده:

دولتی ۸۲ (heap)

سلام دوستان
در مورد این سوال با توجه به اینکه صورت سوال گفته عناصر "متمایز" به نظر من جواب گزینه سه هست ولی در کتاب مقمسی گفته شده همه موارد و در جواب نوشته : در درخت max-heap فرزندان یک گره می توانند مساوی باشند !! نظر شما چیه؟
[تصویر:  211587_1_1379079794.png]
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

azk84 پاسخ داده:

RE: دولتی ۸۲ (heap)

سلام.

با فرض متمایز بودن همه‌ی عناصر داریم:

عنصر اول همیشه در درایه‌ی یک قرار داره.
عنصر دوم همیشه یا در درایه‌ی دوم یا در درایه‌ی سوم قرار داره (حتماً فرزند عنصر اوله).
عنصر سوم یا بابد مستقیم فرزند عنصر اول باشه یا فرزند عنصر دوم. پس اگه عنصر دوم در درایه‌ی دو باشه عنصر سوم می‌تونه توی درایه‌های ۳، ۴ یا ۵ باشه و اگه عنصر دوم در درایه‌ی ۳ باشه عنصر سوم می‌تونه توی درایه‌های ۲، ۶ یا ۷ باشه.
عنصر چهارم هم باید مستقیماً فرزند عنصر اول، دوم یا سوم باشه، پس در مجموع این خونه‌ها براش امکان‌پذیره:
۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، ۱۱، ۱۲، ۱۳، ۱۴، ۱۵

بنابراین همه موارد گزینه‌ی صحیح است. اون توضیح اضافه‌ای که کتاب مقسمی داده (که فرزندان گره می‌تونن مساوی باشند) مال اینه که حل کننده‌ی سؤال دلیل درست بودن گزینه‌ی ۴ رو اشتباه فهمیده ;-)
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

tabassomesayna پاسخ داده:

RE: دولتی ۸۲ (heap)

(۲۱ شهریور ۱۳۹۲ ۰۶:۴۰ ب.ظ)azk84 نوشته شده توسط:  سلام.

با فرض متمایز بودن همه‌ی عناصر داریم:

عنصر اول همیشه در درایه‌ی یک قرار داره.
عنصر دوم همیشه یا در درایه‌ی دوم یا در درایه‌ی سوم قرار داره (حتماً فرزند عنصر اوله).
عنصر سوم یا بابد مستقیم فرزند عنصر اول باشه یا فرزند عنصر دوم. پس اگه عنصر دوم در درایه‌ی دو باشه عنصر سوم می‌تونه توی درایه‌های ۳، ۴ یا ۵ باشه و اگه عنصر دوم در درایه‌ی ۳ باشه عنصر سوم می‌تونه توی درایه‌های ۲، ۶ یا ۷ باشه.
عنصر چهارم هم باید مستقیماً فرزند عنصر اول، دوم یا سوم باشه، پس در مجموع این خونه‌ها براش امکان‌پذیره:
۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، ۱۱، ۱۲، ۱۳، ۱۴، ۱۵

بنابراین همه موارد گزینه‌ی صحیح است. اون توضیح اضافه‌ای که کتاب مقسمی داده (که فرزندان گره می‌تونن مساوی باشند) مال اینه که حل کننده‌ی سؤال دلیل درست بودن گزینه‌ی ۴ رو اشتباه فهمیده ;-)
ممنون از پاسختون ولی مگه طبق تعریف درخت heap که درخت کامل هست عنصر سوم نباید حتما" فرزند عنصر اول باشه ؟ اگه فرزند عنصر دوم باشه قانون کامل بودن نقض میشه که ؟؟!
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

SnowBlind پاسخ داده:

RE: دولتی ۸۲ (heap)

(۲۱ شهریور ۱۳۹۲ ۰۶:۱۱ ب.ظ)tabassomesayna نوشته شده توسط:  سلام دوستان
در مورد این سوال با توجه به اینکه صورت سوال گفته عناصر "متمایز" به نظر من جواب گزینه سه هست ولی در کتاب مقمسی گفته شده همه موارد و در جواب نوشته : در درخت max-heap فرزندان یک گره می توانند مساوی باشند !! نظر شما چیه؟
[تصویر:  211736_1_1379079384.png]

شما به این نکته توجه کنید که k امین عنصر در سطحی بیشتر از k نمیتونه قرار بگیره، (اگه بگیره دیگه K امین نیست) و از طرفی، عنایت داشته باشید که عنصر سطح i ام میتونه توی درایه های [tex]\[ 2^{i} \dots 2^{i 1}-1\][/tex] قرار بگیرن که با توجه به این موضوع، ۴ امین عنصر میتونه توی سطح اول یعنی درایه های ۲ تا ۳ و یا سطح سوم درایه هاس ۸ تا ۱۵ و یا سطح دوم که میشه درایه های ۴ تا ۷، که با توجه به این مقدمات میشه گزینه ۴ بدون هیچ سر دردی Big Grin
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

azk84 پاسخ داده:

RE: دولتی ۸۲ (heap)

منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر می‌تونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

tabassomesayna پاسخ داده:

RE: دولتی ۸۲ (heap)

(۲۱ شهریور ۱۳۹۲ ۰۷:۳۲ ب.ظ)azk84 نوشته شده توسط:  منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر می‌تونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]

بله حرفتون کاملا" درسته .. ممنون بابت پاسختونSmile
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

azk84 پاسخ داده:

RE: دولتی ۸۲ (heap)

(۲۱ شهریور ۱۳۹۲ ۱۱:۵۸ ب.ظ)tabassomesayna نوشته شده توسط:  
(21 شهریور ۱۳۹۲ ۰۷:۳۲ ب.ظ)azk84 نوشته شده توسط:  منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر می‌تونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]

بله حرفتون کاملا" درسته .. ممنون بابت پاسختونSmile

خواهش می‌کنم ;-)
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  امریه ارگان های دولتی it_man ۰ ۷۱۹ ۰۸ دى ۱۴۰۱ ۰۱:۵۳ ب.ظ
آخرین ارسال: it_man
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۹,۶۵۵ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  ثبت نام نمونه دولتی هفتم ۹۹-۱۴۰۰ edumoshaver1 ۰ ۱,۹۸۹ ۱۲ اسفند ۱۳۹۸ ۰۴:۵۸ ب.ظ
آخرین ارسال: edumoshaver1
  اعلام نتایج آزمون نمونه دولتی ۹۹-۱۴۰۰ edumoshaver1 ۰ ۲,۵۴۲ ۱۲ اسفند ۱۳۹۸ ۰۴:۵۶ ب.ظ
آخرین ارسال: edumoshaver1
  سوالی از max-heap sir_ams ۳۳ ۲۳,۶۰۱ ۲۸ دى ۱۳۹۶ ۰۲:۳۴ ب.ظ
آخرین ارسال: سیمول
  مهندسی کامپیوتر دولتی ۹۱ Saman ۰ ۱,۶۹۰ ۲۲ دى ۱۳۹۶ ۱۱:۰۱ ب.ظ
آخرین ارسال: Saman
  گذراندن ارشد دولتی در کنار شاغلی kobraa ۵ ۵,۲۲۴ ۱۹ آذر ۱۳۹۶ ۰۵:۱۲ ب.ظ
آخرین ارسال: Happiness.72
  دروس ارائه شده در دانشگاههای دولتی تهران kadoos ۱ ۲,۸۶۹ ۲۰ شهریور ۱۳۹۶ ۰۱:۴۱ ب.ظ
آخرین ارسال: kadoos
  احتمال قبولی در مصاحبه دانشگاه های دولتی با مدرک دانشگاه آزاد plusdeck ۱ ۳,۱۷۵ ۲۶ خرداد ۱۳۹۶ ۱۲:۱۰ ب.ظ
آخرین ارسال: shahmorteza
  روش تبدیل یک لیست صعودی از اعداد به max heap peace2013 ۳ ۳,۲۴۸ ۱۸ فروردین ۱۳۹۶ ۰۲:۴۰ ب.ظ
آخرین ارسال: msour44

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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