صفحه اصلی

تست لایک

کنکور دکتری

مهندسی کامپیوتر - نرم افزار

ساختمان داده ها و طراحی الگوریتم ها

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

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

درباره آزمون ساختمان داده ها و طراحی الگوریتم ها(20 سوال)مدار منطقی و معماری کامپیوتر(20 سوال)سیستم های عامل پیشرفته(15 سوال)پایگاه داده های پیشرفته(10 سوال)شناسایی الگو - یادگیری ماشین(25 سوال)شبکه های پیشرفته(10 سوال)معماری کامپیوتر پیشرفته - VLSI پیشرفته(25 سوال)

سوالات ساختمان داده ها و طراحی الگوریتم ها

20 سوال

1.

اگر زمان اجرای مرتب سازی حبابی $c_{1} n^{2}$ و زمان اجرای مرتب سازی ادعامی $c_{1} n lo g_{2} n$ با فرض ( $1 \leq c_{1} \leq c_{2}$ ) باشد، در کدام یک از حالات مرتب سازی ادغامی به ازای هر $n > 2$ سریع تر از مرتب سازی حبابی است؟

1)

$c_{1} > \frac{c _{2}}{n}$

2)

$c_{2} < 16 c_{1}$

3)

$\frac{n}{2} > (\frac{c _{2}}{c _{1}})$

4)

مرتب سازی ادغامی همیشه سریع تر از مرتب سازی حبابی است.

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

2.

دو آرایه مرتب A و B از اعداد صحیح با طولهای n و m (با فرض $n \leq m$ ) و عدد صحیح $k \geq lo g_{2} n$ داده شده است. با چه تعداد مقایسه می‌توان k آمین کوچکترین عضو را در اجتماع این دو آرایه پیدا کرد؟ (بهترین گزینه را انتخاب کنید.)

1)

$O (lo g (nm))$

2)

$O (k lo g (n + m))$

3)

$O (n lo g m)$

4)

$O (lo g n . lo g m)$

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

3.

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

1)

با سه پشته میتوان این کار را انجام داد و سه پشته برای این کار لازم است.

2)

با دو پشته میتوان این کار را انجام داد و دو پشته برای این کار لازم است.

3)

با یک پشته میتوان این کار را انجام داد.

4)

این کار امکان پذیر نیست.

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

4.

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

1)

$O (m + lo g n)$

2)

$O (n lo g m)$

3)

$O (n + m)$

4)

$O (nm)$

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

5.

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

1)

درخت متناظر با این لیست رئوس منحصر به فرد است.

2)

دقیقاً دو درخت با این ترتیب ملاقات رئوس وجود دارد.

3)

دقیقا $\frac{n}{2}$ درخت با این ترتیب ملاقات رئوس وجود دارد.

4)

هیچ یک از موارد درست نیست.

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

6.

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

1)

$O (\frac{n}{l o g ( n )})$

2)

O(log(n))

3)

O(n)

4)

$O (n)$

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

7.

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

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

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

1)

درست - درست

2)

درست - نادرست

3)

نادرست - درست

4)

نادرست - نادرست

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

8.

هرم دودویی را ............... از روی یک درخت قرمز - سیاه در زمان (n)O ساخت و درخت قرمز - سیاه را ................... از روی هرم دودویی در زمان (n)O ساخت.

1)

نمی‌توان - می‌توان

2)

می‌توان - نمی‌توان

3)

نمی‌توان - نمی‌توان

4)

می‌توان - می‌توان

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

9.

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

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

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

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

1)

$d p [n] = 2 d p [n - 2]$

2)

$d p [n] = 2 d p [n - 1]$

3)

$d p [n] = max (2 d p [n - 2], 3 d p [n - 3])$

4)

$d p [n] = max (d p [n - 1], 2 d p [n - 2])$

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

10.

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

1)

O(nlog(n))

2)

$O (n n)$

3)

$O (n^{2})$

4)

O(n)

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

11.

در مسئله "پوشش رأسی"، گراف ساده G=(V,E) و عدد صحیح K داده شده است و میخواهیم ببینیم "آیا زیر مجموعه $C \subseteq V$ با اندازه حداکثر k وجود دارد طوری که حداقل یک سر هر یال گراف G در C باشد؟" چند مورد از گزاره‌های زیر در خصوص این مسئله درست هستند؟

مسئله پوشش رأسی ان پی - کامل است.
مسئله پوشش راسی آن پی - سخت است.
مسئله پوشش رأسی قابل کاهش به مسئله ۳SAT است.
مسئلة SAT قابل کاهش به مسئله پوشش راسی است.

1)

1

2)

2

3)

3

4)

4

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

12.

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

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

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

1)

نادرست - درست

2)

درست - درست

3)

درست - نادرست

4)

نادرست - نادرست

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

13.

ماتریس A به اندازه n.m داده شده است. سطرهای آن از چپ به راست و ستونهای آن از بالا به پایین مرتب هستند. هزینه یافتن عدد داده شده x در این ماتریس چقدر است؟ (بهترین گزینه را انتخاب کنید.)

1)

O((n+m)(logn+m))

2)

O(mlogn+nlog)

3)

O(n+m)

4)

O(nm)

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

14.

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

1)

$Θ (n)$

2)

$Θ (n lo g n)$

3)

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

4)

$Θ (n^{2})$

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

15.

مسئله برنامه ریزی خطی با محدودیتهای زیر را در نظر بگیرید:

$x_{1} - x_{4} \leq - 1$

$x_{2} - x_{1} \leq - 4$

$x_{2} - x_{1} \leq - 9$

$x_{3} - x_{1} \leq 5$

$x_{4} - x_{3} \leq - 3$

کدام مورد یک جواب برای مسئله برنامه ریزی فوق است؟

1)

مسئله جواب ندارد.

2)

مسئله بی نهایت جواب دارد.

3)

حتما $x_{1} = - 9$

4)

حتما $x_{3} = - 4$

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

16.

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

1)

O(n)

2)

$O (n)$

3)

O(logn)

4)

$O (l o g^{2} n)$

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

17.

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

1)

O(logn)

2)

$O (n)$

3)

$O (n)$

4)

O(m)

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

18.

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

1)

O(nlog(n))

2)

$O (n^{2})$

3)

O(logn)

4)

O(n)

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

19.

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

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

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

1)

درست - درست

2)

درست - نادرست

3)

نادرست - درست

4)

نادرست - نادرست

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

20.

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

الف - اگر ظرفیت تمام یالهای شبکه عددی صحیح باشد آنگاه شار عبوری از هر یال شبکه در شار بیشینه حتماً عددی صحیح است.

ب - اگر ظرفیت تمام یالهای شبکه عددی گنگ باشد آنگاه مقدار شار بیشینه شبکه حتماً عددی گنگ است.

1)

درست - درست

2)

درست - نادرست

3)

نادرست - درست

4)

نادرست - نادرست

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