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

کد درس 1115112

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

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

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

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

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

1. مرتبه اجرای قطعه برنامه زیر کدام است؟ s=0; for(x=1;x<=n;++x) for(y=1;y<=x;++y) for(z=1;z<=y;++z) s+=1;

جستجو

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

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

3. کدامیک از روابط زیر نشان دهنده رابطه صحیح زمان محاسبات الگوریتم ها می باشد؟

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

4. فرض کنید آرایه B به صورت int B[15] تعریف شود و base(b) برابر با 5000 می باشد و با فرض اینکه هر عدد صحیح 2 بایت فضا از حافظه را اشغال می کند آدرس خانه B[9] را محاسبه کنید؟

جستجو

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

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

6. تعداد عناصر آرایه یک بعدی بعدی کدام است؟

جستجو

7. فرض کنید آرایه A 200 عنصری مرتب شده باشد. زمان اجرای بدترین حالت F(n) برای پیدا کردن عنصر معلوم x در آرایه A با استفاده از جستجوی دودویی چقدر است؟

پشته (Stack)

8. کدام یک از ساختارهای داده زیر را LIFO می نامند؟

پشته (Stack)

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

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

10. عبارت پسوندی (postfix) معادل عبارت ریاضی a/b-c+d*e-a*c/d را به دست آورید؟

صف (Queue)

11. پیچیدگی زمانی تابع اضافه کردن به صف و تابع حذف از صف کدام است؟

صف (Queue)

12. در ساختار داده صف، پربودن صف چگونه ارزیابی می شود؟

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

13. کدام یک در خصوص مقایسه آرایه با لیست پیوندی صحیح می باشد؟

صف (Queue)

14. قطعه کد زیر کدام یک از اعمال زیر را در ساختار داده صف انجام می دهد؟ { Node *ptr; ptr=front; front=front->next; freenode(ptr); }

درخت‌ها

15. کدام تعریف در خصوص درخت ها صحیح می باشد؟

درخت‌ها

16. درخت عمومی کدام است؟

درخت‌ها

17. بعد از حذف گره 20، درخت heap حاصل چگونه است؟

درخت‌ها

18. با مقادیر 1 و 2 و 3 چند درخت جستجوی دودویی می توان ساخت؟

گراف‌ها

19. کدام تعریف زیر در خصوص نظریه گراف صحیح می باشد؟

گراف‌ها

20. حداکثر تعداد یال های یک گراف جهت دار همبند کدام است؟

مرتب‌سازی

21. پیچیدگی الگوریتم Quick sort در بهترین حالت، حالت متوسط و بدترین حالت از راست به چپ کدام است؟

مرتب‌سازی

22. کدام یک در خصوص ویژگی های مرتب سازی هرمی صحیح می باشد؟

درخت‌ها

23. نمایش پیوند زیر، کدام یک از درخت ها را توصیف می کند؟ (مقدار گره، فرزند چپ، فرزند راست)

گراف‌ها

24. گراف زیر را در نظر بگیرید. پیمایش ردیفی یا BFS آن کدام گزینه می باشد؟

مرتب‌سازی

25. کدام مرتب سازی در بردار مرتب بهترین عملکرد و در بردار نامرتب بدترین عملکرد را دارد؟

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

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

پشته (Stack)

1. اگر در آرایه S[495] بخواهیم 4 پشته درست کنیم، آدرس ابتدای هر پشته را به دست آورید؟

صف (Queue)

2. عناصر صف های Q1، Q2 از چپ به راست به صورت زیر باشند: Q1: 10,25,17,41,44,26,75 — Q2: 1,5,7,4,9,6. اگر x و y عناصر صف باشند پس از اجرای قطعه کد زیر، محتوای صف Q3 چه مقداری خواهد بود؟ i=0; while(!Empty(Q1) && Empty(Q2)){ i++; x=Delete(Q1); y=Delete(Q2); if(y=i) Add(Q3,x); }

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

3. تابعی بنویسید که لیست L را دریافت کرده، معکوس لیست پیوندی خطی را بدست آورد؟

درخت‌ها

4. پیمایش های inorder و preorder یک درخت دودویی به صورت زیر می باشد، درخت دودویی معادل را رسم نمایید؟ inorder: D B H E A I F J C G

گراف‌ها

5. گراف جهت دار G مانند شکل زیر است، ماتریس مجاورت آن را رسم نمایید؟

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