سوال ۶۹ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱
اهمیت
۰/۵
مسئله جستجوی عنصر x در آرایه A شامل n عنصر را در نظر بگیرید. فرض کنید اطلاع داریم که توزیع ورودی به اینصورت است که احتمال حضور عنصر x در نیمه دوم آرایه سه برابر احتمال حضور آن در نیمه اول است. همچنین برای هر نیمه، احتمال حضور در هر خانه یکسان است. تعداد مقایسه‌های الگوریتم جستجوی خطی برای یافتن عنصر x در آرایه A به‌طور متوسط چقدر است؟ (فرض کنید طول آرایه A زوج است و عدد x در آرایه وجود دارد. ضمناً جستجوی خطی از ابتدای آرایه شروع می‌شود.)
پاسخ صحیح: گزینهٔ B —
پاسخ تشریحی
Linear search from the start performs exactly comparisons to locate an element stored at position . The expected cost is therefore
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#linear-search#average-case#expected-value#non-uniform-distribution#probabilistic-analysis