بعضی سوالات ساختمان IT سال ۹۶
۱- فرض کنید n رشته متمایز از ۰و۱ با طول حداکثر k که برای ذخیره سازی از درخت ترای استفاده شده ، ارتفاع درخت کدام است ؟
سوال اسونی هستش و جواب میشه k ( منبع کتاب دکتر قدسی )
۲-یک درخت دودویی به ارتفاع O(logn) که دسترسی هر گره به فرزند و پدر از O(1) باشه یافتن کوتاهترین مسیر بین دو گره دلخواه u,v از چه مرتبه ای هستش ؟
سوال اسونی هستش و میشه از مرتبه تتای logn
۳- رابطه بازگشتی ( تمرین MIT )
[tex]T(x,y)=T(\frac{x}{2},\frac{y}{2})+\: \langle x+y\rangle\: ->\: T(n,n)\: =\: ?\: \theta(n)[/tex]
کافیه جاگذاری بکنید البته من صورت سوال و کامل ننوشتم
۴ -
n تا کاراکتر داریم ، طول بزرگترین کاراکتر در درخت هافمن سوال شد که برابر n-1 است
۵ - الگوریتم دایکسترا روی گراف با وزن منفی یعنی حداقل یک وزن منفی دارد ولی دور منفی ندارد ، سوال شد که خروجی الگوریتم چطوری میشه ؟
سوال تکراری هستش و بعضی وقت ها خروجی الگوریتم درسته
۶ - سوال دادن کدام گزاره صحیح است : الف ) بدون اینکه پیچیدگی الگوریتم مرتب سازی مبتنی بر مقایسه و عوض کنیم میتونیم اونو از حالت ناپایدار به پایدار تبدیل کنیم ؟ بله گزاره صحیح است ( منبع تمرین CLRS )
ب ) ارتفاع درخت تصمیم برای الگوریتم مبتنی بر مقایسه [tex]\Omega(nlogn)[/tex] که n تعداد اعداد هست که این گزاره هم درسته
بقیه سوالات ایشالله بعدا" حل میکنیم
سوال در مورد هرم کمینه دادن و گفتن چنتا از گزاره های زیر درموردش درسته :
الف ) بزرگترین عدد همیشه در برگ هستش . درسته
ب ) سومین کوچکترین عنصر ( با فرض حداقل ۳ عنصر ) حتما" در فرزند ریشه ذخیره میشه . غلطه ممکنه برگ باشه ( سوال تکراری ۹۴ فکر کنم باشه )
ج ) عملیات حذف عنصر کمینه از مرتبه O(1) هستش > غلطه اگه میگفت یافتن کمینه درست بود ، بعد از حذف هرم باید دوباره ساخته بشه
د ) k امین کوچکترین عنصر نمیتونه در سطحی بیشتر از k+1 باشه . درسته