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

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

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

درباره آزمون زبان عمومی (انگلیسی)(10 سوال)زبان تخصصی (انگلیسی)(15 سوال)ریاضی عمومی (1 و 2)(7 سوال)آمار و احتمال مهندسی(7 سوال)ریاضیات گسسته(6 سوال)نظریه زبان‌ها و ماشین‌ها(5 سوال)سیگنال‌ها و سیستم‌ها(5 سوال)ساختمان داده‌ها(6 سوال)طراحی الگوریتم(6 سوال)هوش مصنوعی(8 سوال)مدار منطقی(7 سوال)معماری کامپیوتر(7 سوال)الکترونیک دیجیتال(6 سوال)سیستم‌های عامل(7 سوال)شبکه‌های کامپیوتری(6 سوال)پایگاه داده‌ها(7 سوال)

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

6 سوال

62.

فرض کنید آرایه ای به طول n داریم که به شکل حلقوی مرتب صعودی است. برای مثال ارایه زیر:

30	20	10	90	80	70	60	50	40

می خواهیم الگوریتمی بنویسیم که $[n]$ امین کوچکترین عنصر این ارایه را بیابیم ، مرتبه زمانی این الگوریتم چیست؟

$O (n)$

$O (lo g^{2} n)$

$O (lo g n)$

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

63.

بهترین پیچیدگی زمانی مورد نیاز برای محاسبه مجموع دو جمله i ام و j ام از دنباله فیبوناچی چیست؟

$O (i * j)$

$O (max {i, j})$

$O (2^{i} + 2^{j})$

$O (max {2^{i}, 2^{j}})$

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

64.

هر یک از کارهای زیر در یک واحد زمان قابل اجرا است. هر یک از این کارها دارای یک زمان خاتمه است و در صورتی که بعد از زمان خاتمه انجام شود مشمول یک جریمه خواهد شد. اگر این کارها را برای اجرا به کمترین جریمه زمان بندی کنیم مقدار جریمه چقدر است؟

$W_{7}$	$W_{6}$	$W_{5}$	$W_{4}$	$W_{3}$	$W_{2}$	$W_{1}$	work
1	5	2	3	3	2	10	deadline
18	33	70	65	55	45	10	penalty

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

65.

فرض کنید که در الگوریتم مرتب سازی سریع برای انتخاب محور از میان n عنصر آرایه $2 [lo g n] + 1$ عنصر اولیه را انتخاب کنیم و الگوریتم مرتب سازی درجی انها را مرتب کنیم. عنصر میانه این تعداد عنصر مرتب را به عنوان محور انتخاب میکنیم . بقیه الگوریتم همانند الگوریتم مرتب سازی عمل میکند. بهترین گزینه برای بدترین زمان اجرای این الگوریتم کدام است؟

$T (n) = T (n - [lo g n]) + O (n)$

$T (n) = T (n - [lo g n]) + O (lo g^{2} n)$

$T (n) = T (n - [lo g n]) + T ([lo g n]) + O (n)$

$T (n) = T (n - [lo g n]) + T ([lo g n]) + O (lo g^{2} n)$

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

66.

فرض کنید f(n)=n و $g (n) = n^{(1 + s i n n)}$ ، که n یک عدد مثبت صحیح است. کدام یک از گزاره های زیر درست است؟

$I.$ f(n)= O(g)n))

$Π.$ f(n)= $Ω$ (g(n))

فقط $I$

فقط $Π$

نه $I$ و نه $Π$

هم $I$ و هم $Π$

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

67.

چند مورد از گزاره های زیر دست است؟

هر الگوریتم که ضرب دو ماتریس را محاسبه کند، می تواند در همان مرتبه وارون یک ماتریس را محاسبه کند و بالعکس.
برای محاسبه ضرب دو چندجمله ای از درجه 16 تعداد فراخوانی های لازم با استفاده از الگوریتم تقسیم و حل ، وقتی که چندجمله ای کوچک تلقی می شود برابر است با 13.

در شبکه جریان داده شده شکل زیر اگر فقط مجاز به افرینش ظرفیت یک یال باشیم ، حداکثر می توان 7 واحد به ظرفیت یک یال آن اضافه کرد تا شبکه حداکثر جریان عبوری را داشته باشیم .

صفر

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