نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۳۹۵-۹۶
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرایی تابع زمانی روبرو چیست؟ T(n)=4*2^n+5n^3logn+2n^4
2. جستجوی دودویی بر روی چه آرایه ای قابل انجام است؟
3. در جستجوی ترتیبی زمان اجرا در بهترین حالت چقدر است؟
4. معادل پیشوندی عبارت زیر کدام است؟ ((A+B)*(C-D))
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-/ چیست؟
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. الگوریتم پریم برای بدست آوردن درخت پوشای کمینه را توضیح داده و نتیجه اعمال آن بر روی گراف زیر را نشان دهید.
4. به کمک دو ساختمان داده صف و پشته، الگوریتمی بنویسید که رشته ای از کاراکترها را از ورودی بخواند و تعیین کند آیا رشته متقارن است یا خیر؟
5. فرض کنید آرایه دو بعدی A(20×30) بصورت ستونی در حافظه ذخیره شده است. اگر آدرس شروع ذخیره سازی 1000 باشد و هر عنصر آرایه نیاز به 2 بایت حافظه داشته باشد، در اینصورت آدرس عنصر A(11,9) از چه آدرسی شروع می شود؟