نمونه سوالات ساختمان داده‌ها — تابستان ۱۳۹۷

کد درس 1115112

25 سوال تستی + 5 تشریحی🔒 پاسخ‌ها با اشتراک

پاسخ‌ها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیام‌نور استخراج و تطبیق داده شده‌اند.

فصل:
پاسخ داده‌شده: 0 از 25

پیشرفت شما به‌صورت خودکار روی همین مرورگر ذخیره می‌شود و با رفرش کردن صفحه از بین نمی‌رود.

مبانی الگوریتم و پیچیدگی زمانی

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 با استفاده از جستجوی دودویی چقدر است؟

پشته (Stack)

9. پیچیدگی زمانی تابع push,pop در پشته کدامند؟

پشته (Stack)

10. اگر در آرایه s[495] بخواهیم 4 پشته درست کنیم، آدرس ابتدای پشته L[0]=-1 و L[1]=123 باشد، آدرس ابتدای L[2] کدام است؟

عبارات پیشوندی و پسوندی

11. شکل پسوندی عبارت a+b*(c/(d+e))*f کدام است؟

صف (Queue)

12. شرط پربودن صف در پیاده سازی عملگرهای صف کدام است؟

صف (Queue)

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

صف (Queue)

3. برای یک ساختار صف حلقوی با n=7، چه حالتی بیان کننده خالی و یا پربودن صف می باشد؟

گراف‌ها

4. گراف وزن دار زیر را در نظر بگیرید: با استفاده از الگوریتم وارشال، درخت پوشای کمینه را رسم نمایید.

مرتب‌سازی

5. مرتب سازی حبابی را توضیح دهید و لیست زیر را با استفاده از الگوریتم مرتب سازی حبابی، مرتب نمائید. لیست: 33،57،48،37،92،12،86،25

سایر نیمسال‌های ساختمان داده‌ها