انجمنصفحه اولجستجوی انجمن

[psps1368]

من البته هوش بودم. ولی سوالای ساختمان یکی بود. (دفترچه F - برای تخصصی نرم افزار که توی سایت آپلود شده)
لینک دفترچه:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


۱- نزدم
۲- گزینه ۲ - با جدول درهم سازی با تابع درهم سازی خوب به ازای هر برخورد یه عنصر مشترک میاد. پس اگر هیچ برخوردی رخ نده، عنصر مشترک ندارن. (توی ارشد ۹۰ هم سوال اول ساختمان این نکته رو داشت. چون چیزی هم توی سوال مثل مبتنی بر مقایسه و اینا گفته نشده، فکر کنم جواب منطقی باشه)
۳- من گزینه ۴ رو زدم ولی فکر کنم گزینه ۳ میشه. چون دومی همیشه درست نیست. مثلا توی زنجیر...
۴- گزینه ۳ - n عمل درج که برای هر عنصر داریم. توان های دو هم هر کدوم موقع ساخت جدول جدید هزینه رو به اندازه خودشون اضاه می کنن. جمع توان های دو تا n میشه ۲n که در مجموع هزینه میشه ۳n که تقسیم بر n همون ۳ میشه.
۵- گزینه ۲
۶- نزدم
۷- گزینه ۱ - چون ترتیب این عناصر مهم نیست با یه DFS روی هیپ با شروع از ریشه و ادامه اون تا جایی که بزرگتر از x بشه. واضحه که فقط روی عناصر کوچکتر از x حرکت می کنیم.
۸- گزینه ۳
۹- گزینه ۳- مرتب سازی ادغامی در بهترین حالت n/2logn و در بدترین حالت nlogn - n + 1 مقایسه انجام می دهد.
۱۰ - نزدم
۱۱- گزینه ۲
$T(n)=n \sum_{k=1}^{n-1}(T(k) T(n-k))=n 1 T(n-1) \sum_{k=1}^{n-2}(T(k) T(n-k))=n 1 T(n-1) T(n-1)-(n-1)\\\\ \Rightarrow T(n)=2T(n-1) 2\Rightarrow T(n)\in\theta(2^n)$
۱۲- گزینه ۳ - به نظرم اگر گزینه الف و ب درست باشه ج هم درسته! صرفا دلیلم همین بود!
۱۳- گزینه ۲ - الف که مشخصه. ب هم گره های تک فرزندی رو نمیشه مشخص کرد.
۱۴- نزدم
۱۵- گزینه ۲
$3^{log n}=n^{log 3}$
$3log~n < log~n~loglog~n \Rightarrow log~n^3 < log (log~n^{log~n})\Rightarrow n^3 < log~n ^{log n}$
۱۶- نزدم
۱۷- گزینه ۱- فقط سومی درسته. همیشه میشه چنین درختی ساخت که اتفاقا یکتا هم هست. به راحتی میشه مثالی زد که ارتفاع درخت بشه n. مثلا (۱,۲) - (۳,۴) - (۵,۶) - و به همین ترتیب. با این مثال جمله دوم و چهارم نقض میشه.
۱۸- نزدم
۱۹- نزدم
۲۰- گزینه ۳ - به راحتی بدست میومد.

[mahdiii]

جوابا خوب بود. به جز یه چندتایی که بهشون اشاره می کنم.
اول از همه سوال ۱۸ که واقعا برای خودم متاسفم چه سوال چرتی رو جواب ندادم. اومدم خونه سریع تونستم حلش کنم. نمی دونم چرا سر کنکور کند میشم و وقت کم میارم. تمرکزم یکم پایین میاد.
برای سوال ۱۸ کافیه که اون تابع f رو برای گره ها درنظر بگیرید و بعدش با h ضرب و جمع کنید و حالتی که از همه کمتره رو پیدا کنین. تنها کافیه ۴ یا ۵ درخت بکشین که جای گره ها عوض شده. جواب میشه ۱و۲ یعنی دو درخت پیدا میشه که h(4) یک و دوست و در هردو مورد هم کمینه هست فکر کنم میشه ۳۰ برای بقیه میشن ۴۰ و بیشتر از ۴۰
در مورد اون سوالی که گفتید میشه ok چطور این کارو با k انجام میدید. کمتر از n نمیشه. شما که جای اعداد کوچکتر از x رو در هیپ نمیدونید. باید کلشو پیمایش کنین حالا با هرچی مثل DFS که میشه n اما می دونیم که این کارو می تونیم با klogn انجام بدیم که برای k های کوچک این گزینه بهتر از n هست.
سوال ۱۱ رو چطور حل کردین. دو طرف Tn داشت. مجموع روی k=1 تا n هست؟؟؟؟!!!!!!! حل نمیشه
سوال ۱۷ هم با بچه ها زیاد بحث شد. اگه منظور این ساختار treap باشه که می گه ساختاری که هم درخت جستجوی دودویی هست و هم max heap یا min heap البته بدون شرط کامل بودن که حرف شما صحیحه و جواب یکتاست. من هم یک زدم اما یکی گفت این گفته min heap و اشاره ای به treap نکرده یعنی می تونه منظورش درخت کامل هم باشه همون طوری که در heap ها این طوریه. پس گاهی جواب نداره. چون باید کامل هم باشه. طراح خیلی ناشی بوده و بد سوال طرح کرده. باید می گفت تنها شرط کوچک بودن گره از فرزنداش

