بچه منم با نظر آقای دکتر موافقم به نظرم برای هر درس مشترک یک تایپیک جدا باز کنیم (برای هر سوال که خیلی تایپیکها زیاد میشه)
من اولیش که ساختمان داده بود را شروع کردم بقیه اش را بسم الله
لطفاً سوالاتتون و گزینه هاتون را با سوالاهای که در سایت دوستان برای دانلود گذاشتن یکی کنید تا بقیه را گیج نکنید فکر کنم مجموعه سوال A هست
سوال ۵۱ -گزینه ۲
۵۵- گزینه ۳ ؟لطفا جواب بدید
نظرتون چیه
۵۲-۴ سوال ساده ای هست نمیدونم که چرا بچه‌ها نزدن
۵۳-۲ با مثال حل کردم
ما طبق دفترچه a که از همین مانشت دانلود کردیم داریم میگیم شما بگید چی زدید دلایلش بعد
(۳۰ بهمن ۱۳۸۹ ۰۵:۴۷ ب.ظ)vahidshahi نوشته شده توسط: سلام-به نظر من نگید گزینه رو.بهتره سوال رو با دلیل حل کنیم.چون روی سوالات یکسان نیستند.من خودم دفترچم با این سوالا تطابق نیستن.پس جواب سوال رو با منبعش بگیم خوبه.موفق باشید.
ما داریم بر طبق لینک تصویر توی همین فروم بحث میکنیم
دانلودش کن عزیزم
اینم لینکش برا مشترکا
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
من ۵۱ رو ۴ زدم چون عناصر مرتب نیستند و حالت میانگین و بدترین حالت هم یکیه چون معمولاً با یه تابع تصادفی بدترین حالت هیچ وقت رخ نمیده( احتمالش خیلی کمه)
۵۵ رو هم ۳ زدم که تشریح عمل یک AVL هست که فقط نیاز داره عناصر غیر تکراری رو ذخیره کنه. در غیر اینصورت چطوری میشه جستجو در زمان خطی انجام داد( فقط با آرایه مرتب یا جداول د رهم سازی )خوب چطوری حالا در زمان خطی درج کنیم که جستجو هم خطی باشه و هم میزان حافظه رادیکالی باشه (تناقض )و ...
سلام
سوال ۵۳-۳ مثال درختی بکش به n,k هر عددی بدی گزینه ۳ میاد مثلا ۱۶ و۴ بده میبینی.
۵۴-۲ اینم با مثال عددی حل میشد.
۵۵-۳ ساختمان داده avl جواب میشد در ضمن بچه‌ها هش نمیشه میدونین چرا چون در هش ممکن تصادم داشته باشیم و همه اعمال‌ها در o(n) بشه.
بقیه شم نزدم
اما سوال ۵۲-من حساب کردم ۲۰۴۷ شد چون فقط توان های دو را با هم جمع میزنه از دو به توان یک تا دو به توان ۱۰ اما شک کردم نزدم.
آقا کسی میدونه سوال ۵۴ یعنی چی؟
من که هنوزم نفهمیدم این سوال دقیق چی میخواد؟
(۳۰ بهمن ۱۳۸۹ ۰۷:۴۱ ب.ظ)www نوشته شده توسط: سلام
سوال ۵۳-۳ مثال درختی بکش به n,k هر عددی بدی گزینه ۳ میاد مثلا ۱۶ و۴ بده میبینی.
۵۴-۲ اینم با مثال عددی حل میشد.
۵۵-۳ ساختمان داده avl جواب میشد در ضمن بچه‌ها هش نمیشه میدونین چرا چون در هش ممکن تصادم داشته باشیم و همه اعمال‌ها در o(n) بشه.
بقیه شم نزدم
اما سوال ۵۲-من حساب کردم ۲۰۴۷ شد چون فقط توان های دو را با هم جمع میزنه از دو به توان یک تا دو به توان ۱۰ اما شک کردم نزدم.
اما سوال از دو به توان یک تا دو به توان ۱۰ رو باهم جمع میزنه اما دقت نکردی بازم ما نمیتونیم توی یه بافر ۱۰۲۴ تایی همه رو جا بدیم پس در نهایت کل قبلی‌ها با همه اونایی که مونده وارد بافر جدید میشه که ۱۳۸۹ با عددی که تو بدست آوردی جمع میشه گزینه چهار میشه جواب
خوب منم اونو نزدم واسه همین
در مورد سوال ۵۴ هم بگم یه درخت به ارتفاع سه بکش گره‌ها رو جمع بزن میشه گزینه دو دقیق. سه تا از ساختمان که من زدم اینا بودن.
در مورد سوال ۵۲ بگم فکر کنم جواب ۲۰۴۸ هست برا یقین تو فصل ۱۴ یا ۱۷ کورمن نوشته اونجا بخون جداول پویا را بخون میبینی. در ضمن من نزدم. در مورد دروس دیگه هم بگم سیستم عامل سخت بود بقیه متوسط بود نظریه اش شبیه جزوه گام اخر پارسه بود.
۵۲ منم ۴ زدم.
در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.
در مورد سوال ۵۳ به نظر من گزینه ۴ درسته بستگی داره که k , n چند در نظر گرفته بشه ماکزیمم این‌ها فکر کنم جواب درست تری بدهد.
۵۲ روش حلش اینه تا ۱۰۲۵ متوسط هزینه هر دستور ۳ هست که میشه ۳۰۷۵ از ۱۰۲۶ تا ۱۳۸۹ هم هزینه ۳۶۴ است ۳۰۷۵+۳۶۴=۳۴۳۹
چون گفته ارتفاع درخت ۱۰۰% میشه ماکزیمم اگه گفته مدت زمان اجرا اونوقت جمع میکردیم.
(۳۰ بهمن ۱۳۸۹ ۰۸:۴۷ ب.ظ)afagh1389 نوشته شده توسط: 52 منم ۴ زدم.
در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.
مرتب سازی شمارشی فقط برا حالاتی هست که بازه مشخص باشه و نه یه مقدار مثل n که به بینهایت میل میکنه. پس این تحلیل غلطه.
سوال ۵۳: گزینه ۳، اگر منظور سوال از ارتفاع، طولانی ترین مسیر از ریشه تا برگ باشه، این جوری میشه: توی از ریشه به سمت پایین سعی کنید فقط n رو به دو تقسیم کنید. وقتی که به k و ۱ رسیدیم تا این جا log2 n رو داریم. حالا از این جا به پایین k رو تقسیم کنید تا به ۱ و ۱ برسید. تا این جا هم log4 k اومدیم پایین و در مجموع log2 n + log4 k
سوال ۵۵: گزینه ۱، در سوال هیچ اشاره ای به اعداد خارج بازه sqrt n و ۱ نشده. اگر اعداد آینده رو هم در همین بازه در نظر بگیریم، می تونیم یک آرایه به اندازه sqrt n در نظر گرفته و برای درج و حذف و جستجو اعداد داخل آرایه رو زیاد و کم کنیم.
سوال ۵۶: گزینه ۲، به توان دو می رسونیم و داریم:
[tex]T^2(n) = \frac{1}{2} \left [ T^2(n-1) T^2(n-2) \right ] n\Rightarrow S(n) = \frac{1}{2} \left [ S(n-1) S(n-2) \right ] n\Rightarrow \left\{\begin{matrix} S(n)\leq \frac{1}{2} \left [ S(n-1) S(n-1) \right ] n=S(n-1) n \in \theta(n^2)\\ S(n)\geq \frac{1}{2} \left [ S(n-2) S(n-2) \right ] n=S(n-2) n \in \theta(n^2) \end{matrix}\right.\Rightarrow S(n) \in \theta(n^2)\Rightarrow T^2(n) \in \theta(n^2)[/tex]