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

کد درس 1115112

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

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

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

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

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

1. زمان اجرای T(n)=4n+5nlogn+2 موجود است. مرتبه یا پیچیدگی زمانی آن را محاسبه نمایید؟

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

2. کدام یک از عبارات زیر صحیح می باشد؟

پشته (Stack)

3. کدام ساختار داده زیر، به صورت آخرین ورودی اولین خروجی می باشد؟

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

4. رابطه بازگشتی زیر را در نظر بگیرید که در آن d یک ثابت زمانی می باشد. T(n) را محاسبه نمایید. T(n)=2T(⌊n/2⌋)+d

ماتریس اسپارس

5. اگر هر عنصر از آرایه ای با نام a، به اندازه size بایت فضا اشغال کند، محل عنصر i ام، کدام یک از گزینه های زیر می باشد؟

ماتریس اسپارس

6. یک ماتریس پایین مثلثی A را می خواهیم با یک آرایه یک بعدی B نمایش دهیم، اگر هر عضو A[i][j] معادل عنصر B[L] باشد، بین L,j,i چه رابطه ای باید برقرار باشد؟

پشته (Stack)

7. عملگر push در پشته چه عملیاتی انجام می دهد؟

پشته (Stack)

8. مرتبه زمانی تابع push و pop در ساختار پشته کدام است؟

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

9. عبارت a*b+c-a/d به صورت پسوندی کدام است؟

صف (Queue)

10. عبارت queue.rear==queue.front کدام مفهوم را از صف نشان می دهد؟

لیست‌های پیوندی

11. در مقایسه آرایه با لیست پیوندی، کدام مورد زیر صحیح می باشد؟

لیست‌های پیوندی

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

درخت‌ها

13. درختی که اختلاف سطح برگ های آن حداکثر یک باشد، کدام درخت است؟

درخت‌ها

14. حداکثر تعداد گره های سطح i ام یک درخت دودویی با کدام گزینه برابر می باشد؟

درخت‌ها

15. در روش پیمایش inorder، ترتیب مشاهده گره ها به چه صورت می باشد؟

درخت‌ها

16. یک درخت k تایی که در آن فقط یک گره به نام ریشه با درجه ورودی صفر وجود دارد و سایر گره های درجه ورودی یک هستند، کدام درخت است؟

درخت‌ها

17. درخت max tree کدام است؟

لیست‌های پیوندی

18. عمل درج و حذف از ترتیب به راست به چپ در لیست پیوندی مرتب با کدام زمان نمایش داده می شود؟

درخت‌ها

19. زمان میانگین اجرای جستجوی یک عنصر در درخت جستجوی دودوئی، چقدر است؟

گراف‌ها

20. هر گاه اطلاعاتی به یال های گراف نسبت داده شود، آن گراف کدام است؟

گراف‌ها

21. در یک گراف جهت دار به چه گره ای چاه گفته می شود؟

گراف‌ها

22. در گراف جهت دار G=(V,E)، مجموع یال های ورودی گره ها با کدام گزینه برابر می باشد؟

مرتب‌سازی

23. کدام الگوریتم مرتب سازی، در آرایه های مرتب دارای بدترین عملکرد و در آرایه های نامرتب دارای بهترین عملکرد است؟

مرتب‌سازی

24. در کدام یک از الگوریتم های مرتب سازی، در هر سه حالت بهترین، متوسط و بدترین حالت دارای مرتبه زمانی O(nlogn) می باشند؟

مرتب‌سازی

25. بهترین روش مرتب سازی برای n های کوچک، کدام الگوریتم می باشد؟

سوالات تشریحی

این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینه‌ای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.

جستجو

1. پیچیدگی زمانی الگوریتم جستجوی ترتیبی را در سه حالت بهترین، متوسط و بدترین حالت تحلیل نمایید.

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

2. عبارت پیشوندی زیر را به عبارت پسوندی معادل تبدیل کنید. /-*+ABC-DE+FG

صف (Queue)

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

لیست‌های پیوندی

4. تابعی بنویسید که اشاره گر لیست پیوندی را بگیرد و تعداد گره های لیست را برگرداند.

درخت‌ها

5. عبارت A+(B-C)×D∧(E×F) را به صورت درخت نمایش دهید.

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