Posted: Sat Jan 26, 2008 1:04 pm Post subject: چند تست ساختمان داده
میشه یکی اینا رو برا من حل کنه؟
1-اگر عناصر یک درخت جستجوی باینری را به صورت inorder پیمایش کنیم و در داخل یک استک قرار دهیم و سپس عناصر استک را خارج کنیم و یک درخت جستجوی باینری بسازیم درخت حاصل چه درختی خواهد بود؟
1)درخت باینری تغییر نمی کند 2)درخت باینری مورب به چپ
3)درخت باینری مورب به راست 4)زیر درختهای چپ و راست درخت باینری عوض می شود
جواب اینو زده گزینه 2. در حالیکه من فک میکنم جواب گرینه 3 هست. میشه خواهش کنم بگید چرا گفته گزینه 2 درسته؟؟
2-اگر بخواهیم دو min heap به تعداد m و n را با هم merge کنیم پیچیدگی زمانی آن برابر است با :
1) m log mn 2) mlogn + nlogm 3) nlogn . logm 4) m.logn.logm
جواب گزینه 1 است. چرا؟
3-در یک درخت باینری T با n گره در چه حالتی اولین گره در پیمایش postorder مشابه آخرین گره در پیمایش inorder است؟
1)زیر درخت چپ T خالی باشد 2) دارای ارتفاع n-1 باشد
3) زیر درخت راست T خالی باشد 4)T حداکثر 3 گره داشته باشد
جواب گزینه 2 است . تو این سوال می خوام بدونم که آیا درختی با ارتفاع n-1 به غیر از درختهای مورب چپ و راست دیگه درختی هست؟ اگه اینجوری باشه که جواب نمی تونه گزینه 2 باشه . درخت مورب چپ رو امتحان کنید . پس چرا گفته 2 ؟؟؟؟؟
سلام
جواب سوال اول:
بله گزینه 2 درست است. دلیلش اینه که
- اگر شما یک درخت جستجوی دودویی رو به صورت inorder پیمایش کنید یعنی داده ها را بصورت مرتب شده صعودی به خروجی می برید. پس در مسئله شما داده ها به صورت صعودی وارد پشته می شوند. در نهایت شما بزرگترین عدد را در بالای پشته دارید و کوچکترین عدد را هم در پایین پشته. حال می خواهیم از پشته یکی یکی pop کرده و یک درخت دیگر بسازیم. با توجه به عناصر داخل گشته بزرگترین عنصر در ابتدا pop می شود و اولین گره درخت را ایجاد میکند. بعد از آن دومین عنصر حذف می شود و دومین گره درخت ساخته می شود. اما چون دومین عنصر از اولین عنصر کوچکتر است پس در درخت به زیر درخت سمت چپ اضافه می شود و عناصر به همین ترتیب از پشته حذف شده و در درخت اضافه می شود. بنابر این ما در نهایت یک درخت دودویی مورب چپ را خواهیم داشت. چون هر گره جدید که اضافه می شود از همه گره های قبلی کوچکتر خواهد بود.
خودتون هم می توانید با رسم یک شکا درخت و پشته قضیه را به خوبی متوجه شوید.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum