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

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

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

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

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

30 سوال

26.

اگر هر زیر مجموعه n عضوی از مجموعه {۱,۲,۰۰۰,۴۹} شامل سه عدد صحیح y, x و z باشد.

به طوری که (z-x)(y-z)(x-y) بر ۴۹ بخش پذیر باشد کوچک ترین مقدار n چقدر است؟

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

27.

می خواهیم اعداد دورقمی را در ۴۵ دسته متمایز ۲ تایی توزیع کنیم، به طوری که دو عدد ۱۰ و ۹۹ در یک دسته نباشند به چند طریق این دسته بندی امکان پذیر است؟

$\frac{88 !}{2 ^{44}}$

$\frac{89 !}{2 ^{45}}$

$45. \frac{88 !}{2 ^{44}}$

$\frac{88}{89} . \frac{90 !}{2 ^{45}}$

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

28.

تعداد دسته جوابهای معادله زیر در مجموعه اعداد صحیح چقدر است؟

$x_{1} + x_{2} + \dots + x_{10} = 1 + 3 + 5 + 7 + \dots + 19$

$x_{1} \geq 1, x_{2} \geq 2, \dots, x_{10} \geq 10$

$(459)$

$(4510)$

$(549)$

$(5410)$

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

29.

چند رشته ۱۰ رقمی از ارقام ۱ , ۲ و ۳ وجود دارد که یا در پنج رقم سمت چپ هیچ رقمی برابر ۱ نباشد و یا

در پنج رقم سمت راست هیچ رقمی برابر ۲ نباشد؟

$2^{10}$

$2^{6} .243$

$2^{6} .227$

$2^{6} .243 - 1$

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

30.

جواب معادله بازگشتی روبه رو کدام است؟

$a_{n} = 8 a_{n - 2} - 16 a_{n - 4}$

$c_{1} 2^{n} + c_{2} (- 2)^{n}$

$c_{1} n 2^{n} + c_{2} n (- 2)^{n}$

$(c_{1} + c_{2} n) 2^{n} + (d_{1} + d_{2} n) (- 2)^{n}$

$(c_{1} + d_{1}) 2^{n} + (c_{2} n + d_{2} n) (- 2)^{n}$

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

31.

هر زیر مجموعه ۳ عضوی از مجموعه n عضوی X را یک رأس گراف G در نظر بگیرید $(n \geq 5)$ و دو رأس A و B را توسط یک یال به هم وصل کنید. هرگاه $∣ A \cap B ∣ = 1$ باشد، کدام مورد درباره این گراف، نادرست است؟

گراف حاصل منتظم است.

گراف حاصل برای هر ۵ n هامیلتونی است.

تعداد یاله‌ای این گراف برابر است با $q = 15 (n 5)$

فاصله هر دو رأس گراف برای $n \geq 7$ حداکثر با ۲ برابر است.

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

32.

چند مورد از عبارات زیر، برای محاسبه زیر دنباله صعودی از یک دنباله دلخواه A به طول n، درست است؟

یک راه حل پویا با مرتبه زمانی $O (n^{2})$ و میزان حافظه کمکی $O (n^{2})$ ، برای آن وجود دارد.
یک راه حل سریع در مرتبه (nlogn)O و با الگوریتمی که از الگوریتم جستجوی دودویی استفاده می کند، ممکن خواهد بود.
دنباله A را مرتب میکنیم و آن را $A^{'}$ می نامیم سپس بزرگترین دنباله مشترک بین A و $A^{'}$ را محاسبه می کنیم.
تعداد زیر دنباله های صعودی به طول از A از رابطه $T (n) = \sum_{i = 1}^{n - 1} T (k) T (n - k)$ به دست می آید.

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

33.

آرایه T به طول n با ارقام $0, 1, 2, \dots, 9$ مفروض است. می‌خواهیم تعداد زیر دنباله های نه لزوماً متمایز ممکن از این آرایه را بیابیم که هر رقم از این زیر دنباله کوچکتر از رقم بعدی باشد در این صورت سریع‌ترین الگوریتم به ترتیب از راست به چپ از چه مرتبه زمانی و حافظه است؟

O(n) و O(n)

O(n) و O(n log n)

O(n lig n) و O(1)

O(n) و O(1)

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

34.

برای محاسبه ضرب ماتریسهای nxn از طریق ضرب استراسن وقتی که ۱۶ = n و مقدار آستانه نیز ۲ باشد.

