صفحه اصلی

تست لایک

کنکور دکتری

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

حل مسئله

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

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

درباره آزمون حل مسئله(15 سوال)مهندسی اطلاعات(15 سوال)خدمات فناوری اطلاعات(15 سوال)

سوالات حل مسئله

15 سوال

1.

آرایه‌ای شامل n عدد متمایز داده شده است. می‌خواهیم از روی این اعداد یک درخت دو دویی بسازیم با این خاصیت که به ازای هر رأس درخت ساخته شده این خصوصیت را نیز داشته باشد که پیمایش میان ترتیب آن دقيقاً معادل ترتیب عناصر در آرایه شود. کدام گزاره درست است؟

1)

چنین درختی لزوماً به ازای هر آرایه وجود دارد، اما یکتا نیست.

2)

چنین درختی لزوماً به ازای هر آرایه شامل n عدد متمایز وجود ندارد.

3)

بهترین زمان برای ساخت چنین درختی از روی یک آرایه O(n) است.

4)

بهترین زمان برای ساخت چنین درختی از روی یک آرایه O(nlogn) است.

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

2.

فرض کنید می خواهیم n تومان را با استفاده از سکه های a و b و c تومانی خرد کنیم به ازای چه تعداد از (a,b,c) زیر، الگوریتم حريصانه n تومان را با کمترین تعداد سکه خرد می‌کند؟

(5,2,1)
(5,4,1)
(6,3,1)

1)

0

2)

1

3)

2

4)

3

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

3.

فرض کنید یک آرایه مرتب از اعداد طبیعی به طول n داریم که در آن هر عدد به غیر از یکی دقیقاً دو بار ظاهر شده است. عضو غیر تکراری را در چه زمانی میتوان پیدا کرد؟

1)

$O (n lo g n)$

2)

$O (lo g n)$

3)

$O (n)$

4)

$O (1)$

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

4.

اگر در الگوریتم هافمن نویسه‌ای بیش از $\frac{2}{5}$ کل متن تکرار شود، در آن صورت کد این نویسه چند بیت می‌تواند باشد؟

1)

هر عددی بین 1 تا 3

2)

فقط 1

3)

فقط 2

4)

1 یا 2

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

5.

چند تا از گزاره های زیر صحیح است؟

اگر پس از اتمام الگوریتم بلمن فورد، به‌روز رسانی فاصله‌ها را ادامه دهیم و فاصله مربوط به یک رأس $ν$ باز هم به روز شود $ν$ در یک دور منفی قرار دارد.
اگر در جست وجوی عمق اول گراف جهت دار G تنها یک یال بازگشتی (e (back edge وجود داشته باشد آنگاه یال $e^{'}$ به جز یال e وجود دارد که $G - e^{'}$ بدون دور است.
اگر در الگوریتم دایكسترا که روی یک DAG و از مبدأ اجرا شده، فقط برخی از یالهای خروجی و وزن منفی داشته باشند الگوریتم ممکن است به درستی فاصله ها را محاسبه نکند.

1)

0

2)

1

3)

2

4)

3

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

6.

در یک مجموعه از اعداد صحیح به اندازه n، دنبال یک ۴ تایی هایی مثل (a,b,c,d) هستیم که $d = a^{2} + b^{2} + c^{2}$ این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید.)

1)

$O (n^{3})$

2)

$O (n^{4})$

3)

$O (n lo g n)$

4)

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

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

7.

خانواده $H = {h_{1}, \dots, h_{k}}$ از توابع درهم ساز را در نظر بگیرید که $h_{i} : {a, b, c, d} \to {0, 1}$ برای آن که این

خانواده یک خانواده در هم ساز سراسری باشد k حداقل چقدر باید باشد؟ خانواده توابع H سراسری است

اگر به ازای هر دو مقدار u و v داشته باشیم. $P r_{h \in H} [h (u) = h (v) \leq \frac{1}{m}]$ که m اندازه جدول درهم سازی است.

1)

16

2)

4

3)

2

4)

1

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

8.

آرایه A[1..n] از اعداد صحیح داده شده است. زیر دنباله متوالی A[i..j] یک بازه مثبت نامیده میشود، اگر جمع اعضای A[i] تا A[j] مثبت (بزرگ‌تر از 0 ) باشد. می‌خواهیم کمترین تعداد بازه‌های مثبت که تمام اعداد مثبت آرایه را پوشش می‌دهد پیدا کنیم. اگر ورودی آرایه زیر باشد جواب کدام است؟

$A [1..15] =< 3, - 5, 4, 1, - 9, - 8, 2, 3, 4, - 10, 1, - 2, - 3, 6, - 1 >$

1)

5

2)

4

3)

3

4)

2

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

9.

