ساختمان داده

حل تشریحی سوالات ساختمان داده - کنکور دکتری مهندسی کامپیوتر 1398

منوی آزمون (درس ها)

درباره آزمون ساختمان داده(10 سوال)طراحی الگوریتم(10 سوال)سیستم‌های عامل پیشرفته(15 سوال)پایگاه داده پیشرفته(10 سوال)

سوالات ساختمان داده

10 سوال

یک ماتریس دو بعدی $n \times n$ از اعداد داده شده که اعداد هر سطر و هر ستون آن مرتب شده است. به ازای عدد داده شده x جست و جوی x در این ماتریس در چه زمانی امکان پذیر است؟

O(n)

O(log n)

$O (lo g^{2} n)$

O(n log n)

مشاهده پاسخ ها

می خواهیم بزرگ ترین زیر دنباله مشترک دو دنباله $a_{1}, \dots, a_{n}$ و $b_{1}, \dots, b_{m}$ را محاسبه کنیم. فرض کنید L(i,j) برابر طول بزرگترین زیر دنباله مشترک $a_{1}, \dots, a_{n}$ و $b_{1}, \dots, b_{m}$ باشد. کدام یک از تعاریف بازگشتی زیر درست است؟

الف) $L (n, m) = max (L (n - 1, m)), L (n, m - 1), L (n - 1, m - 1 + 1 i f a_{n} = b_{m})$

ب) $L (n, m) = max (L (n - 1, m), L (n - 1, k - 1) + 1)$ که K برابر بزرگ‌ترین عددی است که $a_{n} = b_{k}$ (در صورت عدم وجود خواهد بود)

فرض کنید $L (i, 0) = L (0, i) = 0$ و $L (i, - 1) = - 1$ برای هر $i \geq 0$

فقط الف

فقط ب

الف و ب

هیچ یک از الف و ب

مشاهده پاسخ ها

فرض کنید یک آرایه دوبعدی $m \times n$ در اختیار داریم که هر ردیف آن مرتب شده است. فرض کنید همه اعداد متمایز هستند میخواهیم امین عدد در آرایه را پیدا کنیم در چه زمانی این کار امکان پذیر است؟

O(m.n)

O(logn logm)

O(logn + logm)

O(m(logn + logm))

مشاهده پاسخ ها

اگر ظرفیت همۀ یال‌ها در یک شبکه برابر C باشد، زمان اجرای الگوریتم فورد - فالكرسون برای محاسبه شار بیشینه از مبدا s و به مقصد t در بدترین حالت کدام مورد خواهد بود؟

(فرض کنید تعداد رئوس و یالهای گراف به ترتیب n و m هستند و درجه خروجی s برابر k باشد. همچنین فرض کنید در هر مرحله الگوریتم بیشترین شار ممکن را از مسیر انتخاب شده عبور می‌دهد.

O(kC+m+n)

O(kC(m+n))

O(C(m+n))

O(k(m+n))

مشاهده پاسخ ها

فرض کنید ۱۳۹۷ نقطه متمایز روی محور اعداد حقیقی داده شده است. می‌خواهیم این ۱۳۹۷ نقطه را طوری رنگ آمیزی کنیم که به ازای هر بازه [a,b] روی محور اعداد حقیقی از بین نقاطی که در این بازه قرار گرفته اند حداقل یک نقطه وجود داشته باشد که رنگ آن با بقیه نقاط داخل بازه متفاوت باشد حداقل چند رنگ برای این کار نیاز است؟

1397

مشاهده پاسخ ها

فرض کنید یک B-tree داریم با n برگ که درجه هر گره حداقل logn و حداکثر $2 lo g n - 1$ است. هزینه جست وجوی یک عدد در این درخت کدام است؟ (فرض کنید کلیدها داخل هر گره میانی در یک لیست پیوندی یک سویه ذخیره شده‌اند.)

O(log n)

O(log n log log n)

$O (lo g n lo g^{2} lo g n)$

$O (lo g^{2} n / lo g lo g n)$

مشاهده پاسخ ها

فرض کنید یک گراف وزن دار همبند داده شده است که وزن یالها متمایز است یک یال را امن گوییم اگر در هیچ دوری حضور نداشته باشد و یک یال را خطرناک گوییم اگر سنگینترین یال در یک دور باشد. کدام یک از دو گزاره زیر درست است؟

الف) هر یال امن عضو درخت پوشای کمینه است.

ب) هر یال خطرناک عضو درخت پوشای کمینه نیست.

الف

الف و ب

هیچ یک از الف و ب

مشاهده پاسخ ها

گراف جهت‌دار G با n رأس و nیال داده شده است. هر رأس i از گراف ارزشی به اندازهٔ $V_{i}$ دارد به ازای هر رأس i از گراف، با ارزش‌ترین رأسی که از رأس i قابل دسترسی است را $W_{i}$ مینامیم میخواهیم تمام $W_{i}$ ها را به ازای i از ۱ تا n محاسبه کنیم. این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید.)

$O (m + n)$

$O (m + n^{2})$

$O (n (m + n))$

$O (m + n lo g n)$

مشاهده پاسخ ها

یک درخت جست وجوی دودویی با n گره داریم که به علت نویز اعداد ذخیره شده در برخی از گره های آن تغییر کرده است تنها عملی که میتوان برای اصلاح این درخت انجام داد جابه جا کردن مقادیر ذخیره شده در یک گره و یکی از فرزندان آن است. کمینه تعداد اعمال مورد نیاز برای تبدیل درخت به یک درخت دودویی جست وجو در بدترین حالت کدام است؟ (دقت کنید که درخت اولیه لزوماً متوازن نیست.)

O(n)

$O (n^{2})$

O(nlogn)

O(nloglogn)

مشاهده پاسخ ها

10.

زوج‌های مرتب زیر را در نظر بگیرید:

(10,A), (2,B), (5, C), (7, D), (8, E), (1, F), (4,G)

فرض کنید درختی داریم که براساس مؤلفه‌های اول این زوج‌ها یک هرم ،کمینه و براساس مؤلفه های دوم یک درخت جست وجوی دودویی است ارتفاع این درخت کدام است؟

مشاهده پاسخ ها