سوالات طراحی الگوریتمها با جواب

دانلود رایگان نمونه سوالات طراحی الگوریتمها با جواب (استخدامی)

برای دانلود رایگان اینجا کلیک کنید

قسمتی از سوالات طراحی الگوریتمها :

 – در کدام روش مرتب سازی از یک عنصر به عنوان عنصر محور استفاده می شود؟ 

الف. مرتب سازی سریع (quick sort)  ☑

ب. مرتب سازی ادغامی 

ج. مرتب سازی دودویی 

د. مرتب سازی تقسیم و حل

 – در الگوریتم حریصانه کدام جزء تشکیل دهنده آن برای بررسی اینکه مشخص کند در نهایت جواب حاصل شده است یا  خیر به کار می رود؟ 

الف. SELECT 

ب. FEASIBLE 

ج. SOLUTION ☑

د. یک تابع هدف

 – کدام الگوریتم برای یافتن کوتاه ترین مسیرها از مبدا واحد به مقصدهای متفاوت به کار می رود؟ 

الف. الگوریتم دیکسترا  ☑

ب. الگوریتم کروسکال 

ج. الگوریتم پریم 

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

 – یک گراف همبند با چند راس حداقل میتواند 111 یال داشته باشد که اگر فقط n-1 یال داشته باشد یک درخت نامیده  می شود.

الف. n ☑

ب. n-1

ج. n+1

د. n-2

 – دو مرحله روش حدس و استقرا کدام است؟ 

الف. حدس جواب به کار گیری استقرا ریاضی برای یافتن متغیرها 

ب. حدس جواب به کار گیری استقرا ریاضی برای یافتن ثابت ها  ☑

ج. یافتن قطعی جواب به کار گیری استقرا ریاضی برای یافتن متغیرها 

د. یافتن قطعی جواب، به کار گیری استقرا ریاضی برای یافتن ثابت ها

 – یکی از روشهای خوب برای حل یا حدس روابط بازگشتی از طریق تکرار استفاده از کدام روش است؟ 

الف. روش مرتب سازی ادغامی 

ب. روش مرتب سازی سریع 

ج. روش درخت بازگشت  ☑

د. روش بهینه سازی 

 – زمان جستجوی موفق در بدترین حالت در درخت تصمیم دودونی کدام است؟ 

الف. O(n) 

ب. O(n2)

ج. O(nlogn)

د. O(logn) ☑

 – کدام مورد در خصوص روش الگوریتم مرتب سازی سریع صحیح می باشد؟ 

الف. لزوما لیست به دو بخش با طول مساوی تقسیم نمی شود.  ☑

ب. معمولاً عنصر آخر را به عنوان عنصر محوری انتخاب می کنیم 

ج. حتما باید زیر لیست های مرتب شده ادغام شود. 

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

 – اگر دو لیست یا فایل مرتب را به ترتیب با n و m کد ادغام کنیم به طوری که فایل حاصل از این ادغام نیز مرتب باشد.  در چه زمان اجرا می شود؟ 

الف. O(m) 

ب. O(n)

ج. O(m+n) ☑

د. O(m.n)

 – در کدام الگوریتم زیر برای یافتن کلیه کوتاهترین مسیرها از مبدا واحد به مقصدهای متفاوت به کار می رود و همچنین  طول یک مسیر را برابر مجموع وزن یالهای آن مسیر در نظر می گیرد؟ 

الف. الگوریتم بریم 

ب. الگوریتم ديكسترا  ☑

ج. الگوریتم کروسکال 

د. الگوريتم فلويد

 – کدام گزینه در خصوص درختهای جستجوی دودوئی صحیح می باشد؟ 

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

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

ج. کلیدهای موجود در زیر درخت راست یک راس بزرگتر با مساوی کلید آن راس هستند.  ☑

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

 – کدام ویژگی در خصوص مسائلی که به روش برنامه نویسی پویا حل میشود به درستی بیان شده است؟ 

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

ب. مسائل را از بالاترین سطح به طرف پایین ترین سطح حل می کنند. 

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

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

 – کدام ویژگی مسائل روش بازگشت به عقب صحیح بیان شده است؟ 

الف. اکثر مسائلی که به روش بازگشت به عقب حل میشوند دانا مسائل سختی هستند. ☑

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

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

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

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

الف. خطی 

ب. نمایی  ☑

