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

کد درس 1115112

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

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

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

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

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

1. مرتبه اجرایی تابع زمانی روبرو چیست؟ T(n)=4*2^n+5n^3logn+2n^4

جستجو

2. جستجوی دودویی بر روی چه آرایه ای قابل انجام است؟

جستجو

3. در جستجوی ترتیبی زمان اجرا در بهترین حالت چقدر است؟

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

4. معادل پیشوندی عبارت زیر کدام است؟ ((A+B)*(C-D))

صف (Queue)

5. در لیست اولین ورودی اولین خروجی را چه می نامند؟

درخت‌ها

6. منظور از درخت k تایی چیست؟

درخت‌ها

7. اگر درخت دودویی که هرگره ی آن یا 2 فرزند داشته باشد و حداکثر اختلاف بین سطح گره های برگ آن یک باشد، چگونه درختی است؟

درخت‌ها

8. اگر T یک درخت دودویی کامل با n گره باشد: اگر i≠1 باشد آنگاه پدر i در ...... است.

گراف‌ها

9. کدام عملیات بر روی گراف انجام نمی پذیرد؟

گراف‌ها

10. چند نوع جستجو در گراف داریم و نام آن ها چیست؟

مرتب‌سازی

11. در الگوریتم های مرتب سازی ............. از حداقل زمان و حافظه استفاده می شود و درجه این نوع الگوریتم های مرتب سازی ............ می باشند.

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

12. مرتبه اجرای الگوریتم زیر چیست؟ For(j=1; j<=m; j++) For(k=1; k<=j; k++) X++;

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

13. کدامیک از روابط زیر نشان دهنده رابطه صحیح زمان محاسبه الگوریتم های مختلف است؟

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

14. الگوریتم های بازگشتی چه معایبی دارند؟

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

15. با توجه به تابع func(100) روبرو چه خواهد بود؟ int Func(int n){ if(n==0) return 0; return(n+func(n-1)); }

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

16. در ضرب سه آرایه A(3,4) و B(4,6) و C(6,2) به ترتیب A*B*C چند عمل ضرب انجام می شود؟

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

17. اگر a=2, b=4, c=8, d=10 باشد، ارزش عبارت پسوندی ab*c+da-/ چیست؟

پشته (Stack)

18. یک پشته خالی با اعداد 1 تا 6 در ورودی داده شده است. اعمال push و pop بر روی پشته قابل انجام هستند. کدامیک از گزینه های زیر را نمی توان با هیچ ترتیبی از این اعمال فوق به دست آورد؟ (اعداد را از چپ به راست بخوانید)

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

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

درخت‌ها

20. پیمایش پس ترتیبی (postorder) یک درخت به صورت DEBFCA می باشد. کدامیک از گزینه های زیر پیش ترتیبی (preorder) آن را نشان می دهد؟

مرتب‌سازی

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

مرتب‌سازی

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

درخت‌ها

23. می خواهیم با وارد کردن مقادیر 1، 2، 3 به هر ترتیب دلخواه، در یک درخت جستجوی دودویی که در ابتدا خالی است، یک درخت جستجوی دودویی با 3 گره بسازیم. چند درخت جستجوی دودویی متفاوت ممکن است ساخته شود؟

گراف‌ها

24. در گراف زیر پیمایش bfs و با شروع از راس v1 کدام ترتیب رئوس دیده خواهد شد؟ (از چپ به راست)

گراف‌ها

25. کدام گراف معادل ماتریس مجاورت زیر است؟

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

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

درخت‌ها

1. متنی شامل 7000 حرف از حروف f.e.d.c.b.a با تفاوت تکرار a=1000 و b=1200 و c=800 و d=1500 و e=1800 و f=700 موجود است چنانچه کدی بهینه برای حروف بالا انتخاب نمایید تعداد کل بیت های لازم برای تبدیل متن مذکور به مجموعه ای از بیت ها چقدر است؟

مرتب‌سازی

2. فرض کنید آرایه زیر را می خواهیم با روش heapsort مرتب کنیم. پس از اجرای مرحله اول الگوریتم درخت heap حاصل کدام است؟ 5, 26, 40, 18, 12, 35, 15

گراف‌ها

3. الگوریتم پریم برای بدست آوردن درخت پوشای کمینه را توضیح داده و نتیجه اعمال آن بر روی گراف زیر را نشان دهید.

پشته (Stack)

4. به کمک دو ساختمان داده صف و پشته، الگوریتمی بنویسید که رشته ای از کاراکترها را از ورودی بخواند و تعیین کند آیا رشته متقارن است یا خیر؟

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

5. فرض کنید آرایه دو بعدی A(20×30) بصورت ستونی در حافظه ذخیره شده است. اگر آدرس شروع ذخیره سازی 1000 باشد و هر عنصر آرایه نیاز به 2 بایت حافظه داشته باشد، در اینصورت آدرس عنصر A(11,9) از چه آدرسی شروع می شود؟

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