یک گراف ۵ رأسی همبند و بدون جهت داریم که رأسهای آن با شماره های ۱ تا ۵ شماره گذاری شده اند. فرض کنید از رأس ۱ الگوریتم BFS را اجرا میکنیم و تمام حالتهایی که BFS می تواند رئوس را ملاقات کند عبارتند از (۱,۲,۳,۴,۵)، (۱,۳,۲,۵,۴)، (۱,۳,۲,۴,۵) و (۱,۲,۳,۵,۴). حال اگر از رأس ۵ الگوریتم DFS را اجرا کنیم کدام گزینه نمی‌تواند ترتیب ملاقات‌ها رئوس گراف باشد؟

1)

5,4,3,1,2

2)

5,4,3,2,1

3)

5,3,4,1,2

4)

5,4,1,2,3

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

10.

برنامه زیر چه کاری می‌کند و زمان اجرای آن کدام است؟

SS(A[0.. n-1])

If n = 2 and A[0] > A[1] then

Swap (A[0], A[1])

else if n >2

m= [2n٫3]

SS(A[0.. m-1])

SS(A[n-m. .n-1])

SS(A[0.. m-1])

1)

آرایه A را مرتب می‌کند و زمان اجرای آن $θ (n^{l o g_{3/2} 3})$ است.

2)

آرایه A را مرتب می‌کند و زمان اجرای آن $θ (n^{l o g_{2/3} 3})$ است.

3)

آرایه ۸ را لزوماً مرتب نمی‌کند اما زمان اجرای آن $θ (n^{l o g_{3/2} 3})$ است.

4)

آرایه A را لزوماً مرتب نمی‌کند اما زمان اجرای آن $θ (n^{l o g_{2/3} 3})$ است.

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

11.

دنباله (۳,۱,۴,۱,۵,۹,۲,۶,۵,۳,۸,۹,۷,۹,۳,۲,۳,۸,۴,۶,۲,۷,۹) را در نظر بگیرید. چند عضو متوالی این دنباله را می‌توان به‌صورت یک عدد تصور کرد. مثلاً سه سه عنصر متوالی ۵ و ۳ و ۸ را عدد ۵۳۸ تصور کرد. دو عدد به این شکل را مجزا گوییم اگر هیچ یک از عناصر دنباله در ساخت هر دوی آنها نقش نداشته باشند. حداکثر چند عدد مجزا به این شکل میتوان ساخت که به ترتیب از چپ به راست صعودی باشند؟

1)

11

2)

10

3)

9

4)

8

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

12.

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

محاسبه طول بزرگترین زیر دنباله آینه ای یک دنباله
تشخیص این که آیا یک دنباله زیر دنباله یک دنباله دیگر است.
تشخیص این که آیا یک دنباله آینه ای است.

1)

0

2)

1

3)

2

4)

3

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

13.

یک مسیریاب را در نظر بگیرید که بسته ای به اندازه ۴۰۰ بایت را دریافت می‌کند. این مسیریاب باید این بسته را به شبکه‌ای با 200MTU بایت ارسال کند. تعداد fragmentها و مقادیر بیت More Fragment (MF) و offset در هدر سرآیند تکه ها کدام است؟ (فرض کنید پروتکل TCP و پروتکل IP بخش آپشن ندارند.)

1)

سه تکه بسته اول: offset=0,MF=1، بسته دوم: 0=offset=22 ،MF، بسته سوم: 0=offset=44 ، MF

2)

سه تکه بسته اول: offset=0,MF=1، بسته دوم: 1=offset 22 ,MF، بسته سوم: 0=offset=44 ، MF

3)

سه تکه بسته اول: offset=0,MF=1، بسته دوم: 1=offset 23 ,MF، بسته سوم: offset=46 ، MF=0

4)

چهارتکه بسته اول: offset=0,MF=1، بسته دوم: 1=offset 23 ,MF، بسته سوم: 1=offset=46 ،MF

بسته چهارم: offset=66 ، MF=0

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

14.

کدام گزاره در ارتباط با پروتکل ARP درست است؟

1)

یک بسته ARP در یک فریم لایه پیوند کپسوله بندی می‌شوند.

2)

پروتکل ARP یک آدرس MAC را به آدرس IP متناظر نگاشت می‌کند.

3)

پروتکل ARP و DNS هر دو به نگاشت آدرس IP و MAC به یکدیگر می‌پردازند.

4)

یک درخواست ARP به صورت تک پخشی و پاسخ آن به‌صورت همه پخشی در شبکه محلی ارسال می‌شود.

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

15.

روش ping sweep برای کدام کاربرد استفاده می‌شود؟

1)

مسیریابی

2)

ipconfig

3)

اسکن شبکه

4)

اندازه‌گیری تأخیر

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