من البته هوش بودم. ولی سوالای ساختمان یکی بود. (دفترچه F - برای تخصصی نرم افزار که توی سایت آپلود شده)
لینک دفترچه:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
۱- نزدم
۲- گزینه ۲ - با جدول درهم سازی با تابع درهم سازی خوب به ازای هر برخورد یه عنصر مشترک میاد. پس اگر هیچ برخوردی رخ نده، عنصر مشترک ندارن. (توی ارشد ۹۰ هم سوال اول ساختمان این نکته رو داشت. چون چیزی هم توی سوال مثل مبتنی بر مقایسه و اینا گفته نشده، فکر کنم جواب منطقی باشه)
۳- من گزینه ۴ رو زدم ولی فکر کنم گزینه ۳ میشه. چون دومی همیشه درست نیست. مثلا توی زنجیر...
۴- گزینه ۳ - n عمل درج که برای هر عنصر داریم. توان های دو هم هر کدوم موقع ساخت جدول جدید هزینه رو به اندازه خودشون اضاه می کنن. جمع توان های دو تا n میشه ۲n که در مجموع هزینه میشه ۳n که تقسیم بر n همون ۳ میشه.
۵- گزینه ۲
۶- نزدم
۷- گزینه ۱ - چون ترتیب این عناصر مهم نیست با یه DFS روی هیپ با شروع از ریشه و ادامه اون تا جایی که بزرگتر از x بشه. واضحه که فقط روی عناصر کوچکتر از x حرکت می کنیم.
۸- گزینه ۳
۹- گزینه ۳- مرتب سازی ادغامی در بهترین حالت n/2logn و در بدترین حالت nlogn - n + 1 مقایسه انجام می دهد.
۱۰ - نزدم
۱۱- گزینه ۲
[tex]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)[/tex]
۱۲- گزینه ۳ - به نظرم اگر گزینه الف و ب درست باشه ج هم درسته! صرفا دلیلم همین بود!
۱۳- گزینه ۲ - الف که مشخصه. ب هم گره های تک فرزندی رو نمیشه مشخص کرد.
۱۴- نزدم
۱۵- گزینه ۲
[tex]3^{log n}=n^{log 3}[/tex]
[tex]3log~n < log~n~loglog~n \Rightarrow log~n^3 < log (log~n^{log~n})\Rightarrow n^3 < log~n ^{log n}[/tex]
۱۶- نزدم
۱۷- گزینه ۱- فقط سومی درسته. همیشه میشه چنین درختی ساخت که اتفاقا یکتا هم هست. به راحتی میشه مثالی زد که ارتفاع درخت بشه n. مثلا (۱,۲) - (۳,۴) - (۵,۶) - و به همین ترتیب. با این مثال جمله دوم و چهارم نقض میشه.
۱۸- نزدم
۱۹- نزدم
۲۰- گزینه ۳ - به راحتی بدست میومد.
من هم بیشترین مقدار ممکن رو زدم یعنی گزینه ی ۴.
