نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۴-۹۵
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
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
6. مقادیر a,b,c به ترتیب وارد پشته می شوند. به چند طریق این مقادیر را می توان از پشته خارج کرد؟
7. یک آرایه مربعی n×n را می خواهیم در یک آرایه یک بعدی B ذخیره کنیم. آدرس [i][j] از آرایه A در آرایه بعدی B کدام گزینه خواهد بود؟
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 که در آن فقط عناصر قطر اصلی مخالف صفر می باشند را به اسپارس تبدیل می کنیم. محاسبه کنید اندازه ماتریس چند باشد تا ذخیره آن به صورت اسپارس مقرون به صرفه باشد؟
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