سوالهای امتحان داده‌های حجیم (میان‌ترم)

۱- با استفاده از روش لگاریتمی یک سری B-tree بسازید که کافی است فقط عمل درج را پشتیبانی کند.

۲- سوال جستجوی بازه‌ی تمرین Arge

۳- اگر b<B و m<M باشد در Buffer-tree، تعداد IO جستجو و درج چقدر می‌شود؟ اگر روی هر بافر یک B-tree بسازیم و m=B^2 باشد، زمان جستجو و درج چقدر می‌شود؟

۴- می‌خواهیم یک لیست پیوندی بسازیم که زمان درج در آن O(1) باشد و حافظه‌ی آن 4/3ceil{N/B} باشد. اگر بخواهیم فضا ۱+اپسیلون برابر N/B باشد و زمان کوئری یک بر اپسیلون باشد باید چه کار کنیم؟

۵- تقاطع‌های تعدادی پاره‌خط افقی با تعدادی خط عمودی را پیدا کنید. اگر به جای خط، پاره‌خط عمودی داشته باشیم چطور؟