نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۴۰۳-۱۴۰۴
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. کدام گزینه تعریف صحیحی از الگوریتم ارائه میدهد؟
2. پیچیدگی زمانی الگوریتم جستجوی خطی در بدترین حالت چیست؟
3. کدام ساختار داده از اصل LIFO پیروی میکند؟
4. عمل Push در پشته چه کاری انجام میدهد؟
5. پیچیدگی الگوریتم جستجوی دودویی در آرایه مرتب، از چه مرتبهای است؟
6. کدام گزینه ویژگی اصلی صف (Queue) را توصیف میکند؟
7. در پشته، عمل Pop چه کاری انجام میدهد؟
8. کدام روش برای حل روابط بازگشتی استفاده میشود؟
9. ماتریس اسپارس چیست؟
10. اگر T(n) = 3n^2 + 2n + 1 باشد، نماد O بزرگ آن چیست؟
11. برای ارزیابی عبارات پسوندی (POSTFIX)، استفاده از کدام نوع ساختمان داده، مفیدتر است؟
12. کدام گزینه نمایش صحیح عبارت (A+B)*C به صورت پسوندی است؟
13. در پیادهسازی صف، اشارهگر front به ...... اشاره دارد و موقع ...... به کار میرود.
14. کدام روش برای نمایش ماتریس اسپارس مناسب است؟
15. فرض کنید تعدادی عنصر در یک پشته درج شدهاند. در صورتی که بخواهیم محتویات آن را بدون حذف عنصر بالایی از پشته فقط مشاهده نمائیم، کدام روش میتواند جوابگو باشد؟
16. چند درخت جستجوی دودویی متفاوت با ۳ مقدار میتوان ساخت؟
17. فرض کنید درخت هافمن برای کاراکترهای A تا H با وزنهای زیر ساخته شده و کدهای زیر به هریک از کاراکترها استخراج شده است. تعداد بیتهای لازم برای ذخیرهسازی کل این کاراکترها چند بیت خواهد بود؟ عنصر: A B C D E F G H — وزن: 22 5 11 19 2 11 25 5
18. کدام یک از الگوریتمهای مرتبسازی زیر در همه حالات (بهترین، متوسط، بدترین) پیچیدگی زمانی O(nlogn) دارد؟
19. کدام گزینه صحیح است؟ الف- با داشتن پیمایش میان ترتیبی و پس نرتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت. ب- با داشتن پیمایش پیش ترتیبی و پس نرتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت. ج- با داشتن پیمایش پیش ترتیبی و میان ترتیبی یک درخت دودویی را می توان آن را به صورت یکتا ساخت.
20. خروجی تابع زیر با فرض اینکه T اشارهگر به گره رأس یک درخت دودویی جستجو باشد چیست؟ (نوع داده Tree، یک درخت جستجوی دودویی است) int what(Tree T){ Tree P; P=T; while(P->left) P=P->left; return P->data; }
21. اگر بخواهیم یک گراف با n راس و m یال را به صورت یک ماتریس مجاورت ذخیره نمائیم، از یک ماتریس با چه ابعادی باید استفاده خواهیم کرد؟
22. معادل میانوندی عبارت پیشوندی (Prefix) روبرو چیست؟ / × + a b c − a b
23. در پیاده سازی صف حلقوی، یک خانه را حتماً باید خالی نگه داریم، دلیل این کار چیست؟
24. تابع زیر بر روی یک لیست یکطرفه چه میکند؟ int Test(List *L){ List *x; T=0; if(L){ x:=L; while(x){ T=T+1; x=x->link; } } return T; }
25. برای حذف گرهی میانی در یک لیست پیوندی دوطرفه، چند تغییر آدرس لازم است؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. تابعی بنویسید که محتویات لیست یک طرفه را به روش بازگشتی نشان دهد.
راهنما: صفحه ۳۰
2. فرض کنید پیمایشهای inorder و preorder یک درخت دودویی به صورت زیر باشد، درخت دودویی موردنظر را رسم کنید. inorder: D B H E A I F J C G — preorder: A B D E H C F I J G
راهنما: صفحه ۲۸
3. درخت جستجوی دودویی حاصل از درج اعداد زیر را رسم کنید: 34, 42, 21, 9, 18, 38, 39, 37, 14, 10, 12, 16
راهنما: صفحه ۷۵
4. توابع مربوط به درج و حذف از پشته را به طور کامل بنویسید.
راهنما: پاسخ در فصل ۳ کتاب درسی، توابع push و pop
5. یک آرایه مرتب n عنصری را در نظر گرفته با تابعی به نام Search، عنصر x را در آن جستجو نمائید. سپس زمان آن را تحلیل نمائید (جستجوی دودویی مدنظر است).
راهنما: صفحه ۴۵