mahdiii

کلا کیفیت سوالای پارسال واقعا افتضاح بود. اعتراضم که نمیشد بکنیم. یکیشم همین سوال 8 که دقیقا یادمه بین گزینه یک و چهار با خودم کلنجار رفتم کدومو بزنم. با خودم گفتم این گفته خاصیت هرم بییشینه رو داشته باشه. هرم بیشینه دارای دو خاصیته یکی کامل بودن درخت و دیگری فرزنداش ازش کوچکتر باشند. خوب تو پرانتز فقط یه موردو نوشته پس منظورش تنها همین خاصیت بوده. یعنی اون درختی که مدنظرش بوده که گفته درخت جستجوی دودویی دارای یک خاصیت هرم بیشینه هم هست(بزرگ بودن از فرزنداش). پس درخت مورب میشه و گزینه یک رو زدم. یه استدلال دیگم زمانی هست که درخت دو عنصر داره(یکی ریشه و دومی سمت چپ ریشه) اون موقع این درخت وجود داره و کامل هم هست و همچنین بقیه خاصیتها رو هم داره. پس درخت داریم.

mardin200

آخه اگه اين جور بود اصلا نبايد بحث هرم مي كرد درختي كه شما ميگيد ميشه maxtree كه با maxheap فرق ميكنه وگرنه اگه اسم هرم را نمي آورد منم با شما موافق بودم

در مورد سوال 7 هم استدلالتون رو بگيد.

__________________

mehran2008

سلام،

آقا من هر کاری می کنم سایت برام بالا نمیاد. الان هم شانسی نمی دونم چی شد بالا اومد.

ادامه طبقه بندی رو براتون می نویسم:
سوالات مرتب سازی: 14 و 15
سوالات ساختمان داده های معمولی: 1 - 3 - 5 - 9 - 12
سوالات ساختمان داده های پیشرفته: 2 - 7 - 8 - 16 - 17 - 19
گراف: 6
سوالات ترکیبی: 13 و 20

mahdiii

برای سوال هفت تنها کافیه از فرمول ترکیبات استفاده کنیم. فقط بقیه هم نظر بدن شاید اشتباه باشه.
چون گفته درخت دودویی با ارتفاع کمینه باید تمام گره ها رو به ترتیب بگذاریم (مثل درخت کامل) اون موقع در سطح آخر که 16 تا نود می تونیم داشته باشیم 10 تا باقی می مونه از 25 تا. پس یه حالتش میشه ترکیب 16 و 10. من خودم تو کنکور اشتباه زدم. بی دقتی کردم. چون حالات دیگه هم وجود داره. مثلا میشه یک گره از سطح ماقبل آخر رو برداریم و بگذاریمش در یکی از گره های سطح آخر. بنابراین تعداد مکانهای خالی در این صورت میشه 14 تا که باید 11 تا گره رو توش بگذاریم. این کارم برای هر کدوم از گره ها در سطح ماقبل آخر می تونیم انجام بدیم که تعدادش 8تاست. پس میشه 8 ضربدر ترکیب 14و11 و در آخر می تونیم دو گره از گره ها در سطح ماقبل آخر برداریم که در سطح آخر 12 تا گره (16-4)می مونه که باید 10+2 تا گره رو توش جا بدیم یعنی یک حالت. که این دو تا گره ای که از سطح ماقبل آخر بر می داریم خودش میتونه به صورت 8 از دو انتخاب بشه. حالت دیگه ای هم نیست به نظرم.

mardin200

آفرين استدلالتون قشنگه منم تقريبا همين طور فكر ميكنم
ولي به نظر من تركيب 16 به 10 به عنوان تعدادي از درختهاي قابل قبول بايد به صورت مستقل در جواب وجود داشته باشد. شما در گزينه 3 كه انتخاب كرده ايد. تركيب 16 به 6 مربوط به كدام درختها است؟؟ گزينه 4 انتخاب بهتري به نظر مي رسد.

__________________

mahdiii

ترکیب 16 و 10 با ترکیب 16 و 6 برابر است
!!!)

mardin200

كاملا درسته اصلا هواسم به اونجا نبود
الان سراغ كدوم سوالات بريم ؟ ماشاا سوالا قاطيه همه موضوعات با هم ادغام شدن
اگه به همين ترتيب هم جلو بريم اتفاقي نمي افته

__________________

narssic

عین همین سوال تو کتاب "600 مساله چند گزینه ای" دکتر قدسی اومده صفحه 72 سوال 17.4
جواب در صفحه 236 به این صورت اومده:
میدانیم مقدار یک گره در یک درخت جستجوی دو دو یی از مقدار فرزندان راستش کمتر است، اما این درخت ضمنا هرم بیشینه هم هست. پس گره ها نباید فرزند راست داشته باشند. یعنی این درخت یک بصورت لیست n راسی خواهد شد. جواب گزینه الف است یعنی O(n)

narssic

در مورد سوال 7 من جوابم گزینه الف هستش
درخت برای کمینه بودن ارتفاع باید پر باشد.
25 = 0^2 + 1^2 + 2^2 + 3^2 + 10
یعنی ارتفاع درخت 5 است که تا ارتفاع 4 پر است و 10 گره برای سطح آخر در ارتفاع 5 می ماند. در سطح 5، 16 جای خالی داریم. یعنی جواب ترکیب 10 محل از 16 جای خالی میشه.
البته بعضی جاها ذکر شده که هیچ یک از گزینه ها درست نیست!

mahdiii

"البته بعضی جاها ذکر شده که هیچ یک از گزینه ها درست نیست!"
اگه شما پاسخ سوالارو دارین می تونین اینجا بگذارین لطف می کنین. با این کار ما مطمئن می شیم راهمون درست بوده یانه.
در مورد این سوال تعداد حالات بیشتر از ترکیب 16و10 است قطعا همون طوری که توضیح دادم.