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

کد درس 1115112

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

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

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

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

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

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

درخت‌ها

2. ماکزیمم تعداد node ها در یک درخت دودویی با ارتفاع h برابر است با

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

3. کدام گزینه مرتبه زمانی کد زیر را نشان می دهد؟ for (i=1; i<=n; i++) for (j=1; j<=n; j=j+i) ++x;

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

4. توابع زیر را در نظر بگیرید. کدام یک از گزاره های زیر صحیح است؟ f(n)=4 logn, g(n)=(logn) logn, h(n)=log2 n

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

5. در پردازه مقابل اگر b=64 باشد خروجی کدام است؟ void test(int b){ if b>1 then {b/=2; test(b);} Printf("%d",b); }

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

6. آرایه M(30x20x10) را که هر عنصر آن نیاز به 4 بایت حافظه دارد به صورت ستونی (column major) از بایت 20000 در حافظه ذخیره می نماییم (مبنای 10). در این صورت آدرس خانه M(21,11,9) از چه بایتی شروع می شود؟

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

7. زمان ترانهاده گرفتن از یک ماتریس خلوت (sparse) چقدر است اگر n تعداد سطرها و m تعداد ستون ها و t تعداد عناصر غیرصفر ماتریس باشد؟

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

8. چهار ماتریس با ابعاد زیر در نظر بگیرید: A 10x2, B 2x25, C 25x3, D 3x4 کدام یک از گزینه های زیر مربوط به پرانتزبندی بهینه برای محاسبه حاصلضرب آنهاست؟

جستجو

9. اگر A آرایه ای مرتب از اعداد صحیح 1 الی 1024 باشد الگوریتم جستجوی دودویی با چند بار تکرار عدد 4 را پیدا می کند؟

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

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

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

11. می خواهیم تغییراتی در یک لیست پیوندی اعمال کنیم که عمل افزودن عنصر ابتدا یا انتهای لیست با عملیاتی از مرتبه O(1) قابل انجام باشد. لیست پیوندی را.....

صف (Queue)

12. عناصر صف های Q1 و Q2 از چپ به راست بصورت زیر است (عنصر سمت چپ ابتدای صف است) اگر x و y عناصر صف باشند پس از اجرای تکه برنامه زیر محتوی صف Q3 برابر است با: Q1=10,2,3,4,5,6,7 Q2=1,12,13,4,15,6 — makeNULL(Q3); i=0; while(not empty(Q1) and not empty(Q2)){ i=i+1; x=DeleteQ(Q1); y=DeleteQ(Q2); if(y=i) then AddQ(Q3,x); }

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

13. حاصل عبارت postfix روبرو چیست؟ 3 1 2 × + 2 3 8 − + 3 2 6 +

درخت‌ها

14. تعداد درخت های دودویی با n عنصر و با ارتفاع h برابر است با:

درخت‌ها

15. اگر در یک درخت با حداکثر درجه 2، تعداد کل گره های آن 17 و تعداد گره ها با درجه 2 برابر 6 باشد، تعداد گره ها با درجه 1 برابر است با

درخت‌ها

16. پیمایش یک درخت دودویی به شکل preorder و inorder داده شده است. پیمایش postorder آن کدام است؟ Preorder: GBQACPDER — Inorder: QBCAGPEDR

درخت‌ها

17. تابع زیر برای درخت دودویی T چه عملی انجام می دهد؟ Function n(T:tree):integer; Begin if T=NULL then n:=0; if T≠NULL then if Rchild(T)=NULL and Lchild(T)=NULL then n:=1; else n:=n(Rchild(T))+n(Lchild(T))+1; end

گراف‌ها

18. پیمایش عمقی dfs گراف زیر می تواند کدام باشد؟

گراف‌ها

19. در تست قبل کدام گزینه پیمایش bfs را نشان می دهد؟

گراف‌ها

20. خروجی کدام الگوریتم درخت پوشا برای گراف نیست؟

گراف‌ها

21. هزینه درخت پوشای مینیمم گراف زیر چیست؟

گراف‌ها

22. اگر تعداد گره های یک گراف |V| و تعداد لبه های آن |E| باشد و بر روی آن الگوریتم DFS اعمال کنیم، مرتبه این الگوریتم به ترتیب از چپ به راست برای پیاده سازی گراف با ماتریس همجواری و لیست همجواری چه خواهد بود؟

مرتب‌سازی

23. در الگوریتم insertion sort بهترین شرایط و بدترین شرایط به ترتیب از راست به چپ عبارتند از:

مرتب‌سازی

24. لیست زیر را در نظر بگیرید. (3،15،6،7،8،10،9) اگر عنصر اول لیست یعنی عدد 9 را به عنوان لولا (pivot) انتخاب کنیم کدام یک از گزینه های زیر می توانند خروجی مرحله اول الگوریتم مرتب سازی سریع Quick sort باشد؟

مرتب‌سازی

25. اگر در الگوریتم Merge sort برای مرتب سازی لیست های زیر 20 عنصر از الگوریتم Insertion sort استفاده شود پیچیدگی زمانی الگوریتم چه خواهد شد؟

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

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

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

1. تابعی بنویسید که عناصر یک آرایه 10 عنصری را گرفته و به صورت اینه ای (قرینه ای) قرینه کند (جای عنصر اول و آخر جابجا شود سپس جای عنصر دوم و ماقبل آخر جابجا شود و ...)

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

2. تابعی بنویسید که داده های لیست پیوندی را از آخر به اول چاپ کند.

مرتب‌سازی

3. مراحل مرتب سازی آرایه زیر را با روش مرتب سازی مبنایی اعداد بنویسید: 25،57،48،37،12،92،86،33

مرتب‌سازی

4. الگوریتم مرتب سازی selection sort را توضیح داده و پیچیدگی آن را در بهترین حالت و بدترین حالت و حالت متوسط بیان کنید. آیا این الگوریتم پایدار است؟

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

5. رابطه بازگشتی زیر را در نظر بگیرید پیچیدگی زمانی آن را بدست آورید: T(n)≤C1 اگر n=1؛ T(n)≤2T(n/2)+C2n اگر n>1

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