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

$T\left(x\right)=\theta \left(x\log x\right)$

$T\left(x\right)=\theta \left(x{\left(\log \right)}^2\right)$

$T\left(x\right)=\theta \left(x^2\log x\right)$

$\theta \left(n^4\right)$

$\theta \left(n^5\right)$

$\theta \left(n^3\log n\right)$

$f\left(n\right)=o\left(g\left(n\right)\right)$

$g\left(n\right)=o\left(f\left(n\right)\right)$

هیچ کدام

$\theta \left(\frac{m}{n}\right)$

$\theta \left(\frac{n^2}{m}\right)$

$\theta \left(\frac{n^2}{m^2}\right)$

برای هر یال وزن منفی، یک چرخه نامحدود از به روز رسانی فاصله ها ایجاد می کند که باعث توقف ناپذیری الگوریتم می شود.

کاملا بر روی گراف های دارای یال منفی، درست کار می کند و مشکلی ندارد.

فقط بر روی طوقه های منفی و یال های مثبت، درست کار می کند.

با دو گذر روی لیست و حافظه $O\left(1\right)$، می توان تشخیص داد که عنصر اکثریت وجود دارد یا نه.

با دو گذر روی لیست و حافظه $O\left(n\right)$، نمی توان تشخیص داد که عنصر اکثریت وجود دارد یا نه.

با یک گذر روی لیست و حافظه $O\left(\sqrt{n}\right)$، می توان تشخیص داد که عنصر اکثریت وجود دارد یا نه.

در هرم هر دو ساختار، کوچک ترین مقدار، ممکن است در هر سطح یا شاخه وجود داشته باشد. بنابراین، باید همه گره ها را در هر دو ساختار جستجو کنید که پیچیدگی زمانی $O\left(n\right)$ خواهد بود.

در هرم بیشینه، کوچک ترین مقدار باید در پایین ترین سطح و در گره های برگ قرار داشته باشد که نیازمند پیمایش تمامی گره های برگ است $\left(O\left(\sqrt{n}\right)\right)$. در درخت AVL، کوچک ترین مقدار در گره سمت چپ ترین قرار دارد و می توان آن را در زمان $O\left(n\right)$ پیدا کرد.

هرم بیشینه، برای پیدا کردن کوچک ترین مقدار مناسب نیست، زیرا ساختار آن برای دسترسی سریع به بزرگ ترین مقدار طراحی شده است. اما درخت AVL، کوچک ترین مقدار در گره چپ ترین قرار دارد و این مقدار را در زمان $O\left(\log n\right)$ برمی گرداند.

استفاده از جستجوی دو دویی (Binary Search) برای بررسی نیمه مناسب آرایه در هر مرحله

مرتب سازی مجدد آرایه و استفاده از جستجوی خطی برای بررسی شرط $A\left[i\right]i$

پیمایش خطی آرایه از ابتدا تا انتها و بررسی شرط $A\left[i\right]i$

در هر بار فراخوانی FIND-MAX(S)، تمامی عناصر پشته را با استفاده از عملیات POP خارج کنید، بزرگ ترین مقدار را پیدا کنید و سپس عناصر را به ترتیب اصلی به پشته بازگردانید. این روش دارای پیچیدی زمانی O(n) برای هر فراخوانی است.

از یک پشته کمکی M استفاده کنید که در هر PUSH مقدار بزرگ ترین عنصر پشته S را تا آن لحظه ذخیره می کند. در هنگام POP، مقدار بالای پشته M نیز حذف می شود. عملیات FIND-MAX(S) در این روش، دارای پیچیدگی زمان O(1) است.

در هر PUSH، مقدار بزرگ ترین عنصر پشته تا آن لحظه را با استفاده از مقایسه بازگشتی تعیین کنید و آن را به پشته اصلی S اضافه کنید. این روش دارای پیچیدگی زمان O(logn) برای FIND-MAX(S) است.

ادغامی

