حل تشریحی سوالات ساختمان داده‌ها - کنکور ارشد مهندسی کامپیوتر 1403

گوییم

آرایه A به طول n را K- مرتب میکنیم. هرگاه برای هر i که $k\le i\le n-k$ داشته باشیم $A\left[i-k\right]\le A\left[i\right]\le A\left[i+k\right]$ ، یعنی آرایه A به k لیست مرتب که هر کدام تقریبا $\frac{n}{k}$ عنصر دارند افراز میشود. فرض کنید A یک آرایه k- مرتب به طول n باشد. سریع ترین الگوریتم برای تبدیل ابن آرایه به یک آرایه 1- مرتب، از چه مرتبه زمانی است؟

فرض کنید $G=\left(V,E\right)$ ، یک گراف هم بند وزن دار باشد. چند مورد از گزاره های زیر درست است؟

- اگر وزن تمام یال های گراف با هم برابر باشد، می توان درخت فراگیر کمینه آن را با الگوریتمی از مرتبه $O\left(\left|E\right|\right)$ به دست آورد.

-اگر G گراف جهت دار باشد، یافتن دور در این گراف را می توان در مرتبه $O\left(\left|V\right|+\left|E\right|\right)$ محاسبه کرد.

-چنانچه وزن یال های گراف دو به دو متمایز باشند، الگوریتم پریم و کروسکال دارای جواب یکسانی هستند.

-الگوریتم پریم را می توان به نحوی پیاده سازی کرد که همواره مرتبه آن بدتر از الگوریتم کروسکال نباشد.

رشته هایی که از دو طرف یکسان خوانده می شوند پالیندروم (Palindrome) نامیده می شوند (مانند abcba) .

برای محاسبه بزرگ ترین زیررشته پالیندروم یک رشته به طول n ، یک الگوریتم پویا کارا به ترتیب از راست به چپ دارای چه مرتبه زمان و حافظه است؟

فرض کنید s رشته‌ای به طول n باشد. می خواهیم بزرگترین زیررشته به شکل ww را در این آرایه بیابیم که طول آن را با Longest Double String) LDS (S)) نشان دهیم . در این صورت رابطه بازگشتی طول بزرگترین زیررشته (LDS) چیست؟ (توجه کنید LCS تابعی است که طول بزرگترین زیررشته مشترک دو رشته ورودی را برمیگرداند.)

تابع بازگشتی زیر را نظر بگیرید:

int f(int n)

$\{$

if$\left(n==0||n==1\right)return\left(n+1\right);$

else if$\left(n==2\right)return4;$

return $\left(f\left(n-1\right)+2\ast f\left(n-2\right)+f\left(n-3\right));\right\}$

برای $n\ge 3$، کدام گزینه بهترین کاندید برای $f\left(n\right)$ است؟