۰
subtitle
ارسال: #۱
سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳- درخت دودویی
دوستان لطفا به این سوال توجه کنید
داده ساختار یک درخت دودویی است که اعداد طبیعی دلخواه x1,...xn در برگها ذخیره می کند. هر گره داخلی درخت دودویی x حاوی بزرگترین مقدار کلید دو فرزندش می باشد کدام یک از اعمال زیر را می توان در
۱ ) حذف ریشه درخت
۲) کاهش مقدار کلید
۳) برگرداندن مقدار دومین بزرگترین عنصر
۴) هیچ کدام
طبق کلید پارسه گزینه ۳ هست به دلیل اینکه دومین بزرگترین حتما فرزند ریشه هست و به یک مقایسه بیشتر نیاز نداریم ..... ولی امکان داره دومین بزرگترین و بزرگترین در عمقهای پایین تر باهم همزاد باشند به نظر من هیچ کدام درسته نظر دوستان؟؟؟
داده ساختار یک درخت دودویی است که اعداد طبیعی دلخواه x1,...xn در برگها ذخیره می کند. هر گره داخلی درخت دودویی x حاوی بزرگترین مقدار کلید دو فرزندش می باشد کدام یک از اعمال زیر را می توان در
o(1)
انجام داد؟۱ ) حذف ریشه درخت
۲) کاهش مقدار کلید
۳) برگرداندن مقدار دومین بزرگترین عنصر
۴) هیچ کدام
طبق کلید پارسه گزینه ۳ هست به دلیل اینکه دومین بزرگترین حتما فرزند ریشه هست و به یک مقایسه بیشتر نیاز نداریم ..... ولی امکان داره دومین بزرگترین و بزرگترین در عمقهای پایین تر باهم همزاد باشند به نظر من هیچ کدام درسته نظر دوستان؟؟؟
۰
ارسال: #۲
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
ارسال: #۳
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
(۱۹ آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
۷۰
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
ارسال: #۴
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
، پس احتمالا هیچ کدام گزینه صحیح هست.
ارسال: #۵
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
(۱۹ آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
ارسال: #۶
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
(۲۰ آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
ارسال: #۷
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
(۲۰ آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
ورودیها برگها هستند و تکراری نیستند
(۲۰ آبان ۱۳۹۲ ۰۹:۴۸ ق.ظ)amin222 نوشته شده توسط:ممنون دوست عزیز ولی حتی اگر نا مرتب در نظر بگیریم باز این جواب درست نیست فرض کنید مثلا ٦ سطح باشه گره برگ ٤٠ و ٧٠ همزاد باشن وبقیه نا مرتب و کوچکتر ٤٠(20 آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
۰
ارسال: #۸
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
ارسال: #۹
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
ارسال: #۱۰
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
۰
ارسال: #۱۱
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳
طبق فرمول باید دومین بزرگترین کلید در محدوده ۱^۲ تا ۱- ۲^۲ (یعنی از گره ۲دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
ارسال: #۱۲
RE: سوال ۳۹ پارسه ۲۵ درصد دوم ایتی کنکور ۹۳- درخت دودویی
(۲۸ آذر ۱۳۹۲ ۰۳:۱۱ ق.ظ)۲۰۱۳محمد نوشته شده توسط: طبق فرمول باید دومین بزرگترین کلید در محدوده ۱^۲ تا ۱- ۲^۲ (یعنی از گره ۲دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
این فرمولی که شما می گین مربوط به درخت heap هست این درخت heap نیست طبق صورت سوال دقت کنید گفته شده گره x1 تا xn برگها هستند پست ۳ رو نگاه کنید یه مثال ساده از این درخت رو نوشتم...بخوام دقیقتر بگم این درخت مثل الگوریتم تورمنت بازی عمل می کنه وبرای به دست اورد دومین max باید کل حریفهای (همزاد ها) max اول یا همون ریشه رو با هم مقایسه کنیم
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close