WWWy 29FIL E. ORG . የማየ/: -
= انشتاه پیام نور._ . کارشناسی و کارشناسی ارشد W.:*. مون و سنجمنتںjمِر ---ز ا
SW 丝
- -
-> 然ミー
द्रं, N
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱
عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها
رشته تحصیلی / کد درس : مهندسی کامپیوتر - نرم افزار، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۷۸ -، علوم کامپیوتر(چند بخشی )، مهندسی فناوری اطلاعات (چندبخشی )، مهندسی فناوری اطلاعات، مهندسی کامپیوتر گرایش رایانش امن، مهندسی کامپیوتر گرایش فناوری اطلاعات، مهندسی کامپیوتر گرایش معماری سیستم های کامپیوتری، مهندسی کامپیوتر گرایش نرم افزار، مهندسی کامپیوتر (سخت افزار)، مهندسی کامپیوتر - نرم افزار(چند بخشی ) ۱۱۱۵۱۴۲ -، علوم کامپیوتر ۱۱۱۵۱۶۶
—چند جمله ای an+bn+ c مربوط به زمان اجرای کدام الگوریتم مرتب سازی می باشد ؟ ۱. ادغامی ٢. سریع ۰۳ درجی ۴. حبابی
۲- در الگوریتم زیر در صورتی که T1=IT1 باشد مرتبه اجرایی برابر است با: For i:=1 to n do For ji=1 to m do Fork:=1 to j do Χ:=Χ+1;
() (ಣ್ಣ) () (ಸ್ಥ)
2 2 ۳- کدامیک از روابط زیر نشان دهنده رابطه صحیح زمان محاسبه الگوریتم های مختلف است؟ o(log2 n).f— در ضرب سه آرایه )6,2(A(3,4), B(4,6),c به ترتیب A*B+C چند عمل ضرب انجام می شود ؟
Y్చp . f Y SAY . Y \·入 Y Y○ .い
۵- در الگوریتم IT1ergeSOrt اگر به جای اینکه هر بار لیست به دو قسمت مساوی تقسیم شود به چهار قسمت مساوی تقسیم گردد و در مرحله ترکیب با چهار لیست در یک دیگر ادغام شوند پیچیدگی زمانی الگوریتم چه خواهد شد؟
. Y.
3 * o(n "*") o(n°) ' o(no log2 n) '
O(n 2)
Vץץץ"ו. ו. ון. ו. ו
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۱ از ۵
***
WWWy 29FIL E. ORG . የማየ/: -
."s = انشکاه پیام نور کارشناسی و کارشناسی ارشد W.:*. مرمت - ازمون و اسنجانش द्रं, N تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک
عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها رشته تحصیلی / کد درس : مهندسی کامپیوتر - نرم افزار، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۷۸ -، علوم کامپیوتر(چند بخشی )، مهندسی فناوری اطلاعات (چندبخشی )، مهندسی فناوری اطلاعات، مهندسی کامپیوتر گرایش رایانش امن، مهندسی کامپیوتر گرایش فناوری اطلاعات، مهندسی کامپیوتر گرایش معماری سیستم های کامپیوتری، مهندسی کامپیوتر گرایش نرم افزار، مهندسی کامپیوتر (سخت افزار)، مهندسی کامپیوتر - نرم افزار(چند بخشی ) ۱۱۱۵۱۴۲ -، علوم کامپیوتر ۱۱۱۵۱۶۶
۶- مرتبه زمانی رابطه بازگشتی مقابل برابر است با: T(n)=9T(n/3)+n
o(n) o(log n) " o(n"*") 。ャ o(n°) '
۷- تعداد گره ها در درخت فضای حالت برای الگوریتم عقبگرد برای مساله مدارهای هامیلتونی برابر است با: (n —1)" —1 -‘ (n — 1)" +1 -W (n-1)" +1 " (n-1)" –1 : )
n + 2 n + 2 n – 2 n – 2
۸- چند مورد از عبارات زیر صحیح می باشد؟ - الگوی جستجو برای روش عقبگرد به صورت جستجو در پهنا می باشد. - در روش انشعاب و تحدید روش جستجوی درخت به ترتیب عمق می باشد. - در هر دو روش بازگشت به عقب و انشعاب و تحدید شاخه هایی از درخت هرسی می شود.
. . * \ . Y. Y Y * . ) ۹- مرتبه زمانی مساله فروشنده دوره گرد با استفاده از برنامه نویسی پویا برابر است با: O(n°2") Y O(n^2") Y O(n°3") Y Ο(n"3").
۱۰- کدامیک از مرتبه زمانی های زیر جزو مسائل رام نشدنی نمی باشد؟
n! t „“ . Yʻ n . Y. n . ) 3 2
۱۱- مجموعه تمامی مسائل تصمیم گیری که توسط الگوریتم های زمانی چند جمله ای قابل حل هستند جزو کدام کلاس می
باشند؟ ۱. کلاسی O ۲. کلاسی np .۳ np کاملی ۴. np سخت
۱۲- تعداد درخت های جستجو با عمق 1-Il برابر است با:
3- Y 2 ۳. اوn-1 .x 2 .
Vץץץ"ו. ו. ון. ו. ו
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۲ از ۵