---

در مورد سوال دو، خیلی نامردیه اگه بشه با هش حل کرد. تو همین مانشت هم دقیقا همین نوع سوال اومده بود و بچه ها می گفتن که با هش نمیشه چون باید فرضیاتی بکنیم. منم خودم با هش موافق بودم. اما بچه ها گفتن که با هش در بدترین حالت امکان داره برای درج و واکشی برای یک عنصر on زمان ببره که منم قبول کردم. این دومین سوال ناشی طراح.
بعد اون n<m هم دیدم و بعدش دو گزینه ۳و۴ به خاطر همین ۴ زدم. الآن یکی از ما ها درست و یکی دیگه غلط زده (از نظر تست) درصورتی که هر دو این موضوعو می دونیم (با هش و بدون هش). این یعنی ارزیابی درست!!!!!!!!!

[امیدوار]

جوابای من با توجه به دفترچه f
۶- گزینه ۴
۷- گزینه ۴
۸- گزینه ۱
۹- گزینه ۲
۱۰- گزینه ۴
۱۱- گزینه ۴
۱۲ - گزینه ۳
۱۳ - گزینه ۲
۱۴ - گزینه ۲
۱۵ - گزینه ۲
۱۶ - گزینه ۲
۱۷ - گزینه ۲(با توجه به زوج مرتب ها فقط دو مورد اول می تواند درست باشد و دو مورد بعدی مثال نقض دارند)
۱۸ - گزینه ۳
۱۹ - .....
۲۰- گزینه ۳

[psps1368]

(۱۹ اسفند ۱۳۹۱ ۰۷:۱۲ ب.ظ)mahdiii نوشته شده توسط:  در مورد اون سوالی که گفتید میشه ok چطور این کارو با k انجام میدید. کمتر از n نمیشه. شما که جای اعداد کوچکتر از x رو در هیپ نمیدونید. باید کلشو پیمایش کنین حالا با هرچی مثل DFS که میشه n اما می دونیم که این کارو می تونیم با klogn انجام بدیم که برای k های کوچک این گزینه بهتر از n هست.

سوال ۱۱ رو چطور حل کردین. دو طرف Tn داشت. مجموع روی k=1 تا n هست؟؟؟؟!!!!!!! حل نمیشه

در مورد سوال دو، خیلی نامردیه اگه بشه با هش حل کرد. تو همین مانشت هم دقیقا همین نوع سوال اومده بود و بچه ها می گفتن که با هش نمیشه چون باید فرضیاتی بکنیم. منم خودم با هش موافق بودم. اما بچه ها گفتن که با هش در بدترین حالت امکان داره برای درج و واکشی برای یک عنصر on زمان ببره که منم قبول کردم. این دومین سوال ناشی طراح.

در مورد سوال ۷ قبول دارید که در مسیر ریشه به برگ ها توی هیپ کمینه عناصر صعودی هستن؟ بنابراین پیشروی روی این عناصر تا جایی که بزرگتر از x نشدن نباید مشکلی داشته باشه.

در مورد سوال ۱۱ قبول دارم. فکر کنم اشتباه تایپی بوده. من k رو تا n-1 فرض کردم.

در مورد سوال ۲ هم واکشی لازم نیست. فقط برخورد مهمه. در مورد پر شدن یک خانه از جدول هم میشه به راحتی اندازه جدول هش رو تا هر اندازه که می خواهید بزرگ بگیرید. مثلا بزرگتر از n که خیالتون از load factor راحت باشه. در مورد ارزیابی درست هم کاملا موافقم!

[Mansoureh]

ساختمان داده:

