نمونه سوالات ساختمان دادهها — تابستان ۱۳۹۹
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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) قابل انجام باشد. لیست پیوندی را.....
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