***
SW 丝
-
S = انشجاه پیام نوه کارشناسی و کارشناسی ارشد •:*. مرمت - ازمون و اسنجانش |
-
NS
-
Z
WWWy 29FIL E. ORG . የማየ/: - تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک
عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها
رشته تحصیلی / کد درس : مهندسی کامپیوتر - نرم افزار، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۷۸ -، علوم کامپیوتر(چند بخشی )، مهندسی فناوری اطلاعات (چندبخشی )، مهندسی فناوری اطلاعات، مهندسی کامپیوتر گرایش رایانش امن، مهندسی کامپیوتر گرایش فناوری
اطلاعات، مهندسی کامپیوتر گرایش معماری سیستم های کامپیوتری، مهندسی کامپیوتر گرایش نرم افزار، مهندسی کامپیوتر (سخت افزار)، مهندسی کامپیوتر - نرم افزار(چند بخشی ) ۱۱۱۵۱۴۲ -، علوم کامپیوتر ۱۱۱۵۱۶۶
۱۳- در کدام روش ابتدا نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و هر گاه به آنها نیاز پیدا شد به جای محاسبه دوباره کافی است آن را بازیابی کنیم؟ ۱. حریصانه آن برنامه نویسی پویا ۳. تکنیک عقبگرد " روش انشعاب و تحديد ۱۴- الگوریتم تولید کننده کد هافمن ، ................ ۱. همیشه درخت بهینه تولید می کند. ۲. گاهی اوقات درخت بهینه تولید می کند.
I .۳. هیچ وقت درخت بهینه تولید نمی کند. ۲. اغلب اوقات درخت بهینه تولید می کند
۱۵- کدام الگوریتم برای یافتن کلیه کوتاهترین مسیرها از مبدا واحد به مقصدهای متفاوت بکار می رود؟
۱. فلوید ۲. دیکسترا ۳۔ پریم ۴. کروسکال ۱۶- کدام الگوریتم یالی را( از بین رئوس همسایه ) در هر مرحله انتخاب می کند که منجر به حداقل افزایش در مجموع هزینه ها
می گردد ؟
۱. کروسکال آ ، پریم ۰۲ سولين ۲. دیکسترا
۱۷- کدامیک از موارد ذیل جزو سه شرط لازم برای روش تقسیم و حل نمی باشد؟
۱. تعیین دقیق مرحله ای که باید دست از فراخوانی های بازگشتی برداریم.
۲. بررسی اینکه مسئله مرتبه ای از لگاریتم می باشد. ۳. بررسی امکان تقسیم ورودی به بخش کوچک تر و سپس ترکیب آنها
آ، اندازه تقریبا یکسان بخش های حاصل از تجزیه
۱۸- کدام روشی پیشنهاد می کند که می توان الگوریتمی نوشت که ، مرحله به مرحله اجرا شود و در هر زمان یک ورودی را بررسی نماید و بررسی انجام شده در مورد شدنی بودن یا نبودن جواب ها می باشد؟
۱. روش تقسیم و حل ۲. حریصانه ۳. برنامه نویسی پویا ۴. عقبگرد
Vץץץ"ו. ו. ון. ו. ו
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۳ از ۵***
WWWy 29FIL E. ORG . የማየ/: -
S!! 2
یک S = انشجاه پیام نوه کارشناسی و کارشناسی ارشد W.:*. مرمت - ازمون و اسنجانش ŽNS تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک
عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها
رشته تحصیلی / کد درس : مهندسی کامپیوتر - نرم افزار، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۷۸ -، علوم کامپیوتر(چند بخشی )، مهندسی فناوری اطلاعات (چندبخشی )، مهندسی فناوری اطلاعات، مهندسی کامپیوتر گرایش رایانش امن، مهندسی کامپیوتر گرایش فناوری اطلاعات، مهندسی کامپیوتر گرایش معماری سیستم های کامپیوتری، مهندسی کامپیوتر گرایش نرم افزار، مهندسی کامپیوتر (سخت افزار)، مهندسی کامپیوتر - نرم افزار(چند بخشی ) ۱۱۱۵۱۴۲ -، علوم کامپیوتر ۱۱۱۵۱۶۶
۱۹- مرتبه زمانی تابع زیر برابر است با:
T(n)=3T(*)+n 2 O(n log n) " Ο(η"ε") O(n ) - Y Ο(η"ε") .)
۲۰- بکارگیری روش تقسیم و حلی برای کدامیک از مسئله های زیر مناسب نمی باشد؟
١. سرى فيبوناچی ۲. مرتب سازی ادغام
* Y.
‘ مرتب سازی سریع ضرب ماتریسی ها به روشی استراسن
۲۱- مرتبه زمانی پیدا کردن ماکزیمم و مینیمم در لیستی با 11 عنصر برابر است با: О(Vп ) f O(n ) Y Ο(n") O(nlog n ) :) ۲۲- بدترین حالت الگوریتم CuiCKSOrt چه زمانی رخ می دهد ؟ ۱. داده ها از قبل به صورت صعودی مرتب شده باشند. ۲. داده ها از قبل به صورت نزولی مرتب شده باشند. ۳. داده ها از قبل مرتب شده باشند. ۲. به وضعیت ورودی داده ها بستگی ندارد.
۲۳- برای ادغام دو لیست مرتب با عنصر، حداکثر چه میزان مقایسه نیاز می باشد؟
n \ . Y η . γ' η - 1. Υ . n 2 ۲۴- زمان یک جستجوی موفق در بدترین حالت در الگوریتم جستجوی دودوئی برابر است با:
69(log n ) : * 6(nlog n ) -V O(nlog n ) { O(log n) : )
۲۵- مرتبه زمانی رابطه بازگشتی زیر برابر است با: T(n) = 2T(n-1)+3T(n − 2) T(0) = 0,T(1) = 1
Ο(2"n) ." O(4") - Y Ο(2") . O(3") . )
Vץץץ"ו. ו. ון. ו. ו
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۴ از ۵

***