صفحه اصلی

تست لایک

کنکور ارشد

کنکور ارشد فناوری اطلاعات

دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

حل تشریحی سوالات دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری) - کنکور ارشد مهندسی فناوری اطلاعات (IT) 1404

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

درباره آزمون زبان عمومی و تخصصی (انگلیسی)(25 سوال)دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)(30 سوال)اصول و مبانی مدیریت(20 سوال)دروس تخصصی مشترک(20 سوال)

سوالات دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

30 سوال

26.

شبکه کد زیر را در نظر بگیرید.

$y = 0$

$for (i_{1} = 1; i_{1} <=n;i_{1} + +)$

$for (i_{2} = 1; i_{2} <=n;i_{1}; i_{2} + +)$

$⋮$

$for (i_{m} = 1; i_{m} <=i_{m - 1};i_{m} + +)$

تعداد جوابهای صحیح نامنفی کدام یک از معادلات زیر با تعداد دفعات اجرای دستور $y + +;$ و برابر است؟

1)

$x_{1} + x_{2} + \dots + x_{m} = n$

2)

$x_{1} + x_{2} + \dots + x_{n} = m$

3)

$(i = 1, 2, \dots, m) x_{i} \geq 1; x_{1} + x_{2} + \dots + x_{m} = n$

4)

$(i = 1, 2, \dots, n) x_{i} \geq 1; x_{1} + x_{2} + \dots + x_{n} = m$

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

27.

در یک کلاس چه تعداد دانشجو وجود داشته باشد تا اطمینان داشته باشیم که حداقل ۴ نفر آنها در یک روز هفته متولد شده اند؟

1)

22

2)

21

3)

18

4)

16

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

28.

فرض کنید (V,E)= G یک گراف ساده با n گره و m یال باشد. همچنین فرض کنید ۸ ماتریس مجاورت گراف G باشد که در آن یک درایه غیر قطری ماتریس $B = \sum_{i = 1}^{n - 1} A^{i}$ صفر است. کدام مورد در خصوص گراف G درست است؟

1)

G یک گراف دوبخشی است

2)

G یک گراف کامل است.

3)

G، همبند نیست.

4)

G، همبند است.

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

29.

فرض کنید (x)P به این معنی باشد که x خاصیت P دارد کدام یک از گزاره های زیر نشان دهنده این است که "دقیقاً یک شی با خاصیت P وجود دارد"؟

1)

$\exists x P (x)^\forall_{y}, y = x$

2)

$\exists x, P (x)^\forall_{y}, P (y) ⟹ y = x$

3)

$\exists x, \exists y, P (x)^P (y) ⟹ y = x$

4)

$\exists x, P (x)^\exists_{y}, P (y) ⟹ y = x$

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

30.

فرض کنید یک ربات برای بالا رفتن از پله های یک پارکینگ در هر گام بتواند یک یا دو پله را به سمت بالا برود و حرکت به سایر جهتها مجاز نیست تعداد شیوه های بالا رفتن از یک پلکان n پله ای توسط این ربات با کدام یک از رابطه های بازگشتی زیر داده می‌شود؟

1)

$P_{1} = 1, P_{2} = 2, P_{n} = P_{n - 1} + 2 P_{n - 2} + 1, n \geq 3$

2)

$P_{1} = 1, P_{2} = 3, P_{n} = 2 P_{n - 1} + P_{n - 2}, n \geq 3$

3)

$P_{1} = 1, P_{2} = 3, P_{n} = P_{n - 1} + 2 P_{n - 2}, n \geq 3$

4)

$P_{1} = 1, P_{2} = 2, P_{n} = P_{n - 1} + P_{n - 2}, n \geq 3$

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

31.

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

1)

$12! (2212)$

2)

$12! (5712)$

3)

$22! (2212)$

4)

$12! (5712)$

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

32.

پیچیدگی کدام یک از رابطه های بازگشتی زیر از نظر مجانبی از بقیه بیشتر است؟

1)

$T (n) = T (\frac{n}{9}) + T (\frac{8 n}{9}) + θ (n)$

2)

$T (n) = 3 T (\frac{n}{2}) + θ (n n)$

3)

$T n = 4 n T (n) + 2 n^{2}$

4)

$T (n) = 2 T (n - 1) + θ (1)$

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

33.

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

1)

O(n log n)

2)

$O (n^{2})$

3)

O(log n)

4)

$O (n^{3})$

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

34.

