صفحه اصلی

تست لایک

کنکور دکتری

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

حل مسئله

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

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

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

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

22 سوال

1.

الگوریتم فلوید - وارشال از یک الگوریتم ...................... برای حل مسئله کوتاه‌ترین مسیرهای تمام جفت رئوس در یک گراف جهت دار $G = (V, E)$ در زمان ..................... استفاده می‌کند.

1)

حریصانه، $Θ (v^{3})$

2)

حریصانه، $Θ (v^{2} lo g E)$

3)

برنامه‌نویسی پویا، $Θ (v^{3})$

4)

برنامه‌نویسی پویا، $Θ (v^{2} lo g E)$

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

2.

با فرض اینکه $P \neq = N P$ باشد کدام مورد درست است؟

1)

NP-hard=NP

2)

NP-complete=P

3)

NP-complete=NP

4)

$N P - co m pl e t e \cap P = ϕ$

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

3.

کمترین تعداد مقایسه مورد نیاز برای تعیین اینکه یک عدد صحیح بیش از صحیح به طول $\frac{n}{2}$ ظاهر می‌شود، از کدام مرتبه است؟

1)

$Θ (1)$

2)

$Θ (lo g n)$

3)

$Θ (n)$

4)

$Θ (n lo g n)$

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

4.

آرایه نامرتب $A_{1}, \dots, A_{n}$ را در نظر بگیرید (n عددی فرد است.) هر کدام از این آرایه ها دارای n عنصر متمایز است. هیچ عنصر مشترکی میان هیچ دو آرایه ای وجود ندارد. کمترین پیچیدگی زمانی الگوریتمی برای محاسبه میانه این آرایه‌ها از چه مرتبه‌ای است؟

1)

$Θ (n)$

2)

$Θ (n lo g n)$

3)

$Θ (n^{2})$

4)

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

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

5.

فرض کنید W(n) و A(n) ، به ترتیب نشان دهنده بدترین حالت و میانگین زمان اجرای الگوریتم اجراشده بر روی ورودی با اندازه باشند. کدام مورد همواره درست است؟

1)

$A (n) = O (W (n))$

2)

$A (n) = Θ (W (n))$

3)

$A (n) = Ω (W (n))$

4)

$A (n) = o (W (n))$

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

6.

یک آرایه مرتب‌شده از اعداد داریم می‌خواهیم دو عدد در این آرایه پیدا کنیم که جمع آن دو عدد مساوی یک عدد داده شده x باشد. کمترین پیچیدگی زمانی حل این مسئله کدام است؟

1)

$Θ (n)$

2)

$Θ (n^{2})$

3)

$Θ (lo g n)$

4)

$Θ (n lo g n)$

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

7.

فرض کنید آرایه ای از اعداد صحیح $A = [a_{1}; a_{2}; \dots a_{n}]$ داده شود. فرض کنید یک اندیس ناشناخته وجود

دارد به طوری که زیر آرایه $A = [a_{1}; a_{2}; \dots a_{k}]$ به ترتیب اکیداً افزایشی مرتب شده است و زیر آرایه $A = [a_{k}; a_{k + 1}; \dots a_{n}]$ به ترتیب اکیداً نزولی مرتب شده است (یعنی اگر $1 \leq i \leq j \leq k$ کا، آنگاه $a_{i} < a_{j}$ ، و اگر $k \leq i < j \leq n$ ، آنگاه $a_{i} > a_{j}$ هدف شما تعیین است. یک الگوریتم بهینه برای حل این مسئله چه زمان اجرایی دارد؟

1)

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

2)

$Θ (n lo g n)$

3)

$Θ (n)$

4)

$Θ (lo g n)$

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

8.

کدام یک از موارد زیر درست است؟

1)

آرایه $A = [10; 3; 5; 1; 4; 2]$ یک max heap است.

2)

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

3)

برای تمام توابع مثبت f(n) ، g(n) و h(n) ، اگر f(n)=O(g(n)) و $f (n) = Ω (h (n))$ باشد، آنگاه $g (n) + h (n) = Ω (f (n))$ است.

4)

اگر هر رقم جداگانه در RADIX SORT را با استفاده INSERTION SORT به‌جای COUNTING SORT مرتب کنیم، آنگاه RADIX SORT به‌درستی کار نمی‌کند (یعنی خروجی صحیح را تولید نمی‌کند).

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

