نمونه سوالات ساختمان داده‌ها — تابستان ۱۳۹۸

کد درس 1115112

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

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

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

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

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

1. تابع زیر از چه مرتبه ای میباشد؟ a=n; While(a>1){ a/=2; b=n; while(b>1){ b/=3; x++; } }

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

2. زمان اجرای الگوریتم F(N) به صورت زیر برابر کدام گزینه است؟ F(N)=1 اگر n=1؛ F(N)=n+T(n-1) اگر n≥2

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

3. بهترین الگوریتم بازگشتی برای محاسبه x به توان y دارای چه مرتبه زمانی است؟

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

4. پیچیدگی زمانی قطعه برنامه زیر چیست؟ FOR i=1 to n do FOR j=1 to i do FOR k=1 to n do x:=x+1;

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

5. آرایه A به صورت زیر تعریف شده است: A=array[3...50] of integer; اگر آرایه در آدرس 1000 حافظه قرار داشته باشد آدرس A[14] به روش سطری کدام است؟

جستجو

6. در صورتیکه آرایه مورد جستجو در جستجوی دودویی به صورت 7 6 5 4 3 2 1 0 -1 باشد متوسط تعداد مقایسه ها برای جستجوی موفق چیست؟

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

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

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

8. تعداد عناصر غیر صفر یک آرایه اسپارس سه قطری n×n چقدر است؟

پشته (Stack)

9. پشته (STACK) ساختمان داده ای است از نوع:

پشته (Stack)

10. اگر رشته اعداد 1-2-3-4-5 را به ترتیب به یک پشته STACK وارد کنیم کدام یک از خروجی های زیر از این پشته امکان پذیر نخواهد بود؟ (خروجی پشته را از سمت چپ به راست بخوانید.)

پشته (Stack)

11. مناسب ترین ساختار داده جهت آدرس ثبت محل بازگشت در موقع فراخوانی زیر برنامه ها کدام است؟

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

12. عبارت پیشوندی (prefix) مقابل داده شده است: ++a/b-cd/-ab-+c*d5/a-bc معادل پسوندی آن کدام است؟

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

13. اگر a=2 b=4 c=8 d=10 باشد ارزش عبارت پسوندی ab*c+da-/ چیست؟

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

14. یک لیست خطی یک طرفه با دو اشاره گر F و R که به ترتیب به عنصر اول و آخر لیست اشاره می کند پیاده سازی شده است. هزینه کدام یک از عملیات زیر وابسته به تعداد عناصر لیست است؟

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

15. در اضافه کردن یک گره به لیست پیوندی دو طرفه چند اشاره گر باید تغییر یابد؟

درخت‌ها

16. در یک درخت جستجوی باینری کدام عمل در O(1) انجام می شود؟

درخت‌ها

17. در یک درخت دودویی کامل با 5 سطح حداکثر چند گره وجود دارد؟ (سطح ریشه برابر یک فرض شود)

درخت‌ها

18. پیمایش preorder درخت زیر کدام است؟ (ریشه A، فرزندان B و C؛ زیر B: D و E؛ زیر E: H و I؛ زیر C: F و G؛ زیر F: J و K)

درخت‌ها

19. کد هافمن عبارت AABAABAACAABAACACABA چند بیت دارد؟

گراف‌ها

20. بیشترین تعداد لبه در یک گراف غیر جهت دار با N راس عبارتند از:

مرتب‌سازی

21. الگوریتم InsertionSort زیر چه نوع مرتب سازی است؟ void InsertionSort(int[] A){ int N=A.length; for(i=1;i<N;i++){ key=A[i]; for(j=i-1;j>=0 && A[j]>key;j--) A[j+1]=A[j]; A[j+1]=key; } }

مرتب‌سازی

22. الگوریتم QUICK SORT یک رشته N تایی را در حالت متوسط به چه سرعتی مرتب میکند؟

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

23. در برنامه زیر خروجی F(3,6) چه می شود (تابع فیبوناچی)؟ int F(int m,int n){ if(m==1 || n==0 || m==n) return 1; else return F(m-1,n)-F(m-1,n-1); }

درخت‌ها

24. به درختی Heap گفته می شود که:

مرتب‌سازی

25. کدامیک از روشهای مرتب سازی زیر در بدترین حالت از o(n*n) است؟

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

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

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

1. آرایه A:ARRAY[5..20] OF REAL تعریف شده است. اگر این آرایه از آدرس 100 حافظه به بعد قرار گرفته باشد آدرس خانه A[16] کدام است؟ تعداد عناصر آرایه را نیز بدست آورید.

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

2. عبارت postfix معادل عبارت (A+B)*D+E/(F+A*D) را بدست آورید.

صف (Queue)

3. تابع اضافه کردن و حذف کردن یک عنصر به صف را پیاده سازی کنید.

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

4. تابعی بنویسید که اشاره گر لیست پیوندی را بگیرد و تعداد گره های لیست را برگرداند.

درخت‌ها

5. درخت شکل زیر را در نظر بگیرید و این درخت را به صورت درخت دودویی نشان دهید.

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