حل تشریحی سوالات طراحی الگوریتم - کنکور ارشد مهندسی کامپیوتر 1400
منوی آزمون (درس ها)
سوالات طراحی الگوریتم
6 سوالمتنی که هر حرف آن یکی از چهار نویسه {a,b,c,d} است را با الگوریتم هافمن کدگذاری کرده ایم. طول کد هافمن این متن 2021 بیت شده است. طول کد چهار نویسه فوق در کدگذاری هافمن کدام است؟
1,2,3,3
1,2,2,3
1,2,3,4
2,2,2,2
یک درخت 10 راسی داریم که یکی از راس های ان به عنوان هدف درنظر گرفته شده است، اما ما از ان اطلاع نداریم. در هر پسمان میتوانیم یک راس را انتخاب کنیم و متوجه شویم ایا این راس هدف است یا نه و اگر نیست کدام یال ان به هدف نزدیکتر است. در بدترین حالت با حداقل چند پرسمان میتوانیم راس هدف را پیدا کنیم؟
9
5
4
3
گراف بدون جهت و وزن‌دار G و راس مشخص s از این گراف را در نظر بگیرید. از الگوریتم دایکسترا برای محسابه کوتاه ترین مسیر ساده s به بقیه رئوس استفاده کرده‌ایم. به ازای چندحالت زیر این الگوریتم با وجود وزن های منفی همیشه درست کار میکند؟
- هر یالی بتواند وزن منفی داشته باشد.
- تنها یال های منتهی به s بتوانند وزن منفی داشته باشند.
- تنها یال های برشی گراف G بتوانند وزن منفی داشته باشند.
- به ازای هر دو از گراف G حداکثر یک یال بتواند وزن منفی داشته باشد.
0
1
2
3
سالن مربعی شکل در اختیار داریم که مختصات گوشه چپ - پایین آن (0و0) و مختصات گوشه راست- بالا ان (10 و 10) است. چهار نفر در این سالن در مکان های (9،4) , (5,8) , (4,3) , (1,7) قرار گرفته اند. میخواهیم از گوشه چپ-پایین به گوشه راست-بالا برویم. به هر شکل میتوانیم حرکت کنیم، تنها نباید از سالن خارج شویم. حداکثر فاصله اجتماعی که میتوانیم رعایت کنیم چند است؟
2/5
/2
ارایه‌ای شامل n عدد را در نظر بگیرید. در هر پسمان، میتوانیم دو اندیس i و j که اندیس شروع و پایان یک بازه از ارایه هستند را بدهیم و به ما مجموع اعداد بازه داده میشود. هدف پیدا کردن بازه‌ای است که مجموع اعداد بازه بیشینه شود. چه تعداد پرسمان برای اینکار نیاز است؟
دو دنباله که هر کدام یک جایگشت از اعداد 1 تا n هستند، داده شده است. بزرگترین زیر دنباله مشترک این دو دنباله را در چه زمانی میتوان بدست اورد؟