بررسی سوالات طراحی و ساختمان IT سال ۹۳ - نسخهی قابل چاپ |
بررسی سوالات طراحی و ساختمان IT - راضیه اکبری - ۲۴ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ
برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا |
RE: سوال ساختمان داده - parinaz_st70 - 24 بهمن ۱۳۹۲ ۰۲:۴۸ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۲۹ ب.ظ)راضیه اکبری نوشته شده توسط: سلامتو بدترین کیس من زیک زاک رفتم یعنی ۱۳۵۷ و اون یکی هم ۲۴۶۸ به نظرم بیشتر از این دیگه نمیشه چون تو هر گام مقایسه داریم که شذ ۷ تا ۲n-1! |
سوال ساختمان داده - amirgh142 - 24 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ
گزینه ها رو برعکس نداده بودن؟؟؟ حداقل و حداکثر و میخواست به ترتیب اما جاشون اشتباه بود فکر کنم.. منظورم اینه که حداکثر اول نوشتن بعدش حداقل... منم ۲n-1 و n رو آوردم |
بررسی سوالات طراحی و ساختمان IT - parinaz_st70 - 24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ
k هی داشت نصف میشد تو هر محله هم nk باهاش جمع میشد زدم nklgk |
RE: بررسی سوالات طراحی و ساختمان IT - sahar_rostami2 - 24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط: مرتبه زمانی T(k,n) رو من زدم O(nk) من knlogn زدم...سوال ماکس هیپ هم nlogm +mlogn |
بررسی سوالات طراحی و ساختمان IT - blue70 - 24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ
سلام به همه اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟ nlogn یا log n؟ |
RE: بررسی سوالات طراحی و ساختمان IT - Fot30 - 24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط: برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا اگر هر دو آرایه باشن میشه به صورت درجا با O(N) هیپ ساخت. |
سوال ساختمان داده - iammiti - 24 بهمن ۱۳۹۲ ۰۲:۵۱ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)راضیه اکبری نوشته شده توسط: ببینید در الگوریتم merg sort در ساختمان داده انتهای دو تا لیست یک بی نهایت میذارن در نتیجه مقایسه دو لیست اینجوری میشه که میگین منتهی این جا دو لیست مرتب داریم اگه بزرگترین عنصر یکی از لیست ها از عنصر اول لیست دیگه کوچکتر باشه خب بقیه عناصر لیست اول هم کوچکتر میشن دیگه مقایسه نمیخوادشرایط خاص در نظر نگیرید در حل مساله..همیشه باعث خطا میشه..شما تو این مورد شرایط خاص گرفتین n=1 , n=2 مثال میزدید راحت به جواب میرسیدید..البته n=1 کافی بود تا ۳تا گزینه حذف بشه |
بررسی سوالات طراحی و ساختمان IT - mehdi1902 - 24 بهمن ۱۳۹۲ ۰۲:۵۲ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط: مرتبه زمانی T(k,n) رو من زدم O(nk)به نظر منم O(nk) میشه ! |
RE: بررسی سوالات طراحی و ساختمان IT - izadan11 - 24 بهمن ۱۳۹۲ ۰۲:۵۲ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط: مرتبه زمانی T(k,n) رو من زدم O(nk)من هم nk زدم با اینکه اثباتش کردم ولی باز ازش مطمئن نبودم اینجور عمل کرد که [tex]\frac{n1k}{2} \frac{n2k}{2}=\frac{k}{2}(n1 n2)[/tex] پس هر بار نصف میشه در نتیجه با سری هندسی شد kn (۲۴ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)Orchid نوشته شده توسط: من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟ من این سوال مشکل داره چون ما نمی دونیم مرتبه n و m چه جوری هست فرض کنیم m>n الان با یک راه(اضافه کردن یکی یکی) حل میشه nlogm و با یه راه حل دیگه میشه n+m الان کدوم کوچکتره؟ اگر اولی کوچکتر باشه میشه اون گزینه که مین داشت اگر دومی کوچیکتر هم میشه n+m |
RE: بررسی سوالات طراحی و ساختمان IT - Aseman7 - 24 بهمن ۱۳۹۲ ۰۲:۵۲ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۳ ب.ظ)unicornux نوشته شده توسط: اون ترکیب ماکس هیپ و مین هیپ چطور میشه به نظرت؟باید ترکیب شون ماکس هیپ می شد(صورت سوال) پس اگه یه نود خالی برای ریشه ماکس هیپ جدید بذاریم و ماکس دو ریشه ی دو تا هیپ را بذارم داخل ان نود (که البته بیشتر ریشه همان ماکس قرار می گیره ) بعدش این جا مهمترین کار یعنی تبدیل مین هیپ به ماکس باید صورت بگیره که به نظرم همان گزینه ۱ o(m+N) میشه. |
RE: بررسی سوالات طراحی و ساختمان IT - izadan11 - 24 بهمن ۱۳۹۲ ۰۲:۵۴ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط: سلام به همه من زدم n مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n اگر هم منظور دونستن گره بوده میشه log n |
سئوال مرتبه زمانی - itsgu88 - 24 بهمن ۱۳۹۲ ۰۲:۵۵ ب.ظ
مرتبه زمانی عبارت زیر: T(n,k)=T(n1,[k/2])+T(n2,[k/2])+nkT(n=n1+n2) , T(n,1)=T(1,k)=1 O(n^2k):A O(nk):B O(klogn):C O(nlogk) من خودم گزینه دوم رو انتخاب کردم |
بررسی سوالات طراحی و ساختمان IT - mehdi1902 - 24 بهمن ۱۳۹۲ ۰۲:۵۵ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط: برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانااین سوالش اشتباه نبود :-؟ یه دونه O(n) برای تبدیل مین به ماکس. یه دونه min {logn , log m} هم برای اینکه به هم وصل بشن. مثلن ماکس یکی رو بیاریم ریشه و مرتبش کنیم درخت رو و فرزند دیگه شو بذاریم اون یه درخت. یعنی میشه n + min {logn , logm} |
RE: سوال ساختمان داده - virtual girl - 24 بهمن ۱۳۹۲ ۰۲:۵۸ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۳ ب.ظ)damavand_kellap نوشته شده توسط: مرتبه زمانی ادغام دو لیست مرتب به طول M و n در بهترین حالت میشه min(m,n) و در بدترین حالت میشه m+n_1 که اینجا چون طول هر دو لیست n بود پس مرتبه میشه n و ۲n_1 به نظرم همین گزینه پاسخ درست باشه تو یکی از آزمونهای آزمایشی یه موسسه این سوال اومده بود و جواب همین بود |