نمونه سوالات ساختمان داده‌ها — نیمسال دوم ۱۴۰۳-۱۴۰۴

کد درس 1115112

25 سوال تستی + 5 تشریحیرایگان

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

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

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

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

1. کدام گزینه تعریف صحیحی از الگوریتم ارائه می‌دهد؟

جستجو

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

پشته (Stack)

3. کدام ساختار داده از اصل LIFO پیروی می‌کند؟

پشته (Stack)

4. عمل Push در پشته چه کاری انجام می‌دهد؟

جستجو

5. پیچیدگی الگوریتم جستجوی دودویی در آرایه مرتب، از چه مرتبه‌ای است؟

صف (Queue)

6. کدام گزینه ویژگی اصلی صف (Queue) را توصیف می‌کند؟

پشته (Stack)

7. در پشته، عمل Pop چه کاری انجام می‌دهد؟

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

8. کدام روش برای حل روابط بازگشتی استفاده می‌شود؟

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

9. ماتریس اسپارس چیست؟

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

10. اگر T(n) = 3n^2 + 2n + 1 باشد، نماد O بزرگ آن چیست؟

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

11. برای ارزیابی عبارات پسوندی (POSTFIX)، استفاده از کدام نوع ساختمان داده، مفیدتر است؟

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

12. کدام گزینه نمایش صحیح عبارت (A+B)*C به صورت پسوندی است؟

صف (Queue)

13. در پیاده‌سازی صف، اشاره‌گر front به ...... اشاره دارد و موقع ...... به کار می‌رود.

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

14. کدام روش برای نمایش ماتریس اسپارس مناسب است؟

پشته (Stack)

15. فرض کنید تعدادی عنصر در یک پشته درج شده‌اند. در صورتی که بخواهیم محتویات آن را بدون حذف عنصر بالایی از پشته فقط مشاهده نمائیم، کدام روش می‌تواند جوابگو باشد؟

درخت‌ها

16. چند درخت جستجوی دودویی متفاوت با ۳ مقدار می‌توان ساخت؟

درخت‌ها

17. فرض کنید درخت هافمن برای کاراکترهای A تا H با وزن‌های زیر ساخته شده و کدهای زیر به هریک از کاراکترها استخراج شده است. تعداد بیت‌های لازم برای ذخیره‌سازی کل این کاراکترها چند بیت خواهد بود؟ عنصر: A B C D E F G H — وزن: 22 5 11 19 2 11 25 5

مرتب‌سازی

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

درخت‌ها

19. کدام گزینه صحیح است؟ الف- با داشتن پیمایش میان ترتیبی و پس نرتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت. ب- با داشتن پیمایش پیش ترتیبی و پس نرتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت. ج- با داشتن پیمایش پیش ترتیبی و میان ترتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت.

درخت‌ها

20. خروجی تابع زیر با فرض اینکه T اشاره‌گر به گره رأس یک درخت دودویی جستجو باشد چیست؟ (نوع داده Tree، یک درخت جستجوی دودویی است) int what(Tree T){ Tree P; P=T; while(P->left) P=P->left; return P->data; }

گراف‌ها

21. اگر بخواهیم یک گراف با n راس و m یال را به صورت یک ماتریس مجاورت ذخیره نمائیم، از یک ماتریس با چه ابعادی باید استفاده خواهیم کرد؟

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

22. معادل میانوندی عبارت پیشوندی (Prefix) روبرو چیست؟ / × + a b c − a b

صف (Queue)

23. در پیاده سازی صف حلقوی، یک خانه را حتماً باید خالی نگه داریم، دلیل این کار چیست؟

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

24. تابع زیر بر روی یک لیست یک‌طرفه چه میکند؟ int Test(List *L){ List *x; T=0; if(L){ x:=L; while(x){ T=T+1; x=x->link; } } return T; }

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

25. برای حذف گره‌ی میانی در یک لیست پیوندی دوطرفه، چند تغییر آدرس لازم است؟

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

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

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

1. تابعی بنویسید که محتویات لیست یک طرفه را به روش بازگشتی نشان دهد.

راهنما: صفحه ۳۰

درخت‌ها

2. فرض کنید پیمایش‌های inorder و preorder یک درخت دودویی به صورت زیر باشد، درخت دودویی موردنظر را رسم کنید. inorder: D B H E A I F J C G — preorder: A B D E H C F I J G

راهنما: صفحه ۲۸

درخت‌ها

3. درخت جستجوی دودویی حاصل از درج اعداد زیر را رسم کنید: 34, 42, 21, 9, 18, 38, 39, 37, 14, 10, 12, 16

راهنما: صفحه ۷۵

پشته (Stack)

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

راهنما: پاسخ در فصل ۳ کتاب درسی، توابع push و pop

جستجو

5. یک آرایه مرتب n عنصری را در نظر گرفته با تابعی به نام Search، عنصر x را در آن جستجو نمائید. سپس زمان آن را تحلیل نمائید (جستجوی دودویی مدنظر است).

راهنما: صفحه ۴۵

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