نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۵-۹۶
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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 دو بایت فضا اشغال می کند.)
6. اگر رشته اعداد زیر را به ترتیب (از چپ به راست) به یک پشته وارد کنیم کدام یک از خروجی های زیر از پشته امکان پذیر خواهد بود؟ 1,2,3,4,5
7. معادل postfix عبارت روبرو کدام است؟ x+y/(u-t*w)*y
8. برای تبدیل عبارت a+b*(c/(d+e))*f به عبارت پسوندی با استفاده از پشته، حداقل سایز پشته چند خانه باشد؟
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] می باشد.)
3. تابع حذف یک عنصر از صف و تابع اضافه کردن یک عنصر به صف را بنویسید.
4. الف) اعداد زیر را (از چپ به راست) به یک درخت جستجوی دودویی اضافه کرده، درخت را مرحله به مرحله رسم نمایید. 44, 30, 50, 22, 60, 55, 46 — ب) عدد 50 را از آن حذف نمایید و دوباره درخت را مرحله به مرحله رسم نمایید.
5. اعداد زیر را به روش مبنایی (Radix) مرتب کنید و همه گذرها را نیز رسم کنید. (از چپ به راست بخوانید.) 25, 57, 47, 36, 12, 91, 82, 31