سوال 11
حل تشریحی سوال شماره 11 ساختمان داده ها و طراحی الگوریتم ها
کنکور دکتری مهندسی کامپیوتر 1404
11.
فرض کنید که یک صف دوتایی (Deque) با استفاده از یک لیست پیوندی دوطرفه پیاده سازی شده است و می توانید هم از ابتدا و هم از انتهای صف عملیات enqueue و dequeue را انجام دهید. کدام مورد زیر در خصوص پیچیدگی زمانی این عملیات ها درست است؟
1)
عملیات enqueue و dequeue در هر دو سمت صف (ابتدا و انتها)، دارای پیچیدگی زمانی O(n) است.
2)
فقط عملیات dequeue از ابتدای صف دارای پیچیدگی زمانی O(1) است، در حالی که سایر عملیاتها پیچیدگی زمانی O(n) دارند.
3)
تمامی عملیات های enqueue و dequeue در صف دوتایی دارای پیچیدگی زمانی O(1) هستند، چه از ابتدای صف و چه از انتهای صف.
4)
عملیات enqueue در انتهای صف و عملیات dequeue از ابتدای صف، دارای پیچیدگی زمانی O(1) هستند، اما عملیات dequeue از انتهای صف، دارای پیچیدگی O(n) است.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،