نمونه سوالات ساختمان دادهها — تابستان ۱۳۹۷
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. کدام یک از عبارات زیر درست می باشد؟
2. زمان اجرای T(n)=n^4+5n^2 الگوریتمی محاسبه شده است. Ω(f(n)) آن را بدست آورید.
3. رابطه بازگشتی T(n)=2T(⌊n/2⌋)+d که در آن d یک ثابت زمانی می باشد را در نظر بگیرید. مرتبه اجرایی آن کدام است؟
4. فرض کنید a,b نمایش دو عدد صحیح مثبت باشند و تابع Q به شکل زیر به صورت بازگشتی تعریف شده است. تعداد Q(14,3) را پیدا کنید؟ Q(a,b)=0 اگر a<b؛ Q(a,b)=Q(a-b,b)+1 اگر a≥b
5. فرض کنید آرایه A به صورت float A[10] تعریف شود و base(a) برابر با 4000 باشد و با فرض اینکه هر عدد اعشاری 4 بایت فضا از حافظه را اشغال می کند. آدرس خانه A[7] را محاسبه نمائید؟
6. زمان اجرا در بدترین حالت برای جستجوی ترتیبی و جستجوی دودویی به ترتیب از راست به چپ کدام است؟
7. کدام تعریف، تعریف صحیحی از ماتریس اسپارس می باشد؟
8. فرض کنید آرایه A 200 عنصری مرتب شده باشد، زمان اجرای بدترین حالت (F(n)) الگوریتمی برای پیدا کردن عنصر معلوم x در آرایه A با استفاده از جستجوی دودویی چقدر است؟
9. پیچیدگی زمانی تابع push,pop در پشته کدامند؟
10. اگر در آرایه s[495] بخواهیم 4 پشته درست کنیم، آدرس ابتدای پشته L[0]=-1 و L[1]=123 باشد، آدرس ابتدای L[2] کدام است؟
11. شکل پسوندی عبارت a+b*(c/(d+e))*f کدام است؟
12. شرط پربودن صف در پیاده سازی عملگرهای صف کدام است؟
13. در کدام یک از ساختمان داده های زیر، ترتیب عناصر آن ها، همان ترتیب ورود آن ها به ساختار است؟
14. در پرانتزگذاری عبارات، کدام عملگر بیشترین تقدم را دارد؟
15. کدام یک در خصوص تفاوت های بین آرایه و لیست پیوندی صحیح می باشد؟
16. می خواهیم تغییراتی در یک لیست پیوندی اعمال کنیم که عمل افزودن ابتدا یا انتهای لیست با عملیاتی با مرتبه O(1) قابل انجام باشد. از چه نوع لیستی باید استفاده کنیم؟
17. درختی که اختلاف سطح برگ های آن حداکثر یک باشد را چه می نامند؟
18. برای هر درخت دودویی غیرتهی اگر n0 تعداد گره های پایانی و n2 تعداد گره های درجه 2 باشد، کدام رابطه صحیح است؟
19. در ساختار داده های آرایه مرتب و لیست پیوندی مرتب، عمل درج و حذف از ترتیب به راست به چپ با چه پیچیدگی زمانی انجام می گیرد؟
20. با مقادیر 1 و 2 و 3 چند درخت جستجوی دودوئی می توان ساخت؟
21. گراف کامل با n رأس، چند یال دارد؟
22. کدام مرتب سازی در آرایه های مرتب دارای بدترین عملکرد و در آرایه های نامرتب دارای بهترین عملکرد می باشد؟
23. در کدام یک از الگوریتم های مرتب سازی، در هر سه حالت بهترین، متوسط و بدترین، دارای پیچیدگی زمانی O(nlogn) می باشد؟
24. در مرتب سازی انتخابی، پیچیدگی زمانی در بهترین و بدترین حالت به ترتیب از راست به چپ کدام است؟
25. برای n های کوچک، کدام الگوریتم، بهترین روش مرتب سازی است؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. الگوریتمی دارای تابع زمانی زیر می باشد: T(n)=0 اگر n=1؛ T(n)=1 اگر n=2؛ T(n)=T(n-2)+3 اگر n>2. رابطه بازگشتی بالا را به روش تکرار با جایگذاری حل کنید؟
2. عبارت پیشوندی زیر را به عبارت پسوندی معادل تبدیل کنید. /-*+abc-de+fg
3. برای یک ساختار صف حلقوی با n=7، چه حالتی بیان کننده خالی و یا پربودن صف می باشد؟
4. گراف وزن دار زیر را در نظر بگیرید: با استفاده از الگوریتم وارشال، درخت پوشای کمینه را رسم نمایید.
5. مرتب سازی حبابی را توضیح دهید و لیست زیر را با استفاده از الگوریتم مرتب سازی حبابی، مرتب نمائید. لیست: 33،57،48،37،92،12،86،25