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

[Farid_Feyzi]

سلام
در این پست قصد دارم پاسخ تشریحی سوالات درس ساختمان داده ها مربوط به آزمون دکتری ۹۲ رو قرار بدم.
از دوستانی که تو آزمون شرکت کرده بودن و یا دوستانی که امسال میخوان شرکت کنن، دعوت میشه که مشارکت داشته باشن و نظراتشونو راجع به سوالات بیان کنن.


سوالات رو از اینجا دانلود کنید :

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

********************************************************************************​​***********************

---

سوال۱: گزینه ۲ صحیح است.
مجموعه دوران هایی که بعد از درج ۴ باید انجام گیرد به ترتیب در شکل نشان داده شده است.

---

********************************************************************************​​***********************

سوال ۲: گزینه ۴ صحیح است.
کافیه که مجموعه کوچکتر رو سورت کنیم (nlogn)؛ بعد اعضای مجموع بزرگ رو یک به یک توی مجموعه کوچیکه باینری سرچ کنیم (mlogn)، جواب مجموع این دو خواهد بود.
توجه کنید گزینه ۲ فقط در حالت میانگین بوسیله جدول درهم ساز امکان پذیر است و در بدترین حالت نه!

---

********************************************************************************​​***********************

سوال ۳: گزینه ۴ صحیح است.
هر دو گزاره درست می باشند.

الف: هزینه سرشکن شده ی یک عمل اگر n بار تکرار شود، جمع بدترین حالت هزینه ی آن عمل بخش بر n است. پس مجموع هزینه سرشکن شده ی n عمل، کران بالای جمع هزینه های واقعی آن n عمل است.

ب: با رسم چند مثال براحتی میتوان به درستی گزاره پی برد.

---

********************************************************************************​​***********************

سوال۴: گزینه ۳ صحیح می باشد.

---

********************************************************************************​​***********************

سوال ۵: گزینه ۲ صجیج است.

---

********************************************************************************​​​***********************

سوال۶: گزینه ۴ صحیح است.

هر عمل ایجاد مجموعه و یافتن در این داده ساختار در زمان ثابت انجام میگیرد. از سویی دیگر، هر عمل ادغام، لیستی را ایجاد میکند که دست کم دوبرابر لیست کوچکتر است. هزینه سرشکن شده ی هر عمل ادغام در این نوع پیاده سازی lgn بوده و هزینه n بار انجام عمل، در مجموع nlgn خواهد بود.

---

********************************************************************************​​​​***********************

سوال۷: گزینه ۱ صحیح است.

از ریشه شروع می کنیم و DFS می زنیم، به هر گره ای که رسیدیم اگر شرط براش برقرار نبود(یعنی بزرگتر از k بود)
ادامه نمی دهیم و از اون زیردرخت برمی گردیم. هزینه اش همان k خواهد بود.

---

********************************************************************************​​​​​***********************

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

[Farid_Feyzi]

