نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۳۹۷-۹۸
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. زمان اجرای T(n)=4n+5nlogn+2 موجود است. مرتبه یا پیچیدگی زمانی آن را محاسبه نمایید؟
2. کدام یک از عبارات زیر صحیح می باشد؟
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 چه رابطه ای باید برقرار باشد؟
7. عملگر push در پشته چه عملیاتی انجام می دهد؟
8. مرتبه زمانی تابع push و pop در ساختار پشته کدام است؟
9. عبارت a*b+c-a/d به صورت پسوندی کدام است؟
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
3. برای یک ساختار صف حلقوی با n=7، چه حالتی بیان کننده خالی و یا پربودن صف می باشد؟
4. تابعی بنویسید که اشاره گر لیست پیوندی را بگیرد و تعداد گره های لیست را برگرداند.
5. عبارت A+(B-C)×D∧(E×F) را به صورت درخت نمایش دهید.