فرض کنید یک صف (Queue) داریم که با استفاده از یک لیست پیوندی با عناصر یکتا پیاده سازی شده است. این صف دو عملیات اصلی enqueue (افزودن به انتهای صف) و dequeue (حذف از انتهای صف) را پشتیبانی می کند. حال می‌خواهیم تابعی به این صف اضافه کنیم که میانه (Median) عناصر موجود در صف را در زمان بهینه برگرداند کدام روش زیر مناسب است؟

1)

پیمایش کل صف در هر بار فراخوانی تابع میانه برای پیدا کردن مقدار میانه

2)

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

3)

استفاده از دو صف دیگر برای نگهداری عناصر کوچک تر و بزرگتر از میانه و به روزرسانی آنها هنگام هر عملیات enqueue و dequeue

4)

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

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

35.

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

1)

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

2)

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

3)

استفاده از یک پشته برای ذخیره سازی نیمی از گره ها و سپس بازیابی گره میانی از پشته

4)

استفاده از الگوریتم جست و جوی دودویی روی لیست پیوندی

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

36.

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

1)

O(n!)

2)

O(n log n)

3)

$O (n^{2})$

4)

$O (2^{n})$

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

37.

می خواهیم یک قطعه چوب به طول L را از نقاط $x_{1}$ تا $x_{n - 1}$ که فاصله برش‌ k ام از انتهای چپ قطعه چوب است ببریم فرض کنید $x_{0} = 0$ و $x_{n} = L$ ) میدانیم که هزینه برش یک قطعه چوب به اندازه m متر از هر نقطه برابر m تومان است (مستقل از مکان نقطه برش) زیر مسئله $P_{i, j}$ که $i < j$ را قطعه چوب بین نقاط $x_{i}$ و $x_{j}$ در نظر میگیریم که باید از نقاط $x_{i + 1}$ تا $x_{j - 1}$ بریده شود. مسئله اصلی $P_{0, n}$ است. اگر r اولین نقطه برش برای $P_{i, j}$ و $C_{i, j}$ همچنین $C_{i, j}$ هزینه کمینه این زیر مسئله باشد آنگاه $C_{i, j}$ برابر کدام یک از رابطه های زیر است؟

$(C_{i, i} = C_{i, i + 1} = 0)$

1)

$min (C_{i, r} + C_{r, j} + x_{j} - x_{i})$

i<r<j

2)

$min (C_{i, r} + C_{r, j} + x_{j})$

i<r<j

3)

$min (C_{i, r} + C_{r + 1, j} + x_{j})$

i<r<j

4)

$min (C_{i, r} + C_{r + 1, j} + x_{j} - x_{i})$

i<r<j

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

38.

فرض کنید یک درخت دودویی با n گره داریم و میخواهیم از دو پشته و یک صف معمولی برای انجام پیمایش در

عمق (DFS) و پیمایش در عرض (BFS) به صورت همزمان استفاده کنیم شرایط زیر باید رعایت شود.

گره ریشه ابتدا در هر دو پشته و صف قرار می گیرد.

در هر مرحله یک گره از پشته اول برای پیمایش در عمق (DFS) و یک گره از صف برای پیمایش در عرض

(BFS) خارج می شود.

هنگام پیمایش فرزندان گره خارج شده باید طبق قواعد زیر به داده ساختارهای مربوطه اضافه شود:

الف - فرزندان چپ و راست گره به پشته دوم اضافه میشوند برای پیمایش DFS)

ب - فرزندان چپ و راست گره و به صف اضافه میشوند برای پیمایش BFS)

در نهایت الگوریتم تمام گره های درخت را پیمایش میکند.

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

1)

O(n log n)

2)

O(log n)

3)

O(n)

4)

$O (n^{2})$

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

39.

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

اگر T یک درخت پوشا برای گراف بدون جهت G باشد آنگاه اضافه کردن یال e که $e \in / E (T)$ و $e \in E (G)$ به T باعث ایجاد یک دور منحصر به فرد در T می شود.
در گراف کامل $\frac{P ( P - 1 )}{2}, k_{P}$ یال وجود دارد.
تعداد درختهای پوشای $K_{P}$ برابر $n^{n - 2}$ است.

1)

3

2)

2

3)

1

4)

صفر

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

40.

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

به نام مسیر ویژه را روی این درخت پیاده سازی کنید:

مسیر ویژه از ریشه شروع میشود و در هر مرحله به یک فرزند چپ با راست حرکت می‌کند.
شرط حرکت:

اگر مقدار گره فعلی زوج باشد به فرزند چپ بروید.

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

