حل مسئله

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

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

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

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

22 سوال

جواب رابطه بازگشتی $T (n) = T (\frac{n}{3}) + T (\frac{n}{6}) + n^{l o g n}$ (با فرض اینکه برای مقادیر کوچک n داریم: $T (n) = 1$ ) کدام مورد است؟

$θ (n^{n})$

$θ (n^{l o g n})$

$θ (n^{l o g n} lo g n)$

$θ (n^{n} lo g n)$

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

فرض کنید k عددی بین ۱ تا n باشد. پیچیدگی زمانی قطعه کد زیر چیست؟ (k، عددی ثابت است.)

for(i = 0; i<=n;i++)

for(j= 0; j<=min(i,k); j++)

if(j==i ||j==0) B[i][j]=1;

else B[i][j]=B[i-1][j-1]+B[i-1][1];

$θ (nk)$

$θ (n lo g n)$

$θ (n^{2})$

$θ (n)$

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

فرض کنید می خواهید یک داده ساختار طراحی کنید که همزمان بتواند عملیات زیر را پشتیبانی کند:

افزودن عدد صحیح x به داده ساختار
حذف و بازگرداندن بزرگ ترین مقدار ذخیره شده (عملیات Remove Max)
محاسبه و بازگرداندن مجموع تمام اعداد ذخیره شده (Sum)، بدون حذف هیچ کدام

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

O(nlogn)

O(logn)

O(n)

O(1)

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

فرض کنید یک سیستم مدیریت جریان داده ها (Data Stream Management System) دارید که جریان مداومی از اعداد صحیح را در قالب یک دنباله ورودی پیوسته دریافت می‌کند. هدف شما این است که ساختاری پیاده سازی کنید که از طریق آن بتوانید عملیات زیر را به طور کارآمد انجام دهید:

Insert(x) :اضافه کردن عدد x به جریان

FindMedian :پیدا کردن میانه اعداد موجود در هر لحظه از جریان

GetTopK(k) :بازگرداندن k عدد شامل بزرگ ترین عددهای موجود در جریان

Delete(x) :حذف عدد مشخص x از جریان در صورتی که وجود داشته باشد

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

استفاده از یک درخت جستجوی دو دویی متوازن (Balanced Binary Search Tree) برای نگهداری تمامی اعداد در جریان به طوری که میانه و بزرگترین مقادیر به صورت مرتب مستقیماً نگهداری شوند.

ترکیب یک هرم بیشینه (Max-Heap) برای مدیریت بزرگترین اعداد و یک هرم کمینه Min-eap برای مدیریت کوچک ترین اعداد به همراه یک جدول هش Hash Table برای دسترسی سریع به اعداد

استفاده از یک درخت فیبوناچی (Fibonacci Heap) برای مدیریت میانه و بزرگترین مقادیر به همراه یک جدول هش برای دسترسی سریع به به اعداد در جریان

استفاده از یک لیست پیوندی دو طرفه به همراه یک آرایه مرتب برای نگهداری و دسترسی سریع به میانه و بزرگترین مقادیر

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

فرض کنید در یک پیاده سازی از تکنیک شاخه و حد فضای جستجو شامل ۱۰۰ گره باشد. اگر حد بالای فعلی برابر با ۵۰ و حد پایین برای گره های ۱ تا ۴ به صورت زیر باشد در این صورت کدام گره هرس میشود؟

گره 1: $L_{B} = 40$

گره 2: $L_{B} = 55$

گره 3: $L_{B} = 48$

گره 4: $L_{B} = 50$

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

فرض کنید می خواهید الگوریتم مرتب سازی سریع (Quick sort) را برای یک آرایه A با اندازه n پیاده سازی کنید. اما شرایط زیر بر الگوریتم اعمال شده است:

شما فقط میتوانید از دو صف معمولی (Queues) استفاده کنید و دسترسی مستقیم به آرایه مجاز نیست.

برای انتخاب محور (Pivot)، همیشه باید عنصر میانی آرایه را در نظر بگیرید، اما پیدا کردن عنصر میانی باید از طریق یکی از صف ها انجام شود.

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

