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

کد درس 1115112

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

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

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

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

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

1. اگر تابع زمان اجرای الگوریتمی به شکل T(n) = am·n^m + am-1·n^(m-1) + ... + a1n + a0 باشد، زمان اجرای این الگوریتم برابر کدام گزینه خواهد بود؟

مرتب‌سازی

2. زمان اجرای الگوریتم زیر، کدام گزینه خواهد بود؟ (زمان اجرای exchange را O(1) در نظر بگیرید.) void bubble(elementtype A[], int n){ for(i=0;i<n-1;i++) for(j=n-1;j>i+1;j--) if(A[j-1]>A[j]) exchange(A[j],A[j-1]); }

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

3. رابطه بازگشتی زیر از چه مرتبه ای است؟ T(n)≤C1 اگر n=1؛ T(n)≤2T(n/2)+C2n اگر n>1

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

4. خروجی تابع زیر به ازای 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)); }

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

5. اگر داشته باشیم int A[10][5]: و آدرس پایه این ماتریس 50 باشد و بخواهیم ماتریس را به صورت ستونی در حافظه ذخیره کنیم، آنگاه عنصر A[3][2] در چه محلی ذخیره می شود؟ (sizeof(int)=2)

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

6. می خواهیم ماتریسی به شکل int matrix[10][10] را که تنها 10 عنصر غیر صفر دارد، به شکل بهبودیافته (اسپارس) ذخیره کنیم. در این صورت چند بایت مصرف خواهد شد؟ (هر int، 4 بایت فضا اشغال می کند.)

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

7. عبارت پیشوندی + d c 7 d c * b a + / - داده شده است. معادل پسوندی آن کدام است؟

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

8. حاصل عبارت پیشوندی b b c / * a b c * + - با فرض a=3، b=2، c=5 برابر با کدام گزینه خواهد بود؟

پشته (Stack)

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

پشته (Stack)

10. خروجی قطعه برنامه زیر چیست؟ stack s; int i; for(i=1;i<=4;i++){ s.push(2*i); s.push(3*i); } for(i=1;i<=4;i++) s.push(s.pop()-s.pop()); for(i=1;i<=4;i++) cout<<s.pop();

گراف‌ها

11. در یک گراف جهت دار با 6 راس، حداکثر تعداد یال ها تا چند تا است؟

صف (Queue)

12. اگر N=7 تعداد عناصر در یک صف حلقوی باشد و متغیر F به خانه ای که بلافاصله قبل از جلوی صف قرار دارد اشاره کند و متغیر R به عقب صف، در این صورت کدام گزینه پر بودن صف را نشان می دهد؟

جستجو

13. در روش جستجوی خطی، برای یافتن یک عنصر درون آرایه 19 عنصری، به طور متوسط چه تعداد مقایسه نیاز است؟

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

14. اگر L آدرس شروع یک لیست پیوندی باشد، برنامه زیر چه کاری انجام می دهد؟ int f1(Node* L){ int m=0; for(Node *p=L; p!=NULL; p=p->Next) if(m<p->info) m=p->info; return(m); }

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

15. کدام دستور به شکل صحیح گره بعد از p را از لیست پیوندی حذف می کند؟

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

16. تابع test چه عملی را روی لیست یکطرفه انجام می دهد؟ void test(list* first){ if(first!=NULL) if(first->link==NULL) first->data=0; else test(first->link); }

درخت‌ها

17. حداکثر تعداد گره ها در یک درخت دودویی به عمق 5 چند است؟

درخت‌ها

18. کدام آرایه نمی تواند نشان دهنده ی ذخیره یک درخت دودویی توسط آرایه ها باشد؟

درخت‌ها

19. به یک min heap خالی به ترتیب گره هایی با کلیدهای (از چپ به راست) 75، 40، 55، 45، 42، 50، 70 اضافه شده است. سپس 3 عمل حذف بر روی این min heap انجام می گیرد. درخت نهایی (که به صورت آرایه از چپ به راست نشان داده شده است) کدام گزینه است؟

گراف‌ها

20. حاصل پیمایش عرضی (BFS) گراف زیر با شروع از گره A چیست؟ (فرض کنید اولویت فرزندان بر اساس ترتیب حروف الفبا است.)

گراف‌ها

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

گراف‌ها

22. اگر در گراف زیر جستجوی dfs را از رأس c شروع کنیم، پیمایش گره ها از چپ به راست کدام است؟ (فرض کنید فرزندان یک گره به ترتیب حروف الفبا انتخاب شوند.)

مرتب‌سازی

23. کمترین زمان مورد نیاز برای مرتب سازی یک لیست n تایی چیست؟

مرتب‌سازی

24. الگوریتم مرتب سازی درجی را روی آرایه زیر انجام دهید. پس از گذر اول آرایه چگونه خواهد بود؟ (از چپ به راست) 20 43 17 5 30 18

مرتب‌سازی

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

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

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

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

1. اگر A یک آرایه n عنصری باشد، تابع زمانی و پیچیدگی زمانی تابع زیر را محاسبه کنید. int func(int A[], int n){ if(n==1) return A[0]; else return(A[n-1]+func(A,n-1)); }

درخت‌ها

2. پیمایش پیشوندی درختی ABCGDHEFR، و پیمایش میانوندی آن GCBHDAFRE می باشد. درخت را رسم نمایید.

درخت‌ها

3. الگوریتم حذف از یک max heap را به صورت کامل بیان کرده و با رسم شکل نشان دهید.

گراف‌ها

4. گراف وزن دار زیر را در نظر بگیرید. با استفاده از الگوریتم راشال درخت پوشای کمینه آن را رسم کنید.

مرتب‌سازی

5. الگوریتم مرتب سازی ادغامی را به طور کامل بنویسید. سپس الگوریتم را برای لیست حاوی اعداد زیر دنبال نموده و مراحل اجرای الگوریتم را به صورت یک ساختار درختی نمایش دهید.

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