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

کد درس 1115112

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

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

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

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

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

1. کدام یک از توابع زمانی زیر از پیچیدگی زمانی بالاتری برخوردار است؟

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

2. مرتبه اجرایی قطعه برنامه زیر چیست؟ for (int i=n; i>=1; i/=2) X++;

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

3. آرایه a به صورت int a[10] تعریف شده است. اگر آدرس اولین خانه آرایه در حافظه 5200 باشد، با فرض اینکه هر داده int دو بایت اشغال کند، آدرس a[4] کدام است؟

پشته (Stack)

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

پشته (Stack)

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

صف (Queue)

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

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

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

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

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

صف (Queue)

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

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

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

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

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

صف (Queue)

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

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

13. کدام گزینه لیست پیوندی L را معکوس می کند؟ (مقدار اولیه m برابر NULL است)

درخت‌ها

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

درخت‌ها

15. تابع زیر چه پیمایشی روی درخت دودویی T انجام می دهد؟ void traverse(node* T){ if (T==NULL) return; cout << T->info; traverse(T->left_child); traverse(T->right_child); }

درخت‌ها

16. پیمایش پیش ترتیب (PreOrder) یک درخت دودویی ABDCE و پیمایش میان ترتیب (InOrder) آن BDAEC می باشد. پیمایش پس ترتیب (PostOrder) درخت، کدام گزینه است؟

درخت‌ها

17. می خواهیم با استفاده از یک heap تعداد n داده را به طور صعودی مرتب کنیم. کدام روش صحیح است؟

درخت‌ها

18. پیمایش inorder یک درخت جستجوی دودویی (BST) چه ویژگی دارد؟

درخت‌ها

19. تابع زیر کدام ویژگی درخت دودویی T را محاسبه می کند؟ int f(node* T){ if (T==NULL) return 0; if (T->Left==Null) && (T->Right==Null) return 1; return f(T->Left)+f(T->Right); }

درخت‌ها

20. یک درخت دودویی با 20 گره مفروض است. اگر تعداد گره های درجه 2 برابر 7 باشد تعداد برگها کدام است؟

گراف‌ها

21. حاصل پیمایش عرضی (BFS) گراف زیر با شروع از رأس A کدام است؟ (گره ها به ترتیب حروف الفبا ملاقات می شوند)

گراف‌ها

22. هزینه احداث جاده برای شهرهای یک استان، مطابق جدول زیر است. کمترین هزینه برای اینکه از هر شهری به هر سایر شهرها مسیری وجود داشته باشد کدام است؟ (از درخت پوشای کمینه استفاده کنید)

درخت‌ها

23. استفاده از کدام ساختار برای حذف عناصر تکراری از یک لیست مناسب است؟

مرتب‌سازی

24. کدام یک از روش های مرتب سازی زیر در تمام شرایط (بهترین، بدترین و متوسط) از پیچیدگی زمانی O(nlogn) برخوردار است؟

مرتب‌سازی

25. در یک روش مرتب سازی برای n داده، در مرحله i ام، کوچکترین عنصر لیست را در بازه [i..n-1] پیدا کرده و جای آن را با اندیس i تعویض می کنیم (i از صفر تا n-2 می باشد). این روش چه نام دارد؟

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

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

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

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

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

2. الگوریتم تبدیل عبارت میانوندی به پسوندی را به کمک پشته بنویسید.

صف (Queue)

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

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

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

درخت‌ها

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

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