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

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

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

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

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

4 سوال

51.

پاسخ رابطه بازگشتی زیر کدام است؟

O(log n )

O(log log n )

O(log n / log log n)

O(log n / (log log n) $^{2}$ )

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

52.

فرض کنید یک درخت دودویی جست و جو با n گره داریم. به ازای گره u از این درخت، وزن آن را تعداد گره‌ها در زیر درخت به ریشه u ( شامل u) در نظر بگیرید. میدانیم در درخت فوق به ازای هر گره داخلی u نسبت وزن فرزند چپ و فرزند راست حداقل 0/5 و حداکثر 2 است. بهترین کران بالا برای زمان جست و جو در این درخت در بدترین حالت، در بین گزینه‌ها کدام است؟ ( مبنای لگاریتم‌ها 2 است)

1/5 log n

2/5 log n

2 log n

3 log n

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

53.

در الگوریتم مرتب سازی سریع در هر مرحله یک عنصر دلخواه به عنوان محور (pivot) انتخاب و بقیه اعداد با آن مقایسه میشود. اگر در هر مرحله میانه اعداد به عنوان محور انتخاب شود و ار الگوریتم با تعداد خطی مقایسه برای محاسبه میانه استفاده شود، در بدترین حالت تعداد مقایسه‌ها در این نسخه تغییر یافته الگوریتم مرتب سازی سریع کدام است؟

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

$O (n lo g n)$

$O (n^{2})$

$O (n)$

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

54.

فرض کنید k پشته $S_{1}, .... S_{k}$ را در اختیار داریم. تنها اعمال مجاز گرفتن یک ورودی و پوش کردن آن داخل پشته $S_{1}$ ، پاپ کردن یک عنصر از پشته $S_{k}$ و قرار دادن در خروجی، پاپ کردن یک عنصر از پشته $S_{i}$ (برای i<k) و پوش کردن آن داخل پشته $S_{i} + 1$ است. فرض کنید اعداد $1, ..., n$ را با اعمال مجاز گفته شده تولید کرد، در بین گزینه‌ها کدام است؟

n-1

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

55.

فرض کنید از ادرس دهی باز و وارسی خطی برای درهم سازی استفاده شده و تابع درهم سازی $i^{2}$ به پیمانه 7 است. بعد از دریافت همه اعداد 6,...,0 میدانیم نحوه قرارگیری اعداد در جدول درهم ساز بصورت زیر است:

$A [0, ..., 6] = 0, 6, 4, 3, 1, 5, 2$

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

120

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