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

کد درس 1115112

25 سوال تستی + 5 تشریحی🔒 پاسخ‌ها با اشتراک

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

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

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

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

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 به عبارت پسوندی آخرین عملگر پسوندی برابر است با:

پشته (Stack)

6. اگر دنباله اعداد 1,3,4,5,7 را به ترتیب از چپ به راست وارد یک پشته کنیم کدامیک از خروجی های زیر از پشته امکان پذیر نیست؟

صف (Queue)

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

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