جواب سوال ۱:
من زدم گزینه ی ۲، قرمز و عمق ۳ - متاسفانه عددها معلوم نیست که بتونم حلش رو بنویسم.

جواب سوال ۲:
همزمان دو مجموعه ی A و B را sort می کنیم که چون n<m میباشد این کار در mlogm انجام میگردد. حال تعداد اعضای مجموعه ی کوچکتر را با جستجوی باینری در مجموعه ی مرتب شده ی دوم پیدا میکنیم که حداکثر در مدت زمان nlogm صورت میگیرد. با جمع این مقادیر داریم:
mlogm+nlogm=(n+m)logm
گزینه ی ۳ صحیح می باشد.

سوال ۳: جواب ندادم!
سوال ۴: جواب ندادم.
سوال ۵: متاسفانه من زدم گزینه ی ۳ ولی توی کتاب چک کردم گزینه ی ۲ درسته...
سوال ۶: جواب ندادم.
سوال ۷: گزینه ی ۳
سوال ۸: گزینه ی ۲ رو زدم ولی جواب قسمت ب رو نمیدونستم! ۵۰/۵۰ انتخاب کردم!
سوال ۹: من زدم ۱ ولی باز هم توی کتاب چک کردم میشه ۳
جواب سوال ۱۰: گزینه ی ۳
۱- جابجایی ۳ و ۴
۲- جابجایی ۷ و ۹
۳- جابجایی ۱ و ۷
۴- جابجایی ۱ و ۳
حالا درخت ساخته شده و حذف رو شروع میکنیم
۵- جابجایی ۳ به ریشه
۶- جابجایی ۷ به پدر خود
۷- جابجایی ۴ به ریشه
۸- جابجایی ۷ به ریشه
۹- جابجایی ۹ به ریشه
سوال ۱۱: من زدم گزینه ی ۱ چون من T1 و T2 و T3 و T4 و T5 را بوجود آوردم و با توجه به عدد n آن رشدش را با گزینه ها مقایسه کردم به نظرم به گزینه ی اول نزدیک تر بود. ولی این روشم به هیچ عنوان علمی نیست... به نظر میاد اثبات psps درست باشه...
سوال ۱۲: نمیدونم چرا سر جلسه گزینه ی ۱ رو سریعا رد کردم!!! ب و ج درسته ولی د در هیچ شرایطی بوجود نمیاد در نتیجه گزینه ی ۳ درسته
سوال ۱۳: گزینه ی ۲ حرفی در آن نیست!
سوال ۱۴: راستش به نظر من همه ی گزینه ها درست بود ولی عدد ۴ در گزینه ها وجود نداشت! من هم بیشترین مقدار ممکن رو زدم یعنی گزینه ی ۴.
سوال ۱۵: گزینه ی ۲ همانطور که کاربر psps گفتند.
سوال ۱۶: جواب ندادم
سوال ۱۷: جواب دادم ولی به یاد ندارم چه گزینه ای زدم
سوال ۱۸: گزینه ی ۴، دقیقا همانطور که کاربر mehdiii توضیح دادند.
سوال ۱۹: طمع کردم و گزینه ی ۱ رو زدم چون به نظرم با دوتا حلقه ی تو در تو این کار انجام میشد!
سوال ۲۰: گزینه ی ۳

[nomad:D]

سوال ۲ گزینه ۴ درسته
چون میتونیم فقط مجموعه ای که n عنصر دارد رو مرتب کنیم که این عمل را از مرتبه nlogn میتوان انجام داد
و در مرحله بعد تک تک عناصر مجموعه m عنصری را در مجموعه مرتب شده n عنصری (به روش جستجوی دودویی) جستجو کرد که این هم از مرتبه mlogn است.

---

این سوال دقیقا مشابه یکی از سوالات ساختمان ارشد هست که سالش یادم نیست. ولی روش حل همین بود که من گفتم.البته اگر طراح دکتری نظرش با طراح ارشد فرق نکنه !!!

[Mansoureh]

(۲۰ اسفند ۱۳۹۱ ۱۲:۲۹ ق.ظ)nomad:D نوشته شده توسط:  سوال ۲ گزینه ۴ درسته
چون میتونیم فقط مجموعه ای که n عنصر دارد رو مرتب کنیم که این عمل را از مرتبه nlogn میتوان انجام داد
و در مرحله بعد تک تک عناصر مجموعه m عنصری را در مجموعه مرتب شده n عنصری (به روش جستجوی دودویی) جستجو کرد که این هم از مرتبه mlogn است.

---

