(۰۸ اسفند ۱۳۹۵ ۱۲:۰۴ ق.ظ)computerman نوشته شده توسط: چرا log n
الگوریتم‌پیدا کردن عنصد بعدی و قبلی در درخت bst وابسته به ارتفاع درخت هست که حداکثر n هست
به قول خودتون LVR درخت رو باید بنویسین که با اون روشم میشه N
تنها در یک حالت خاص اگر جایگشت اعداد ورودی به صورت مرتب شده باشد بله اونموقع نظر شما درست است
چون هیچ فرضی در صورت سوال برای ورودی در نظر نگرفته شده و حالت بدترین نیز به طور خاص خواسته نشده، به همین دلیل منظور حالت میانگین الگوریتم است که از درجه logn می باشد
رجوع کنید به الگوریتم succ در درخت جستجوی دودویی کتاب ساختمان داده
سوال چهارم که نسبتا سوال سختی هست من قبلا توی سوال های آزمون برنامه نویسی گوگل دیده بودم این سوال رو
راه حل ساده این الگوریتم خب استفاده از دو تا حلقه تو در تو با زمان n^2 می باشد
چیزی که به ذهن من میاد برای این سوال ، اگر استفاده از فضای حافظه نامحدود باشه و البته نکته مهمتر اینکه علامت اعداد ورودی چی باشه دو الگوریتم به ذهنم میرسه
برای اعداد صحیح فقط مثبت میشه الگوریتمی از درجه n نوشت با الهام از الگوریتم مرتب سازی شمارشی
برای کل اعداد صحیح که احتمالا منظور سوالم همین حالته من الگوریتمی کمتر از nlogn رو نمیتونم پیدا کنم برای این مسئله
اقای mahditorki منم موافقم با نظرتون راجب به سوال ۳
چون از O استقاده کرده و O یعنی همه حالت یه الگوریتم حداکثر به این پیچیدگی برسن و به نطر من هم O)nمیشهنا
راس میگینا
برای سوال ۲ که هر دو گزینه ۳ و ۴ درسته ک
به نظرم روی کلید اولیه اومد اعتراض کنیم ممکنه به خاطر کلمه "بهترین" بگن نه هر دوش امکان پذیر نیست؟
سلام
سوال ۳۴ و ۳۶ و ۳۹ و کسی زده ؟ کدوم گزینه درسته؟
راستی در مورد سوال ۱ گزینه ۱ و در مورد سوال ۲ گزینه ۴ درسته. تو این دو مورد شک ندارم
هر چند که خودم هر دو رو غلط زدم
من ۳ رو گزینه ۳ زدم یعنی( o(n
سول ۴ رو هم ۳ زدم یعنی(۲^ o (n
سوال ۵ رو نزدم
۶ گزینه ۲ میشه
۷ رو نزدم
۸ گزینه ۱ درسته
۹ گزینه ۲ درسته
۱۰ رو نزدم
۱۱ به نظر من ۴ میشه
۱۲ قطعا ۱ میشه
۱۳ رو نزدم
۱۴ قطعا ۴ میشه
۱۵ قطعا ۲ میشه
۱۶ مطمئنا ۲ میشه
۱۷ رو ۴ زدم
۱۸ رو هم ۴ زدم
۱۹ رو هم ۲ زدم
۲۰ رو نزدم
۳۹ گزینه ۳ میشه
۱۴ ۴ نمیشه چون گره تک فرزندی وجود ندارد پس می توان درخت رو به صورت واحد رسم کرد
ار کجا متوجه شدین گره تک فرزندی نداره؟
۳۹ نرم یا هوش؟
من هوشم
۳۹ گزینه ۴ میشه. عین سوال دو سال پیش
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
سلام
بچه ها بنظرتون کتاب سیستم عامل و پایگاه مرجعش کدوم کتاب ها بود؟
سوالهای ۷ و ۳۴ و ۴۰ چند زدین؟
(۰۸ اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیشتوی همه منابع نوشته وقتی preorder , و postorder را داشته باشیم فقط در صورتی میتونیم به درخت واحد برسیم که برچسب برگها رو داشته باشیم اما اینجا که نداشتیم
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
برای سوال ۹ هم dfs O(N میشه و bfs log n
(۰۸ اسفند ۱۳۹۵ ۱۲:۱۲ ق.ظ)ADELZX نوشته شده توسط:(08 اسفند ۱۳۹۵ ۱۲:۰۴ ق.ظ)computerman نوشته شده توسط: چرا log n
الگوریتم‌پیدا کردن عنصد بعدی و قبلی در درخت bst وابسته به ارتفاع درخت هست که حداکثر n هست
به قول خودتون LVR درخت رو باید بنویسین که با اون روشم میشه N
تنها در یک حالت خاص اگر جایگشت اعداد ورودی به صورت مرتب شده باشد بله اونموقع نظر شما درست است
چون هیچ فرضی در صورت سوال برای ورودی در نظر نگرفته شده و حالت بدترین نیز به طور خاص خواسته نشده، به همین دلیل منظور حالت میانگین الگوریتم است که از درجه logn می باشد
رجوع کنید به الگوریتم succ در درخت جستجوی دودویی کتاب ساختمان داده
سوال چهارم که نسبتا سوال سختی هست من قبلا توی سوال های آزمون برنامه نویسی گوگل دیده بودم این سوال رو
راه حل ساده این الگوریتم خب استفاده از دو تا حلقه تو در تو با زمان n^2 می باشد
چیزی که به ذهن من میاد برای این سوال ، اگر استفاده از فضای حافظه نامحدود باشه و البته نکته مهمتر اینکه علامت اعداد ورودی چی باشه دو الگوریتم به ذهنم میرسه
برای اعداد صحیح فقط مثبت میشه الگوریتمی از درجه n نوشت با الهام از الگوریتم مرتب سازی شمارشی
برای کل اعداد صحیح که احتمالا منظور سوالم همین حالته من الگوریتمی کمتر از nlogn رو نمیتونم پیدا کنم برای این مسئله
الگوریتم succ در درخت جستجوی دودویی وابسته به ارتفاع درخت و ارتفاع درخت o(n) هست دیگه
(۰۸ اسفند ۱۳۹۵ ۰۳:۱۴ ب.ظ)robotic1981 نوشته شده توسط:خب خودتون دارین میگین برچسب برگ ها(08 اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیشتوی همه منابع نوشته وقتی preorder , و postorder را داشته باشیم فقط در صورتی میتونیم به درخت واحد برسیم که برچسب برگها رو داشته باشیم اما اینجا که نداشتیم
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
برای سوال ۹ هم dfs O(N میشه و bfs log n
برگ ها هم در همه پیشمایش ها ثابت هست باید عناصری که ترتیب ان ها توی دوتا پیمایش ثابت هست رو پیدا کنید
که اگه رسم کنید درخت رو به گزینه ۱ میرسید
(۰۸ اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیش
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
اون سال که پاسخ این سوال(سوال۳۹) رو گفتند گزینه ۱ که!!
(۰۸ اسفند ۱۳۹۵ ۰۵:۳۹ ب.ظ)mahditorki نوشته شده توسط: در مورد اینکه چطور میشه فهمید گره تک فرزند تداره علاوه بر مطلب قبل یاداوری کنم که :
N0=N2+1
پیدا کردن برگها هم گفته شد.
من مدرسان شریف و کتاب دکتر قدسی رو خوندم تو هردوش نوشته بود با pre و post نمیشه به درخت واحد رسید
من با اطمینان کامل این تست رو زدم
(۰۷ اسفند ۱۳۹۵ ۰۷:۱۶ ب.ظ)computerman نوشته شده توسط: سلام دوستان
دوستان جواب سوال هایی هم که زدید بگید
مثلا اون سوال NP-complete و یا اون سوالات پیچیدگی زمانی
و یا سوال اول تحخصصی ها و ...
(۰۸ اسفند ۱۳۹۵ ۰۶:۰۵ ب.ظ)robotic1981 نوشته شده توسط:بله، دلیل این قضیه اینه که اگر درخت گره تک فرزند داشته باشه، صرفا با این دو پیمایش نمیشه مشخص کرد که اون تک فرزند، به عنوان فرزند چپ محسوب میشه یا راست. اما در صورتی که گره تک فرزند وجود نداشته باشه، میشه یک درخت منحصربفرد را تعیین کرد.(08 اسفند ۱۳۹۵ ۰۵:۳۹ ب.ظ)mahditorki نوشته شده توسط: در مورد اینکه چطور میشه فهمید گره تک فرزند تداره علاوه بر مطلب قبل یاداوری کنم که :
N0=N2+1
پیدا کردن برگها هم گفته شد.
من مدرسان شریف و کتاب دکتر قدسی رو خوندم تو هردوش نوشته بود با pre و post نمیشه به درخت واحد رسید
من با اطمینان کامل این تست رو زدم