اگر گره ای فرزند متناظر چپ یا راست را نداشته باشد عملیات در آن نقطه متوقف می‌شود.
شما باید جمع تمام گره های این مسیر را محاسبه کنید.

با توجه به این که ساختار درخت به صورت سطح به سطح (Level Order) در یک صف معمولی (Queue) ذخیره

شده است و شما میتوانید از دو پشته (Stacks) و یک صف استفاده کنید پیچیدگی زمانی محاسبه این مسیر

ویژه چیست؟ (n تعداد کل گر‌ها و ارتفاع درخت است.)

1)

O(h)

2)

O(n)

3)

$O (2^{h})$

4)

O(n log n)

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

41.

فرض کنید یک گراف جهت دار وزن دار داده شده است که شامل n گره و m یال است. این گراف ممکن است دورهای مثبت یا منفی داشته باشد. شما میخواهید یک الگوریتم طراحی کنید که کوتاه ترین مسیر از گره مبدأ s به تمام گره های دیگر را محاسبه کند با رعایت شرایط زیر:

اگر گراف حاوی یک دور با وزن منفی باشد باید الگوریتم به صورت موثر تشخیص دهد که این دور وجود دارد و نتیجه محاسبه را متوقف کند.
شما میتوانید از یک صف معمولی (Queue) و یک پشته (Stack) برای مدیریت گره ها و یالها استفاده کنید.
اگر دور منفی وجود ندارد الگوریتم باید کوتاهترین مسیرها را به درستی محاسبه کند.

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

1)

O(n+m)

2)

$O (n^{2})$

3)

O(m log n)

4)

O(m.n)

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

42.

فرض کنید مسئله ای به نام تقسیم مجموعه با تفاوت کمینه (Minimum Difference Partitioning) داریم به شما یک مجموعه از n عدد صحیح مثبت داده شده است. هدف این است که مجموعه را به دو زیر مجموعه تقسیم کنید به طوری که تفاوت مجموع عناصر دو زیر مجموعه کمینه باشد. برای این مسئله میخواهیم از رویکرد شاخه و حد (Branch and Bound) استفاده کنیم. کدام یک از روش‌های زیر بهینه‌ترین راه برای محاسبه حد پایین (Lower Bound) در هر گره است تا شاخه های کم بازده به سرعت هرس شوند؟

1)

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

2)

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

3)

استفاده از میانگین مجموع اعداد در هر گره و مقایسه تفاوت فعلی با این میانگین به عنوان حد پایین

4)

استفاده از مجموع همه اعداد تقسیم نشده و افزودن آن به تفاوت فعلی به عنوان حد پایین

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

43.

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

1)

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

2)

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

3)

ابتدا گره ها را بر اساس تعداد همسایگانشان مرتب کنید و گره های با بیشترین تعداد همسایه را زودتر رنگ آمیزی کنید.

4)

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

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

44.

کدام یک از اصول شی‌ءگرایی در طراحی زیر نقض شده است؟

در یک برنامه مدیریت بانک کلاسی به نام Account وجود دارد که متد withdraw برای برداشت پول را ارائه می‌کند. کلاس دیگری به نام Fixed Deposit Account از کلاس Account ارث بری می‌کند و متد withdraw را بازنویسی کرده است اما این متد، برداشت پول را ممنوع می‌کند پیاده سازی متد به صورتی است که هیچ پولی برداشت نمی‌شود.

1)

(Encapsulation) کپسوله‌سازی

2)

اصل چندریختی (Polymorphism)

3)

اصل باز و بسته بودن ماژول (open - close)

4)

(Liskov Substitution) اصل جایگزینی لیسکوف

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

45.

در خصوص نیازمندی امنیتی (Security)، کدام مورد یک نیازمندی غیر کارکردی (Non - Functional) است؟

1)

سیستم باید داده های حساس را رمزنگاری کند.

2)

سیستم باید امکان مدیریت حساب کاربران را فراهم کند.

3)

سیستم باید رمز عبور کاربران را در پایگاه داده ذخیره کند.

4)

سیستم باید امکان بازیابی کلمه عبور را برای کاربران فراهم کند.

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

46.

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

1)

افزودن کش گذاری (Caching) در لایه سرویس ها

2)

پیاده سازی پروکسی (Proxy) در لایه سرویس ها

3)

به کارگیری میکروسرویسها به جای لایه های ارائه و داده

4)

استفاده از تزریق وابستگی (Dependency Injection) برای کنترل دسترسی به داده ها در تمامی لایه‌ها

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

47.

