نمونه سوالات ساختمان دادهها — تابستان ۱۳۹۴
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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. روش لهستانی معکوس نام دیگر کدام روش است؟
16. اگر دنباله اعداد 1، 3، 4، 5، 7 را به ترتیب از چپ به راست وارد پشته کنیم، کدام یک از خروجی های زیر از پشته امکان پذیر نیست؟
17. در کدام ساختار، ترتیب ورود و خروج داده ها به صورت آخرین ورودی اولین خروجی (LIFO) است؟
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 را در حافظه بنویسید.
3. برای یک ساختار صف حلقوی با n=7، چه حالتی بیان کننده خالی و پر بودن صف می باشد؟
4. تابعی بنویسید که اشاره گر به ابتدای لیست پیوندی یک طرفه را بگیرد و تعداد گره های لیست را برگرداند.
5. پیمایش پیشوندی یک درخت دودویی به صورت ABDFCEG می باشد و پیمایش میانوندی آن به صورت DFBAEGC است. درخت دودویی مربوطه را ترسیم نمائید.