ج. بدتر از نمایی 

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

 – الگوی جستجو برای روش بازگشت به عقب (عقبگرد به کدام صورت انجام می پذیرد؟ 

الف. جستجو در عمق  ☑

ب. جستجو در پهنا 

ج. جستجوی ردیمی 

د. جستجوی پایین به بالا 

 – فضای مساله ای که با استفاده از روش انشعاب و تحدید حل میشود باید چگونه نمایش داده شود؟ 

الف. باید با یک درخت قابل نمایش باشد. 

ب. باید با یک پشته قابل نمایش باشد. 

ج. باید با یک گراف قابل نمایش باشد.  ☑

د. باید با یک لیست پیوندی قابل نمایش باشد. 

 – زمان الگوریتمهای انشعاب و تحدید در بدترین حالت چگونه است؟ 

الف. خطی 

ب. نمایی 

ج. نمایی یا بهتر 

د. نمایی یا بدتر  ☑

 – مسائلی که الگوریتم کارا چند جمله ای برای آنها ابداع نشده است ولی غیر ممکن بودن آن نیز هنوز به اثبات نرسیده  کدام مسائل هستند؟ 

الف. p

ب. Np

ج. Np-hard 

د. Np کامل ☑

 – مجموعه تمام مسائل تصمیم گیری که توسط الگوریتمهای زمانی چند جمله ای قابل حل هستند کدام کلاس را نشان می  دهند؟ 

الف. کلاس p  ☑

ب. کلاس Np 

ج. کلاس Np-hard 

د. کلاس Np کامل

 – الگوریتم رام نشدنی کدام است؟ 

الف. الگوریتم هایی با مرتبه زمانی n2،n و n3 را مسائل رام نشدنی می نامند. 

ب. مسائی که نوشتن یک الگوریتم کارآمد برای آنها غیر ممکن است مسائل راه شنیدنی می گویند.  ☑

ج. الگوریتم هایی که مرتبه زمانی آنها چند جمله ای باشد را مسائل رام نشدنی می نامند. 

د. الگوریتم هایی که مرتبه زمانی آنها logn nlogn باشد را مسائل رام نشدنی می گویند. 

کلاس ND کامل

 – از اجزای تشکیل دهنده یا الگوریتم حریصانه کدام است؟

الف. مجوعه از انتخاب های ممکن برای مولفه های جواب به نامK

ب. مجموعه ای مولفه های انتخاب شده تا به حال به نام Q

ج. روانی به نام Objcct

د. یک تابع هدف ☑

 – یک گراف همبند با n راس حداقل می تواند چند ریال داشته باشد؟

الف. n – 1 ☑

ب. n-2

ج. n2-l

د. 2n-2

 – از کدام الگوریتم برای یافتن کلیه کوتاه ترین مسیرها از مبدا واحد به مقصدهایی متفاوت به کار میرود؟

الف. الگوریتم پریم

ب. الگوریتم کروسکال

ج. الگوریتم دیکسترا ☑

د. الگوریتم حریصانه

 – هدف ما از انتخاب شیء ها و قرار دادن آن‌ها در کوله پشتی چیست؟

الف. ارزش شی‌های قرار داده شده در کوله پشتی (با توجه به محدودیت ظرفیت کوله پشتی) ماکزیمم (حداکثر) باشد. ☑

ب. ارزش شی‌های قرار داده شده در کوله پشتی (با توجه به محدودیت ظرفیت کوله پشتی) می نیمم (حداقل) باشد

ج. وزن شی های قرار شده در کوله پشتی (با توجه به محدودیت ظرفیت کوله پشتی) ماکزیمم (حداکثر) باشد.

د. . وزن شی های قرار شده در کوله پشتی (با توجه به محدودیت ظرفیت کوله پشتی) می نیمم (حداقل) باشد

 – از مراحل مساله کوتاهترین مسیر کدام است؟

الف. مرحله صفر: داده های اولیه: تمامی اعمال در این مرحله انجام می شود

ب. مرحله 1 مسیر بهینه: مجموع وزن کلیه مسیرهایی که از راس اول می گذرند و کوتاهترین مقدار را داشته باشد ☑

ج. مرحله 2 مسیر بهینه: مجموع وزن کلیه مسیرهایی که از راس سوم و چهارم می گذرند و کوتاهترین مقدار را داشته باشد

د. مرحله m-1 مسیر بهینه : مجموع وزن کلیه مسیرهایی که از راس سوم شروع و به راس مقصد ختم می شود و کوتاهترین مقدار را داشته باشد