پس از تحویل نرم افزار به مشتری برای حفظ کاربرد پذیری نرم افزار در محیط کاربر نهایی که دارای تغییرات است.

کدام نوع نگهداری (Maintenance) انجام میشود؟

1)

(corrective) اصلاحی

2)

انطباقی (Adaptive)

3)

(Preventive) پیشگیرانه

4)

(Perfective) تکاملی

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

48.

مدل‌های فرایندی توسعه صوری (Formal) برای توسعه چه نرم افزارهایی تجویز می‌شود؟

1)

نیازمندیهای مبهم داشته باشند.

2)

عملیات محاسباتی زیادی داشته باشند.

3)

خواسته های کاربر کاملاً روشن و صریح باشند.

4)

نیازمندی های امنیتی قابلیت اعتماد و حفاظت آنها اولویت بالایی داشته باشند.

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

49.

موارد زیر در ارتباط با شمول (include) و گسترش (extend) در تدوین موارد کاربری ( use case) را در نظر بگیرید.

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

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

ب - مورد کاربری که با include به آن ارجاع میشود حتماً در روند اصلی مورد ارجاع واقع شده است.

ج - در extend مورد کاربری که به آن ارجاع داده میشود برای پاسخ دادن به شرایطی استثنا است که در روند اصلی

پیش بینی نشده است.

د - include و extend تنها در فاز شناخت تفکیک میشوند این دو در فاز طراحی تفاوتی با هم ندارند.

1)

"ب" و "د"

2)

"ج" و "د"

3)

"ب" و "ج"

4)

"الف" و "ج"

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

50.

مطابق تصویر شبکه‌ای متشکل از ۵ مسیریاب به همراه هزینه درج شده روی پیوندها را در نظر بگیرید. در صورت استفاده از الگوریتم Bellman Ford، در تکرار آخر هزینه کم‌هزینهRترین مسیر به سمت مسیریاب R5 و نیز گام

بعدی واقع روی کم هزینه ترین مسیر به سوی R5 برای مسیریابهای RI تا R4 کدام است؟

1)

R1:8, R3; R2:∞; R3:1, R5; R4:8,R2

2)

R1:6,R2; R2:3, R3; R3:1, R5; R4:9, R5

3)

R1:8. R3; R2:3, R3; R3:1, R5; R4:8.3

4)

R1:6. R2; R2:3, R3;R3:1, R5; R4:8.R2

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

51.

چنانچه رنج آدرس ۱.۱ ۱۹۵ از کلاس به یک شرکت تخصیص داده شده باشد و این شرکت به ۶ زیر شبکه نیاز داشته باشد تعداد بیت‌های ۱ در ماسک زیر شبکه (Subnet Mask) این شرکت چند است؟

1)

27

2)

26

3)

24

4)

21

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

52.

یک مسیریاب با N ورودی را که هر یک دارای نرخ R هستند در نظر بگیرید. فابریک سوئیچینگ داخلی مسیریاب به میزان 2N مرتبه سریع‌تر از R است. کدام مورد درست است؟

1)

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

2)

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

3)

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

4)

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

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

53.

در رابطه با عملکرد پروتکلهای لایه حمل TCP و UDP کدام مورد درست نیست؟

1)

در سرآیند (هِدِر) TCP فیلد Urgent Pointer جهت مشخص کردن اولین بابت داده حاوی اطلاعات اضطراری

استفاده می شود.

2)

تنها سرویس تأمین‌شده توسط UDP به عنوان پروتکل لایه حمل مالتی پلکسینگ کاربردهاست.

3)

checksum در UDP هم روی سرآیند (هِدِر) لایه حمل و هم روی payload اعمال می‌شود.

4)

پروتکل UDP یک پروتکل لایه حمل مناسب برای چند بخشی (Multicasting) است.

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

54.

چه تعداد سرور نام (name server) نوع ریشه (root) منطقی در سامانه DNS وجود دارد؟

1)

حدود ۱ میلیون

2)

حدود ۱۰۰

3)

13

4)

1

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

55.

فرض کنید در یک شبکه جداول مسیریابی همگرا بوده و همه گردها اعم از پایانه ها و مسیریاب‌ها، صرفاً از آدرس فیزیکی خود مطلع بوده اما از آدرس فیزیکی سایر گره ها آگاه نیستند. اگر بین یک گره پایانه مبدا و یک گره پایانه مقصد ۳ مسیریاب وجود داشته باشد برای این ارتباط به چندبار اجرای پروتکل ARP نیاز است؟

1)

1

2)

3

3)

4

4)

8

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