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

کد درس 1115112

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

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

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

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

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

1. یک آرایه دوبعدی با اندازه 10×10 موجود است. در این آرایه قطر اصلی و قطر فرعی یک و سایر مقادیر صفر می‌باشند. کدام گزینه در مورد این آرایه صحیح نیست؟

جستجو

2. دو آرایه مرتب a و b موجود است طول آرایه اول 900 و طول آرایه دوم 450 میباشد به طور همزمان در هردو آرایه عملیات جستجو برای پیدا کردن عنصر فرضی x را انجام می‌دهیم. در بدترین حالت بیشترین تعداد مقایسه کدام گزینه می‌باشد؟

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

3. یک ماتریس بالا مثلثی با اندازه n×n موجود است در این آرایه تمام عناصر زیر قطر یک میباشند مابقی عناصر ان صفر میباشند. ابتدا دو سطر اول آرایه را به صفر تبدیل میکنیم. کدام گزینه مجموع کل عناصر آرایه را نشان می‌دهد؟

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

4. آدرس پایه در آرایه چیست؟

درخت‌ها

5. یک درخت دودویی با 6 گره موجود است چند گزینه از موارد زیر صحیح است. ارتفاع ریشه یک صحیح است. الف- حداقل ارتفاع درخت 3 می‌باشد. ب- حداکثر ارتفاع درخت 6 است. ج- حداکثر سه گره با دو فرزند در درخت موجود است. د- اگر ارتفاع درخت 3 باشد درخت الزاما الزام درخت کامل است.

درخت‌ها

6. کدام گزینه در مورد درخت دودویی کامل درست است؟

درخت‌ها

7. ارتفاع یک درخت پر دودویی را دوبرابر می‌کنیم کدام گزینه درست است؟

درخت‌ها

8. در یک درخت دودویی 6 گره وجود دارد شماره اولین گره یک و آخرین گره 30 می‌باشد کدام گزینه الزاما درست است؟

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

9. یک آرایه مربعی با اندازه n موجود است در این آرایه سه ستون اول عدد و مابقی ستون‌ها صفر میباشند. میخواهیم محاسبه کنیم چه عددی باشد که ذخیره این آرایه به صورت اسپارس مقرون به صرفه باشد. مقدار n کدام گزینه است؟ اندازه هر عنصر را 4 بایت در نظر بگیرید.

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

10. مرتبه زمانی قطعه کد زیر کدام است؟ For(i=1; i<=n; i++) For(j=n; j>=1; j=j/2) K=k+1;

صف (Queue)

11. چند گزینه از موارد زیر درست است؟ الف- در صف خطی با حذف یک عنصر هردو متغیر front و rear تغییر میکنند. ب- در صف خطی با حذف یک عنصر، سایر عناصر به ابتدای صف شیفت داده میشوند. ج- در صف دایره‌ای ابتدا و انتهای صف به هم متصل است. د- در صف دایره‌ای همواره یک خانه از صف باید خالی بماند. ح- در صف دایره‌ای با حذف یک عنصر، سایر عناصر به ابتدای صف شیفت داده میشوند.

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

12. یک لیست پیوندی خطی با مقادیر گره‌های زیر موجود است: 12,9,-5,13,10,3,16 پس از اجرای قطعه کد زیر مجموع مقادیر لیست کدام گزینه خواهد شد؟ P=first; While(p!=null){ If(p->info>8) p->info=p->info-5; else p->info=p->info+3; p=p->next;}

مرتب‌سازی

13. روی داده‌های 10,15,24,23,31,17,9 مرتب سازی درجی انجام می‌شود پس از یک دور از مرتب سازی کدام عنصر در ابتدای لیست قرار می‌گیرد؟

مرتب‌سازی

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

مرتب‌سازی

15. کدام الگوریتم بر اساس ارقام داد ها ( یکان- دهگان و ... ) مرتب سازی را انجام می‌دهد؟

