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

کد درس 1115112

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

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

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

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

مرتب‌سازی

1. در مرتب سازی ادغامی، برای ادغام دو آرایه مرتب شده با m و n عنصر، حداکثر چند مقایسه لازم است؟

مرتب‌سازی

2. پیچیدگی کدامیک از الگوریتم های مرتب سازی زیر در حالت متوسط و در بدترین حالت با هم متفاوت است؟

گراف‌ها

3. کدامیک از الگوریتم های زیر برای تهیه درخت پوشای کمینه مورد استفاده قرار می گیرد؟

مرتب‌سازی

4. کدامیک از الگوریتم های مرتب سازی زیر پایدار است؟

مرتب‌سازی

5. کدامیک از الگوریتم های مرتب سازی زیر برای مرتب کردن یک آرایه n عنصری به یک آرایه کمکی به همان اندازه نیاز دارد؟

مرتب‌سازی

6. کدامیک از روش های مرتب سازی زیر در لیست مرتب بهترین عملکرد و در لیست نامرتب بدترین عملکرد را دارد؟

مرتب‌سازی

7. در روش مرتب سازی ......، رکوردهای با کلید مساوی به همان ترتیب قبل از عمل مرتب سازی نگهداری می شوند.

مرتب‌سازی

8. در لیست زیر اگر عنصر اول یعنی عدد 9 را به عنوان عنصر لولا در نظر بگیریم، کدامیک از گزینه های زیر می تواند خروجی مرحله اول الگوریتم مرتب سازی سریع باشد؟ (9, 10, 8, 7, 6, 15, 3)

گراف‌ها

9. حداکثر تعداد لبه های یک گراف جهت دار شامل n گره همبند است برابر با:

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

10. کدامیک از عوامل زیر در زمان اجرای برنامه مهم تر است؟

جستجو

11. مرتبه زمانی الگوریتم های جستجوی ترتیبی و یافتن بیشترین مقدار در یک لیست (در بدترین حالت)، به ترتیب از چپ به راست برابر است با:

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

12. فرض کنید a و b نمایش دو عدد صحیح مثبت باشند و تابع Q به شکل زیر به صورت بازگشتی تعریف شده باشد: Q(a,b)=0 اگر a<b؛ Q(a,b)=Q(a-b,b) اگر b≤a. این تابع چه عملی انجام می دهد؟

جستجو

13. زمان اجرای الگوریتم جستجوی دودویی در بدترین حالت برای یک آرایه n عنصری برابر است با:

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

14. به ازای چه مقادیری از n، نمایش یک ماتریس قطری به صورت اسپارس مقرون به صرفه است؟

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

15. روش لهستانی معکوس نام دیگر کدام روش است؟

پشته (Stack)

16. اگر دنباله اعداد 1، 3، 4، 5، 7 را به ترتیب از چپ به راست وارد پشته کنیم، کدام یک از خروجی های زیر از پشته امکان پذیر نیست؟

پشته (Stack)

17. در کدام ساختار، ترتیب ورود و خروج داده ها به صورت آخرین ورودی اولین خروجی (LIFO) است؟

صف (Queue)

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

درخت‌ها

19. در کدام نوع درخت، همه گره ها به جز گره های سطح آخر دقیقا دو فرزند دارند؟

درخت‌ها

20. در کدام روش پیمایش درخت، ابتدا زیر درخت چپ، سپس ریشه و بعد از آن زیر درخت راست پیمایش می شود؟

درخت‌ها

21. پیچیدگی تابع درج یک عنصر جدید به درخت heap برابر است با:

درخت‌ها

22. با مقادیر 1، 2، 3 چند درخت جستجوی دودویی می توان ساخت؟

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

23. قطعه کد زیر چه کاری انجام می دهد؟ q=getnode(); q->info=x; q->next=p->next; p->next=q;

گراف‌ها

24. تعداد یال های یک گراف کامل بدون جهت برابر است با:

درخت‌ها

25. حداکثر تعداد گره ها در سطح i ام یک درخت دودویی برابر است با: (1<i<=n)

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

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

مرتب‌سازی

1. الگوریتم مرتب سازی حبابی را نوشته و پیچیدگی آن را محاسبه نمائید.

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

2. فرمول ذخیره سازی سطری و ستونی عناصر آرایه دو بعدی A با ابعاد m×n را در حافظه بنویسید.

صف (Queue)

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

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

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

درخت‌ها

5. پیمایش پیشوندی یک درخت دودویی به صورت ABDFCEG می باشد و پیمایش میانوندی آن به صورت DFBAEGC است. درخت دودویی مربوطه را ترسیم نمائید.

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