فرض کنید سه آرایه A و B و C هر کدام شامل n عدد است. عناصر داخل آرایهها متمایز هستند. آرایهٔ A بهصورت صعودی و آرایهٔ B بهصورت نزولی مرتب است. اگر بخواهیم آرایهٔ D را بسازیم که شامل عناصر (A∪ B)∩ C باشد و بهصورت صعودی مرتب شده و عضو تکراری نیز نداشته باشد، بهترین پیچیدگی زمانی ممکن برای این کار کدام مورد است؟ (توجه: ممکن است عناصری در دو یا سه آرایه باشند.)

سوال ۶۵ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان داده

اهمیت

۰/۵

فرض کنید سه آرایه $A$ و $B$ و $C$ هر کدام شامل n عدد است. عناصر داخل آرایه‌ها متمایز هستند. آرایهٔ $A$ به‌صورت صعودی و آرایهٔ $B$ به‌صورت نزولی مرتب است. اگر بخواهیم آرایهٔ $D$ را بسازیم که شامل عناصر $(A\cup B)\cap C$ باشد و به‌صورت صعودی مرتب شده و عضو تکراری نیز نداشته باشد، بهترین پیچیدگی زمانی ممکن برای این کار کدام مورد است؟ (توجه: ممکن است عناصری در دو یا سه آرایه باشند.)

#set-operations#sorted-merge#hash-table#union-intersection#linear-time#data-structure-selection