در صورتی که آرایه مورد جستجو در جستجوی دودوی به صورت 7و6و5و4و3و2و1و0و1- باشد، متوسط تعداد مقایسه ها برای جستجوی موفق چیست؟
الف9/27 ب9/25 ج9/31 د هیچکدام
ببخشید اینجوری نوشتم اینها رو به صورت کسری فرض کنید. باتشکر
Printable View
در صورتی که آرایه مورد جستجو در جستجوی دودوی به صورت 7و6و5و4و3و2و1و0و1- باشد، متوسط تعداد مقایسه ها برای جستجوی موفق چیست؟
الف9/27 ب9/25 ج9/31 د هیچکدام
ببخشید اینجوری نوشتم اینها رو به صورت کسری فرض کنید. باتشکر
نقل قول:
نوشته شده توسط lvenoos
25/9 (ب) صحیح هست.
از اونجا که یک آرایه مرتب داریم درخت جستجوی دودیی کامل رو میشه براحتی تشکیل داد.
در نتیجه برای عناصر سطر اول یک مقایسه، برای عناصر سطر دوم 2 مقایسه، سطر سوم 3 مقایسه و ... لازم هست. با جمع تعداد مقایسه ها تقسیم اون بر تعداد عناصر(در اینجا 9) میانگین مقایسه ها بدست میاد.