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

کد درس 1115112

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

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

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

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

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

1. مرتبه اجرای الگوریتم زیر چیست؟ for(j=1; j<=m; j++) for(k=1; k<=j; k++) x++;

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

2. اگر T(n)=3n^3+2n^2 باشد، کدام عبارت درست است؟

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

3. اگر a,b دو عدد صحیح مثبت و تابع Q به صورت زیر تعریف شده باشد، آنگاه Q(14,3) برابر خواهد بود با: Q(a,b)=0 اگر a<b؛ Q(a,b)=Q(a-b,b)+1 اگر a≥b

جستجو

4. برای آرایه ای با 12 عنصر حداکثر تعداد مقایسه ها برای یافتن عنصر در جستجوی دودویی چقدر خواهد بود؟

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

5. اگر آرایه به شکل int A[3][4]; تعریف شود و آدرس پایه این آرایه 3000 باشد، آدرس عنصر A[1][1] به روش سطری کدام گزینه است؟ (هر عنصر از نوع int دو بایت فضا اشغال می کند.)

پشته (Stack)

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

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

7. معادل postfix عبارت روبرو کدام است؟ x+y/(u-t*w)*y

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

8. برای تبدیل عبارت a+b*(c/(d+e))*f به عبارت پسوندی با استفاده از پشته، حداقل سایز پشته چند خانه باشد؟

صف (Queue)

9. برای یک صف حلقوی با اندازه 4 خانه پس از اجرای دستورات زیر عنصر سر صف کدام گزینه است؟ دستورات را از چپ به راست بخوانید. Addq(A); Addq(B); delq(); Addq(C); delq(); Addq(E); delq(); Addq(F);

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

10. دستورات مقابل چه کاری انجام می دهند؟ node* first; first=new struct node; return first;

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

11. دستورات لازم برای درج یک عنصر newp در لیست پیوندی دو طرفه بعد از گره p، به شکل مقابل است اما ناقص است. مکان خالی A با کدام گزینه کامل می شود؟ p->right->left=newp; A: ...........; p->right=newp; newp->left=p;

درخت‌ها

12. پیمایش درخت مقابل به صورت LRV (پسوندی) چگونه خواهد بود؟ (ریشه A، فرزندان C و B؛ زیر C: E؛ زیر B: F)

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

13. تابع زیر چه عملی انجام می دهد؟ (با فرض اینکه نوع list اشاره گر است) list Func(list L){ list m,t; m=NULL; while(L){ t=m; m=L; L=L->link; m->link=t; } return m; }

درخت‌ها

14. درخت زیر یک درخت: (ریشه 12، فرزندان 10 و 17؛ زیر 10: 6 و 11؛ زیر 17: 18)

درخت‌ها

15. آرایه زیر یک heap است برای درج عدد 95 در آرایه به گونه ای که آرایه نهایی نیز وضعیت heap داشته باشد، چند عمل exchange (تعویض دو کمیت) لازم است؟ (آرایه: 100, 90, 82, 85, 74, 75, 73, 68, 70)

درخت‌ها

16. کدام یک از موارد زیر برای درخت انتخابی صحیح است؟

درخت‌ها

17. کدام درخت AVL است؟

درخت‌ها

18. چه تعداد درخت دودویی را می توان با 4 گره ساخت؟

درخت‌ها

19. پیمایش پس ترتیب (postorder) یک درخت به صورت ECFBA می باشد و پیمایش میان ترتیب (inorder) آن ECABF می باشد. پیمایش پیش ترتیب (preorder) آن کدام است؟

گراف‌ها

20. با فرض نمایش یک گراف با کمک لیست همسایگی، اگر تعداد رئوس گراف G برابر n و تعداد یال ها برابر e باشد، زمان یافتن تعداد کل یال ها کدام است؟

گراف‌ها

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

گراف‌ها

22. وزن درخت پوشای کمینه برای گراف زیر کدام گزینه است؟

مرتب‌سازی

23. مرتبه اجرایی کدام روش مرتب سازی همواره O(n log n) است؟

مرتب‌سازی

24. زمان اجرای الگوریتم merge sort کدام گزینه است؟

مرتب‌سازی

25. بدترین حالت در روش مرتب سازی سریع (quick sort) چیست؟

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

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

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

1. رابطه بازگشتی زیر را در نظر بگیرید: T(n)=C اگر n=2؛ T(n)=T(n-2)+d اگر n>2. این رابطه را به روش تکرار با جایگذاری حل کنید.

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

2. اگر ماتریس پایین مثلثی A(m*n) را با یک آرایه یک بعدی B نمایش دهیم و هر عضو A[i][j] معادل عضو B[L] باشد، بین i و j و L چه رابطه ای باید برقرار باشد؟ (اولین عنصر ماتریس A[1][1] می باشد.)

صف (Queue)

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

درخت‌ها

4. الف) اعداد زیر را (از چپ به راست) به یک درخت جستجوی دودویی اضافه کرده، درخت را مرحله به مرحله رسم نمایید. 44, 30, 50, 22, 60, 55, 46 — ب) عدد 50 را از آن حذف نمایید و دوباره درخت را مرحله به مرحله رسم نمایید.

مرتب‌سازی

5. اعداد زیر را به روش مبنایی (Radix) مرتب کنید و همه گذرها را نیز رسم کنید. (از چپ به راست بخوانید.) 25, 57, 47, 36, 12, 91, 82, 31

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