درجی

سریع

فقط عملیات dequeue از ابتدای صف دارای پیچیدگی زمانی O(1) است، در حالی که سایر عملیاتها پیچیدگی زمانی O(n) دارند.

تمامی عملیات های enqueue و dequeue در صف دوتایی دارای پیچیدگی زمانی O(1) هستند، چه از ابتدای صف و چه از انتهای صف.

عملیات enqueue در انتهای صف و عملیات dequeue از ابتدای صف، دارای پیچیدگی زمانی O(1) هستند، اما عملیات dequeue از انتهای صف، دارای پیچیدگی O(n) است.

$F_{n+3}$

$2F_{n+2}-2$

$F_{n+3}-1$

32

31

16

$O\left(n{\log }_{2}n\right)$

$O\left({\log }_2^n\right)$

$O\left(n^2\right)$

1

2

3

دومین بزرگ ترین مقدار در یک هرم بیشینه همیشه یکی از دو فرزند گره ریشه است و می توان آن را در زمان O(1) با مقایسه مقادیر این دو گره به دست آورد.

برای پیدا کردن دومین بزرگ ترین مقدار در یک هرم بیشینه، تنها کافی است گره های فرزند ریشه (سطح اول زیر ریشه) ر بررسی کنیم. این فرایند پیچیدگی زمانی O(logn) دارد.

برای پیدا کردن دومین بزرگ ترین مقدار در یک هرم بیشینه، باید تمام گره های هرم بررسی شوند، زیرا دومین بزرگ ترین مقدار ممکن است در هر سطح قرار داشته باشد. ین فرایند پیچیدگی زمانی o(N) دارد.

هر گره نمایانگر مسیرهایی است که می توان از یک موقعیت خاص طی کرد و پیچیدگی زمانی برابر $O\left(2^n\right)$ است که n، تعداد خانه های هزارتو است.

هر گره نمایانگر یک مسیر کامل از نقطه شروع تا مقصد است و پیچیدگی زمانی برابر $O\left(4^n\right)$ است که n، تعداد خانه های هزارتو است.

هر گره نمایانگر یک مسیر کامل از نقطه شروع تا مقصد است و پیچیدگی زمانی برابر $O\left(n!\right)$ است که n، تعداد خانه های هزارتو است.

شاخه ها نشان دهنده تمام ترتیب های ممکن برای گروه بندی ضرب ماتریس ها هستند و حد پایین (Lower Bound)، نشان دهنده تعداد حذداقل عملیات ضرب عددی ممکن در کل مسئله است.

شاخه ها تعداد عملیات ضرب برای هر ترتیب خاص از ماتریس ها را نشان می دهند و حد پایین (Lower Bound)، تنها برای شناسایی شاخه هایی استفاده می شود که منجر به بیشترین تعداد عملیات ضرب عددی می شوند.

شاخه ها نشان دهنده تمامی نقاط تقسیم ممکن بین ماتریس ها هستند که مسئله را به دو زیرمسئله تقسیم می کنند و حد پایین (Lower Bound)، مجموع تعداد عملیات ضرب مورد نیاز برای حل زیر مسئله ها و عملیات نهایی ادغام آنها است.

گره های روش عقبگرد هشت حالت خواهد داشت و بعد از هرس شاخه های غیر قابل قبول، پیچیدگی زمانی آن $O\left(8^n\right)$ خواهد بود.

روش عقبگرد با استفاده از ساختار داده ای مانند صف اولویت (priority Queue)، تعداد مسیرهای ممکن را کاهش داده و پیچیدگی زمانی آن را به $O\left(\left(n\log \right)!\right)$ می رساند.

روش عقبگرد با بررسی تمام مسیرهای ممکن و هرس شاخه های غیر قابل قبول کار می کند. تعداد حالت های ممکن برابر با $\left(n^2\right)!$ است و پیچیدگی زمانی آن در عمل بسیار بالا است.

2

1

صفر