طراحی الگوریتم

حل تشریحی سوالات طراحی الگوریتم - کنکور دکتری مهندسی کامپیوتر 1398

منوی آزمون (درس ها)

درباره آزمون ساختمان داده(10 سوال)طراحی الگوریتم(10 سوال)سیستم‌های عامل پیشرفته(15 سوال)پایگاه داده پیشرفته(10 سوال)

سوالات طراحی الگوریتم

10 سوال

11.

در گراف همبند و بدون جهت G با n رأس، از یک رأس مشخص BFS و DFS را اجرا می‌کنیم، ترتیب ملاقات رئوس در هر دو اجرا یکسان شده. است در این خصوص کدام مورد درست است؟

گراف G فقط ستاره‌ای است.

گراف G فقط یک مسير است.

تعداد یالهای G از (n)O است

تعداد یال‌های G میتواند $Ω (n lo g n)$ باشد.

مشاهده پاسخ ها

12.

فرض کنید گراف G همبند، بدون جهت و وزن دار است به‌طوری که می‌تواند دور منفی هم داشته باشد. در مورد مسئله پیدا کردن کوتاهترین مسیر از یک رأس به رأس دیگر طوری که از هر رأسی حداکثر یک بار عبور کند چه می توان گفت؟

یک مسئله ان پی - تمام است.

یک مسئله ان پی - سخت است.

به علت وجود دور منفی در گراف لزوماً چنین مسیری وجود ندارد.

در زمان چند جمله‌ای برحسب اندازه ورودی می‌توان مسئله را حل کرد.

مشاهده پاسخ ها

13.

تعدادی فایل با اندازه های مشخص را میخواهیم روی نوار ذخیره کنیم. فرض کنید $f_{1}, \dots, f_{n}$ به ترتیب (از راست به چپ) روی نوار ذخیره شده باشند، هزینه خواندن فایل $f_{i}$ برابر $\sum_{k - 1}^{i} ∣ f_{i} ∣$ خواهد بود که $∣ f_{k} ∣$ برابر طول فایل $f_{k}$ می‌باشد. فرض کنید قرار است هر فایل تنها یکبار خوانده شود میخواهیم مجموع هزینه را کمینه کنیم. بدین منظور از الگوریتم حریصانه زیر استفاده می‌کنیم فایل‌ها را به ترتیب اندازه از کوچک به بزرگ روی نوار ذخیره می‌کنیم. اگر n تعداد فایل‌ها ،باشد کم‌ترین n که به ازای آن الگوریتم فوق لزوماً درست کار نمی‌کند، کدام است؟

به‌ازای هر n، الگوریتم فوق بهینه عمل می‌کند.

مشاهده پاسخ ها

14.

آرایه A شامل n عنصر داده شده است. می‌دانیم که تمام عناصر به جز $4 n$ عنصر ر در محل مرتب شده خود هستند ولی مکان عناصر نامرتب را نمی‌دانیم این آرایه را در چه زمانی می‌توان مرتب کرد؟

O(n)

$O (n 4 n)$

O(nlogn)

$O (n lo g n)$

مشاهده پاسخ ها

15.

پیمایشهای پیش ترتیب و پس ترتیب یک درخت دودویی به صورت زیر است:

preorder: abcdefg, postorder: cbfgeda

با فرض ذخیره سازی درخت در آرایه ریشه در خانه ی ۱ و فرزندان گره اندیس در اندیس‌های $2 i$ و $2 i + 1$ )، حداکثر تعداد خانه‌های بلا استفاده قبل از محل آخرین گره در آرایه کدام است؟

مشاهده پاسخ ها

16.

یک ساختمان داده را در نظر بگیرید که از دو پشته $S_{1}$ و $S_{2}$ تشکیل شده است این ساختمان داده دو عمل درج و استخراج را پشتیبانی می‌کند. به هنگام درج عنصر x در این ساختمان داده $p u sh (S_{1}, x)$ را اجرا میکنیم به هنگام اسخراج اگر $S_{2}$ خالی نبود، $P o p (S_{2})$ را اجرا می‌کنیم در غیر این صورت همه عناصر داخل $S_{2}$ را پاپ و داخل S پوش میکنیم و بعد دستور $P o p (S_{2})$ را اجرا و به عنوان خروجی دستور استخراج در نظر می‌گیریم اگر دو پشته در ابتدا خالی باشد و n عمل درج و استخراج به ترتیب دلخواه انجام شود هزینه سرشکن این عمل‌ها کدام است و ساختمان داده فوق چه ساختمان داده ای را پیاده سازی می‌کند؟

O(1) و صف

O(n) و صف

O(1) و پشته

O(n) و پشته

مشاهده پاسخ ها

17.

اگر الگوریتم جانسون برای یافتن کوتاهترین مسیر بین تمام رأس‌های گراف را روی گراف وزن دار زیر اجرا کنیم پس از اجرای مرحله تغییر وزن یال‌ها در الگوریتم وزن جدید یال بین رأس‌های ۱ و ۵ که وزن اولیه آن $- 4$ است. کدام مقدار خواهد شد؟

-4

مشاهده پاسخ ها

18.

اگر رشته ababbcbaabdadad را به وسیلهٔ الگوریتم هافمن کدگذاری کنیم طول رشتۀ حاصل چند بیت خواهد بود؟

مشاهده پاسخ ها

19.

فرض کنید n عدد صحیح k بیتی داریم. فرض کنید هزینه جمع تفریق و مقایسه دو عدد kبیتی O(k) است. اگر k=O(logn) باشد کدام گزینه در مورد الگوریتم‌های مرتب سازی درست است؟

زمان اجرای الگوریتم مرتب سازی شمارشی (n)O است.

زمان اجرای الگوریتم مرتب سازی سریع (nlogn)O است.

زمان اجرای الگوریتم مرتب سازی ادغامی $O (n lo g^{2} n)$ است.

زمان اجرای الگوریتم مرتب سازی درجی $Ω (n^{2} lo g^{2} n)$ است.

مشاهده پاسخ ها

20.

آرایه‌ای شامل n عدد داریم. اگر در اجرای الگوریتم مرتب سازی ادغامی روی این آرایه هرگاه تعداد اعداد کمتر از $n$ شد روال بازگشتی را متوقف و از الگوریتم مرتب سازی درجی استفاده کنیم، زمان اجرای الگوریتم کدام مورد خواهد بود؟ فرض کنید زمان اجرای الگوریتم مرتب سازی درجی از مرتبه $O (m^{2})$ است که m تعداد اعداد می‌باشد.)

$O (n^{2})$

$O (n n)$

$O (n lo g n)$

مشاهده پاسخ ها