9.

کدام مورد زیر مطمئنا عبارت $f (n) = Ω (g (n))$ را پشتیبانی می‌کند؟

1)

برای تمام $n \geq 1$ $f (n) \leq 4 \times g (n)$

2)

$f (n) \geq 4 \times g (n)$ برای تمام $n \geq 136$

3)

برای تمام $n \geq 100$ $f (n) \leq 4 \times g (n)$

4)

$lim_{n \to \infty} \frac{f ( n )}{g ( n )} = 0$

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

10.

کدام یک از گزاره های زیر درست است؟

الف - اگر مسئله $P_{1}$ بتواند به مسئله $P_{2}$ در زمان خطی کاهش (reduce) یابد، آنگاه اگر $P_{2}$ یک مسئله NP-hard باشد، می توان نتیجه گرفت $P_{1}$ نیز NP-hard است.

ب - یک Clique در یک گراف بدون جهت لزوماً یک vertex cover در گراف مکمل نیست.

1)

فقط گزاره «الف» درست است.

2)

فقط گزاره «ب» درست است.

3)

هر دو گزاره «الف» و «ب» درست است.

4)

هر دو گزاره «الف» و «ب» نادرست است.

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

11.

کدام یک از گزاره های زیر درست است؟

الف - اینکه زمان حل یک مسئله P حد پایین $Ω (n^{2})$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند فقط برخی از نمونه‌های P وقتی به عنوان ورودی به A داده شوند باعث می‌شود A زمان $Ω (n^{2})$ صرف کند.

ب - اینکه زمان حل یک مسئله P حد پایین $Ω (n^{2})$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند هر نمونه از P که به عنوان ورودی به A داده شود باعث می‌شود A زمان $Ω (n^{2})$ صرف کند.

1)

فقط گزاره «الف» درست است.

2)

فقط گزاره «ب» درست است.

3)

هر دو گزاره «الف» و «ب» درست هستند.

4)

هر دو گزاره «الف» و «ب» نادرست هستند.

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

12.

کدام یک از گزاره‌های زیر درست است؟

الف - اگر یک الگوریتم زمان چند جمله‌ای برای یک مسئله که NP-hard است ارائه شود آنگاه می‌توان نتیجه گرفت P = NP است.

ب - اگر یک مسئله NP-complete است، آنگاه می‌توان نتیجه گرفت که آن مسئله هیچ راه حلی ندارد.

1)

فقط گزاره «الف» درست است.

2)

فقط گزاره «ب» درست است.

3)

هر دو گزاره «الف» و «ب» درست هستند.

4)

هر دو گزاره «الف» و «ب» نادرست هستند.

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

13.

یک مشتری پس از دانلود و مشاهده یک فایل html پایه از یک سایت نیازمند دانلود سه فایل ۱۲۸ کیلوبایتی دیگر است. به ازای هر کدام از نحوه اتصالات زیر مدت زمان دریافت سه فایل چقدر است؟

(RTT=10ms پهنای باند 10= مگابیت بر ثانیه و از اندازه بسته‌های TCP SYN/ACK و درخواست HTTP صرف‌نظر کنید.)

الف - درخواست‌های پشت سرهم، اتصالات nonpersistent TCP

ب - درخواست‌های موازی، اتصالات nonpersistent TCP

ج - درخواست‌های پشت سرهم، اتصالات persistent TCP

د - درخواستهای موازی اتصالات persistent TOP

1)

الف: ۰/۳۶ ب: ۰/۳۲ - ج: ۰/۳۴ - د: ۰/۳۲

2)

الف: ۰/۳۶ - ب: ۰/۲۲ - ج: ۰/۳۵ - د: ۰/۳۳

3)

الف: ۰/۳۷ - ب: ۰/۳۲ - ج: ۰/۳۴ - د: ۰/۳۲

4)

الف: ۰/۳۷ - ب: ۰/۲۲ - ج: ۰/۳۵ - د: ۰/۳۳

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

14.

یک اتصال TCP برقرار شده است که در آن MSS=1kB و RTT=100ms است. وقتی اندازه پنجره فرستنده برابر ۳۲ کیلوبایت است یک timeout تشخیص داده می‌شود. چند میلی‌ثانیه طول می‌کشد که اندازه پنجره فرستنده برابر ۲۲ کیلوبایت شود؟

