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

اگر به یک گراف جهت دار یک یال اضافه کنیم تعداد اجزای قویا همبند در گراف چه مقدار تغییر میکند؟

فرض کنید شکل زیر، درخت حاصل از اجرای DFS روی یک گراف همبند و بدون جهت G است. با فرض این که میدانیم گراف G دقیقاً یک رأس برشی دارد کدام گزاره در مورد درجه رأس در این گراف صحیح است؟ (یک راس گراف G برشی است اگر حذف آن تعداد مؤلفه های همبندی G را افزایش دهد.)

آرایه ای شامل n عدد متمایز داده شده است میخواهیم از روی این اعداد یک درخت دودویی بسازیم با این خاصیت که به ازای هر رأس درخت ساخته شده این خصوصیت را نیز داشته باشد که پیمایش میان ترتیب آن دقیقاً معادل ترتیب عناصر در آرایه شود کدام گزاره درست است؟

فرض کنید میخواهیم n تومان را با استفاده از سکه های a و b و c تومانی خرد کنیم به ازای چه تعداد از سه تایی های (a,b,c) زیر الگوریتم حریصانه n تومان را با کمترین تعداد سکه خرد میکند؟

• (۵,۲,۱)
• (۵,۴,۱)
• (۶,۳,۱)

آرایه A حاصل ترکیب دو زیر آرایه B و C است که B یک آرایه صعودی و C یک آرایه نزولی است. به عنوان نمونه A میتواند به صورت $\left[2,9,7,4,6,5,8,1\right]$ باشد که در واقع ترکیب آرایه صعودی $\left[2,4,6,8\right]$ و آرایه نزولی $\left[9,7,5,1\right]$ است. این آرایه را در چه زمانی میتوان مرتب کرد؟ (بهترین گزینه را انتخاب کنید.)

فرض کنید یک آرایه مرتب از اعداد طبیعی به طول n داریم که در آن هر عدد به غیر از یکی دقیقاً دو بار ظاهر شده است. عضو غیر تکراری را در چه زمانی میتوان پیدا کرد؟

یک هرم کمینه شامل n عنصر داده شده است. سومین کوچکترین عنصر این آرایه را در چه زمانی میتوان پیدا کرد؟

اگر در الگوریتم هافمن نویسه ای بیش از $\frac{2}{5}$ كل متن تکرار شود، در در آن صورت که این نویسه چند بیت می تواند باشد؟

