نمونه سوالات ساختمان داده‌ها — نیمسال دوم ۱۴۰۲-۱۴۰۳

کد درس 1115112

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

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

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

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

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

1. کدام یک از موارد زیر در خصوص پیچیدگی زمانی کد زیر صحیح است؟ S=0; for(i=0;i<n;i++) for(j=0;j<i;j++) S++;

جستجو

2. پیچیدگی زمانی جستجوی دودویی در یک آرایه با طول n چیست؟

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

3. گزاره‌های زیر را در نظر بگیرید: ۱- اگر T(n)∈Ω(G(n)) آنگاه G(n)∈O(T(n)). ۲- اگر T(n)∈θ(G(n)) آنگاه G(n)∈θ(T(n)). ۳- اگر T(n)∈O(G(n)) آنگاه G(n)∈Ω(T(n)). کدام گزاره‌ها صحیح هستند؟

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

4. توابع زیر را در نظر بگیرید: G(n)=n^2, F(n)=2^n, K(n)=n!, Z(n)=n^n, Q(n)=nlogn. با توجه به این توابع کدام یک از موارد زیر صحیح است؟

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

5. کدام‌یک از موارد زیر برقرار است؟ ۱) 4n^2-7n+2 ∈ θ(n^2) ۲) n^3+n^2logn ∈ θ(n^3) ۳) n!+4n^5 ∈ θ(n^n) ۴) 4n^2·2^n+5n^2logn ∈ θ(n^2·2^n)

گراف‌ها

6. گرافی بدون جهت با ۱۰ گره حداکثر چند یال می‌تواند داشته باشد (بدون در نظر گرفتن یال از یک گره یال به گره خودش)؟

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

7. تابع زیر چه کاری انجام می‌دهد؟ node *f(node* list){ node *m,*t; m=NULL; while(list){ t=m; m=list; list=list->next; m->next=t; } return m; }

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

8. یک ماتریس اسپارس به نام A به صورت زیر نمایش داده شده است. کوچکترین عدد ستون با اندیس ۳ و میانگین اعداد ماتریس A چیست؟ (اندیس‌های آرایه از صفر شروع می‌شوند)

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

9. اگر آرایه دوبعدی به نام A از نوع int با ابعاد ۳۰ سطر و ۴۰ ستون به صورت سطری ذخیره شود و آدرس آن در حافظه ۱۰۰۰ باشد، آدرس خانه A[10][20] چیست؟ (اندیس آرایه از صفر شروع می‌گردد و هر متغیر int دوبایت حافظه مصرف می‌کند.)

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

10. معادل پیشوندی عبارت پسوندی زیر را بنویسید. Ab+cd-*

پشته (Stack)

11. پیچیدگی زمانی درج و حذف در پشته چیست؟

پشته (Stack)

12. اگر اعداد ۶۵۴۳۲۱ به ترتیب از راست به چپ در پشته وارد شوند، کدام یک از خروجی‌های زیر (از راست به چپ) امکان‌پذیر نیست؟

پشته (Stack)

13. برای پیاده سازی عملیات Undo در نرم افزاری مانند Word، کدام ساختار مناسب‌تر است؟ (Undo گزینه‌ای است که باهر بار انتخاب آن، آخرین عملیاتی که کاربر انجام داده است لغو می‌گردد.)

پشته (Stack)

14. کدام یک از موارد زیر مربوط به پشته است؟

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

15. کدام گزینه صحیح است؟

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

16. کد زیر چه کاری انجام می‌دهد؟ void f(node* list){ if(list!=NULL){ f(list->next); cout<<list->info; } }

صف (Queue)

17. در یک صف حلقوی که با آرایه پیاده سازی شده است اگر f=6 و r=2 باشد و ظرفیت آرایه ۲۰ باشد، تعداد عناصر داخل صف حلقوی چیست؟ (f نشان گر سر صف و r نشانگر ته صف است)

گراف‌ها

18. پیمایش گراف زیر به روش BFS با شروع از گره a چیست؟

درخت‌ها

19. پیمایش preorder درختی که پیمایش postorder و inorder آن به صورت زیر است چیست؟ inorder: bfdaegc — postorder: fdbgeca

درخت‌ها

20. حداقل و حداکثر تعداد گره ها در یک درخت دودویی کامل با ۴ سطح چیست؟

درخت‌ها

21. اگر تعداد گره‌های درجه صفر درخت دودویی ۲۰ باشد، تعداد گره‌های درجه دو این درخت چند است؟

درخت‌ها

22. پیچیدگی زمانی حذف از درخت maxheap چیست؟

درخت‌ها

23. یک درخت maxheap به صورت زیر در آرایه‌ای پیاده سازی شده است. بعد از درج عدد ۱۵ چه عددی در خانه آرایه با اندیس ۵ قرار می‌گیرد؟ (اندیس ۱ تا ۱۰: 16,14,10,8,7,9,3,2,4,1)

درخت‌ها

24. درخت زیر چه نوع درختی است؟ (ریشه ۶۰، فرزندان ۴۱ و ۷۴؛ زیر ۴۱: ۱۶ و ۵۳؛ زیر ۵۳: ۴۶ و ۵۵؛ زیر ۱۶: ۲۵؛ زیر ۲۵: ۴۲؛ زیر ۷۴: ۶۵؛ زیر ۶۵: ۶۳ و ۷۰؛ زیر ۶۳: ۶۲ و ۶۴)

مرتب‌سازی

25. پیچیدگی زمانی مرتب سازی انتخابی چیست؟

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

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

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

1. یک تابع بازگشتی برای محاسبه سری فیبوناچی ارائه دهید.

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

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

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

3. فرض کنید دو لیست یک پیوندی موجود است و firsta، firstb به ابتدای این دو لیست اشاره می‌کنند. قطعه کدی بنویسید که این دو لیست را ترکیب کند به طوری‌که لیست دوم در انتهای لیست اول قرار گیرد.

گراف‌ها

4. درخت پوشای کمینه گراف زیر را رسم کنید. (گراف شامل گره‌های A,B,C,D,E,F با یال‌های وزن‌دار: A-B=1، A-D=4، A-E=3، B-E=2، B-C=4، C-F=5، D-E=4، E-F=7)

مرتب‌سازی

5. تابعی بنویسید که یک آرایه را به روش انتخابی به صورت صعودی مرتب کند.

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