1)

600

2)

900

3)

1000

4)

1100

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

15.

در شبکه خطی زیر که شامل روترهای A تا E است از روش بردار فاصله برای مسیریابی استفاده می‌شود. تأخیر لینک بین هر دو روتر را یک واحد در نظر بگیرید. تأخیر همه روترها تا روتر A را قبل از خرابی روتر A در سطر اول و پس از خرابی روتر A را پس از اولین دور مبادله اطلاعات روترها به هم در سطر دوم مشاهده می نمایید. کدام یک از گزینه های زیر در مورد تأخیر روترها به روتر A پس از دور ششم مبادله اطلاعات درست است؟

1)

$B = 5, C = 6, D = 5, E = 6$

2)

$B = 7, C = 8, D = 7, E = 8$

3)

$B = 7, C = 6, D = 7, E = 6$

4)

$B = 9, C = 8, D = 9, E = 8$

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

16.

کدام یک از پروتکل‌های زیر انصافی که تقریباً شبیه انصاف نسبی است را رعایت می‌کنند؟

1)

UDP

2)

TCP

3)

CSMA/CD

4)

MACA

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

17.

فرض کنید در محاسبات CRC مقسوم‌علیه 1011 و پیغام 100110111100 باشد. در کدگذاری به روش CRC پیغام ارسالی از سمت فرستنده کدام است؟

1)

100110111100101

2)

100110111100011

3)

100110111100100

4)

100110111100010

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

18.

این شکل مراحل 5 و 6 از پروتکل Kerberos را نشان می‌دهد. در این شکل E(K,.) نماد رمزنگاری با کلید K، C نماد کلاینت، V نماد سرور، ID نماد شناسه، AD نماد آدرس (مثلا IP address و یا MAC) و TS نماد Timestamp یا همان مهر زمانی است. اگر کلاینت در $A u th e n t i c a t or_{c}$ به‌جای $T S_{5}$ از یک عدد تصادفی مانند N استفاده کند و سرور نیز در مرحله 6، رمز شده $N + 1$ را به کلاینت بفرستد، چه اتفاقی می‌افتد؟ (منظور جایگذاری N و N+1 دقیقا در همان محل‌هایی است که $T S_{5}$ و $T S_{5} + 1$ استفاده شده‌اند. تغییر دیگری در پروتکل داده نشده و به سرورها قابلیت و یا حافظه‌ای اضافه نگردیده است).

1)

ایجاد مشکل امنیتی کرده و Replay Attack را امکان‌پذیر می‌کند.

2)

ایجاد مشکل امنیتی کرده و احراز هویت سرور V توسط کلاینت C را خدشه‌دار می‌کند.

3)

از نظر امنیتی هیچ مشکلی ایجاد نمی‌کند، چون همچنان جلوی Replay Attack گرفته می‌شود.

4)

از نظر امنیتی هیچ مشکلی ایجاد نمی‌کند، چون همچنان احراز هویت سرور V توسط کلاینت C انجام می‌شود.

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

19.

فرض کنید شما یک سیستم رمزنگاری RSA ساخته‌اید که در آن پیمانه (n) عدد 119 است. تعداد کلید‌های عمومی‌ای که می‌توانید برای این سیستم انتخاب کنید به کدام مورد نزدیک‌تر است؟

(راهنمایی: اگر m یک عدد نوعی صحیح مثبت باشد که به صورت $P_{1}^{e 1} P_{2}^{e 2} \dots P_{k}^{e k}$ تجزیه و فاکتورگیری شود (که در آن $P_{i}$ ها اعداد اول متمایز هستند)، آنگاه مقدار تابع فی اولر (یا همان Euler Totient Function) برای عدد m برابر خواهد بود با $(ϕ (m) = (P_{1}^{e 1} - P_{1}^{e_{1} - 1}) (P_{2}^{e 2} - P_{2}^{e_{2} - 1}) \dots (P_{k}^{e k} - P_{k}^{e_{k} - 1})$

1)

119

2)

96

3)

40

4)

32

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

20.