این سوال دقیقا مشابه یکی از سوالات ساختمان ارشد هست که سالش یادم نیست. ولی روش حل همین بود که من گفتم.البته اگر طراح دکتری نظرش با طراح ارشد فرق نکنه !!!

بله درست میفرمایید

[امیدوار]

سوال ۱۰ ، ۱۲ مورد جابجایی داریم
جابجایی ۷ بجای پدرش در حذف یک رخ نمیده بلکه ما وقتی ۱ رو حذف می کنیم چون با آرایه پیاده شازی شده اونو با ۷ که سمت راسترین برگ در سطح آخر است جابجا می کنیم و یک واحد از اندازه هیپ کم می کنیم و سپس heapify انجام داده که ۷ با ۳ جابجا میشه یعنی تو حذف ۱ ما دو جابجایی داریم در کل ۱۲ جابجایی دو عنصر در پیاده سازی با آرایه رخ می دهد

سوال ۱۴ ب و ج مثال نقض داره فقط دو مورد الف و د درسته

[mahdiii]

وای خدا چقدر نظرا متناقضن.
من در مورد سوال دو با بچه ها موافقم بحثم شد چهار میشه.
سوال ۱۰ ۱۲ تا داره به نظر من. فقط یه سوال اگه از ریشه عمل heapify رو انجام بدی و بیای پایین مثلا ریشه ۵ هست و فرزند چپش مثلا کمترینه مثلا هست ۱ و باز فرزند این گره دو هست که باز کمترینه ما یهو که ۵ و با ۲ جابجا نمی کنیم. فکر کنم اول ۵ با یک جابجا میشه و بعد در ادامه مسیر پنج با دو.
سوال ۱۴ سه تای اولش که غلطه. برای یک حتما طول کد با بیشترین تکرار یک نیست مثلا ۵ ۶ ۷ ۸ که ۵و۶ با هم میشن ۱۱ و ۷ و۸ که با هم میشن ۱۵ پس طول همه دو شد. برای چهار هم من یه راهی رفتم اونم غلط گرفتم خدا کنه درست باشه.
۱۹ خیلی وسوسه کننده بود چون به راحتی با دو حلقه تمام حالات چک میشن من نزدم ولی ای کاش می زدم احتمالا انقدر آبکی بوده؟

[Mansoureh]

من خیلی توی جواب دادن خنگ بازی در آوردم! وای خدایا... همه اش غلطه!

[Potential]

اون سوال هیپ کمینه سوال ما هم بود! منم k logn زدم

[امیدوار]

در مورد سوال ۱۴ درخت هافمن یک درخت دودویی است و همانطور که میدونیم میانگین ارتفاع درخت های دودویی ساخته شده با n برابر lgn است یعنی از ریشه تا هر برگ lgn بیت میای پایین خوب n کارکتر داری که کل بیت ها میشه nlgn که تقسیم بر n میشه lgn به نظر میاد مورد چهارم درست باشه

هیپ کمینه هم بهترین جواب فکر کنم دوستمون آقای psps1368 داده باشند و منطقی هم هست

[mahdiii]

کلا سوال ۱۴ سوال بدی بود. به نظر من این منظورش حالت میانگین (از نظر مرتبه) میانگین طول کدها نیست. فقط گفته میانگین طول کدها و بعدش نوشته O یعنی در بدترین حالت. مثال زیادی وجود داره که برای بدترین حالت on میشه میانگین طول کدها

[امیدوار]

نمیدونم شاید نظر من هم اشتباه باشه برای نقضش هم شده شما یه مثال بزنید من که چیزی به ذهنم نمیرسه هر چی مثال میزنم lgn میشه

[mahdiii]

منم خیلی با خودم کلنجار رفتم که بین بدترین و حالت میانگین یکیو انتخاب کنم. که گفتم چون گفته o پس بدترین باید باشه.
شما فرض کن دو کاراکتر با کمترین تکرارو انتخاب می کنی و بعدش نتیجه رو با سومین کوچکترین و باز نتیجه رو با چهارمین کوچکترین و ... مثل۱و۲و۳و۴و۷و۱۱ این طوری میشه یه فرمول براش درآورد. مجموع طول کدها میشه
$(n-2)(n-1)/2 2(n-1)$
که اگه بر n تقسیم کنی میشه حالت میانگین کدها در بدترین حالت که On هست

---

اینجا طول کدها به این صورت میشه برای یکی یک بعد دو بعد سه ... و دوتای آخر که n-1 هستن در اینجا ۵/ میانگین طول کدها با n/2 تناسب داره