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

کد درس 1115112

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

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

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

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

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

1. مرتبه زمانی قطعه برنامه مقابل کدام است؟ for(i=1; i<=n-1; i++) for(j=1; j<=n+2; j++)

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

2. تابع زمانی یک تابع بازگشتی به شکل زیر است، مرتبه زمانی این تابع کدام است؟ T(n)=c اگر n=1؛ T(n)=T(n/2)-d اگر n>1

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

3. ماتریس a طبق دستور itemType a[12][4] تعریف شده است. با فرض اینکه طول داده itemType ۱۰ (ده) بایت باشد، و آدرس شروع آرایه ۳۰۰۰ باشد، آدرس داده a[5][2] کدام است؟ (نحوه ذخیره سازی ماتریس سطری است)

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

4. یک ماتریس ۱۰۰×۱۰۰ حاوی ۹۹ داده عددی صحیح می باشد. اگر این ماتریس را به صورت اسپارس (خلوت) ذخیره کنیم، نسبت فضای اشغالی ماتریس اسپارس به ماتریس معمولی چه کسری خواهد شد؟ (فرض کنید row, col, value هر سه از نوع عددی صحیح می باشند.)

پشته (Stack)

5. کدام گزینه تمام داده های موجود در پشته s را بازیابی کرده و در خروجی چاپ می کند؟

پشته (Stack)

6. اگر دنباله اعداد ۱ تا ۶ را از کوچک به بزرگ وارد پشته کنیم، کدام یک از خروجی های زیر از پشته، غیر قابل تولید است؟

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

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

پشته (Stack)

8. دو پشته غیر خالی s1 و s2 و صف خالی q و پشته خالی s مفروض است. پشته s1 را در q خالی می کنیم و q را در s1 خالی می کنیم. پشته s2 را نیز در s خالی می کنیم و دوباره پشته s را در s2 خالی می کنیم. کدام گزینه صحیح است؟

صف (Queue)

9. شرط خالی بودن و شرط پر بودن صف حلقوی کدام است؟

صف (Queue)

10. صف های Q1 و Q2 با داده های زیر (از چپ به راست) و صف Q3 مفروض است. پس از اجرای قطعه کد زیر، صف Q3 چگونه خواهد بود؟ Q1: 4,3,1,2,9,5 — Q2: 1,8,6,7. while(!Empty(Q1)&&!Empty(Q2)){ a=Delete(Q1); b=Delete(Q2); Add(Q3,a+b); }

پشته (Stack)

11. اگر بخواهیم عمل Process صف را در پشته شبیه سازی کنیم با ترکیب کدام اعمال پشته این کار امکان پذیر است؟

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

12. تابع زیر چه عملی روی لیست دو پیوندی انجام می دهد؟ void f(node* p){ node* n=new node; n->next=p->next; n->prev=p; p->next->prev=n; p->next=n; }

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

13. تابع زیر چه کاری انجام می دهد؟ (first اشاره گر ابتدای لیست پیوندی است) double something(node* first){ node* p=first; double s=0,n=0; while(p){ n++; s+=p->info; p=p->next; } return s/n; }

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

14. تابع زیر چه کاری انجام می دهد؟ (first اشاره گر ابتدای لیست پیوندی است) void solve(node* first){ if(!first) return; cout<<first->info; solve(first->next); }

درخت‌ها

15. اگر نمایش پرانتزی یک درخت عمومی به شکل A(B,C,D(S,T),E(P,Q,R),F) باشد، پس از تبدیل درخت عمومی به درخت دودویی، کدام گره ها برگ خواهند بود؟

درخت‌ها

16. پیمایش پیش ترتیب درختی به صورت acbefd و پیمایش میان ترتیب آن به صورت bceafd می باشد. پیمایش پس ترتیب این درخت کدام است؟

پشته (Stack)

17. در صورتی که بخواهیم یک پشته را با استفاده از لیست پیوندی پیاده سازی کنیم، تابع PUSH باید به چه شکلی نوشته شود؟

درخت‌ها

18. تابع زیر چه ویژگی از درخت دودویی T را محاسبه می کند؟ int compute(node* T){ if(!T) return 0; if(T->left_child==NULL && T->right_child==NULL) return 1; return compute(T->left_child)+compute(T->right_child); }

درخت‌ها

19. کدام ساختار برای حذف داده های تکراری موجود در یک لیست اولیه مناسب تر است؟

درخت‌ها

20. اعداد 1 تا 99 را بدون در نظر گرفتن ترتیب خاصی در یک درخت جستجوی دودویی درج می کنیم. سپس درخت ایجاد شده را به صورت میان ترتیب (InOrder) پیمایش می کنیم. کدام گزینه در مورد خروجی بدست آمده صحیح است؟

گراف‌ها

21. نتیجه جستجوی عمقی (DFS) روی گراف زیر با شروع از رأس 1 چیست؟

گراف‌ها

22. گراف غیر جهت دار G توسط ماتریس مجاورتی زیر تعریف شده است. وزن درخت پوشای کمینه (مینیمم) با استفاده از الگوریتم وارشال روی گراف G کدام است؟ (A-B=20, A-C=10, A-D=18, A-E=6, B-C=15, B-D=2, C-D=39, C-E=4)

گراف‌ها

23. اگر A ماتریس مجاورتی گراف G و B=A*A*A باشد، B[2][4] چه اطلاعاتی به ما می دهد؟

مرتب‌سازی

24. کدام یک از الگوریتم های مرتب سازی زیر غیر درجا است؟

مرتب‌سازی

25. در مرتب سازی سریع اگر اولین عنصر را به عنوان محور (Pivot) در نظر بگیریم، کدام گزینه بدترین شرایط را برای مرتب سازی نشان می دهد؟

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

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

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

1. یک تابع بازگشتی برای محاسبه فاکتوریل بنویسید و پیچیدگی زمانی آن را به روش تکرار با جایگذاری به دست بیاورید.

پشته (Stack)

2. یک کلاس برای پشته طراحی کنید و تمامی توابع آن را پیاده سازی کنید.

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

3. تابعی بنویسید که اشاره گر یک لیست پیوندی به همراه یک عدد را دریافت کرده و پس از جستجو در لیست، آدرس اولین گره حاوی داده مورد جستجو را برگرداند. در صورت عدم وجود داده در لیست، مقدار NULL برگشت داده شود.

درخت‌ها

4. داده های زیر را به ترتیب از چپ به راست وارد یک Max Heap کنید و مراحل کار را با رسم شکل توضیح دهید. 40, 30, 50, 25, 60, 55, 75

مرتب‌سازی

5. داده های زیر را به روش مرتب سازی سریع مرتب کنید و مراحل مرتب سازی را نشان دهید. 40, 10, 50, 90, 11, 36, 22

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