پاسخ سوالات الگوریتم و ساختمان مهندسی کامپیوتر کنکور ارشد ۱۴۰۳

پاسخ سوالات الگوریتم ساختمان مهندسی کامپیوتر ارشد ۱۴۰۳

سوالات ساختمان داده، طراحی الگوریتم و هوش مصنوعی رشته مهندسی کامپیوتر سال 1403

۵۷. گزینه چهارم

۵۸. گزینه‌ چهار

مورد اول صحیح زیرا گراف همبند و وزن‌ها یکسانه پس bfs بزنیم، همچنین چون گراف همبندعه تعداد یال‌ها حداکثر یه دونه از تعداد رئوس کمترن پس مرتبه O(|E|) است.
گزاره دوم صحیحه کافیه DFS بزنید و یال بک باشه.
گزاره سوم صحیح زیرا یکتایی وزن‌ها باعث یکتایی درخت نهایی خواهد بود
گزاره چهارم درسته کافیه از هیپ فیبوناچی استفاده کنیم در نتیجه مرتبه
Kruskal O(elgn)
Prim O(e+nlogn)
چون گراف همبند است میدانیم که
e>=n-1
هست پس درسته این گزاره

۵۹. گزینه دوم (طراح ممکنه نامردی کنه و گزینه ۴ام بزنه چون با گزینه ۴ام الگوریتم داریم)

به کمک LCS میشه (دقت کنید اینجا منظور از LCS طولانی‌ترین زیررشته هست) میشه که مرتبش ان دو حافظه آن n خواهد بود.

۶۰. گزینه سوم

گزینه سوم میشه چون LCS پیدا کنیم در دو ضرب کنیم طول ww رو میده. لازم به ذکره گزینه دوم و چهارم میتونن پاسخی رو برگدونن که اورلپ داشته باشه پس غلطه.

۶۱. گزینه سوم

اثبات استقرایی دارد:

۶۲. گزینه چهارم

ما دو زیر ارایه مرتب داریم کافیه شروع زیر آرایه دوم رو پیدا کنیم که با باینری سرچ میشه. فکر کنید شروعش شده t حالا t به علاوه کف رادیکال ان میشه اونی که سوال میخواد که هزینه یافتن t لاگ ان هست هزینه یافتن عنصری که گفته O(1)

۶۳. گزینه دوم

طبق کلاس، کافیه مکس این دوتا رو j بگیرید، حالا یه ارایه به طول j تعریف کنید و جمله jام رو پیدا کنید که این منجر میشن جمله iام هم پیدا بشه. پس مرتبه Max(i,j) هست. مابقی گزینه‌ها به همین دلیل رد میشن

۶۴. گزینه چهارم

شما حداقل در ۳ واحد مجبورین کار‌های سوم تا ۵ام رو اجرا کنید چون پنالتی سنگینی دارند در نتیجه کار هفتم و دوم میشه کل جریمه شما که میشه ۶۳ بهتر از اینم ممکن نیست!

۶۵. گزینه سوم

۶۶. گزینه سوم

طبق تمرین کلاس، هیچ رابطه مجانبی ندارند چون به ازای n های مختلف توان تابع g میتونه عددی بین صفر و دو باشه.

۶۷.گزینه سوم

مورد اول صحیحه میتونیم اگر ماتریس وارن پذیر بود رو وارن اون رو به کمک ضرب ماتریس‌ها محاسبه کنیم (زیاده جزئیاتش)

مورد دوم غلطه درخت بازگشت که بکشیم با فرض اینکه کوچکترین چندجمله‌ای ایکس به توان ۴ هست، تعداد فراخونی‌ها حداقل ۲۱ خواهد بود. رابطه بازگشتی آن: T(n)=4T(n/2)+1 حالا اگر شرط اولیه رو حتی  T(4)=1

بگیریم ۲۱ خواهد بود و حتی اگر طبق واژه حداکثر در سوال، شروط اولیه رو کوچکتر کنیم باز هم تعداد فراخوانی‌ها از 21 بیشتر خواهد شد پس این گزاره غلط است.

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