حل تشریحی سوالات حل مسئله - کنکور دکتری مهندسی فناوری اطلاعات (IT) 1401

اگر بخواهیم داده ساختار صف را با استفاده از پشته پیاده سازی کنیم طوری که عملیات‌های پایه‌ای صف در زمان سرشکن O(1) قابل انجام باشد کدام مورد درست است؟

فرض کنید m آرایه مرتب داریم که در مجموع آرایه ها شامل 1 عدد هستند. می‌خواهیم از هر کدام از آرایه ها یک عدد را انتخاب کنیم به طوری که اختلاف بیشینه و کمینه اعداد انتخاب شده کمترین مقدار ممکن شود. این کار در چه زمانی ممکن است؟ بهترین گزینه را انتخاب کنید.

نمایش پیش‌ترتیب (Preorder) و میان ترتیب (Inorder) یک درخت دو دویی مرتب با رأس داده شده است. کدام مورد درست است؟

فرض کنید یک هرم بیشینه شامل حداکثر n عدد داده شده است. جستجوی یک مقدار در این هرم بیشینه در کدام کلاس پیچیدگی است؟ (بهترین گزینه را انتخاب کنید.)

کدام مورد در خصوص دو گزاره (الف) و (ب) به ترتیب درست است؟

الف- اگر $f\left(n\right)\in O\left(2^{2n}\right)$آنگاه $f\left(n\right)\in \Omega \left(2^n\right)$

ب- اگر $T\left(n\right)=2T\left(\frac{n}{2}+O\left(n^2\right)\right)$ ، آنگاه $T\left(n\right)=\Theta \left(n^2\right)$

رشته‌ای به طول اوليه $m\ge 1$ در یک صفحه از نرم افزار حروف چین داریم. دو عمل زیر را می‌توانیم به ترتیب دلخواه روی این رشته انجام دهیم.

• کپی: کل رشته موجود در صفحه را در حافظه ذخیره کن.
• پیست: رشته ذخیره شده در حافظه را به انتهای رشته موجود در صفحه اضافه کن.

به طور مثال اگر رشته اولیه ab باشد، پس از انجام یک عمل کپی و یک عمل پیست رشته موجود در صفحه به صورت abab درخواهد آمد. اگر $dp\left[n\right]$ نشان دهنده طول بزرگترین رشته قابل ایجاد با n بار استفاده از عمل کپی یا پیست (به‌ترتیب دلخواه) باشد، کدام رابطه بازگشتی زیر برای محاسبة $dp\left[n\right]$ به ازای $n\ge 5$ درست است؟ (فرض کنید در ابتدا حافظه خالی است.)

محاسبه عنصر با بیشترین تکرار در یک آرایه n عضوی دلخواه در چه زمانی ممکن است؟ (بهترین گزینه را انتخاب کنید.)

کدام یک از دو گزارة (الف) و (ب) در خصوص الگوریتم هافمن به‌ترتیب درست است؟

الف - اگر فراوانی یک حرف در یک متن بیشتر از 0/4 باشد. آنگاه درخت هافمن متن لزوماً شامل کد یک بیتی است.

ب - اگر فراوانی هر حرف در یک متن کمتر از 0/3 باشد آنگاه درخت هافمن متن لزوماً شامل کد یک بیتی نیست.

فرض کنید G یک گراف کامل وزن دار با n رأس است. درخت پوشای کمینه‌ی G در چه زمانی قابل محاسبه است؟ (بهترین گزینه را انتخاب کنید.)

آرایه مرتب A شامل n عدد به صورت اکیداً صعودی داده شده است. یک نفر این آرایه را به اندازه k واحد شیفت دوری داده و نتیجه را به صورت یک آرایه B به ما داده است. هدف پیدا کردن k مقدار است. در چه زمانی می‌توان مقدار را با داشتن آرایه B محاسبه کرد؟ (بهترین گزینه را انتخاب کنید.)

به ازای اعداد صحیح مثبت n و m و a، در چه مرتبه زمانی می‌توان $a^n\mathrm{mod}m$ را محاسبه کرد؟ فرض کنید عملیات‌های ضرب و جمع به پیمانه m در زمان $O\left(1\right)$ قابل انجام هستند. (بهترین گزینه را انتخاب کنید.)

کدام گزینه در خصوص دو گزاره (الف) و (ب) به‌ترتیب درست است؟

الف - به ازای هر گراف G، ترتیبی از پال‌های گراف وجود دارد که با تنها یک دور ریلکس کردن یال‌ها به آن ترتیب در اجرای الگوریتم بلمن - فورد کوتاه ترین مسیر از رأس و به تمام رأس‌های دیگر محاسبه می‌شوند.

ب - در مرتب سازی ادغامی هر عنصر با (logn)O عنصر دیگر مقایسه می‌شود.