حل تشریحی سوال شماره 64 ساختمان داده‌ها
کنکور ارشد مهندسی کامپیوتر 1400
64.
یک ماتریس 64 در 64 داریم که درایه های ان همه 0 یا 1 هستند. میخواهیم این ماتریس را به صورت مارپیچی مرتب کنیم. یعنی اگر در انتها، سطر اول را از چپ به راست به سطر دوم از راست به چپ و .... بچسبانیم یک ارایه 4096 بیتی مرتب از 0 و 1 خواهیم داشت. ادعا میکنیم که الگوریتم زیر این کار را انجام میدهد:
بار تکرار کن.
همه سطرها را مستقلا و در جهت خود مرتب کن. یعنی سطرهای فرد را از چپ به راست، سطرهای زوج را از راست به چپ مرتب کن.
همه ستون ها را از بالا به پایین مرتب کن.
کمترین مقدار k در بدترین حالت چند است؟
1)
7
2)
32
3)
64
4)
ممکن است به ازای هیچ مقدار k ماتریس لزوما مرتب نشود.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،