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

کد درس 1115112

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

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

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

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

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

1. مرتبه اجرایی تابع زمانی زیر کدام گزینه است؟ T(n)=n^5 logn+6n+2^n

جستجو

2. مرتبه زمانی الگوریتم جستجوی دودویی و الگوریتم جستجوی ترتیبی در بهترین حالت به ترتیب کدام گزینه است؟

درخت‌ها

3. تعداد درخت های جستجوی دودویی با n گره و تعداد عمل ضرب حاصل از ضرب n ماتریس در یکدیگر به ترتیب از کدام رابطه بدست می آید؟

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

4. مرتبه زمانی شبه کد زیر چیست؟ j=n; for(i=1;i<n;i++) while(j>1) j/=2;

مرتب‌سازی

5. الگوریتم مرتب سازی سریع در بدترین حالت چه مرتبه زمانی دارد و این بدترین حالت چه موقع رخ می دهد؟

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

6. می خواهیم یک ماتریس پایین مثلثی را در یک آرایه یک بعدی ذخیره سازی نماییم که عضو آن با اندیس یک بعدی k مشخص می شود. بین اندیس دو بعدی i,j و اندیس یک بعدی k در آرایه کدام گزینه درست است؟

صف (Queue)

7. اگر در یک صف حلقوی front=-1 و rear=-1 باشد این صف دارای چند عنصر است؟

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

8. کدام گزینه یک عمل اصلی در مورد آرایه می باشد؟

صف (Queue)

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

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

10. مرتبه زمانی درج یک عنصر در یک آرایه مرتب و مرتبه زمانی درج یک عنصر در آرایه نامرتب به ترتیب برابر است با.......

جستجو

11. در الگوریتم جستجوی دودویی زمانیکه عنصر مورد جستجو در داخل آرایه مورد جستجو قرار ندارد (L اشاره به اولین عنصر آرایه و h اشاره به آخرین عنصر آرایه دارد) در مراحل اجرای الگوریتم در نهایت به چه صورت خواهد شد؟

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

12. جهت تبدیل عبارت میانوندی زیر به عبارت پسوندی با استفاده از پشته، حداکثر سایز پشته مورد نیاز برابر است با: a×b+c/d^e

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

13. تعداد سطرها و ستون ها در ذخیره سازی یک ماتریس اسپارس به ترتیب به چه صورت است؟

پشته (Stack)

14. اگر دنباله اعداد 9،7،5،3،1 را به ترتیب از چپ به راست در پشته وارد کنیم کدامیک از خروجی های زیر از این پشته امکان پذیر نیست؟

درخت‌ها

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

درخت‌ها

16. یک درخت دودویی با 20 گره مفروض است. اگر تعداد گره های درجه 2 برابر 8 گره باشد، تعداد گره های برگ و تعداد گره های درجه 1 به ترتیب چند تاست؟

درخت‌ها

17. در کدام نوع درخت های دودویی همه گره ها به جز گره های سطح آخر، ماکزیمم تعداد فرزندان را دارند؟

درخت‌ها

18. درخت متوازن درختی است که........

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

19. معادل پیشوندی عبارت زیر کدام است؟ (^ علامت توان است.) a+b×c^d^e

درخت‌ها

20. پیمایش پس ترتیب (postorder) و میان ترتیب (inorder) یک درخت به صورت زیر است. پیمایش پیش ترتیب (preorder) آن کدام گزینه است؟ میانوندی: BAEGFC — پسوندی: BGFECA

مرتب‌سازی

21. مرتبه زمانی کدام الگوریتم مرتب سازی در همه شرایط یکسان است و برابر با کدام گزینه است؟

مرتب‌سازی

22. کدامیک از الگوریتم های مرتب سازی زیر در همه حالات (بهترین حالت، بدترین حالت و حالت میانگین) دارای مرتبه زمانی یکسانی نیستند؟

گراف‌ها

23. مجموع وزن های درخت پوشای مینیمم با استفاده از الگوریتم پریم بر روی گراف زیر کدام گزینه است؟

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

24. حاصل عبارت پسوندی زیر چیست؟ 1 2 + 3 × 14 4 1 3 × + / +

درخت‌ها

25. از کدامیک از درخت های زیر می توان برای مرتب سازی مجموعه ای از عناصر استفاده کرد؟

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

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

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

1. مرتبه زمانی عبارت بازگشتی زیر را به روش جایگذاری با تکرار بدست آورید؟ T(n)=2T(n/2)+nc اگر n>2؛ T(n)=d اگر n=2

جستجو

2. شبه کد الگوریتم جستجوی دودویی را بنویسید و در مورد مرتبه زمانی آن در بدترین حالت، بهترین حالت و حالت میانگین بحث کنید.

مرتب‌سازی

3. داده های زیر را با استفاده از heapsort به ترتیب صعودی مرتب نمایید. 40،70،20،30،20،5

پشته (Stack)

4. دو عملگر push، pop پشته را با استفاده از لیست پیوندی پیاده سازی نمایید.

درخت‌ها

5. متنی شامل 5000 حرف از حروف جدول زیر به همراه فرکانس تکرار هر حرف موجود است. چنانچه کدی بهینه برای حروف جدول انتخاب نماییم تعداد کل بیت های لازم برای تبدیل متن مذکور به مجموعه ای از بیت ها چقدر است؟ a=1000 b=700 c=800 d=600 e=1000 f=900

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