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

کد درس 1115112

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

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

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

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

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

1. مرتبه اجرای الگوریتم زیر چیست؟ X=0; For(j=0; j<n-1; j++) For(k=n-1; k>=j+1; k--) X++;

لیست‌های پیوندی

2. پیچیدگی عمل درج و عمل حذف را از لیست پیوندی به ترتیب برابر کدام گزینه است؟

ماتریس اسپارس

3. کدام روش برای ذخیره ماتریس های پایین مثلثی مناسب تر است؟

ماتریس اسپارس

4. فرض کنید آرایه A با row سطر و col ستون به صورت float A[row][col] در زبان ++c تعریف شده باشد. اگر آدرس پایه این آرایه برابر 200 باشد و هر float چهار بایت اشغال کند، آنگاه آدرس A[i][j] به روش ستونی توسط کدام یک از روابط زیر به دست می آید؟

عبارات پیشوندی و پسوندی

5. عبارت infix معادل عبارت زیر کدام است؟ /-/a*bcdg

پشته (Stack)

6. اعداد 1 تا 6 به ترتیب وارد پشته می شوند. کدام یک از گزینه ها را نمی توان در خروجی نمایش داد؟

صف (Queue)

7. کدام گزینه در ساختار صف حلقوی با n=5 بیان کننده خالی یا پر بودن صف است؟

پشته (Stack)

8. برای پیاده سازی کلاس پشته در ++c تابعی به نام ()stack همنام با نام کلاس پشته تعریف می شود که به آن سازنده (constructor) گویند. کدام یک از عمل های زیر در سازنده ()stack انجام می شود؟

صف (Queue)

9. صف خالی q و پشته خالی s را در نظر بگیرید. قطعه برنامه زیر چه داده ای را در خروجی چاپ می کند؟ Cin>>n; While(n){ q.Add(n%10); n/=10; } While(!q.isEmpty()){ m=q.Delete(); if(m!=0) s.push(m); } while(!s.isEmpty()) cout<<s.pop();

لیست‌های پیوندی

10. تابع زیر چه عملی را انجام می دهد؟ List x(node* L){ if(L!=null){ x(L->next); cout<<L->info; } }

لیست‌های پیوندی

11. برای اضافه کردن یک گره به یک لیست پیوندی دوطرفه چند جای گزینی لازم است؟

لیست‌های پیوندی

12. حاصل قطعه کد مقابل کدام گزینه می تواند باشد؟ P=first; Sum=0; While(p!=null){ If(p->info%2==0) Sum=sum+p->info; P=p->next; }

لیست‌های پیوندی

13. قطعه کد زیر چه کاری انجام می دهد؟ P=getnode(); p->info=x; p->next=start; start=p;

درخت‌ها

14. اگر در یک درخت با حداکثر درجه 2 تعداد کل گره ها 17 باشد و تعداد گره ها با درجه 2 دوبرابر تعداد گره ها با درجه 1 باشد، تعداد گره ها با درجه 1 برابر است با:

درخت‌ها

15. حداقل تعداد عناصر یک درخت دودویی کامل کدام است؟

درخت‌ها

16. دوشرط HEAP بودن یک درخت دودویی کدام است؟

درخت‌ها

17. کاربرد درخت جستجوی دودویی چیست؟

مرتب‌سازی

18. کدام گزینه الگوریتم های مرتب سازی ای را نشان می دهد که از لحاظ درجا بودن هم مانند هم هستند؟

مرتب‌سازی

19. در مرتب سازی سریع، دومین دو عددی که جای آنها با یکدیگر عوض می شود کدام است؟ 68, 81, 61, 93, 55, 100, 78, 98, 84, 65, 70, 75

گراف‌ها

20. در گراف مقابل نتیجه جستجوی عمقی برابر است با.........

جستجو

21. اگر یک لیست مرتب شده (با n خانه) را با استفاده از الگوریتم Binary search برای یک مقدار خاص جستجو کنیم تعداد دفعات مقایسه چه خواهد بود؟

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

22. تابع بازگشتی زیر را در نظر بگیرید: مقدار برگشتی rec(3) برابر است با: int f(int n){ if(n==1) return 2; else return(f(n-1)*f(n-1)); }

مرتب‌سازی

23. آرایه زیر را در نظر بگیرید. بعد از یک مرحله اجرای مرتب سازی سریع، آرایه چه شکلی پیدا می کند؟ 25 57 48 37 12 92 86 33

درخت‌ها

24. عمق درخت دودویی معادل عبارت محاسباتی (-a)*b*c-d/e*g+h برابر است با:

درخت‌ها

25. کدام گزینه نادرست است؟

سوالات تشریحی

این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینه‌ای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.

درخت‌ها

1. با استفاده از الگوریتم هافمن، درخت رمزگذاری زیر را محاسبه کنید. طول کلمات bee و disable را به دست بیاورید. (کاراکتر: L s i a e d b — تعداد تکرار: 12 4 2 8 9 4 5)

درخت‌ها

2. تابعی بنویسید که برگ های درخت دودویی را محاسبه کند.

پشته (Stack)

3. ساختمان داده پشته و تمام عملگرهای آن را پیاده سازی کنید.

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

4. الگوریتم بازگشتی، برای سری فیبوناچی را نوشته و مرتبه اجرایی آن را محاسبه نمایید.

مرتب‌سازی

5. الگوریتم مرتب سازی درجی را نوشته و پیچیدگی زمانی آن را محاسبه نمایید. آیا این الگوریتم پایدار است؟

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