در یک درخت T با n گره فرض کنید تعداد برگها B و تعداد فرزندان هر گره غیر برگ ۲ باشد. همچنین فرض کنید [E[T و I[T] به ترتیب مجموع عمق برگها و مجموع عمق عناصر غیر برگ T باشند. اگر ۹۹۹۹ =n باشد. کدام گزینه همیشه درست است؟

چند تا از گزاره های زیر صحیح است؟

• اگر پس از اتمام الگوریتم بلمن فورد، به روزرسانی فاصله ها را ادامه دهیم و فاصله مربوط به یک رأس $\nu$ باز هم به روز شود $\nu$در یک دور منفی قرار دارد.
• اگر در جست و جوی عمق اول گراف جهت دار G تنها یک یال بازگشتی (e (back edge وجود داشته باشد، آنگاه یال $e^{\prime }$ به جز یال e وجود دارد که $G-e^{\prime }$ بدون دور است.
• اگر در الگوریتم دایکسترا که روی یک DAG و از مبدأ اجرا شده فقط برخی از یالهای خروجی s وزن منفی داشته باشند، الگوریتم ممکن است به درستی فاصله ها را محاسبه نکند.

در یک مجموعه از اعداد صحیح به اندازه n، دنبال یک ۴ تایی هایی مثل (a,b,c,d) هستیم که $d=\sqrt{a^2+b^2+c^2}$ این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید.)

با فرض در هم سازی یکنواخت ساده احتمال این که سه عضو متفاوت a و b و c به یک خانه جدول در هم سازی نگاشت شوند برابر کدام گزینه است؟ (فرض کنید اندازه جدول m است.)

خانواده $H=\left\{h_1,\dots ,h_k\right\}$ از توابع در هم ساز را در نظر بگیرید که $h_i:\left\{a,b,c,d\right\}\to \left\{0,1\right\}$ برای آن که این خانواده یک خانواده در هم ساز سراسری باشد k حداقل چقدر باید باشد؟ (خانواده توابع H سراسری است اگر و فقط اگر به ازای هر دو مقدار u و v داشته باشیم. $P{r}_{h\in H}\left[h\left(u\right)=h\left(v\right)\right]\le \frac{1}{m}$ که m اندازه جدول در هم سازی است.)

آرایه $A\left[\mathrm{1..}n\right]$ از اعداد صحیح داده شده است. زیر دنباله متوالی A[i..j] یک بازه «مثبت» نامیده میشود. اگر جمع اعضای [A[i تا [A[j مثبت بزرگتر از 0 باشد میخواهیم کمترین تعداد بازه های مثبت که تمام اعداد مثبت آرایه را پوشش میدهد پیدا کنیم اگر ورودی آرایه زیر باشد، جواب کدام است؟

$A\left[\mathrm{1..15}\right]=<3,-5,4,1,-9,-8,2,3,4,-10,1,-2,-3,6,-1>$

یک گراف ۵ رأسی همبند و بدون جهت داریم که رأسهای آن با شماره های ۱ تا ۵ شماره گذاری شده اند. فرض کنید از رأس ۱ الگوریتم BFS را اجرا میکنیم و تمام حالتهایی که BFS میتواند رئوس را ملاقات کند عبارتند از $<1,2,3,4,5>$، $<1,3,2,5,4>$ ،$<1,3,2,4,5>$ و $<1,2,3,5,4>$ حال اگر از رأس ۵ الگوریتم DFS را اجرا کنیم، کدام گزینه نمی تواند ترتیب ملاقاتها رئوس گراف باشد؟

برنامه زیر چه کاری میکند و زمان اجرای آن کدام است؟

SS(A[0..n-1])

If n=2 and A[0] > A[1] then

Swap (A[0], A[1])

else if n > 2

m= [2n/3]

SS(A[0..m-1])

SS(A[n-m..n-1])

SS(A[0..m-1])

دنباله <۳,۱,۴,۱,۵,۹,۲,۶,۵,۳,۸,۹,۷,۹,۳,۲,۳,۸,۴,۶,۲,۷,۹> را در نظر بگیرید. چند عضو متوالی این دنباله را میتوان به صورت یک عدد تصور کرد مثلاً سه عنصر متوالی ۵ و ۳ و ۸ را عدد ۵۳۸ تصور کرد. دو عدد به این شکل را مجزا گوییم اگر هیچ یک از عناصر دنباله در ساخت هر دوی آنها نقش نداشته باشند. حداکثر چند عدد مجزا به این شکل میتوان ساخت که به ترتیب از چپ به راست صعودی باشند؟

فرض کنید تابعی داریم که به عنوان ورودی دو دنباله گرفته و به عنوان خروجی طول بزرگترین زیر دنباله مشترک آنها را بر می گرداند با حداکثر یک بار فراخوانی این تابع به علاوه هزینه (1) چند مورد زیر را می توان محاسبه کرد؟

• محاسبه طول بزرگترین زیر دنباله آینه ای یک دنباله
• تشخیص این که آیا یک دنباله زیر دنباله یک دنباله دیگر است.
• تشخیص این که آیا یک دنباله آینه ای است.

درخت فراگیر T از گراف وزن دار G یک درخت گلوگاهی است، اگر سنگینترین یال آن در بین تمامی درخت های فراگیر سبک ترین باشد کدام گزینه در خصوص گزاره های زیر درست است؟

(الف) هر درخت گلوگاهی یک درخت فراگیر کمینه است.

(ب) هر درخت فراگیر کمینه یک درخت گلوگاهی است.

گراف جهت دار G با وزن یالهای صحیح و دو رأس خاص s و t از گراف داده شده است. فرض کنید شار بیشینه از s به t در گراف داده شده است. کدام گزینه در خصوص گزاره های زیر درست است؟

(الف) اگر ظرفیت یکی از یالهای G یک واحد افزایش داده شود شار بیشینه در گراف جدید در زمان خطی قابل محاسبه است.

(ب) اگر ظرفیت یکی از یالهای G یک واحد کاهش داده شود شار بیشینه در گراف جدید در زمان خطی قابل محاسبه است.