پاسخ تشریحی سوالات ساختمان داده -دکتری ۹۲
سوال ۹: گزینه ۳ صحیح است.
حداقل : (n/2(logn
حداکثر: nlogn-n+1
که به ترتیب معادل ۸۰ و ۱۲۹ میشود.
*******************************************************************************************************
سوال ۱۰: گزینه هیچ کدام!
مشخص نیست منظورش اول ۱ هست یا اول ۴ برای این پنج تا عدد! چون اصولاً وقتی با ویرگول و «و» می نویسن یعنی راست به چپ. و این که میگه چپ به راست خیلی عجیبه.
به هر حال با فرض این که اول ۴ و آخر ۱ درج بشه این مراحل هست:
۱/ [Add 4: [4
۲/ [Add 9: [4, 9
۳/ {Add 3: [4, 9, 3] => [3, 9, 4] {one swap of 3 with 4
۴/ {Add 7: [3, 9, 4, 7] => [3, 7, 4, 9] {one swap of 7 with 9
۵/ {Add 1: [3, 7, 4, 9, 1] => [3, 1, 4, 9, 7] => [1, 3, 4, 9, 7] {two swap of 1 with 7, then with 3
۶/ {Remove 1: [1, 3, 4, 9, 7] ~~{one swap}~~> [7, 3, 4, 9] => [3, 7, 4, 9] {one swap of 3 with 7
۷/ {Remove 3: [3, 7, 4, 9] ~~{one swap}~~> [9, 7, 4] => [4, 7, 9] {one swap of 4 with 9
۸/ {Remove 4: [4, 7, 9] ~~{one swap}~~> [9, 7] => [7, 9] {one swap of 7 with 9
۹/ [Remove 7: [7, 9] ~~{one swap}~~> [9
۱۰/ [Remove 9: [9] ~~~~> []
جمع اینا میشه ۴ تا جابجایی موقع اضافه کردن. ۴ تا موقع حذف کردن و آوردن اخرین عنصر به جای عنصر اول محذوف. ۳ تا هم موقع هیپیفای کردن نهایی. یعنی میشه ۱۱ تا. که توی گزینهها نیست.
حالا اگه اون آرایه رو برعکس بگیریم (یعنی فرض کنیم منظور شروع از ۱ و انتها در ۴ باشه) قضیه این شکلی میشه:
۱/ [Add 1: [1
۲/ [Add 7: [1, 7
۳/ [Add 3: [1, 7, 3
۴/ [Add 9: [1, 7, 3, 9
۵/ {Add 4: [1, 7, 3, 9, 4] => [1, 4, 3, 9, 7] {one swap of 4 with 7
۶/ {Remove 1: [1, 4, 3, 9, 7] ~~{one swap}~~> [7, 4, 3, 9] => [3, 4, 7, 9] {one swap of 3 with 7
۷/ {Remove 3: [3, 4, 7, 9] ~~{one swap}~~> [9, 4, 7] => [4, 9, 7] {one swap of 4 with 9
۸/ [Remove 4: [4, 9, 7] ~~{one swap}~~> [7, 9
۹/ [Remove 7: [7, 9] ~~{one swap}~~> [9
۱۰/ [Remove 9: [9 ~~~~> []
اینم شده یکی موقع اضافه کردن. ۴ تا موقع حذف کردن. دو تا هم هیپیفای. مجموعش میشه ۷ تا. که بازم توی گزینهها نیست.
|