نمونه سوالات ساختمان دادهها — نیمسال اول ۱۴۰۳-۱۴۰۴
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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) را در نظر بگیرید کدام گزینه معادل پسوندی این عبارت است؟
8. کدام گزارهها در خصوص صف و پشته صحیح است؟ الف) ترکیب دو صف متوالی، عملکرد پشته را شبیهسازی میکند. ب) ترکیب دو پشته متوالی، عملکرد صف را شبیهسازی میکند. ج) ترکیب پشته و صف متوالی، عملکرد صف را شبیهسازی میکند.
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 فرزندان همواره از والد کوچکتر میباشند.
17. یک صف دایرهای به طول ۳۰ وجود دارد اگر front=22 و rear=8 باشد کدام گزینه تعداد خانههای پر را نشان میدهد؟
18. اگر تعداد گرههای یک درخت Heap سیزده عدد باشد، کدام گزینه درخصوص این درخت صحیح است؟
19. در یک درخت دودویی پر، ۱۸ گره وجود دارد. تعداد گرههای تکفرزندی این درخت، کدام گزینه است؟
20. کدام گزینه در مورد ماتریس پایین مثلثی با اندازه n×n درست است؟
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
راهنما: فصل هشت - صفحه ۲۸۷
2. صف دایرهای را با تمام عملگرهای آن شرح دهید. مثال بزنید.
راهنما: فصل چهار - صفحه ۱۱۰
3. شبه کدی بنویسید که یک گره را به لیست پیوندی اضافه کند.
راهنما: صفحه ۱۵۲ - مثال ۱-۵
4. دادههای زیر از چپ به راست در یک درخت max-heap قرار میگیرند. الف- مراحل ساخت درخت heap را نشان دهید (با رسم درخت). ب- گره ۴۶ را از درخت حذف کنید. 45,23,46,17,35,51,28
راهنما: صفحات ۲۰۱ تا ۲۰۶
5. یک ماتریس مربعی با اندازه n موجود است در این ماتریس فقط دو ستون اول غیر صفر هستند و مابقی عناصر ماتریس صفر میباشند. آیا این ماتریس یک ماتریس اسپارس محسوب میشود؟ مقدار n از چه عددی بزرگتر باشد تا ذخیره ان در حافظه مقرون به صرفه باشد؟
راهنما: صفحه ۶۵ مثال ۱-۲؛ مطابق با توضیحات این مثال پاسخ به دست میآید، تنها تغییر در این است که به جای یک ستون غیرصفر، دو ستون غیرصفر داریم.