تقسیم آرایه به دو بخش و مرتب سازی آنها باید بدون استفاده از بازگشت (Recursion) انجام شود.

پیچیدگی زمانی این الگوریتم در بدترین حالت چیست؟

$O (n^{2})$

$O (n)$

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

O(nlogn)

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

یک درخت AVL و یک درخت قرمز سیاه داریم. اگر در هر دو درخت تعداد یکسانی از گره‌ها باشد کدام یک از ویژگی‌های زیر بین این دو درخت همواره درست است؟

تعداد گره های برگ در AVL، بیشتر از قرمز سیاه است.

ارتفاع درخت AVL، بیشتر از درخت قرمز سیاه است.

تعداد گره‌های قرمز در درخت قرمز سیاه بیشتر از تعداد گره های برگ در AVL است.

تعداد چرخش‌های مورد نیاز برای حفظ تعادل در AVL، بیشتر از درخت قرمز سیاه است.

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

در مسئله کوله پشتی با چند محدودیت (Multi-Dimensional Knapsack) کدام مورد نشان می دهد که مسئله NP - کامل است؟

وجود الگوریتم‌های حریصانه که همیشه بهینه است.

امکان حل مسئله با برنامه‌ریزی پویا در زمان خطی

قابلیت تبدیل مسئله sat3 به این مسئله

وجود الگوریتم های تقریبی با نسبت تقریب ثابت

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

فرض کنید می خواهید یک صف اولویت (Priority Queue) را بدون استفاده مستقیم از هرم یا آرایه پیاده سازی کنید. به جای آن تنها می توانید از دو پشته (Stacks) برای این پیاده سازی استفاده کنید. عملیات درج (Insert) با پیچیدگی محاسباتی O(1) و حذف عنصر با بالاترین اولویت (Remove Max) باید به درستی انجام شود. اگر تعداد كل عناصر n باشد پیچیدگی زمانی بدترین حالت برای عملیات حذف عنصر با بالاترین اولویت چیست؟

O(1)

O(n)

O(logn)

O(nlogn)

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

10.

فرض کنید یک مجموعه از سکه با ارزشهای $(v_{1}, v_{2}, \dots, v_{n})$ دارید. می خواهید این سکه ها را به دو گروه تقسیم کنید به طوری که مجموع ارزشهای سکه ها در دو گروه تا حد ممکن برابر باشد. راه حل بهینه چیست؟

تقسیم سکه‌ها به‌صورت تصادفی و بررسی مجموع هر گروه تا زمانی که به یک تقسیم‌بندی نزدیک بهینه برسید.

مرتب‌سازی سکه‌ها بر اساس مقدار و سپس اختصاص سکه‌ها به دو گروه به‌صورت متناوب (یک سکه به گروه اول و سکه بعدی به گروه دوم)

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

استفاده از برنامه‌ریزی پویا برای پیدا کردن نزدیک‌ترین مجموع ممکن به نصف كل مجموع سکه‌ها (این روش با استفاده از یک جدول پویا بررسی می‌کند که آیا میتوان یک زیر مجموعه با مجموع مشخص ساخت یا خیر)

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

11.

فرض کنید یک گراف بدون جهت و وزن دار داده شده است که شامل n گره و mیال است. این گراف ممکن است شامل چندین مؤلفه همبند باشد. شما می خواهید یک الگوریتم طراحی کنید که ویژگی های زیر را داشته باشد:

در هر مؤلفه همبند، یک درخت پوشا کمینه (MST) پیدا کنید.

یال‌هایی که در MST هر مؤلفه نیستند، حذف شوند.

از یک صف اولویت برای انتخاب یال‌ها و از یک پشته برای مدیریت مؤلفه‌های همبند استفاده شود.

اگر هر یال از i به j در گراف، وزنی برابر با $w_{ij}$ داشته باشد پیچیدگی زمانی بدترین وضعیت اجرایی این الگوریتم چیست؟

$O (n^{2})$

$O (m^{2})$

O(mlogn)

O(nlogn)

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

