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

کد درس 1115112

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

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

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

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

جستجو

1. فرض کنید یک ارایه 500 عنصری را در اختیار داریم. زمان اجرای بدترین حالت برای پیداکردن عنصر x در آرایه A با استفاده از جستجوی دودویی کدام گزینه می باشد؟

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

2. می خواهیم یک ماتریس مربعی n×n سه قطری را در یک آرایه خطی B ذخیره کنیم. طول آرایه B چند باشد؟

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

3. در یک آرایه مربعی با اندازه n، برای آدرس عنصر، عدد سطری و ستون با هم برابر است؟

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

4. در یک آرایه nxm که n=4 و m=4 است، آدرس عنصر [2][2] به صورت سطری کدام گزینه است؟ size=4Byte, base=0

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

5. در یک آرایه n×m که n=4 و m=4 است، آدرس عنصر [1][3] را به صورت ستونی محاسبه کنید؟ size=4Byte, base=0

پشته (Stack)

6. مقادیر a,b,c به ترتیب وارد پشته می شوند. به چند طریق این مقادیر را می توان از پشته خارج کرد؟

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

7. یک آرایه مربعی n×n را می خواهیم در یک آرایه یک بعدی B ذخیره کنیم. آدرس [i][j] از آرایه A در آرایه بعدی B کدام گزینه خواهد بود؟

صف (Queue)

8. کدام گزینه در مورد صف دایره ای صحیح می باشد؟

مرتب‌سازی

9. در کدام الگوریتم پیچیدگی زمانی در بدترین- بهترین و حالت متوسط O(n^2) می باشد؟

مرتب‌سازی

10. کدام الگوریتم داده های عددی را بر حسب ارقام مرتب می کند؟

درخت‌ها

11. با 4 گره، چند درخت دودویی متمایز می توان ساخت؟

درخت‌ها

12. کدام گزینه در باره درخت درست می باشد؟

درخت‌ها

13. کدام گزینه در مورد heap صحیح می باشد؟

درخت‌ها

14. یک درخت دودویی کامل با 100 گره موجود است. کدام گزینه درست می باشد؟

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

15. کدام گزینه اولین گره لیست پیوندی را حذف می کند؟

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

16. حاصل عبارت زیر کدام گزینه می باشد؟ 50,20,+,-10,/,7,+,2,3,4,8,+,-,+,+

درخت‌ها

17. داده های زیر را با الگوریتم هافمن رمزگذاری کرده ایم. طول کلمه blue کدام گزینه می باشد؟ b=4 e=10 a=2 u=8 l=5

درخت‌ها

18. کدام درخت را اگر به روش inorder پیمایش کنیم، حاصل یک لیست مرتب می باشد؟

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

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

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

20. خروجی الگوریتم زیر کدام گزینه می باشد؟ int f(int n){ if(n==0) return 0; return(n+f(n-1)); }

درخت‌ها

21. اگر acdfbeg پیمایش پیشوندی یک درخت دودویی باشد، کدام یک از دنباله های زیر نمی تواند پیمایش inorder آن درخت باشد؟

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

22. درج و حذف از یک لیست خطی یکطرفه در صورتی که آدرس گره قبلی را داشته باشیم، از چه مرتبه ای می باشد؟

درخت‌ها

23. در یک درخت جستجوی باینری 16 عنصر ذخیره شده است. برای جستجوی یک عنصر دلخواه حداکثر چند مقایسه مورد نیاز است؟

مرتب‌سازی

24. برای مرتب سازی آرایه 12 عنصری با روش انتخابی، اگر آرایه در ابتدا به صورت معکوس مرتب باشد، چند مقایسه و چند تعویض نیاز می باشد؟

مرتب‌سازی

25. کدام الگوریتم مرتب سازی، یک آرایه تقریبا مرتب شده را سریعتر مرتب می نماید؟

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

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

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

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

صف (Queue)

2. صف خطی و صف دایره ای را شرح دهید، و همه عملگرهای آنها را توضیح دهید.

مرتب‌سازی

3. الگوریتم مرتب سازی درجی را شرح داده و با استفاده از آن داده های زیر را مرتب کنید. از چپ به راست بخوانید. 75,70,65,84,98,78,100,93,55,81,68

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

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

درخت‌ها

5. الف- داده های زیر را از چپ به راست در یک درخت جستجوی باینری قرار دهید. درخت را رسم کنید. 12,8,4,25,7,2,9,14,13,17 — ب- پیمایش های زیر از یک درخت موجود است. درخت را رسم کنید. میانوندی: gfhkdlawrqpz — پسوندی: fghdalpqrzwk

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