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