المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۹:سوال ۹

سوال ۹

درخت جست‌وجوی دودویی یک درخت ریشه‌دار $n$ رأسی با ویژگی‌های زیر است:

  • رأس‌ها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند.
  • هر رأس حداکثر دو فرزند دارد که یکی ریشه‌ی زیردرخت سمت چپ و دیگری، ریشه‌ی زیردرخت سمت راست است.
  • به ازای هر رأس، شماره‌های تمام رأس‌های زیردرخت سمت چپ آن (در صورت وجود) از شماره‌ی خودش کوچک‌تر و شماره‌ی تمام رأس‌های زیردرخت سمت راست آن (در صورت وجود) از شماره‌ی خودش بزرگ‌‌تر است.

برای مثال، یک درخت جست‌وجوی دودویی در زیر کشیده‌ایم:

درخت زیر را در نظر بگیرید. در هر مرحله می‌توانیم یک یال در نظر گرفته و شماره‌ی دو رأس آن را جابه‌جا کنیم. کمینه‌ی تعداد مراحل لازم را بیابید، طوری که بتوانیم شکل را به یک درخت جست‌وجوی دودویی تبدیل کنیم.

  1. 5
  2. 6
  3. 7
  4. 8
  5. 9

پاسخ

گزینه‌ی ۲ درست است.


ابزار صفحه