صفحهها: ۱ ۲
(۱۱ اسفند ۱۳۸۹ ۰۲:۴۳ ق.ظ)raminbarca نوشته شده توسط: علت علامت کوچکتر مساوی همون کلمهی "حداکثر" تو صورت سوال هست دیگه. مشکلش چیه؟ اگه گره آخر هیچ عنصری نداشته باشه و n=h بشه خب طبیعتاً [tex]n=h<h 2^{h}[/tex] هست دیگه.
اگه پست من رو با دقت می خوندید من هم گفتم که گزینهی ۲ درسته و نزدیکترین گزینه هم هست و اشتباه کردم که سر جلسه سوال رو جواب ندادم. ولی باز هم اختلاف فاحشی با جواب داره که بعیده یه سوال بدن با ۴تا گزینه به این بزرگی در حالی که جواب خیلی کوچیکتره و به نظر من یه اشتباهی این وسط رخ داده که معلوم نیست چی بوده
ولی به هرحال سوالی که پیش روی ماست قابلیت حل کردن داره و جوابش رو هم میشه از بین گزینهها انتخاب کرد و احتمال حذف شدنش کمه. پس بهتره با همین استدلال که استدلال ساده ای هستش اعتراض کنید که کارگر بیافته
دوسته عزیز سوال خیلی واضح است و گزینه آن هم بسیار واضح
نکته های سوال
هر گره تنها یک فرزند داشته باشه( مثلا مورب به راست یا چپ یا زیک زاکی به پایین بره ... )توجه کنید درخت هیچ وقت به صورت دیگه در نمیاد! هر گره یک فرزند
گره آخر برابر دو به توان اچ عنصر داشته باشه باشه
عمق درخت به اندازه دی باشه
عمق از صفر شروع میشه
توجه کنید که عمق یک درخت برابر با ارتفاع آن درخت است که یه چیز بدیهی است h = d
خوب برای مثال یک درخت به ارتفاع ۲ به این معنا است که این درخت شامل ۳ عنصر است که گره آخری شامل شامل ۲ به توان ارتفا عنصر دارد
اینم جواب
۲ عنصر (اچ هست ارتفا درخت) + ۲ به توان اچ عنصر (تعداد عنصر های ان گره آخر )
n<= h+ 2^h
مثالم به صورت عکس گذاشتم تا اگه کسی خواست به سنجش اعلام کنه....
برادر من با دقت خوندم، اختلاف فاحش با چی داره؟
یه نامساویه، وقتی شما بگی x<1 اگه x=-500 باشه می گی چون خیلی با ۱ اختلاف داره نامساوی غلطه؟ گزینهی صحیح باید همهی حالات رو پوشش بده دیگه، کاملتر این بود که می گفت [tex]h\leq n\leq h 2^{h}[/tex] اما حالا فقط یه سمت نامساوی رو داده که درسته، نمی دونم منظورت از اختلاف فاحش با جواب چیه. یه حالت خاص مثال زدی که با کران بالا اختلاف داره، من می تونم یه مثال دیگه بزنم که هیچ اختلافی نباشه. حالا اگه بگی منظورت دقیقاً از اختلاف با جواب چیه می شه بهتر بحث کرد
اعتراض به کلید سازمان سنجش-گروه مهندسی کامپیوتر-کد ۱۲۷۷-سوال ۵۴ درس ساختمان داده ها
با توجه به صورت سوال از ارتفاع صفر تا h داریم یعنی h+1 ارتفاع مختلف داریم.در تمامی این ارتفاع ها(سطوح) یک عنصر قرار دارد، بجز سطح آخر.پس h سطح اول یک عنصر دارد و سطح آخر حداکثر [tex]2^{h}[/tex] عنصر دارد.
از طرفی هم صورت سوال گفته "در بین همهی درختها با n عنصر، درختی با بیشترین ارتفاع را در نظر بگیرید" پس باید درخت را اریب در نظر بگیریم پس جواب میشود:
[tex]n<=h\times 1 1\times 2^{h}<=h 2^{h}[/tex]
مثال:
دقت کنید که در این سوال بین گره و عنصر تفاوت وجود دارد.مثلا درخت زیر را نگاه کنید(ضمیمه شده است)
۳ گره دارد (یک دخت اریب با ارتفاع ۲-ریشه در ارتفاع صفر فرض شده)ولی با توجه به این سوال ۶ عنصر خواهد داشت(سطح صفر ۱ عنصر،سطح اول ۱ عنصر،سطح آخر حداکثر ۴ عنصر)
درخت بالا با حداکثر ۶ عنصر بیشترین ارتفاع را نیز خواهد داشت.
در این درخت با ارتفاع ۲(اریب) می تواند حداکثر ۶ عنصر(اگر برگ حداکثر تعداد عنصر را داشته باشد) و حداقل ۳ عنصر(اگر برگ حداقل تعداد عنصر را داشته باشد) را داشته باشد.
یعنی: [tex]h 1\leq n \leq 2^h h[/tex]
که حد بالای آن فقط در گزینه ۲ آمده است.
گزینه ۲ درست می باشد(به اشتباه گزینه ۴ انتخاب شده است)