بعضی سوالات ساختمان 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 باشه . درسته