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

ADT Design & Data-Structure Selection

طراحی نوع دادهٔ انتزاعی (ADT) و انتخاب ساختمان دادهٔ مناسب.

ساختمان داده‌ها کنکور ارشد مهندسی کامپیوتر

اهمیت

۰/۵

کارت‌ها · 1

Choosing a Data Structure: BST vs Hash vs Heap

Match each required operation to the cheapest structure that supports it; when an ADT mixes order queries with lookup-by-identity, combine a balanced BST (or heap) with a hash index instead of forcing one structure to do everything.

abstract-data-typedata-structure-selectionbalanced-bstorder-statistics

سوالات · 9

ساختمان داده‌هاسختطراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۴ — سؤال ۶۵

فرض کنید یک ساختار داده جدید به نام لیست اولویت‌دار پویا (Dynamic Priority List) دارید. این ساختار داده دارای ساختاری از اعمال زیر است که باید به‌طور کارا پشتیبانی شوند. اعمالی که روی آن باید به‌طور…

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۳ — سؤال ۵۶

گوییم H = h : U → ∘,۱,۲,…,m-۱ h تابع است یک خانواده از درهم‌سازهای سراسری (universal) است، هرگاه برای هر h ∈ H و K_1, K_2 ∈ U داشته باشیم Pr(h(K_1) = h(K_2)) ≤ ۱/m . اگر مجموعهٔ H که فقط متشکل از…

ساختمان داده‌هاسختطراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۱ — سؤال ۶۴

اعداد یک تا ۱۲۷ در یک هرم بیشینه که به‌صورت یک درخت دودویی کامل با ارتفاع ۶ پیاده‌سازی شده، قرار گرفته‌اند. حداکثر تعداد برگ با مقدار بیشتر از ۱۰۰ در این درخت چقدر می‌تواند باشد؟

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۱ — سؤال ۶۵

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

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۱ — سؤال ۶۷

فرض کنید یک درخت دودویی جستجو بر روی n عدد حقیقی متمایز با ارتفاع O(log n) در اختیار داریم. چه تعداد از پرسش‌های زیر را بدون پیش‌پردازش و اطلاعات اضافی می‌توان در O(log n) پاسخ داد؟ (در هر گره صرفاً…

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۰ — سؤال ۶۱

خانوادهٔ H = h_۱, h_۲ از توابع درهم‌ساز را درنظر بگیرید که h_i : ۱, ۲, …, n → ۰, ۱ . برای آن که این خانواده یک خانوادهٔ درهم‌ساز سراسری باشد، n حداکثر چند می‌تواند باشد؟ خانوادهٔ توابع Π سراسری است…

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۰ — سؤال ۶۳

چند مورد از داده ساختارهای زیر نمی‌شود ساخت که اعمال گفته شده را در زمان خواسته شده انجام دهد؟ عمل‌های Push ، Pop ، FindMin و FindMax را در Θ(1) انجام دهد. عمل‌های Push ، Pop و DeleteMin را در Θ(1)…

ساختمان داده‌هامتوسططراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۵ — سؤال ۶۴

فرض کنید آرایه A = [a_۱, a_۲, …, a_۲۰] یک min-heap دودویی شامل ۲۰ عدد صحیح مجزا را نشان می‌دهد. چهارمین کوچک‌ترین عنصر در کدام‌یک از مکان‌های زیر می‌تواند قرار داشته باشد؟ (کامل‌ترین پاسخ را انتخاب…

ساختمان داده‌هاسختطراحی نوع دادهٔ انتزاعی و انتخاب ساختمان دادهکنکور ارشد مهندسی کامپیوتر ۱۴۰۵ — سؤال ۶۵

یک جدول درهم‌سازی با n خانه (اسلات) را در نظر بگیرید که در آن تصادم‌ها با روش زنجیره‌ای حل می‌شوند. فرض کنید n کلید در جدول وارد می‌کنیم، به‌طوری‌که هر کلید به‌طور مساوی احتمال دارد به هر خانه…