نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۳۹۴-۹۵
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرای برنامه زیر چیست؟ I=n; While(i>1){ I=i/2; j=n; While(j>1) j=j/3; }
2. کدامیک از روابط زیر نشان دهنده رابطه صحیح زمان محاسبه الگوریتم های مختلف است؟
3. مرتبه اجرای الگوریتم زیر چیست؟ For(j=1; j<=m; j++) For(k=1; k<=j; k++) X++;
4. فرض کنید A یک آرایه سه قطری n مربعی است. فرض کنید بخواهیم A را در یک آرایه خطی ذخیره کنیم. اندیس هر عنصر در آرایه کدام گزینه است؟
5. جهت تبدیل عبارت a+b*(c/(d-e))*f به عبارت پسوندی آخرین عملگر پسوندی برابر است با:
6. اگر دنباله اعداد 1,3,4,5,7 را به ترتیب از چپ به راست وارد یک پشته کنیم کدامیک از خروجی های زیر از پشته امکان پذیر نیست؟
7. عبارات زیر شرط خالی و پر بودن کدام ساختار را نشان می دهد؟ Front=Rear — (Rear+1) mod n=Front
8. به منظور درج یک عنصر در لیست مرتب در قطعه کد زیر به جای ؟ از کدام عبارت زیر استفاده کنیم؟ Newp=getnode(); Newp->info=5; Newp->next=?; p->next=Newp;
9. چندتا از عبارت های زیر راجع به درخت دودویی کامل با n گره صحیح می باشد؟ اگر i≠1 آنگاه پدر i در [i/2] است. اگر 2i<=n آنگاه فرزند چپ i در 2i است. اگر 2i+1<=n آنگاه فرزند راست i در 2i+1 است.
10. چندتا از عبارات زیر راجع به پیمایش درخت صحیح می باشد؟ اگر پیمایش پسوندی یا پیشوندی یک درخت دودوئی داشته باشیم، می توان درخت را به صورت یکتا ترسیم کرد. اگر پیمایش میانوندی و پسوندی یک درخت دودوئی داشته باشیم، می توان درخت را به صورت یکتا ترسیم کرد. اگر پیمایش میانوندی و پیشوندی یک درخت دودوئی داشته باشیم، می توان درخت را به صورت یکتا ترسیم کرد.
11. شکل های زیر به عنوان درخت های ...... دو درخت متمایز هستند ولی به عنوان درخت های ...... با هم هیچگونه تفاوتی ندارند.
12. تعداد عمل ضرب، حاصل ضرب n ماتریس برابر است با:
13. ............ درختی است که مقدار کلید هر گره آن کمتر از مقادیر کلید فرزندانش نباشد.
14. نمایش صف اولویت با کدام الگوریتم این امکان را فراهم می سازند که عملیات درج و حذف در زمان O(logn) صورت پذیرد؟
15. چندتا از عبارات زیر به منظور جستجوی عنصری مثل x صحیح می باشد؟ اگر آرایه مرتب شده باشد میانگین یافتن از مرتبه O(log n) می باشد. اگر ساختار لیست پیوندی باشد جستجوی عنصر مانند اضافه و حذف کردن ساده است. یک درخت دودوئی نمی تواند تهی باشد.
16. کدامیک از عبارات زیر صحیح نمی باشد؟ الف- هر گره 2- دودویی، 0 یا 2 فرزند دارد. ب- در 2- درخت NE=Ni+1 می باشد. ج- حاصل الگوریتم هافمن، 2- درخت دارای n گره خارجی با حداقل طول مسیر وزن دار می باشد.
17. کدامیک از موارد زیر در مورد درخت های دودویی جستجو صحیح است؟
18. برای درخت مقابل چندتا از پیمایش های زیر صحیح می باشد؟ postorder:DHEBIFJGCA — Preorder:ABDEHCIFJG — Inorder:DBEHAIFCJG
19. با مقادیر 1 و 2 و 3 چند درخت جستجوی دودوئی می توان ساخت؟
20. در الگوریتم پیمایش گراف مقدار STATUS=2 نشانه چیست؟ الف- حالت انتظار در صف ب- حالت ملاقات شده ج- حالت انتظار در پشته
21. اگر گراف G زیر را با شروع از راس A با استفاده از الگوریتم جستجوی عمقی پیمایش کنیم آخرین راس ملاقات شده برابر است با:
22. برای تعیین درخت پوشای کمینه با استفاده از الگوریتم پریم روی گراف وزن دار زیر، در مرحله چهارم کدام یال انتخاب می گردد؟
23. کدامیک از الگوریتم های مرتب سازی زیر پایدار و غیر درجا می باشد؟
24. چند تا از عبارات زیر در مورد مرتب سازی درست می باشد؟ مرتب سازی های حبابی و درجی در بهترین حالت از مرتبه O(n) است. مرتب سازی های هرمی و درختی در بدترین حالت از مرتبه O(n^2) است. مرتب سازی های سریع ادغامی در حالت متوسط از مرتبه O(n logn) می باشند.
25. کدامیک از عبارات زیر راجع به مرتب سازی صحیح نمی باشد؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. الگوریتم یافتن بیشترین مقدار آرایه نامرتب را نوشته و پیچیدگی آن را تحلیل نمائید.
2. با لیست اعداد زیر یک max heap بسازید. مراحل را به شکل کامل ترسیم نمائید. 44,30,50,22,60,55,77
3. با داشتن پیمایش های یک درخت دودویی (اعداد دو رقمی هستند)، مراحل حذف گره های 49 و 80 و 30 را ترسیم نمائید. برای پاسخ خود استدلال کافی بیاورید. Inorder: 20 30 38 49 55 65 71 80 — Postorder: 20 49 38 55 30 71 80 65
4. تابعی بنویسید که برگ های درخت دودویی را محاسبه نماید.
5. مراحل مرتب سازی آرایه زیر را با روش مرتب سازی مبنائی نشان دهید. 25,57,48,37,12,92,86,33