درخت‌ها

16. یک درخت کامل با 23 گره موجود است چند گزینه از موارد زیر درست است (ارتفاع ریشه یک است): الف- در این درخت 11 برگ موجود است. ب- حداقل سه برگ با ارتفاع 4 وجود دارد. ج- فقط یک گره تک فرزندی در درخت موجود است. د- اگر 5 گره از درخت حذف کنیم به درخت پر تبدیل می‌شود.

درخت‌ها

17. با استفاده از داده‌های زیر یک درخت جستجوی باینری ساخته شده است کدام گزینه درست است؟ از چپ به راست بخوانید. Input: 30-21-8-13-17-15-41-38-29

درخت‌ها

18. میخواهیم از یک درخت جستجوی باینری یک گره با دو فرزند را حذف کنیم کدام پیمایش مورد نیاز پیمایش است؟

درخت‌ها

19. برای حذف از heap کدام گره ابتدا حذف می‌شود؟

درخت‌ها

20. داد های زیر از چپ به راست در یک max heap قرار میگیرند کدام گزینه درست است؟ Input: 4-5-8-2-13-17-1

درخت‌ها

21. تعداد تکرار کاراکترهای زیر موجود است مطابق با الگوریتم هافمن طول کلمه assassin چند بیت خواهد بود؟ E=4 a=6 s=9 n=13 i=7 m=1

درخت‌ها

22. از موارد زیر چند گزینه درست است؟ الف- اگر ریشه درخت را حذف کنیم جنگل به وجود می‌آید. ب- کاراکتری با بیشترین تکرار کمترین فاصله را از ریشه در درخت هافمن خواهد داشت. ج- در درخت heap همه گره‌ها همواره دو فرزند دارند. د- تعداد برگ در درخت کامل و درخت پر همواره باهم برابر است.

درخت‌ها

23. یک درخت کامل با ارتفاع 6 را با افزودن 12 گره به یک درخت پر تبدیل کرده ایم اگر ارتفاع درخت پر تغییر نکند شماره آخرین گره در درخت کامل چند بوده است؟ ارتفاع ریشه یک است.

درخت‌ها

24. پیمایش‌های زیر از یک درخت دودویی موجود است چند گزینه از موارد زیر درست است؟ Inorder=hklaegjfcdib Preorder=gehaklbfjdci الف- در این درخت 5 برگ موجود است. ب- k و l فرزندان a میباشند. ج- در این درخت سه گره با دو فرزند وجود دارند. د- گره i فرزند راست b میباشد. و- ارتفاع دو زیر درخت راست و چپ ریشه باهم برابر است.

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

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

صف (Queue)

1. یک صف دایره‌ای به طول n موجود است شبه کد موارد زیر را بنویسید: الف- خالی بودن پشته ب- پر بودن پشته ج- اضافه کردن عنصر جدید به صف د- حذف عنصر از صف

درخت‌ها

2. داده های مقابل (چپ به راست) را در یک Min-heap قرار دهید. Input: 12,8,13,6,7,15,20,9 — الف- ایجاد heap ب- حذف گره 7

درخت‌ها

3. پیمایش‌های زیر از یک درخت دودویی موجود است درخت را گام به گام بسازید (مراحل ایجاد درخت نمره دارد) پیمایش میان وندی معادل با inorder و پیمایش پسوندی معادل با postorder میباشد. Inorder=gjbihadfec Postorder=jgbiaefcdh

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

4. چهار عنصر 7 و 10 و 12 و 14 را در لیست پیوندی قرار دهید (لیست مرتب است). الف- بین گره‌های 12 و 14 یک گره جدید به نام new ایجاد کنید و مقدار آن را 13 قرار دهید. ب- آخرین گره لیست را حذف کنید.

مرتب‌سازی

5. الگوریتم مرتب سازی حبابی را مختصر شرح دهید و شبه کد آن را بنویسید.

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