(یعنی ماتریس‌های ۲.۲ کوچک محسوب شوند)، چند فراخوانی انجام می‌شود؟

400

401

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

35.

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

O(n)

O(log n)

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

O(n log n)

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

36.

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

f(n)+o(f(n)) = O(f(n)) -

$O (f (n)) - θ (f (n) = o (f (n))$ -

$f (n) \in O (g (n)) \Rightarrow f (n) \in O (Ω (n))$ -

o(f(n))+O(f(n)) = O(f(n)) -

صفر

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

37.

کدام عبارت در مورد مرتبه زمان اجرا و ساختمان داده مورد نیاز برای پیاده سازی الگوریتم های پریم (Prim) و کروسکال (Kruskal) درست است؟ (v تعداد رئوس، e تعداد یال ها است.)

الگوریتم پریم را میتوان با ساختمان داده فیبوناچی و تحلیل سرشکنی با مرتبه $O (v lo g v + e)$ پیاده سازی کرد.

الگوریتم کروسکال را میتوان با ساختمان داده مجموعه های مجزا از مرتبه $O (v^{2})$ پیاده سازی کرد.

الگوریتم پریم را میتوان با ساختمان داده آرایه دو بعدی از مرتبه $O (e lo g v)$ پیاده سازی کرد.

الگوریتم کروسکال را میتوان با ساختمان داده پشته از مرتبه $O (e lo g v)$ پیاده سازی کرد.

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

38.

برنامه زیر را که برای جستجوی x در آرایه y و با استفاده از جستجوی دودویی نوشته شده است را در نظر بگیرید: (برنامه غلط است)

f(int y [10], int x){

int i, j,k;

i=0;j=9;

do{

k = (i+j)/2;

if(y[k]<x) i = k;

else i=k;

}while(y[k]!= x & &i < j)

if(y[k] = = x) found = True,

else found=false;

}

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

$x < 1, y = [1 3 5 7 9 11 13 15 17 19]$

$x < 10, y = [1 2 3 4 5 6 7 8 9 10]$

$x > 2, y = [2 2 2 2 2 2 2 2 2 2]$

و x زوج $2 < x < 20, y = [2 4 6 8 10 12 14 16 18 20]$

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

39.

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

هر الگوریتم همواره خاتمه‌پذیر است.

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

مجموعه الگوریتم ها شمار است در حالی که مجموعه مسائل ناشما را است.

هیچ برنامه ای در زمان چند جمله ای وجود ندارد که بتواند تشخیص دهد که یک گراف غیر جهت دار دارای

مدار اویلری است یا خیر؟

صفر

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

40.

درخت جستجوی red-black زیر که در آن رنگ گره های با برچسب ۳ و ۵ قرمز است را در نظر بگیرید. پس از اضافه شدن گره ۶، چند گره دارای رنگ قرمز خواهند بود؟ گره‌های هاشور خورده قرمز هستند.

صفر

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

41.

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

از الگوریتم محاسبه جایگشتهای اعداد $1, 2, \dots, n$ می‌توان یک الگوریتم برای حل مسئله 1 وزیر در صفحه شطرنجی nxn استخراج کرد در نتیجه مرتبه الگوریتم مذکور $Ω (n!)$ خواهد بود.

برای مرتب کردن هر ۶ عدد بر مبنای مرتب سازی مقایسه‌ای حداقل ۱۰ مقایسه لازم دارد.

در الگوریتم مرتب سازی ادغامی، در بدترین حالت تعداد مقایسه‌های لازم بین عناصر آرایه برای مرتب کردن هر ۱۰ عنصر (با فرض اینکه مسئله کوچک آرایه یک عنصری می‌باشد). برابر ۲۵ است.

صفر

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

42.

یک آرایه به طول n مفروض است، تعداد مقایسه‌های لازم برای تبدیل این آرایه به یک max heap همواره کمتر یا مساوی ....................... است. (بهترین گزینه را انتخاب کنید.)

$n^{2}$

$\frac{n}{2}$

$[n lo g n]$

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

43.

مجموعه $A = {a_{1}, a_{2}, \dots, a_{n}}$ مفروض است سریع ترین الگوریتم برای آنکه تشخیص دهد برای هر سه عضو متمایز $a_{i}$ و $a_{j}$ و $a_{k}$ از مجموعه A داریم، $a_{i} + a_{j} \geq a_{k}$ از کدام مرتبه است؟

O(n)

$O (n^{2})$

$O (n^{3})$

O(n log n)

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

44.

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

برای یک شی از کلاس A، یک یا چند شی از کلاس B وجود دارد.

با از بین رفتن اشیای کلاس A، همه اشیای کلاس C و B بین خواهد رفت.

با از بین رفتن اشیای کلاس B، همه اشیای کلاس A و ۱ تا ۳ شئ از کلاس B از بین خواهد رفت.

اشیاء کلاس C بدون وجود اشیای کلاس B می‌توانند وجود داشته باشند و با از بین رفتن اشیای کلاس B، اشیای کلاس A از بین خواهد رفت.

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

45.

چند مورد از روش‌های زیر می‌تواند برای اندازه گیری پیچیدگی (Complexity) یک نرم افزار به کار رود؟

تعداد خطوط کد (Line of codes)

(Cyclomatic complexity) پیچیدگی سیکلوماتیک

( Class coupling) اتصال کلاس

(Depth of inheritance) عمق ارث بری

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

46.

چهار رکن اصلی شی گرانی کدام است؟

Hierarchy ,Modularity ,Reusability ,Abstraction

Inheritance ,Modularity ,Encapsulation ,Abstraction

Hierarchy ,Modularity ,Maintainability ,Abstraction

Hierarchy ,Modularity ,Encapsulation ,Abstraction

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

47.

تزریق وابستگی (Dependency injection)، از کدام یک از انواع رابطه های زیر است؟

(Composition) ترکیبی

(Realization) تحقق سازی

(Two-way association) انجمنی دو طرفه

(One-way association) انجمنی یک طرفه

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

48.

نیازمندی‌های غیر عملکردی مقیاس‌پذیری (Scalability) و قابلیت نگهداری (Maintainability)، به ترتیب در کدام سبکهای معماری زیر بهتر برآورده میشود؟

(Event-driven) رخدادگرا - (Layered) لایه بندی

(Layered) لایه بندی - (Component - based) مؤلفه محور

(Component - based) مؤلفه محور - (Layered) لایه بندی

(Client-server) مشتری - خدمتگذار - (Event-driven) رخدادگرا

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

49.

کلاس زیر را در نظر بگیرید در این کلاس سه متد وجود دارد که برای محاسبه مساحت دایره مستطیل و مثلث به کار میروند. این متدها مستقل از هم هستند. این کلاس دارای چه نوع انسجامی (Cohesion) است؟

Class AreaFuncs{

double circle Area (){000)

double rectangle Area (){000

double triangle Area (){000}

}

(Procedural) رویه ای

(Communicational) ارتباطی

(Functional)عملیاتی

(Logical) منطقی

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

50.

در یک ارتباط tep فرستنده با timeout مواجه می‌شود. چنانچه tep در حالت Fast Recovery باشد، اقداماتی را انجام میدهد. این اقدامات کدام اند؟

پنجره ارسال را برابر با ۱ میکند و در حالت Fast Recovery به کار خود ادامه می دهد.

پنجره ارسال را نصف میکند به حالت Congestion Avoidance رفته و به کار خود ادامه می دهد.

مقدار آستانه را نصف مقدار پنجره ارسال میکند به حالت slow start رفته و با پنجره ارسال یک و شمارنده ACKهای تکراری صفر به کار خود ادامه می دهد.

پنجره ارسال را برابر با مقدار استانه (ssthresh) میکند و به حالت Congestion Avoidance می رود. سپس شمارنده ACKهای تکراری را صفر کرده و به کار خود ادامه میدهد

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

51.

در یک کامپیوتر سرور پروتکلهای tcp/ip چگونه حضور دارند؟

پروتکل های لایه کاربرد (application) لایه های انتقال (transport) و شبکه (network)، در مجموعه ای به نام "tcp/ip protocol stack" حضور دارند.

پروتکل های لایه کاربرد (application) و لایه های انتقال (transport) جزئی از API ها هستند. پروتکل های لایه شبکه (network) در کارت شبکه حضور دارند.

پروتکل های لایه کاربرد (application) جزئی از برنامه های کاربرد هستند و پروتکل‌های لایه‌های انتقال (transport) و شبکه (network) در سیستم عامل حضور دارند.

پروتکل‌های لایه کاربرد (application) به صورت نرم‌افزاری بعد از برنامه کاربردی قرار دارند، پروتکل‌های لایه انتقال (transport) جزئی از دستورات سوکت هستند و پروتکلهای لایه شبکه (network) در سیستم عامل حضور دارند.

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

52.

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

در که نرم افزار سرور بعد از ایجاد welcoming socket از دستور bind استفاده می‌کنیم - با این دستور به سوکت ایجاد شده شماره پورت مورد نظر را می‌دهیم و وضعیت آدرس IP کلاینت‌ها را مشخص می‌کنیم.

در کد نرم افزار سرور از دستور bind قبل از دستور accept استفاده می‌کنیم - با این دستور اجازه می‌دهیم که درخواست‌هایی قبول شوند که شماره پورت و آدرس IP مورد نظر را دارا هستند.

در کد نرم افزار کلاینت از دستور bind قبل از دستور receive استفاده می‌کنیم - با این دستور اجازه می‌دهیم که بسته‌های دریافتی از سوکت مشخصی به برنامه تحویل داده شوند.

در کد نرم افزار سرور از دستور bind بعد از دستور accept استفاده می‌کنیم - با این دستور اجازه می‌دهیم که پس از قبول درخواست سوکتی با شماره پورت مشخص به کار گرفته شود.

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

53.

یک مسیریاب (router) برای هر بسته ورودی چه فعالیت‌هایی را انجام می‌دهد؟

ابتدا بسته را در باقر پورت ورودی قرار میدهد. سپس سرآیندهای (headers) آن را بررسی می کند. آنگاه با مراجعه به جدول مقصد آن را پیدا کرده و برای مقصد ارسال می کند.

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

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

ابتدا عملیات لایه لینک (link layer) انجام شده و بسته تحویل لایه شبکه (network layer) می شود. سپس الگوریتم مسیریابی بهترین مسیر را پیدا می‌کند. آنگاه سرآیندهای بسته تنظیم شده و به سمت مقصد ارسال می شود.

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

54.

مزایای استفاده از VLAN Switch نسبت به استفاده از LAN Switch کدام اند؟

فراهم شدن امکان مجازی کردن شبکه LAN - فراهم شدن امکان مدیریت ترافیک همه بخشی (broad cast) مدیریت محل استقرار روترها.

فراهم شدن امکان مجازی کردن شبکه LAN - مرتبط ساختن شبکه های مجازی به ماشین های مجازی - فراهم شدن امکان مدیریت آدرس های MAC

فراهم شدن امکان مدیریت آدرس‌های IP - ایزوله کردن ترافیک LANهای مجازی از ترافیک اینترنت - مرتبط ساختن شبکه‌های مجازی به ماشین های مجازی

فراهم ساختن امکان مدیریت ترافیک همه بخشی (broad cast) - انجام کار چند دستگاه LAN Switch با یک دستگاه VLAN Switch - امکان پذیر شدن مدیریت محل استقرار کاربران به راحتی

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

55.

کنترل کننده Controller در شبکه های (SDN (Software Defined Networks از چه بخش‌هایی تشکیل شده اند؟

بخش کنترل مسیرها برای یافتن تغییرات احتمالی سوئیچ‌ها و لینک‌های آنها

بخش محاسبه جداول جریان (flow tables): برای استفاده توسط سوئیچ‌ها

بخش رابط برنامه‌نویسی کاربردی (API): برای نرم افزارهای کنترل شبکه

بخش کنترل مسیرها و ذخیره سازی حالت آنها برای مدیریت خرابی

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

بخش ایجاد و کنترل جداول جریان (flow tables): برای اعمال اولویت‌ها در برنامه های کاربردی

بخش ارتباط و تبادل اطلاعات با دستگاه تحت کنترل برای جمع آوری اطلاعات و اعمال کنترل‌ها

بخش مدیریت اطلاعات سراسر شبکه: برای به کارگیری در فرایند ایجاد و به روزرسانی جداول جریان (flow tables)

بخش رابط برنامه نویسی کاربردی (API): برای نرم افزارهای کنترل شبکه

بخش پایش حالات لینک‌ها و بافرها برای کنترل کردن سوییچ‌ها

بخش مدیریت ترافیک: برای جلوگیری از ازدحام

بخش محاسبه مسیرها و انتخاب مسیر بهینه: برای ساختن و به روزرسانی جداول جریان (flow tables)

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