ساختمان داده‌هاData Structures

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

سوالات · 13

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

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

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

فرض کنید یک لیست پیوندی یک‌طرفه از n گره داریم و شما می‌خواهید گره‌ای را که در موقعیت 3n/4 قرار گرفته پیدا کنید اما مقدار n را نمی‌دانیم. فرض کنید n مضربی از ۴ است. کدام‌یک از گزینه‌ها ما را به نتیجه…

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

گوییم 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)…

ساختمان داده‌هامتوسطجست‌وجو در درخت با پرس‌وجوی جهت همسایه (جست‌وجوی مرکزوار)کنکور ارشد مهندسی کامپیوتر ۱۴۰۰ — سؤال ۶۸

یک درخت ۱۵ رأسی داریم که یکی از رأس‌های آن به‌عنوان هدف درنظر گرفته شده است، اما ما از آن اطلاع نداریم. در هر پرسمان می‌توانیم یک رأس را انتخاب کنیم و متوجه شویم آیا این رأس هدف است یا نه و اگر نیست…

ساختمان داده‌هاآساندرخت‌های جست‌وجوی دودویی: چرخش و متوازن‌سازیکنکور ارشد مهندسی کامپیوتر ۱۴۰۵ — سؤال ۶۱

‏- insert(x): یک عنصر x به درخت اضافه می‌کند. Delete(x): یک عنصر x را از درخت حذف می‌کند. درخت همیشه متوازن باقی می‌ماند (یعنی بعد از هر عملیات ویژگی درخت AVL برقرار است) هزینه سرشکن هر عملیات Insert…

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

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

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

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