ساختمان داده رو من منفی زدم!
۵۳ رو که اشتباه کردم و ۴ رو زدم در حالی که واضحه ۳ میشه.
۵۶ رو هم ۳ زدم و فکر می کردم ۱ ریشه مرتبه دوم هست.حالا که حساب کردم دیدم ریشه مرتبه ۳ هست و جواب از مرتبه n میشه و گزینه ۲ درسته.
۵۵ هم که قبلا غلط زده بودم.
۵۲ هم چونکه جوابم بین دو گزینه ۳ و ۴ در میومد گزینه‌ی ۳ رو زدم که بچه‌ها میگند به گزینه‌ی ۴ رسیدند.
در صورتی که ۵۴ را درست زده باشم(گزینه ۲) باز هم نمره منفی میخورم.
الان من باید ناراحت باشم؟!
۵۲ من هر چی حساب میکنم میشه ۳۴۳۵ فکر کنم ۳۴۴۵ اشتباه تایپی باشه ها!!
۵۵ هم که هنوز توش شک هست.
سوال ۵۴ رو چه طوری به ۲ رسیدید؟
دوستانی که کلید A داشتند یادشون هست که گزینه ۲ همین گزینه بود یا نه؟
در مورد سوال ۵۴ بازم مثله ۵۳ یه درخت بکش به گزینه دو میرسی فکر کنم این سوال فرق میکرد من دفترچم c بود گزینه یک میشد.
ئر مورد سوال ۵۵ هم بگم تو کتاب کورمن فصل ۱۴ درحت اماره پویا جواب این سوال میشه که مطمینا گزینه ۳ جوابه البته اگه ملاک کورمن باشه که هست.
(۰۲ اسفند ۱۳۸۹ ۰۲:۱۱ ب.ظ)www نوشته شده توسط: در مورد سوال ۵۴ بازم مثله ۵۳ یه درخت بکش به گزینه دو میرسی فکر کنم این سوال فرق میکرد من دفترچم c بود گزینه یک میشد.اون درختی که شما می گی دیگه فضای اضافی نمی خاد.
ئر مورد سوال ۵۵ هم بگم تو کتاب کورمن فصل ۱۴ درحت اماره پویا جواب این سوال میشه که مطمینا گزینه ۳ جوابه البته اگه ملاک کورمن باشه که هست.
منظورتو متوجه نشدم
سلام
من این چند روزه خیلی سرم شلوغ بوده. خوب گویا امسال پیشبینی من مبنی بر متفاوت بودن درست از آب در اومده.
سوال ۵۵ به نظر من گزینه ۱ کاملاً درسته. این دادهساختار رو میشه به راحتی به روش hash و با شماردن تعداد تکرارها به وجود آورد. توی متن سوال اشاره کرده که عناصر تکرار فرقی با هم ندارند، بنابراین تنها کافیه که تعداد تکرارها رو توی خانه مربوطه قرار بدیم.
الگوریتم اضافه عدد n برابر است با اضافه کردن مقدار خانه nام آرایه
الگوریتم حذف عدد n برابر است با کاهش مقدار خانه n ام، در صورتی که خانه n صفر نباشد( یعنی عنصر وجود داشته باشد)
الگوریتم یافتن عدد n برابر است با مقدار خانه n (که نشان دهنده تعداد موجود از n است) اگر این خانه صفر باشد یعنی عنصر وجود ندارد.
پیچیدگی ساختار بالا از لحاظ الگوریتمی برابر O1 و از لحاظ حافظه برابر طول آرایه یعنی رادیکال n است.
بله منم گفتم ۵۵-۱ میشه فقط با hash یا counting ????
در مورد سوال ۵۱ ساختمان داده: گزینه ۴
با پیچیدگی nlogn میتوان لیست A و با همین پیچیدگی لیست B را مرتبسازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو مینماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.
نکته: میتوان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار میشود!!
من فکر میکنم سوال ۵۵-۳ میشه بابا هشم در نظر بگیری خودش گفته میشه عناصری تکراری داشت پس میشه ۳ دیگه.
(۰۳ اسفند ۱۳۸۹ ۰۹:۵۱ ق.ظ)admin نوشته شده توسط: در مورد سوال ۵۱ ساختمان داده: گزینه ۴
با پیچیدگی nlogn میتوان لیست A و با همین پیچیدگی لیست B را مرتبسازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو مینماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.
نکته: میتوان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار میشود!!
دکتر نظرتون در مورد این الگوریتم چیه:
در سوال نگفته از چه نظر بهینه باشه.پس ما تنها از لحاظ سرعت اجرا(که در اکثر موارد همینه)،الگوریتم خواسته شده رو در نظر می گیریم.
حالتی رو در نظر بگیرید که بشه با استفاده از درج عناصر در hashی متعادل(به روش مستقیم فرضا،البته گفته میشه که در صورت استفاده از حداکثر چند بار rehashing با توابع بررسی شده،میتونیم همواره جدول hash متعادلی داشته باشیم که از صحت اون من بی اطلاعم) عناصر آرایه اول رو به ساختمان اضافه کرد.در ادامه آرایه دوم رو را در hash قبلی درج می کنیم و در صورت بروز برخورد و تساوی مقادیر اونا رو چاپ می کنیم.
مرتبه الگوریتم فوق در صورت استفاده از hashی متعادل در حالت میانگین و بدترین حالت از مرتبه n هستش.
پس گزینه مناسب،از نظر من گزینه ۱ه.نظر دیگران هم قابل احترامه و ممکنه بنده اشتباه کنم.
(۰۲ اسفند ۱۳۸۹ ۰۷:۳۴ ب.ظ)admin نوشته شده توسط: سلام
من این چند روزه خیلی سرم شلوغ بوده. خوب گویا امسال پیشبینی من مبنی بر متفاوت بودن درست از آب در اومده.
سوال ۵۵ به نظر من گزینه ۱ کاملاً درسته. این دادهساختار رو میشه به راحتی به روش hash و با شماردن تعداد تکرارها به وجود آورد. توی متن سوال اشاره کرده که عناصر تکرار فرقی با هم ندارند، بنابراین تنها کافیه که تعداد تکرارها رو توی خانه مربوطه قرار بدیم.
الگوریتم اضافه عدد n برابر است با اضافه کردن مقدار خانه nام آرایه
الگوریتم حذف عدد n برابر است با کاهش مقدار خانه n ام، در صورتی که خانه n صفر نباشد( یعنی عنصر وجود داشته باشد)
الگوریتم یافتن عدد n برابر است با مقدار خانه n (که نشان دهنده تعداد موجود از n است) اگر این خانه صفر باشد یعنی عنصر وجود ندارد.
پیچیدگی ساختار بالا از لحاظ الگوریتمی برابر O1 و از لحاظ حافظه برابر طول آرایه یعنی رادیکال n است.
دقیقا،کاملا با نظرتون موافقم.
احساس می کنم طراح اکثر سوالات را بر مبنای hash طرح کرده باشند.
در مورد سوال ۵۳ با گزینه ۴ موافقم.
(۰۳ اسفند ۱۳۸۹ ۰۹:۵۱ ق.ظ)admin نوشته شده توسط: در مورد سوال ۵۱ ساختمان داده: گزینه ۴من این سوال رو گزینه ۱ زدم (میانگین و بدترین [tex]O(n)[/tex]
با پیچیدگی nlogn میتوان لیست A و با همین پیچیدگی لیست B را مرتبسازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو مینماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.
نکته: میتوان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار میشود!!
آخه گفتم هر سری کوچکترین عنصر از هر آرایه با استفاده از "درخت تورنمنت " میکشیم بیرون و با هم مقایسه میکنیم و به همین ترتیب پیش میریم
و تو کتاب مقسمی خونده بودم یک قضیه رو که Kامین عنصر از یک آرایه رو میشه با [tex]O(n)[/tex] بدست آورد.
؟!
در مورد hash که دوستمون مطرح کردند درباره سوال ۵۱ به هیچ وجه امکان چنین کاری وجود نداره. از لحاظ تئوری باید بدترین حالت رو در نظر بگیریم و بدترین حالت hash هر چند که متعادل هم باشه اینه که همه مقادیر به یک خانه map شوند و در این حالت الگوریتم مطرح شده شما از مرتبه n به توان ۲ خواهد بود. الگوریتم hash رو در مورد سوال ۵۵ میشد به کار برد اما توی این سوال نه.
از لحاظ تئوری بدترین حالت hash برای insert و find از O( n )l هست اما به طور میانگین برای hash این دو عملیات O(1)l زمان میبره و من فکر میکنم نظر طراح هم گزینه ۲ بوده.( خودم ۴ زدم )
(۰۳ اسفند ۱۳۸۹ ۱۱:۳۴ ب.ظ)admin نوشته شده توسط: در مورد hash که دوستمون مطرح کردند درباره سوال ۵۱ به هیچ وجه امکان چنین کاری وجود نداره. از لحاظ تئوری باید بدترین حالت رو در نظر بگیریم و بدترین حالت hash هر چند که متعادل هم باشه اینه که همه مقادیر به یک خانه map شوند و در این حالت الگوریتم مطرح شده شما از مرتبه n به توان ۲ خواهد بود. الگوریتم hash رو در مورد سوال ۵۵ میشد به کار برد اما توی این سوال نه.وقت به خیر.
لطف کنید سری به سایت زیر که یه تعدادی تست در زمینه کامپیوتر داده به همراه پاسخ تشریحی،(سوالاتی که در مصاحبه افراد در بدست آوردن شغل در شرکت های مهمی همچون مایکروسافت،گوگل و ... پرسیده شده)،بزیند:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
There are two unsorted array. Find the intersection of both
Method 1) Sort and Compare, O(logn)+O(n) time complexity
...
Method 2) HashMap, O(n) time complexity
Create a HashMap and put all the elements of A
Visit all the elements of B and put it on the same HashMap.
If there is a collision while inserting into the HashMap from B then print the element which is intersection of both the array A and B
Method 1) Sort and Compare, O(logn)+O(n) time complexity
...
Method 2) HashMap, O(n) time complexity
Create a HashMap and put all the elements of A
Visit all the elements of B and put it on the same HashMap.
If there is a collision while inserting into the HashMap from B then print the element which is intersection of both the array A and B