سوال ۹: گزینه ۳ صحیح است.
حداقل : (n/2(logn
حداکثر: nlogn-n+1

که به ترتیب معادل ۸۰ و ۱۲۹ میشود.

---

********************************************************************************​​​​​​***********************

سوال ۱۰: گزینه هیچ کدام!
مشخص نیست منظورش اول ۱ هست یا اول ۴ برای این پنج تا عدد! چون اصولاً وقتی با ویرگول و «و» می نویسن یعنی راست به چپ. و این که می‌گه چپ به راست خیلی عجیبه.

به هر حال با فرض این که اول ۴ و آخر ۱ درج بشه این مراحل هست:
۱/ [Add 4: [4
۲/ [Add 9: [4, 9
۳/ {Add 3: [4, 9, 3] => [3, 9, 4] {one swap of 3 with 4
۴/ {Add 7: [3, 9, 4, 7] => [3, 7, 4, 9] {one swap of 7 with 9
۵/ {Add 1: [3, 7, 4, 9, 1] => [3, 1, 4, 9, 7] => [1, 3, 4, 9, 7] {two swap of 1 with 7, then with 3
۶/ {Remove 1: [1, 3, 4, 9, 7] ~~{one swap}~~> [7, 3, 4, 9] => [3, 7, 4, 9] {one swap of 3 with 7
۷/ {Remove 3: [3, 7, 4, 9] ~~{one swap}~~> [9, 7, 4] => [4, 7, 9] {one swap of 4 with 9
۸/ {Remove 4: [4, 7, 9] ~~{one swap}~~> [9, 7] => [7, 9] {one swap of 7 with 9
۹/ [Remove 7: [7, 9] ~~{one swap}~~> [9
۱۰/ [Remove 9: [9] ~~~~> []
جمع اینا می‌شه ۴ تا جابجایی موقع اضافه کردن. ۴ تا موقع حذف کردن و آوردن اخرین عنصر به جای عنصر اول محذوف. ۳ تا هم موقع هیپیفای کردن نهایی. یعنی می‌شه ۱۱ تا. که توی گزینه‌ها نیست.
حالا اگه اون آرایه رو برعکس بگیریم (یعنی فرض کنیم منظور شروع از ۱ و انتها در ۴ باشه) قضیه این شکلی می‌شه:
۱/ [Add 1: [1
۲/ [Add 7: [1, 7
۳/ [Add 3: [1, 7, 3
۴/ [Add 9: [1, 7, 3, 9
۵/ {Add 4: [1, 7, 3, 9, 4] => [1, 4, 3, 9, 7] {one swap of 4 with 7
۶/ {Remove 1: [1, 4, 3, 9, 7] ~~{one swap}~~> [7, 4, 3, 9] => [3, 4, 7, 9] {one swap of 3 with 7
۷/ {Remove 3: [3, 4, 7, 9] ~~{one swap}~~> [9, 4, 7] => [4, 9, 7] {one swap of 4 with 9
۸/ [Remove 4: [4, 9, 7] ~~{one swap}~~> [7, 9
۹/ [Remove 7: [7, 9] ~~{one swap}~~> [9
۱۰/ [Remove 9: [9 ~~~~> []
اینم شده یکی موقع اضافه کردن. ۴ تا موقع حذف کردن. دو تا هم هیپیفای. مجموعش می‌شه ۷ تا. که بازم توی گزینه‌ها نیست.

[Farid_Feyzi]

سوال ۱۱: به زودی!

********************************************************************************​​​​​​***********************

---

سوال ۱۲: گزینه ۳ درست است.
مورد د صحیح نمی باشد.

********************************************************************************​​​​​​***********************

---

سوال ۱۳: گزینه ۲ درست است.
الف که مشخصه. ب هم گره های تک فرزندی رو نمیشه مشخص کرد.

********************************************************************************​​​​​​​***********************

---

سوال ۱۴: گزینه ۲ صحیح است.
۳ مورد الف و ب و ج مثال نقض دارند.

مثال نقض الف:
۵ ۶ ۷ ۸ را در نظر بگیریم، ۵ و ۶ با هم میشن ۱۱ و ۷ و ۸ که با هم میشن ۱۵. پس طول همه دو میشه.

مثال نقض ب:
اگر سری فیبوناچی ۱ ۱ ۲ ۳ ۵ ۸ را در نظر بگیریم، طول کد نویسه با کمترین تکرار n-1 خواهد شد.

مثال نقض ج:
سری فیبوناچی را در نظر بگیرید. ۱ ۱ ۲ ۳ ۵ ۸

مورد د:
درخت هافمن یک درخت دودویی است و میدانیم که میانگین ارتفاع درخت های دودویی ساخته شده با n عنصر برابر lgn است.
مطمئناً حالت هایی وجود داره که میانگین طول کدها بیشتر از لگاریتمی بشه، ولی باید حالت میانگین کلی را در گرفت. مثلا اگر سری فیبوناچی را برای n عدد در نظر بگیریم، طول کدها به ترتیب ۱ ۲ ۳ ۴ ... n-1 n-1 خواهد بود که اگه مجموعش تقسیم بر n شه، حاصل خطی و تابعی از n خواهد بود.

********************************************************************************​​​​​​​​***********************

---

سوال ۱۵: گزینه ۲ صحیح است.
بدیهی است.

********************************************************************************​​​​​​***********************

---

سوال ۱۶: گزینه ۲ صحیح است.

اگه علاوه بر شمارنده حلقه و متغیر کمکی برای جابه جا کردن عناصر آرایه، از دوتا متغیر دیگه هم بشه استفاده کرد که کافیه ان بار ماکسیمم رو پیدا کنیم ببریم ته. خیر اگه فقط باید با همون دو متغیر کارو انجام داد که باز میشه یه فور ان به توان ۲ آدم بزنه (مثلاً با متغیر حلقه x)، بعد بر حسب x%n و x/n در واقع دو تا متغیر حلقه رو شبیه‌سازی کنه، در این حالت هم میشه در زمان چندجمله ای مرتب سازی کرد.

********************************************************************************​​​​​​​***********************

---

سوال ۱۷: گزینه ۲ صحیح است.

مورد های اول و آخز نادرست می باشند. داده ساختار ارائه شده Treap می باشد، اگر همه زوج مرتب های x,y یکتا باشند، Treap حاصل یکتا خواهد بود، در غیر اینصورت ممکن است چندین Treap داشته باشیم.

********************************************************************************​​​​​​​***********************

---

سوال۱۸: گزینه ۴ صحیح است.

کافیه که اون تابع f رو برای گره ها درنظر بگیرید و بعدش با h ضرب و جمع کنید و حالتی که از همه کمتره رو پیدا کنین. کافیه چندتا درخت بکشین که جای گره ها عوض شده باشه. جواب میشه ۱و۲ یعنی دو درخت پیدا میشه که (h(4 یک و دو هست و در هردو مورد هم کمینه هست.

********************************************************************************​​​​​​​​***********************

---

سؤال ۱۹: گزینه ۳ صحیح است.

کافیه ما تمام ۲ به‌توان ۱۳۹۱ تا زیرمجموعه رو در نظر بگیریم. بعد حالا یه عمل «بررسی» تعریف می‌کنیم که ورودیش یه تعدادی از این زیرمجموعه‌ها هست، خروجیش هم اینه که آیا زیرمجموعه‌ای از بین اینای ورودی هست که جمع اعدادش K بشه یا نه. توش هم یه بار فقط از بلک باکس استفاده می کنه. حالا کارش چه جوریه؟ می یاد تمام این مجموعه‌ها رو دونه دونه می‌چینه پشت سر هم، بعد بین هر دو تای متوالی یه دونه عنصر k+1 قرار می‌ده! واضحه که این دنبال حاصل رو اگه بدیم به بلک باکس، جوابش همون جواب مورد انتظار ما از عمل «بررسی» هست.
حالا از اینجا به بعد یه باینری سرچ می‌خوایم که توی این دو به توان ۱۳۹۱ تا زیرمجموعه، دنبال یه «بله» بگرده. که خب هر سری زیرمجموعه‌های ممکن (با شروع از همه زیرمجموعه‌ها) رو نصف می‌کنیم و نصفش رو می‌دیم به این عمل بررسی. بعد اگه جواب بله یا خیر بود، یکی از این دو تا نصفه (یا اونی که دادیم به عمل بررسی، یا اگه جواب نه بود خب نصفه ی دیگری) رو انتخاب می کنیم. و هزینه نصف کردن فضای جواب ما وقتی یک باشه، با logn بار عمل می‌شه فضای کاندید جواب رو به یک زیرمجموعه رسوند. احتمالاً هم فرض طراح سؤال این بوده که تهش یه پرسش هم برای این که ببینیم آیا این تنها زیرمجموعه باقی‌مانده در فضای جواب (بعد از ۱۳۹۱ بار نصف کردن) اصلاً خودش چیز خوبی هست و جمعش K می شه یا نه. که خب نهایتاً تعداد پرسش ها به ۱۳۹۲ می رسه.

********************************************************************************​​​​​​​​​***********************

---

سوال ۲۰: گزینه ۳ صحیح است.
خیلی راحت بدست میاد.

[monica]

سلام
با تشکر از شما بخاطر پاسخ سوالات

در مورد سوال ۱۸ میشه یه کم بیشتر توضیح بدین؟ من هرجوری درخت رو می کشم در حالت کمینه عدد ۳۰ رو بدست میارم که در این حالت هم (h(4 یک هست

[Farid_Feyzi]

(۱۱ شهریور ۱۳۹۲ ۱۰:۵۶ ق.ظ)monica نوشته شده توسط:  سلام
با تشکر از شما بخاطر پاسخ سوالات

در مورد سوال ۱۸ میشه یه کم بیشتر توضیح بدین؟ من هرجوری درخت رو می کشم در حالت کمینه عدد ۳۰ رو بدست میارم که در این حالت هم (h(4 یک هست

سلام
با توجه به گزینه ۱ باید ارتفاع رو برای ریشه صفر در نظر بگیریم. برای دو درخت زیر که ارتفاع گره ۴ یک بار یک و یک بار دو در نظر گرفته شده، مقدار کمینه ۳۰ بدست میاد.

[monica]

(۱۱ شهریور ۱۳۹۲ ۰۱:۳۲ ب.ظ)Farid_Feyzi نوشته شده توسط:  با توجه به گزینه ۱ باید ارتفاع رو برای ریشه صفر در نظر بگیریم. برای دو درخت زیر که ارتفاع گره ۴ یک بار یک و یک بار دو در نظر گرفته شده، مقدار کمینه ۳۰ بدست میاد.

واقعا ممنونم، درخت سمت چپی رو امتحان نکرده بودم .

[nader14y]

با سلام

برای سوال ۸، فکر کنم در بدترین حالت تمامی عناصر در یک خانه از آرایه به صورت لیست پیوندی پشت سر هم ذخیره می شوند که هزینه جستجو n می باشد. !!!

[MahiS2012]

(۰۶ بهمن ۱۳۹۲ ۰۴:۴۳ ب.ظ)nader14y نوشته شده توسط:  با سلام

برای سوال ۸، فکر کنم در بدترین حالت تمامی عناصر در یک خانه از آرایه به صورت لیست پیوندی پشت سر هم ذخیره می شوند که هزینه جستجو n می باشد. !!!

دقیقا! به نظر من هم هزینه جستجو در بدترین حالت n است!

[amusavi]

سلام
در مورد سوال۱۱ من اینطوری فکر می کنم. بازش کنیم میشه
t(n)=n+(2*sigma(T(i)))

یعنی اگه معادله مشخصه رو بنویسیم از درجه n میشه . پس n تا ریشه داره.
مثلا ریشه ها میشن ۱و ۲و ۳و ۴و ....n
بعد ما داریم
۱به توان n+
۲ به توان n+
....
n به توان n

پس کلش از مرتبه n به توانn هست. گزینه ۴
اشکالش چیه اینطور فکر کردن؟

[fallah_o68]

(۱۱ اسفند ۱۳۹۲ ۰۵:۵۴ ب.ظ)amusavi نوشته شده توسط:  پس کلش از مرتبه n به توانn هست. گزینه ۴
اشکالش چیه اینطور فکر کردن؟

فکر میکنم استدلالتان درست باشد چون بنده هم با کشیدن درخت و پیمایش ۲ سطح آن متوجه شدم که مرحله اول n مرحله دوم n به توان ۲ و مرحله سوم n به توان۳ و ... به وجود آمد. بنابراین از مرتبه n به توان n میشود.
اما من توضیحات سوال ۱۹ آقای فریدخان را اصلا متوجه نشدم. کسی هست که یه مقدار موشکافانه بگه باید تو سوال ۱۹ چکار کرد و چطور حل میشه؟؟
در ضمن دوستانی که زحمت پاسخ به سوالات ساختمان ۹۲ دکتری را کشیدند کاش سوالات مربوط به سال ۹۱ دکتری را هم حل میکردند چون در پست مربوطه خیلی از سوالات حل نشده باقیمانده و به نظر من سال ۹۱ سوالات خیلی سختری نسبت به ۹۲ داشته. بنده خودم سولات ۳ و ۴ و ۹ را به هیچ وجه بلد نیستم. کسی هست که لطفا توضیح بده و یه کمکی به بنده بکنه؟؟
سوالات کنکور ۹۱ دکتری در آدرس زیر قابل دانلوده

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

[newmrd]

سلام.
در مورد سوال ۷
شما اومدین روی هیپ DFS زدین.

به نظر من اگه این اجاره رو داشتیم که روی درخت DFS بزنیم، باید تو صورت سوال اشاره می شد که می تونیم این کار رو بکنیم. وقتی می گیم هیپ، منظور ما اینه که فقط می تونیم از اپراتورهای محدودی (
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
) استفاده کنیم.

مهم ترین اپراتور استاندارد هیپ همون حذف ریشه (delete-max or delete-min) هست. که اگه محدود باشیم به استفاده از اپراتورهای خاص میشه k بار فراخوانی حذف ریشه، که هر حذف ریشه هم log n هزینه داره و میشه گزینه ۳/

البته بعید نیست که منظور سوال این کاری باشه که شما کردین و اگه ما اجازه پیمایش روی درخت رو داشته باشیم روش شما صحیح هست و میشه گزینه ۱

[mhghna]

سوال ۱۳: گزینه ۲ درست است.
الف که مشخصه. ب هم گره های تک فرزندی رو نمیشه مشخص کرد.



سلام
تو سوال گفته درخت دودیی ، پس میشه با یک پیش ترتیب یا پس ترتیب اونو یکتا کشید
من فکر می کنم گزینه ۴ میشه

[hamidsho]

دوستان دکترا میشه ی لطف کنید پاسخ تشریحی ساختمان داده و طراحی الگوریتم کنکور ایتی ۹۳ را برای بنده بنویسید ممنونتون میشم و لطف کنید کلید سنجش رو هم بررسی کنید