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

کد درس 1115112

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

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

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

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

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

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

پشته (Stack)

2. اعداد 1 تا 5 به ترتیب وارد پشته می شوند. کدام یک از دنباله های زیر را نمی توان در خروجی نمایش داد؟

پشته (Stack)

3. پشته به کمک آرایه s پیاده سازی شده است. کدام دستور برای حذف یک عنصر از پشته صحیح است؟

پشته (Stack)

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

صف (Queue)

5. یک صف حاوی تعدادی عدد صحیح مفروض است. کدام گزینه مجموع اعداد درون صف را محاسبه می کند؟ (مقدار اولیه sum را صفر درنظر بگیرید)

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

6. تابع زمانی یک تابع بازگشتی مطابق زیر است. پیچیدگی زمانی این تابع از چه مرتبه ای است؟ T(n)=c اگر n=2؛ T(n)=T(n-2)+d اگر n>2

پشته (Stack)

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

صف (Queue)

8. در یک ساختار صف حلقوی با N=8 اگر front=4 و rear=4 باشد، صف در چه حالتی قرار دارد؟

صف (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); }

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

11. اگر first اشاره گر به اول یک لیست پیوندی یکطرفه باشد، دستورات زیر چه عملی انجام می دهند؟ for (p=first; p!=NULL; p=p->next) p->info++;

پشته (Stack)

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

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

13. در یک لیست پیوندی یکطرفه، گره p، گره q ماقبل p می باشد. کدام گزینه روش صحیح حذف گره q است؟ (p و q غیرتهی هستند)

صف (Queue)

14. پیچیدگی زمانی اضافه کردن یک آیتم جدید به صف حلقوی (پیاده سازی با آرایه) و صف پیوندی (پیاده سازی با لیست پیوندی) از چه مرتبه هایی می باشند؟

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

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

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

16. تابع زیر چه کاری انجام می دهد؟ (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; }

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

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

درخت‌ها

18. گره های یک درخت دودویی کامل از 1 تا n اندیس گذاری شده اند. پدر گره شماره 7 کدام است؟

درخت‌ها

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

درخت‌ها

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

پشته (Stack)

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

درخت‌ها

22. تابع زیر چه ویژگی از درخت دودویی 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); }

درخت‌ها

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

درخت‌ها

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

گراف‌ها

25. گراف غیر جهت دار 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)

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

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

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

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

صف (Queue)

2. کلاسی برای ساختمان داده صف با استفاده از آرایه تعریف نموده و عملگرهای Add و Delete آن را پیاده سازی کنید.

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

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

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

4. تابعی بنویسید که اشاره گر ابتدای یک لیست پیوندی یکطرفه را دریافت کرده و میانگین داده های موجود در لیست را برمی گرداند.

درخت‌ها

5. برای عبارت ریاضی زیر یک درخت دودویی رسم نموده، سپس پیمایش پیش ترتیب و پس ترتیب درخت را نشان دهید. A×B+D/(C-K)

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