12.

فرض کنید می خواهید مسئله n-Queens را حل کنید جایی که باید n وزیر را روی یک صفحه $n \times n$ شطرنج قرار دهید به‌طوری که هیچ دو وزیری یکدیگر را تهدید نکنند. برای حل این مسئله از الگوریتم عقب گرد (Backtracking) استفاده می‌کنید.

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

استفاده از سه آرایه کمکی برای ردیابی ستون‌های اشغال شده قطرهای اصلی و قطرهای فرعی که وزیری در آنها قرار دارد.

استفاده از یک آرایه دو بعدی برای ذخیره سازی کل صفحه شطرنج و بررسی هر موقعیت برای قرار دادن وزیر

استفاده از الگوریتم حریصانه برای قرار دادن وزیری که کمترین تعداد موقعیت‌های مجاز را محدود می‌کند.

تولید تمامی حالات ممکن برای قرار دادن وزیر و سپس بررسی آنهایی که معتبر هستند.

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

13.

فرض کنید یک ارتباط TCP بین یک کلاینت و یک سرور در حال انجام است. اندازه پنجره ارسال اولیه

(Initial Congestion Window) در سرور برابر با ۱ (MSS (Maximum Segment Size و مقدار ssthresh (آستانه slow start) برابر ۱۰ است. اگر الگوریتم کنترل ازدحام TCP از نوع Tahoe باشد و در دور سوم، مبدأ متوجه گم شدن یکی از بسته‌ها به واسطه انقضای زمان سنج شود، اندازه پنجره ارسال در شروع دور چهارم چند MSS خواهد بود؟

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

14.

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

در traceroute، مبدأ از ارسال بسته‌های ICMP با TTLهای متفاوت به سمت یک مقصد مشخص جهت تعیین مسیر بین آن مبدأ و مقصد استفاده می‌کند.

در traceroute پیام‌های ارسالی در جهت رفت (از مبدأ به سمت مقصد) از نوع ICMP و در جهت برگشت از نوع UDP هستند.

در ping صرفاً پیام‌های ارسالی در جهت رفت از مبدأ به سمت مقصد از نوع ICMP هستند.

بسته‌های ICMP به عنوان payload در بسته های IP حمل می‌شوند.

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

15.

با توجه به پیکربندی نشان داده شده در شبکه NAT زیر کدام مورد در خصوص فیلدهای بسته درست است؟

وقتی بسته صادره از سوی B در بین راه توسط مسیریاب NAT سمت چپ دریافت می‌گردد پورت مقصد آن 4444 تنظیم می‌شود.

وقتی بسته صادره از سوی B در بین راه توسط مسیریاب NAT سمت چپ دریافت می‌گردد پورت مبدأ آن 7777 تنظیم می‌شود.

وقتی بسته‌ای از گره B به مقصد نهایی D ارسال می‌گردد، آدرس مقصد آن 7.1.1.1 تنظیم می‌شود.

وقتی بسته‌ای از گره B به مقصد نهایی D ارسال می‌گردد آدرس مقصد آن 7.6.5.4 تنظیم می‌شود.

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

16.

مسیریاب A به همراه همسایگانش C ،B و D در یک شبکه واقع است که از پروتکل RIP استفاده می‌کنند. جدول نشان داده شده در تصویر جدول مسیریابی موجود در مسیریاب A است که در آن اطلاعات شماره گام مورد استفاده توسط پروتکل RIP درج شده است. فرض کنید شبکه برای مدتی طولانی پایدار باقی مانده باشد کدام مورد درست است؟

بهترین مسیر از مسیریاب A به یک میزبان واقع در $1.2.6 .^{*}$ از D می‌گذرد.

تعداد گام برای مسیری از مسیریاب A به یک میزبان واقع در $1.2.6 .^{*}$ برابر با 4 است.

تعداد گام برای مسیری از مسیریاب D به یک میزبان واقع در $1.2.6 .^{*}$ برابر با 2 است.

تعداد گام برای مسیری از مسیریاب A به یک میزبان واقع در $1.2.6 .^{*}$ برابر با 3 است.

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

17.

امروزه پروتکل SNMP به عنوان یک پروتکل استاندارد در مدیریت شبکه‌های TCP/IP مورد استفاده قرار می‌گیرد. کدام مورد در خصوص این پروتکل نادرست است؟

اشیاء در MIB بر اساس زبان توصیف داده‌های (SMI (Structure of Management Information

تعریف شده‌اند.

در پروتکل SNMP، پیام GetRequest از سمت مدیر (manager) به سمت عامل (agent) و به منظور دریافت مقدار یک یا چند شی تعریف شده در MIB عامل ارسال می‌شود.

پروتکل SNMP ، جهت تعامل بین مدير (manager) و عامل (agent) و به منظور دریافت و تنظیم مقدار اشیاء تعریف شده در MIB مدیر مورد استفاده قرار می‌گیرد.

برخی اشیاء تعریف شده در MIB وابسته به برند (vendor-specific) هستند، اما برخی دیگر دارای عمومیت بوده و فارغ از نوع تجهیز شبکه یا برند آن هستند.

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

18.

فرض کنید باب و آلیس به یک سیستم کلید عمومی دسترسی دارند که کلیدهای عمومی آنها را برای یکدیگر قابل دسترس می‌سازد. کدام مورد درست است؟

برای سنجش تازگی نشست ارتباطی نیاز به استفاده از nonce هم هست.

از امضای دیجیتال آلیس میتوان تازگی نشست ارتباطی با وی را نیز متوجه شد.

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

باب تنها با استفاده از کلید عمومی آلیس که در اختیار دارد، می‌تواند مطمئن شود که در حال دریافت اطلاعات قبلی ارسال شده از آلیس نیست.

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

19.

استفاده از SALT در کنار گذرواژه‌ها به هنگام محاسبه چکیده گذرواژه‌ها با استفاده از توابع چکیده‌ساز (Hash) به‌منظور جلوگیری از کدام حمله زیر صورت می‌گیرد؟

تکرار

روز تولد

مرد میانی

لغت‌نامه‌ای

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

20.

مطابق شکل زیر، فرض کنید که روی مسیریاب‌های RI و R2 یک دیواره آتش نصب شده است. کدام مورد درست است؟

در صورت مسدود سازی ترافیک telnet به مقصد net اگر ترافیک telnet به مقصد net2 باز باشد، امکان نفوذ leapfrogging به مقصد net وجود ندارد.

هرگز نمیتوان دو دیواره آتش را به گونه‌ای پیکربندی کرد که برقراری telnet از سوی دنیای بیرون به مقصد net2 ممکن باشد ولی نه به مقصد net1.

مسیریاب R1 می‌تواند جز در شرایطی که مقصد ترافیک telnet شبکه net2 باشد این ترافیک را مسدود سازد.

تنها می‌توان ترافیک telnet به مقصد هر دو شبکه را با همدیگر مسدود نمود و نه به تنهایی برای هر کدام.

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

21.

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

استراق سمع منفعلانه (passive روی ترافیک UDP آسان تر از ترافیک TCP است.

سیاست same-origin به طور کلی اجازه می دهد تا یک جاوا اسکریپت متعلق به Berkeley.edu کوکی های مربوط به stanford.edu را بخواند.

یکی از مزایای جداسازی امتیازات (privilege separation)، این است که فرصتی را برای کاهش اندازه پایگاه محاسبات قابل اعتماد (TCB) فراهم می‌کند.

درصورتی که اطمینان حاصل شود که یک مهاجم اجازه ندارد کوکی‌های نشست را که در مرورگر قربانی ذخیره شده بخواند امکان انجام حملات session fixation غیر ممکن می‌شود.

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

22.

کد HASH یک متن دلخواه، برابر ۸ بیت است. اگر یک شخص مهاجم، به صورت تصادفی بلوک های متنی هم‌اندازه با متن اصلی تولید کند انتظار می‌رود پس از چند بار تلاش بتواند متنی تولید کند که HASH آن، با HASH متن اصلی یکسان باشد؟

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