صفحه‌ها: ۱ ۲
درخت دودویی با عمق n با توپولوژی مختلف: نزدم ولی دو به توان ان منهای یک میشه گویا
درختهای دو دویی با برگهای مشخص: چون v نداشت نزدم ولی جوا در میومده
مرتبه حلقه: می شد nlog n چون در حلقه j:=j+i بود نه j=j+1
تعداد هیپ با ۷ عنصر: ۸۰ می شد که در کنکورهای گذشته (فکر کنم ۸۸) بود
حذف عنصر Iام از max heap: به نظر من چون گفته بود عنصر iام ارایه، با زمان ۱ میشه دسترسی داشت بهش و حذفش می کنیم بعد عنصر اخر می زاریم جای اون و heapify رو اجرا می کنیم که میشه logn
تعداد ضرب مختلط: نزدم
مرتب سازی اعداد تا n^2: با رادیکس میشه احتمالا n
الگوریتم کوله پشتی: ۱۵/۵ اومد چون کوله پشتی کسری بود
الگوریتم کروسکال: یال با وزن ۵ بعد از یال با وزن ۴ در مرحله دوم انتخاب می شد
ماتریس استراسن: دو به توان لوگ ۷ نوشته در کتاب
پاسخ سوال ۴۴ کدام گزینه است؟
بعضی از دوستان میگن گزینه یک غلطه و پاسخ است و در بعضی کتابها هم همین گزینه رو نوشته ولی من غلط بودن گزینه دو با مثالی بیان می کنم
فرض کنیم
g(n)=n^3
f(n)=n^2
O(f(n))=n^4
در اینجا جی ان امگای اف ان هست ولی امگای بیگ - او اف ان نیست
(۰۲ اسفند ۱۳۸۹ ۰۲:۱۴ ق.ظ)alavinejad نوشته شده توسط: ماتریس استراسن: دو به توان لوگ ۷ نوشته در کتابتوی کدوم کتاب نوشته
دو به توان لوگ ۷
نقل قول: توی کدوم کتاب نوشتهطراحی الگوریتم مقسمی - صفحه ۱۲۰
دو به توان لوگ ۷
سلام.
کسی هست اینجا که فرمش A بوده باشه؟؟ واسه من سوال ۳۹ درخت AVL رو نکشیده بودن
الدورادو یعنی هیچ درختی نکشیده بودند؟
اون درخت AVL رو ماهان درست زده؟یعنی ۳۰،۱۵،۱۰،۲۰،۴۰؟ من که ۳۰،۱۰،۲۰،۱۵،۴۰ زدم؟
(۰۶ اسفند ۱۳۸۹ ۰۲:۲۲ ب.ظ)mmpf نوشته شده توسط: اون درخت AVL رو ماهان درست زده؟یعنی ۳۰،۱۵،۱۰،۲۰،۴۰؟ من که ۳۰،۱۰،۲۰،۱۵،۴۰ زدم؟
درخت AVL یک نوع درخت جستجوی دودویی خاصه که عمق دو زیر درخت چپ و راستش حداکثر یک واحد اختلاف دارن. پس در درجه اول باید درخت، جستجوی دودویی باشه که این پیمایشی که شما ذکر کردین، مربوط به درخت جستجوی دودویی نمی شه.
باید درنظر می گرفتین که در AVL پس از اضافه شدن یه گره جدید یا کلا هر تغییری، پروسه ای به نام دوران اتفاق می افته که در این حالت پس از دوران ۱۵ در ریشه قرار می گیره، گره ۱۰ سمت چپ و ۲۰ سمت راستش قرار می گیره.
نقل قول: ارسال شده توسط mmpf - امروز ۰۱:۲۲ عصراحتمالا غلطه، چطور شده که در پیمایش پیشوندی درخت دودویی متعادل (AVL) گره ۱۵ زودتر دیده شده در حالی که گره ۱۰ باید سمت چپ باشه و اونو زودتر ببینه
اون درخت AVL رو ماهان درست زده؟یعنی ۳۰،۱۵،۱۰،۲۰،۴۰؟ من که ۳۰،۱۰،۲۰،۱۵،۴۰ زدم؟
ضمن اینکه درخت جستجوی دودویی است باید خاصیت AVL بودن نیز حفظ بشه درصورتی که فقط بخواهیم
درخت را جستجوی دودویی خالی رسم کنیم دیگه AVL نیست پس ۱۵ زودتر از ۱۰ دیده میشود.
دوستان درخواست بررسی سوال ۴۴ رو در پیغام خصوصی دادن. خواهش می کنم از دوستان عزیز که سوالات رو در پیغام خصوصی نپرسن تا از تایج بحث، دوستان دیگه هم بتونن استفاده کنن.
[attachment=476]
گزینه چهار صحیحه (یعنی طبق صورت سوال نادرسته)
پاسخنامه منتشر شده از طرف ماهان به اشتباه این سوال رو حذف کرده با این تصور که گزینه صحیح وجود نداره.
علت انتخاب گزینه جهار اینه که اگر تابع g از مرتبه O(f نباشه، از مرتبه w(f هست و نه اومگای f
تصحیح بفرمایید:
۳۷- چند درخت دودویی: ۲ بتوان n-1
۳۸- چند maxheap: هشتاد
۳۹- ۴۰و۲۰و۱۰و۱۵و۳۰: AVL
۴۰- مرتبه زمانی شبه کد: nlog n
۴۱- نمایش preorder: حذف
۴۲- maxheap با n عنصر: log n
۴۳- ضرب اعداد مختلط: ؟؟؟؟؟؟
۴۴- گزاره اگر gn کوچکترومساوی از fn نباشد پس gn بزرگتر و مساوی fn است نادرست و جواب مساله بود.
۴۵- الگوریتم کراسکال: مرحله ۲ (یال ۵)
۴۶- مرتبه مرتب سازی
O(n۴۷- مساله کوله پشتی: ۱۵
۴۸- الگوریتم استراسن: n بتوان log7
۴۱- این سوال رو اگر کمی روش متمرکز می شدید، متوجه می شدید که یک حرف V بعد از B و قبل از F جا افتاده.
[attachment=478]
و پیمایش postorder اش می شه ZBVAYODFX که گزینه ۱ هست. حالا اگر سنجش حذف اش کنه که دیگه هیچی.
۴۳- ضرب اعداد مختلط گزینه ۳ می شه یعنی [tex]n^{\log 3}[/tex]
۴۷- مسأله کوله پشتی کسری، ۱۵/۵ جواب صحیحه و نه ۱۵
با تشکر فراوان از دکتر مورتون
در پیمایش ای pre و in و post ترتیب ملاقات برگها یکسانه مثلا اگر برگها a , b , c ,h باشه و فرض کنید ترتیب ملاقات به صورت ..c...b....h....a.... باشه توی هر پیمایش دیگه هم باید همین ترتیب رعایت بشه.
بابا چرا نمیگیرید؟
اگر سوال به این ترتیب بود که این گره‌ها برگ هستند . حال کدام یک از گزینه های زیر میتواند یک پیمایشی
از درخت حاصل باشد؟ حرف شما درست بود.
اما سوال میگه، یک درخت با این گره‌ها وجود دارد. و این گره‌ها برگ هستند. کدام یک نمایش مثلا Postorder
درخت است؟ پیمایش یک گره رو نداره، پس پیمایش درستی نیست.