ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺍﺯ ﺍﻋﺪﺍﺩ ﺩﺍﺭﯾﻢ.ﺩﺭ ﻫﺮ ﻣﺮﺣﻠﻪ میﺗﻮﺍﻥ یکی ﺍﺯ ﺳﻪ ﻋﻤﻠﯿﺎﺕ ﺯﯾﺮ ﺭﺍ ﺭﻭﯼ ﺩﻧﺒﺎﻟﻪ ﺍﻧﺠﺎﻡ ﺩﺍﺩ:

• ﺩﺳﺘﻮﺭ copy: ﺑﺎ ﺩﺳﺘﻮﺭ copy(i) یک ﻋﺪﺩ ﺑﺎ ﻣﻘﺪﺍﺭ i ﺍﻣﯿﻦ ﻋﻀﻮ ﺩﻧﺒﺎﻟﻪ ﺑﻪ ﺍﻧﺘﻬﺎﯼ ﺩﻧﺒﺎﻟﻪ ﺍﺿﺎﻓﻪ می‌‌ﺷﻮﺩ.ﺑﺮﺍﯼ ﻣﺜﺎﻝ ﺍﮔﺮ ﺩﻧﺒﺎﻟﻪﯼ ⟨۳,۷,۲,۱⟩ ﺭﺍ ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ، ﺑﺎ ﺩﺳﺘﻮﺭ (۲)copy ﺑﻪ ﺩﻧﺒﺎﻟﻪﯼ ⟨۳,۷,۲,۱,۷⟩ می‌رﺳﯿﻢ.

• ﺩﺳﺘﻮﺭ delete: ﺑﺎ ﺩﺳﺘﻮﺭ delete(i) ﻋﺪﺩ i ﺍﻡ ﺩﻧﺒﺎﻟﻪ ﺣﺬﻑ میﺷﻮﺩ.ﺑﺮﺍﯼ ﻣﺜﺎﻝ ﺍﮔﺮ ﺩﻧﺒﺎﻟﻪﯼ ⟨۴,۱,۹,۲,۵⟩ ﺭﺍ ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ، ﺑﺎ ﺩﺳﺘﻮﺭ (۲)delete ﺑﻪ ﺩﻧﺒﺎﻟﻪﯼ ⟨۴,۹,۲,۵⟩ می‌رﺳﯿﻢ.

• ﺩﺳﺘﻮﺭ merge: ﺑﺎ ﺩﺳﺘﻮﺭ $merge(i, j)$ ﻋﺪﺩ jﺍﻡ ﺩﻧﺒﺎﻟﻪ ﺣﺬﻑ ﺷﺪﻩ ﻭ ﻣﻘﺪﺍﺭ ﺁﻥ ﺑﻪ ﻋﺪﺩ i ﺍﻡ ﺩﻧﺒﺎﻟﻪ ﺍﺿﺎﻓﻪ میﺷﻮﺩ. ﺩﺭ ﺍﯾﻦ ﺩﺳﺘﻮﺭ ﺑﺎﯾﺪ $i < j$ ﺑﺎﺷﺪ.ﺑﺮﺍﯼ ﻣﺜﺎﻝ ﺍﮔﺮ ﺩﻧﺒﺎﻟﻪﯼ ⟨۴,۱,۹,۲,۵⟩ ﺭﺍ ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ، ﺑﺎ ﺩﺳﺘﻮﺭ $merge(2, 4)$ به دنباله ⟨۴,۳,۹,۵⟩ می‌رسیم.

ﺍﺟﺮﺍﯼ ﻫﺮ یک ﺍﺯ ﺩﺳﺘﻮﺭﻫﺎﯼ ﺑﺎﻻ یک ﻭﺍﺣﺪ ﻫﺰﯾﻨﻪ ﺩﺍﺭﺩ. ﻣﺘﻐﯿﺮ size ﺩﺭ ﻫﺮ ﻟﺤﻈﻪ ﺗﻌﺪﺍﺩ ﻋﻀﻮﻫﺎﯼ ﺩﻧﺒﺎﻟﻪ ﺭﺍ ﻧﺸﺎﻥ می دهد. ﺑﺮﺍﯼ ﻣﺜﺎﻝ ﻭقتی ﺩﻧﺒﺎﻟﻪﯼ ⟨۳,۶,۱۰,۱⟩ ﺭﺍ ﺩﺍﺭﯾﻢ، size=۴ ﺍﺳﺖ.

ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ $⟨۱,۲,...,۱۰۰⟩$ ﺭﺍ ﺩﺍﺭﯾﻢ.ﭘﺲ ﺍﺯ ﺍﺟﺮﺍﯼ ﺍلگوریتم ﺯﯾﺮ، ﻣﺠﻤﻮﻉ ﺍﻋﻀﺎﯼ ﺩﻧﺒﺎﻟﻪ ﭼﻪ ﺧﻮﺍﻫﺪ ﺑﻮﺩ؟

• $1$. اگر size < ۳ است، به گام ۵ برو.
• $2$. delete(size-۱)
• $3$. merge(size-۱, size)
• $4$. به گام ۱ برو.
• $5$. پایان.

1. ۲۵۰۱
2. ۵۰۵۱
3. ۲۵۵۰
4. ۲۵۵۱
5. ۴۹۵۱

ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ $⟨۰,۱⟩$ ﺭﺍ ﺩﺍﺭﯾﻢ.ﭘﺲ ﺍﺯ ﺍﺟﺮﺍﯼ ﺍلگوریتم ﺯﯾﺮ، عنصر اخر دنباله چه خواهد بود؟
به ازای i از ۱ تا ۱۰ انجام بده:

• $1$. copy(size-۱)
• $2$. copy(size-۱)
• $3$. merge(size-۱, size)

1. ۱۰۲۴
2. ۱۴۴
3. ۵۱۲
4. ۲۵۶
5. ۸۹

ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ $⟨۱⟩$ ﺭﺍ ﺩﺍﺭﯾﻢ و می‌خواهیم با یک برنامه به دنباله $⟨۱,۲,...,۱۰۰⟩$ برسیم. کمینه هزینه (تعداد اجرا‌های دستور‌های) مورد نیاز چیست؟

1. ۲۴۰
2. ۳۰۰
3. ۹۹
4. ۱۹۸
5. ۲۹۷

• سوال قبل