نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۳-۹۴
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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 برابر با کدام گزینه خواهد بود؟
9. دنباله اعداد 9،7،5،3،1 را به ترتیب از چپ به راست وارد پشته می کنیم. اگر تنها عمل مجاز بر روی پشته عملیات push و pop باشد، آنگاه کدام یک از خروجی های زیر از پشته (از چپ به راست) امکان پذیر نیست؟
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 راس، حداکثر تعداد یال ها تا چند تا است؟
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. الگوریتم مرتب سازی ادغامی را به طور کامل بنویسید. سپس الگوریتم را برای لیست حاوی اعداد زیر دنبال نموده و مراحل اجرای الگوریتم را به صورت یک ساختار درختی نمایش دهید.