ساختمان داده‌ها

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

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

درباره آزمون زبان عمومی (انگلیسی)(10 سوال)زبان تخصصی (انگلیسی)(15 سوال)ریاضی عمومی (1 و 2)(7 سوال)آمار و احتمال مهندسی(7 سوال)ریاضیات گسسته(6 سوال)نظریه زبان‌ها و ماشین‌ها(5 سوال)سیگنال‌ها و سیستم‌ها(5 سوال)ساختمان داده‌ها(6 سوال)طراحی الگوریتم(6 سوال)هوش مصنوعی(8 سوال)مدار منطقی(7 سوال)معماری کامپیوتر(7 سوال)الکترونیک دیجیتال(6 سوال)سیستم‌های عامل(7 سوال)شبکه‌های کامپیوتری(6 سوال)پایگاه داده‌ها(7 سوال)

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

6 سوال

56.

فرض کنید $T (x) = 2 T (\frac{x}{2}) + \frac{8}{9} T (\frac{3 x}{4}) + θ (\frac{x ^{2}}{l o g x})$ ، در این صورت کدام مورد درست است؟

$T (x) = θ (x^{2} lo g_{x})$

$T (x) = θ (\frac{x ^{2}}{l o g x})$

$T (x) = θ (x^{2} lo g (lo g x))$

$T (x) = θ (2 lo g x - lo g (lo g x))$

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

57.

دنباله $A [1.. n]$ یک دنباله دوآهنگی (Bitonic) است، بدین معنی که هرگاه عناصر دنباله را به ترتیب دور یک دایره بنشانیم، یک عنصر یافت می شود که دنباله عناصر بعدی ابتدا صعودی و سپس نزولی هستند. بهترین زمان برای مرتب سازی یک دنباله دوآهنگی، کدام مورد است؟

$O (n lo g n)$

$O (n n)$

$O (n^{2})$

$O (n)$

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

58.

فرض کنید می خواهیم تمام زیر دنباله های یک دنباله داده شده را با استفاده از روش عقب گرد بررسی کنیم. اگر طول دنباله n باشد، پیچیدگی زمانی این روش چیست؟

$O (2^{n})$

$O (n^{2})$

$O (n!)$

$O (lo g n)$

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

59.

فرض کنید مسئله ای به نام انتخاب پروژه های با بیشترین سود (Maximum Profit Project Selection) داریم. در این مسئله، تعدادی پروژه وجود دارد که در آن پروژه i دارای سود $P_{i}$ و مدت زمان $d_{i}$ است. تنها تعداد مشخصی از پروژه ها را می توان به طور هم زمان انجام داد و کل مدت زمان انجام پروژه ها نباید از T بیشتر شود. هدف این است که بیشترین سود ممکن را از بین پروژه های انتخاب شده به دست آوریم. می خواهیم از الگوریتم شاخه و حد (Branch and Bound) برای حل این مسئله استفاده کنیم. کدام یک از روش های زیر، مناسب ترین روش برای تعیین حدبالا (Upper Bound) در هر گره است تا به سرعت شاخه های غیرممکن یا کم بازده حذف شوند؟

استفاده از میانگین سود پروژه های باقی مانده و افزودن آن به سود فعلی در گره فعلی به عنوان حد بالا

استفاده از بیشترین سود در پروژه های باقی مانده و افزودن آن به سود فعلی در گره فعلی به عنوان حد بالا

استفاده از مجموع سود تمامی پروژه های باقی مانده و افزودن آن به سود فعلی در گره فعلی به عنوان حد بالا

انتخاب پروژه ها به صورت حریصانه، براساس بیشترین نسبت سود به مدت زمان و افزودن آنها تا زمانی که زمان کل از T فراتر نرود و سپس در نظر گرفتن نتیجه به عنوان حد بالا

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

60.

در الگوریتم مرتب سازی Insertion Sort، اگر برای جستجوی مکان مناسب عنصر جاری به جای جستجوی خطی از جستجوی دودویی استفاده کنیم، کدام مورد زیر در خصوص پیچیدگی زمانی آن در بدترین حالت درست است؟

به O(nlogn) کاهش می یابد.

همچنان $O (n^{2})$ بافی می ماند.

به O(logn) کاهش می یابد.

به O(n) کاهش می یابد.

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

61.

فرض کنید می خواهید از میان دنباله ای از اعداد صحیح غیرمنفی تعدادی را انتخاب کنید به گونه ای که به بیشترین مجموع دست یابید، با این شرایط که نمی توانید دو عنصر متوالی را انتخاب کنید. به عبارت دیگر، هر عددی که انتخاب می شود، عدد بعد از آن در دنباله نمی تواند انتخاب شود. کدام مورد، مناسب ترین روش با کمترین پیچیدگی زمانی برای حل این مسئله است؟

استفاده از الگوریتم بازگشتی به همراه حافظه گذاری (Memoriztion) برای ذخیره نتایج زیر مسئله ها و جلوگیری از محاسبه مجدد آنها

استفاده از الگوریتم پویا (Dynamic Programming) که به صورت تکراری مقدار بهینه را از سمت چپ به راست محاسبه می کند.

استفاده از الگوریتم تقسیم و حل (Divide and Conquer)، برای تقسیم مسئله به زیر مسئله های کوچکتر

استفاده از الگوریتم جستجوی کامل (Brute Force) که تمام ترکیب های ممکن را بررسی می کند.

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