این شکل را در IPSec در نظر بگیرید. این سناریو برای اتصال یک کامپیوتر A از راه دور و از طریق اینترنت به یک سرور B در شبکه سازمان از طریق مسیریاب امنیتی لبه آن (Security Gateway) طراحی شده است. در این مورد خاص، کامپیوتر متصل شونده (A) از IP مسیریاب لبه سازمان در اینترنت اطلاع دارد و خودش نیز دارای valid IP در اینترنت است. ضمنا A برای ارتباط با سرور مورد نظر که پشت NAT سازمان است نیز یک IP دیگر در subnet سازمان دارد. رنج IPهای کامپیوترهای سازمان invalid بوده و از بیرون قابل مسیریابی نیستند.

بیرونی‌ترین IPSee Security Association (SA) که بین کامپیوتر A و Gateway ایجاد می‌شود در چه مودی باید باشد (فرض کنید پروتکل ESP است)؟ و در صورتی که A به کامپیوترهای شبکه Local Intranet سازمان اعتماد نداشته باشد، برای آنکه بسته وی با کمترین سربار به نحوی محافظت شود که تمام محتوا رمز شده و نیز محتوا و header بسته در برابر دستکاری محافظت شوند، بهترین مود و ترتیب استفاده از پروتکل‌های IPSee در SA های درونی کدام است؟

1)

بیرونی‌ترین SA باید در مود Tunnel باشد و دو SA درونی باید به شکل Iterated Tunneling باشند که اول پروتکل AH و سپس ESP به بسته اعمال شود.

2)

بیرونی‌ترین SA باید در مود Transport باشد و دو SA درونی باید به شکل Transport Adjacency باشند که اول پروتکل ESP و سپس AH به بسته اعمال شود.

3)

بیرونی‌ترین SA باید در مود Transport باشد و دو SA درونی باید به شکل Iterated Tunneling باشند که اول پروتکل AH و سپس ESP به بسته اعمال شود.

4)

بیرونی‌ترین SA باید در مود Tunnel باشد و دو SA درونی باید به شکل Transport Adjacency باشند که اول پروتکل ESP و سپس AH به بسته اعمال شود.

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

21.

کدام مورد در خصوص امضای دیجیتال و زیرساخت کلید عمومی (PKI) درست است؟

1)

در صورت استفاده از الگوریتم RSA برای امضاء ، دو پیام یکسان دارای امضاهای متفاوت هستند ولیکن در صورت استفاده از استاندارد امضای دیجیتال DSS چنین خاصیتی برقرار نیست.

2)

در لیست گواهی‌های باطل شده (CRL) نیازی به درج همه گواهی‌های باطل شده نیست و فقط کافی است گواهی‌های باطل شده ولی منقضی نشده (از لحاظ زمان اعتبار) را نگهداری کنیم.

3)

با استفاده از امضای دیجیتال می‌توان سرویس عدم انکار فرستنده یک پیام و عدم نقض صحت (یکپارچگی) پیام را در شبکه فراهم کرد، ولی نمی‌توان سرویس احراز اصالت پیام (message authentication) را فراهم کرد.

4)

در صورت ابطال گواهی مرکز صدور گواهی ریشه (root CA)، گواهی‌های مراکز مبانی (intermediate CA) صادر شده توسط مرکز ریشه (با کلید متناظر با گواهی باطل شده) غیر معتبر می‌شود، ولیکن گواهی‌های صادر شده توسط مراکز صدور گواهی میانی برای کاربران نهایی همچنان معتبر است.

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

22.

اگر قواعد مندرج در جدول زیر در فایروال حالت‌مند موجود در شبکه‌ای با هم‌بندی زیر تنظیم شده باشد، کدام مورد درست است؟

1)

سیستم A می‌تواند به سرویس‌های https، http و smtp در اینترنت فقط اتصال جدید برقرار کند.

2)

امکان ping کردن سرورهای وب و پست الکترونیکی (با آدرس‌های 5.10.102.1 و 5.10.102.2 )از اینترنت وجود ندارد.

3)

اگر در شبکه داخلی سرویس DNS نداشته باشیم، کاربران شبکه داخلی در دسترسی به وب سایت‌ها در اینترنت از طریق URL آنها با مشکل مواجه خواهند شد.

4)

سرور وب شبکه داخلی (با آدرس 5.10.102.1) هم می‌تواند به کاربران اینترنتی سرویس بدهد و هم خود می‌تواند به وب سرویس یک سازمان بیرونی که بر روی اینترنت سرویس‌دهی می‌کند متصل شود و سرویس دریافت نماید.

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