سوال 3
حل تشریحی سوال شماره 3 ساختمان داده ها و طراحی الگوریتم ها
کنکور دکتری مهندسی کامپیوتر 1400
3.
آرایه ای شامل n عدد متمایز داده شده است میخواهیم از روی این اعداد یک درخت دودویی بسازیم با این خاصیت که به ازای هر رأس درخت ساخته شده این خصوصیت را نیز داشته باشد که پیمایش میان ترتیب آن دقیقاً معادل ترتیب عناصر در آرایه شود کدام گزاره درست است؟
1)
چنین درختی لزوماً به ازای هر آرایه وجود دارد، اما یکتا نیست.
2)
چنین درختی لزوماً به ازای هر آرایه شامل n عدد متمایز وجود ندارد.
3)
بهترین زمان برای ساخت چنین درختی از روی یک آرایه (n)O است.
4)
بهترین زمان برای ساخت چنین درختی از روی یک آرایه (nlogn)O است.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،