(۰۹ اسفند ۱۳۹۵ ۱۰:۴۴ ق.ظ)computerman نوشته شده توسط: من با تحلیلتون راجب سوال ۶ موافقم
چون هر بار در الگوریتم دایجسترا فاصله یک نود که کمترین مقدار را در میان مابقی دارد با مبدا تغییر میکند پس در کل دفعات O(n بار تغییر داریم که سرشکن شده آن O(1 است.
دقت کنید که باید اون مقدار اولیه بینهایت که در کد الگوریتم اومده رو نیز حتما لحاظ کنیم که مجموع به روز رسانی ها [tex]2n[/tex] باشد و با این تحلیل مرتبه [tex]O(1)[/tex] برامون قطعا صحیح باشه.
دلیل: اگر مقدار اولیه بی نهایت رو در نظر نگیریم و فقط به نکته ای که شما اشاره کردین بسنده کنیم قطعا تحلیل اشتباهی به مسئله داشتیم چرا که با این تحلیل اگر سر جلسه یکم بیشتر تامل میکردین رو گزینه ها، هر دو گزینه ۱ و ۴ اون لحظه صحیح به نظر میومدن!
(۰۸ اسفند ۱۳۹۵ ۰۳:۱۴ ب.ظ)robotic1981 نوشته شده توسط:(08 اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیشتوی همه منابع نوشته وقتی preorder , و postorder را داشته باشیم فقط در صورتی میتونیم به درخت واحد برسیم که برچسب برگها رو داشته باشیم اما اینجا که نداشتیم
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
برای سوال ۹ هم dfs O(N میشه و bfs log n
منظورم سوال ۱۹ بود که بنظرم گزینه ۴ درسته (اشتباهی نوشتم سوال ۹)
(۰۹ اسفند ۱۳۹۵ ۱۲:۲۲ ق.ظ)damash نوشته شده توسط:(07 اسفند ۱۳۹۵ ۰۸:۴۱ ب.ظ)ADELZX نوشته شده توسط: برای سوال دوم نیز این پیدا کردن k امین عنصر در یک درخت هیپ از مرتب klogk می باشد
جزئیات یک الگوریتم پیشنهادی برای آن در صفحه زیر موجود است
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
منم همین گزینه رو زدم.
(۰۷ اسفند ۱۳۹۵ ۱۰:۲۱ ب.ظ)robotic1981 نوشته شده توسط: ۵ رو شک داشتم نزدم
۳ و ۴ رو نزدین؟
سوال ۳ رو زدم logn و سوال ۴ هم زدم (n2)
(۰۸ اسفند ۱۳۹۵ ۰۶:۴۰ ب.ظ)tabestan نوشته شده توسط:به نظر من هم جواب سوال ۱۴ گزینه۱ میشه. برای اطمینان میتونیم با درنظرگرفتن پیمایش میان ترتیب گزینه۱، و دو پیمایش که توی سوال داده شده، درخت رو ترسیم کنیم. به شکل پیوستی نگاه کنید ببینید من درست میگم یا نه.روی این شکل هر سه تا پیمایش رو امتحان کنید(08 اسفند ۱۳۹۵ ۰۶:۰۵ ب.ظ)robotic1981 نوشته شده توسط:بله، دلیل این قضیه اینه که اگر درخت گره تک فرزند داشته باشه، صرفا با این دو پیمایش نمیشه مشخص کرد که اون تک فرزند، به عنوان فرزند چپ محسوب میشه یا راست. اما در صورتی که گره تک فرزند وجود نداشته باشه، میشه یک درخت منحصربفرد را تعیین کرد.(08 اسفند ۱۳۹۵ ۰۵:۳۹ ب.ظ)mahditorki نوشته شده توسط: در مورد اینکه چطور میشه فهمید گره تک فرزند تداره علاوه بر مطلب قبل یاداوری کنم که :
N0=N2+1
پیدا کردن برگها هم گفته شد.
من مدرسان شریف و کتاب دکتر قدسی رو خوندم تو هردوش نوشته بود با pre و post نمیشه به درخت واحد رسید
من با اطمینان کامل این تست رو زدم
در خصوص سوال ۱۴ منم به همین شکل رسیدم و بنظرم گزینه ۱ درسته. ضمنا در کتاب ساختمان داده مقسمی نوشته شده "در صورتیکه پیمایش های preorder و postorder درخت را داشته باشیم ممکن است بتوانیم درخت منحصر بفرد رسم کنیم"
لطفا کمی هم در خصوص سوالات پایگاه داده بحث کنید
سوال ۱۴ گزینه ۱ صحیح است
برای پیدا کردن روش حل اینگونه سوالات، رجوع شود به روش حل سوال ۵۱ کنکور ارشد ۹۳ مهندسی نرم افزار در کتاب ساختمان داده آقای یوسفی
(۰۹ اسفند ۱۳۹۵ ۱۱:۲۴ ق.ظ)lojanak نوشته شده توسط:چرا ۴؟(08 اسفند ۱۳۹۵ ۰۳:۱۴ ب.ظ)robotic1981 نوشته شده توسط:(08 اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیشتوی همه منابع نوشته وقتی preorder , و postorder را داشته باشیم فقط در صورتی میتونیم به درخت واحد برسیم که برچسب برگها رو داشته باشیم اما اینجا که نداشتیم
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
برای سوال ۹ هم dfs O(N میشه و bfs log n
منظورم سوال ۱۹ بود که بنظرم گزینه ۴ درسته (اشتباهی نوشتم سوال ۹)
۲۶ که به دست میاد
به نظر شما سطح سوالات تخصصی نسبت به سال های قبل چطور بود؟
میشه درصدمون رو با قبولی های سال های قبل مقایسه کنیم؟
کسی رو میشناسین که با عمومی خیلی بعد سال های قبل قبول شده باشه؟
البته من هوش مصنوعی هستم
(۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط: به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.
سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه.
سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!!
سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره.
سوال ۱۷ رو گزینه۴ زدم.
لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی
منم همینا روزدم که شما زدی. البته ۱۳ رو نزدم
(۰۹ اسفند ۱۳۹۵ ۱۲:۱۶ ب.ظ)robotic1981 نوشته شده توسط: به نظر شما سطح سوالات تخصصی نسبت به سال های قبل چطور بود؟
میشه درصدمون رو با قبولی های سال های قبل مقایسه کنیم؟
کسی رو میشناسین که با عمومی خیلی بعد سال های قبل قبول شده باشه؟
البته من هوش مصنوعی هستم
من فکر میکنم سوالات تخصصی مثل هر سال بود فقط ممکنه استعداد کمی سخت تر شده باشه
نظر شما چیه؟
(۰۹ اسفند ۱۳۹۵ ۱۲:۰۴ ب.ظ)computerman نوشته شده توسط:والا اگه طبق الگوریتمش حساب کنیم باید آخرش با ۶ هم جمع بشه که میشه ۳۲/ اما (min (2,2 رو چجوری حساب کردین? بنظرم الگوریتم خاتمه پیدا نمیکنه(09 اسفند ۱۳۹۵ ۱۱:۲۴ ق.ظ)lojanak نوشته شده توسط:چرا ۴؟(08 اسفند ۱۳۹۵ ۰۳:۱۴ ب.ظ)robotic1981 نوشته شده توسط:(08 اسفند ۱۳۹۵ ۱۲:۵۹ ب.ظ)lojanak نوشته شده توسط: ۳۹ گزینه ۴ میشه. عین سوال دو سال پیشتوی همه منابع نوشته وقتی preorder , و postorder را داشته باشیم فقط در صورتی میتونیم به درخت واحد برسیم که برچسب برگها رو داشته باشیم اما اینجا که نداشتیم
۱۴ هم ۴ نمیشه. گزینه ۳ درسته
سوال ۹ چطور به گزینه ۲ رسیدین؟؟ بنظرم گزینه ۴ درسته
برای سوال ۹ هم dfs O(N میشه و bfs log n
منظورم سوال ۱۹ بود که بنظرم گزینه ۴ درسته (اشتباهی نوشتم سوال ۹)
۲۶ که به دست میاد
(۰۹ اسفند ۱۳۹۵ ۰۳:۰۰ ب.ظ)hani89 نوشته شده توسط:من سر جلسه فکر میکردم که تخصصی امسال خیلی راحت تر از سالهای قبل هست، اما حالا که دارم نگاه میکنم و بررسی میکنم میبینم هر کدوم یه نکته ای داشته و راحت نبوده، ظاهرش راحت بوده..(09 اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط: به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.
سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه.
سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!!
سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره.
سوال ۱۷ رو گزینه۴ زدم.
لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی
منم همینا روزدم که شما زدی. البته ۱۳ رو نزدم
(۰۹ اسفند ۱۳۹۵ ۱۲:۱۶ ب.ظ)robotic1981 نوشته شده توسط: به نظر شما سطح سوالات تخصصی نسبت به سال های قبل چطور بود؟
میشه درصدمون رو با قبولی های سال های قبل مقایسه کنیم؟
کسی رو میشناسین که با عمومی خیلی بعد سال های قبل قبول شده باشه؟
البته من هوش مصنوعی هستم
من فکر میکنم سوالات تخصصی مثل هر سال بود فقط ممکنه استعداد کمی سخت تر شده باشه
نظر شما چیه؟
در مورد استعداد که معتقدم که سوالها وحشتناک بوده
من سال ۹۴ هم شرکت کرده بودم بدون مطالعه استعداد رو زدم ۵۶
اما امسال همه رو با شک و تردید زدم شایدم منفی زده باشم
اگه عمومی رو بهتر داده بودم قبول میشدم اما با این وضعیت بعید میدونم
چون رتبه های سالهای قبل رو دیدم همه اونهایی که تخصصی بالای ۳۰ زدن با یک عمومی متوسط رتبشون زیر ۵۰ شده
حیف ۳ ماه روزی ۸ ساعت براش وقت گذاشته بودم هدر رفت
(۰۹ اسفند ۱۳۹۵ ۰۵:۵۳ ب.ظ)robotic1981 نوشته شده توسط:(09 اسفند ۱۳۹۵ ۰۳:۰۰ ب.ظ)hani89 نوشته شده توسط:من سر جلسه فکر میکردم که تخصصی امسال خیلی راحت تر از سالهای قبل هست، اما حالا که دارم نگاه میکنم و بررسی میکنم میبینم هر کدوم یه نکته ای داشته و راحت نبوده، ظاهرش راحت بوده..(09 اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط: به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.
سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه.
سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!!
سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره.
سوال ۱۷ رو گزینه۴ زدم.
لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی
منم همینا روزدم که شما زدی. البته ۱۳ رو نزدم
(۰۹ اسفند ۱۳۹۵ ۱۲:۱۶ ب.ظ)robotic1981 نوشته شده توسط: به نظر شما سطح سوالات تخصصی نسبت به سال های قبل چطور بود؟
میشه درصدمون رو با قبولی های سال های قبل مقایسه کنیم؟
کسی رو میشناسین که با عمومی خیلی بعد سال های قبل قبول شده باشه؟
البته من هوش مصنوعی هستم
من فکر میکنم سوالات تخصصی مثل هر سال بود فقط ممکنه استعداد کمی سخت تر شده باشه
نظر شما چیه؟
در مورد استعداد که معتقدم که سوالها وحشتناک بوده
من سال ۹۴ هم شرکت کرده بودم بدون مطالعه استعداد رو زدم ۵۶
اما امسال همه رو با شک و تردید زدم شایدم منفی زده باشم
اگه عمومی رو بهتر داده بودم قبول میشدم اما با این وضعیت بعید میدونم
چون رتبه های سالهای قبل رو دیدم همه اونهایی که تخصصی بالای ۳۰ زدن با یک عمومی متوسط رتبشون زیر ۵۰ شده
حیف ۳ ماه روزی ۸ ساعت براش وقت گذاشته بودم هدر رفت
عجیبه که من اصلا در مورد اختصاصی ها سر جلسه اینطور فکر نمیکردم. کاملا انتظار همین سوالا رو داشتم. سوالهای سالهای قبل هم دقیقا به ظاهر ساده ولی پر از نکته بود که باعث میشد ادم به راحتی سوالها رو غلط جواب بده.. امسال هم مشابه سالهای قبل بود
نه اینطور فکر نکنید، شرایط برای همه یکسان بوده. وقتی سال ۹۴ انقدر استعداد و خوب زدید قطعا امسال هم جزو درصدهای برتر تو اون درس هستین. حالا ممکنه مثلا ۲۰ یا ۱۰ درصد زده باشین ولی درصدهای همه همینقدر پایین اومده..
دوستان فک می کنم سوال ۱۸ میشد گزینه ۲ یعنی logn. چون حلقه اول که یک عدد ثابته. حلقه دوم به دلیل j=j*2 تا logn پیش میره. حلقه سوم هم که هربار با شرط درست شروع میکنه، اما به محض اجرا b=0 میشه و میاد بیرون.
ضمنا منم جواب سوال ۱۹ رو ۲۶ آوردم. (گزینه۲)
سوال ۲۰ رو هم زدم n2، فک میکنم در حالت عادی، پیچیدگی نمایی بشه (۲ به توان n منهای یک)، ولی به کمک روش پویا و استفاده از یک ماتریس میشه n2.
تحلیلم درسته یا نه ؟
(۰۸ اسفند ۱۳۹۵ ۰۱:۴۰ ق.ظ)computerman نوشته شده توسط: اقای mahditorki منم موافقم با نظرتون راجب به سوال ۳
چون از O استقاده کرده و O یعنی همه حالت یه الگوریتم حداکثر به این پیچیدگی برسن و به نطر من هم O)nمیشهنا
راس میگینا
برای سوال ۲ که هر دو گزینه ۳ و ۴ درسته ک
به نظرم روی کلید اولیه اومد اعتراض کنیم ممکنه به خاطر کلمه "بهترین" بگن نه هر دوش امکان پذیر نیست؟
درمورد سوال ۳ تحلیل بنده این بود که هروقت در سوال به "بدترین حالت" اشاره نشده، منظور سوال همون حالت "میانگین" هستش. اما تحلیل شما و سایر دوستان هم قابل توجه هستش که نماد O یعنی پوشش همه حالات!
در مورد سوال ۲، به نظرم گزینه۴ درسته. چون همونطور که میدونیم، حذف از هیپ به ارتفاع هیپ (logn) بستگی داره، برای پیداکردن kامین مینیمم، باید kبار حذف ریشه از هیپ انجام بشه که پیچیدگی اون klogn خواهد بود. اما یه راه حل ساده تر هم هست:
بیایم یک هیپ جدید بسازیم، ریشه هیپ قبلی رو در هیپ جدید کپی و درج کنیم (دقت کنید گفتم کپی از هیپ قبلی که دیگه مجبور نشیم این هیپ قبلی رو هربار heapify کنیم). حالا kبار از این هیپ جدید، ریشه رو حذف کنیم و هربار فرزندان این گره حذف شده رو از هیپ قدیم در هیپ جدید درج کنیم. kامین حذف ریشه به معنی kامین مینیمم هستش.
(فلسفه این روش اینه که ارتفاع درخت بجای logn میشه logk، درنتیجه kبار حذف ریشه از این هیپ، برامون هزینه klogk داره و چون درخت ارتفاع کمتری داره و درج و حذف از اون به صرفه تره)
درمورد سوالات عمومی هم بگم بنده سال گذشته به صورت دورهمی شرکت کردم، ۳۳درصد هوش زدم (به سوالات زبان نرسیدم). اما امسال فقط ۸ سوال اول رو که در مورد تحلیل متن بود، تونستم جواب بدم. احتمالا سه حالت داره:
۱- یا هوش بنده نسبت به پارسال کم شده!
۲- یا سوالات سخت تر شده بود!
۳- یا اینکه برعکس پارسال که موقع جواب دادن به سوالات تخصصی بیخیال و راحت بودم، امسال فشار زیادی بهم اومده و واسه سوالات هوش قند خون کم آوردم.
دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
(۱۰ اسفند ۱۳۹۵ ۱۰:۲۸ ق.ظ)computerman نوشته شده توسط: دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
سلام
۱۰۱ ۲
۱۰۲ ۳
۱۰۴ ۳
(۱۰ اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)sooshian67 نوشته شده توسط:(10 اسفند ۱۳۹۵ ۱۰:۲۸ ق.ظ)computerman نوشته شده توسط: دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
سلام
۱۰۱ ۲
۱۰۲ ۳
۱۰۴ ۳
۱۰۱ - ۱
۱۰۲ - ۲
۱۰۳ - ۳
۱۰۴ - ۲
جالبه که هیچ کدوم رو مثل computerman نزدم!!!
خدا بخیر کنه اوضاع ما رو با این سوالات عجیب استعداد تحصیلی
(۱۰ اسفند ۱۳۹۵ ۰۸:۵۱ ب.ظ)damash نوشته شده توسط:منم هیچ کدوم از این جواب ها رو نزدم که(10 اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)sooshian67 نوشته شده توسط:(10 اسفند ۱۳۹۵ ۱۰:۲۸ ق.ظ)computerman نوشته شده توسط: دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
سلام
۱۰۱ ۲
۱۰۲ ۳
۱۰۴ ۳
۱۰۱ - ۱
۱۰۲ - ۲
۱۰۳ - ۳
۱۰۴ - ۲
جالبه که هیچ کدوم رو مثل computerman نزدم!!!
خدا بخیر کنه اوضاع ما رو با این سوالات عجیب استعداد تحصیلی
فقط پرسیدم چی زدین شما؟
که یکی از دوستانمون جواب دادن
(۱۱ اسفند ۱۳۹۵ ۰۲:۱۱ ق.ظ)computerman نوشته شده توسط:(10 اسفند ۱۳۹۵ ۰۸:۵۱ ب.ظ)damash نوشته شده توسط:منم هیچ کدوم از این جواب ها رو نزدم که(10 اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)sooshian67 نوشته شده توسط:(10 اسفند ۱۳۹۵ ۱۰:۲۸ ق.ظ)computerman نوشته شده توسط: دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
سلام
۱۰۱ ۲
۱۰۲ ۳
۱۰۴ ۳
۱۰۱ - ۱
۱۰۲ - ۲
۱۰۳ - ۳
۱۰۴ - ۲
جالبه که هیچ کدوم رو مثل computerman نزدم!!!
خدا بخیر کنه اوضاع ما رو با این سوالات عجیب استعداد تحصیلی
فقط پرسیدم چی زدین شما؟
که یکی از دوستانمون جواب دادن
۱۰۱ - ۲
۱۰۲ - ۱
۱۰۳ - ۳
۱۰۴ - ۱
(۱۱ اسفند ۱۳۹۵ ۰۸:۰۳ ق.ظ)hani89 نوشته شده توسط:(11 اسفند ۱۳۹۵ ۰۲:۱۱ ق.ظ)computerman نوشته شده توسط:(10 اسفند ۱۳۹۵ ۰۸:۵۱ ب.ظ)damash نوشته شده توسط:منم هیچ کدوم از این جواب ها رو نزدم که(10 اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)sooshian67 نوشته شده توسط:(10 اسفند ۱۳۹۵ ۱۰:۲۸ ق.ظ)computerman نوشته شده توسط: دوستان کسی از سوال های استعداد سوالات ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۱۴ روجواب داده؟
سلام
۱۰۱ ۲
۱۰۲ ۳
۱۰۴ ۳
۱۰۱ - ۱
۱۰۲ - ۲
۱۰۳ - ۳
۱۰۴ - ۲
جالبه که هیچ کدوم رو مثل computerman نزدم!!!
خدا بخیر کنه اوضاع ما رو با این سوالات عجیب استعداد تحصیلی
فقط پرسیدم چی زدین شما؟
که یکی از دوستانمون جواب دادن
۱۰۱ - ۲
۱۰۲ - ۱
۱۰۳ - ۳
۱۰۴ - ۱
۱۰۲ , ۱۰۴ خیلی جالبه ۳ نفریم ۳ تا گزینه مختلف
اینم از سوالهای درک مطلب اسونه استعداد...