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

خانواده $H=\left\{h_1,h_2\right\}$ از توابع درهم‌ساز را در نظر بگیرید که $h_i:\left\{1,2,....n\right\}\to \left\{0,1\right\}$. برای انکه این خانواده یک خانواده درهم ساز سراسری باشد، n حداکثر چند میتواند باشد؟ خانواده توابع$II$ سراسری است، اگر و فقط اگر به ازای هر دو مقدار u و v داشته باشیم: $P{r}_{h\in H}\left[h\left(u\right)=h\left(u\right)\right]\le \frac{1}{m}$ که m اندازه جدول درهم سازی است.

اعداد 10,.....1,2 را به ترتیب از چپ به راست در یک درخت دودویی جستجو که در اول کار تهی است درج میکنیم. بعد از درج همه عناصر میخواهیم درخت حاصل را به درخت دودویی جستجو با ارتفاع 3 تبدیل کنیم. برای اینکار تنها مجاز به استفاده از عمل چرخش (به چپ یا راست) هستیم. با حداقل چندبار چرخش میتوان اینکار را انجام داد؟

(منظور از چرخش همان عملیات متعارفی است که برای متوازن سازی درخت های دودویی جستجتو استفاده میشود)

چند مورد از داده ساختارهای زیر را نمی‌شود ساخت که اعمال گفته شده را در زمان خواسته شده انجام دهد؟

-عمل‌های FindMin, Pop, Push و FindMax را در $\Theta \left(1\right)$ انجام دهد.

-عمل‌های Pop, Push و DeletMin را در$\Theta \left(1\right)$ انجام دهد.

-عمل‌های Pop, Push را در $\Theta \left(1\right)$ انجام دهد.

یک ماتریس 64 در 64 داریم که درایه های ان همه 0 یا 1 هستند. میخواهیم این ماتریس را به صورت مارپیچی مرتب کنیم. یعنی اگر در انتها، سطر اول را از چپ به راست به سطر دوم از راست به چپ و .... بچسبانیم یک ارایه 4096 بیتی مرتب از 0 و 1 خواهیم داشت. ادعا میکنیم که الگوریتم زیر این کار را انجام میدهد:

$k.1$بار تکرار کن.

$.a$همه سطرها را مستقلا و در جهت خود مرتب کن. یعنی سطرهای فرد را از چپ به راست، سطرهای زوج را از راست به چپ مرتب کن.

$.b$همه ستون ها را از بالا به پایین مرتب کن.

کمترین مقدار k در بدترین حالت چند است؟

کدام یک مسائل زیر را می‌توان در زمان $O\left(n^{2.5}\right)$ حل کرد؟

الف) پیدا کردن کوتاه ترین مسیر بین هر دو راس در گراف وزن‌دار با n راس

ب) ضرب دو ماتریس $n\times n$

ج) پیدا کردن تعداد جفت رئوسی که همسایه مشترک دارند در یک گراف n راسی

فرض کنید 100T در اختیار داریم. جدول نرخ تبدیل ارزها در زیر داده شده است. به عنوان نمونه طبق جدول زیر هر 1E برابر 30T میباشد. میخواهیم با چندین بار تبدیل پول و نهایتا تبدیل ان به T درامد کسب کنیم. چه میزان درامد می توانیم کسب کنیم؟ (توجه کنید که 100T اولیه درامد حساب نمیشود.)