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

کد درس 1115112

25 سوال تستی + 5 تشریحیرایگان

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

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

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

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

1. حاصل عبارت پسوندی زیر کدام است؟ 2,3,6,+,*,6,9,-,/

درخت‌ها

2. داده های زیر در یک Min-Heap قرار دارند. کدام گزینه صحیح است؟ (از چپ به راست بخوانید) 8-9-12-20-6-17-10

درخت‌ها

3. یک درخت باینری پر با ارتفاع ۴ موجود است. ۱۹ گره به درخت اضافه می‌کنیم. در چه شرایطی باز هم پر است؟

درخت‌ها

4. تعداد تکرار کاراکترهای زیر موجود است. مطابق با الگوریتم هافمن طول بیتی کلمه street را محاسبه کنید. حرف: t e r s a — تکرار: ۵ ۲ ۹ ۱۲ ۸

جستجو

5. یک آرایه مرتب شده به طول ۸۵۴ موجود است با استفاده از جستجوی باینری یک عنصر دلخواه را در ان جستجو می‌کنیم. حداکثر تعداد مقایسه در آرایه کدام گزینه است؟

درخت‌ها

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

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

7. عبارت میان وندی (a+b)*d-(b*c)/(++k) را در نظر بگیرید کدام گزینه معادل پسوندی این عبارت است؟

صف (Queue)

8. کدام گزاره‌ها در خصوص صف و پشته صحیح است؟ الف) ترکیب دو صف متوالی، عملکرد پشته را شبیه‌سازی می‌کند. ب) ترکیب دو پشته متوالی، عملکرد صف را شبیه‌سازی می‌کند. ج) ترکیب پشته و صف متوالی، عملکرد صف را شبیه‌سازی می‌کند.

پشته (Stack)

9. میخواهیم با استفاده از پشته، متوازن بودن یک عبارت محاسباتی را بررسی کنیم کدام گزینه درست است؟ (عبارت متوازن: عبارتی که تعداد پرانتزهای آن به صورت متناسب باشد. یعنی به ازای هر پرانتز باز، پرانتز بسته معادلی وجود داشته باشد.)

درخت‌ها

10. پیمایش پیشوندی و پسوندی یک درخت موجود است کدام گزینه درست است؟

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

11. مرتبه اجرای قطعه کد زیر چیست؟ For(j=1; j<=m; j++) For(k=1; k<=j; k++) Count=count+1;

درخت‌ها

12. داده های زیر از چپ به راست در یک درخت جستجوی باینری قرار گرفته‌اند کدام گزاره‌ها صحیح است؟ 23,19,8,35,17,14 — الف- با حذف ۱۷ ارتفاع درخت تغییر نمی‌کند. ب- با اضافه شدن ۳۳ ارتفاع درخت یک واحد اضافه می‌شود. ج- با اضافه شدن ۲۰ ارتفاع درخت تغییر نمی‌کند. د- با اضافه شدن ۱۶ ارتفاع درخت یک واحد اضافه میشود.

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

13. مرتبه اجرای الگوریتم زیر چیست؟ for(k=0; k<=n; k++){ J=k; While(j!=0) J=j/2; }

درخت‌ها

14. پیمایش postorder یک درخت دودویی debfca می‌باشد. کدام گزینه می‌تواند پیمایش preorder آن باشد؟

مرتب‌سازی

15. کدام گزینه در مورد الگوریتم‌های مرتب‌سازی زیر درست است؟

درخت‌ها

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

صف (Queue)

17. یک صف دایره‌ای به طول ۳۰ وجود دارد اگر front=22 و rear=8 باشد کدام گزینه تعداد خانه‌های پر را نشان می‌دهد؟

درخت‌ها

18. اگر تعداد گره‌های یک درخت Heap سیزده عدد باشد، کدام گزینه درخصوص این درخت صحیح است؟

درخت‌ها

19. در یک درخت دودویی پر، ۱۸ گره وجود دارد. تعداد گره‌های تک‌فرزندی این درخت، کدام گزینه است؟

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

20. کدام گزینه در مورد ماتریس پایین مثلثی با اندازه n×n درست است؟

پشته (Stack)

21. عناصر زیر از چپ به راست وارد پشته میشوند کدام گزینه نمی‌تواند خروجی پشته باشد؟ از چپ به راست بخوانید. ۵-۴-۳-۲-۱

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

22. آرایه دو بعدی A با اندازه ۸×۶ موجود است. این ارایه به صورت سطری در حافظه ذخیره میکنیم اگر اندازه هر عنصر (size) برابر با چهار بایت باشد. آدرس عنصر A[4][5] کدام است. آدرس پایه (base) برابر با صد میباشد؟

درخت‌ها

23. کدام گزینه در مورد درخت جستجوی باینری صحیح است؟

مرتب‌سازی

24. در مورد الگوریتم مرتب‌سازی حبابی، کدام گزینه درست است؟

درخت‌ها

25. داده‌های زیر از چپ به راست در یک درخت جستجوی باینری قرار می‌گیرند کدام گزینه صحیح است؟ (عمق ریشه را یک در نظر بگیرید) 17-19-8-4-21-20-14-12-9

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

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

مرتب‌سازی

1. الگوریتم مرتب سازی انتخابی را به صورت مختصر شرح دهید. الگوریتم را روی داده‌های زیر اجرا کنید. همه مراحل مرتب سازی را بنویسید. داده‌ها را از چپ به راست بخوانید. 77,33,44,11,88,22

راهنما: فصل هشت - صفحه ۲۸۷

صف (Queue)

2. صف دایره‌ای را با تمام عملگرهای آن شرح دهید. مثال بزنید.

راهنما: فصل چهار - صفحه ۱۱۰

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

3. شبه کدی بنویسید که یک گره را به لیست پیوندی اضافه کند.

راهنما: صفحه ۱۵۲ - مثال ۱-۵

درخت‌ها

4. داده‌های زیر از چپ به راست در یک درخت max-heap قرار میگیرند. الف- مراحل ساخت درخت heap را نشان دهید (با رسم درخت). ب- گره ۴۶ را از درخت حذف کنید. 45,23,46,17,35,51,28

راهنما: صفحات ۲۰۱ تا ۲۰۶

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

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

راهنما: صفحه ۶۵ مثال ۱-۲؛ مطابق با توضیحات این مثال پاسخ به دست می‌آید، تنها تغییر در این است که به جای یک ستون غیرصفر، دو ستون غیرصفر داریم.

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