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

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

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

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

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

7 سوال

85.

به ازای چند زوج ( a,b ) از اعدادد طبیعی کوچکتر از 5، جواب رابطه بازگشتی $+ n^{2}$ T(n)=aT(n/b) برابر $θ (n^{2})$ میشود؟

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

86.

جدوا درهم‌سازی 10 خانه‌ای و تابع درهم‌ساز h(x)=3x+5 mod 10 و روش زنجیره‌ای به عنوان روش رفع تصادم را در نظر بگیرید. در این خصوص کدام گزینه درست است؟

احتمال انکه ورودی x=4 به خانه 7 نگاشت شود برابر 1 است

احتمال انکه ورودی x=4 به خانه 7 نگاشت شود برابر 0 است

احتمال انکه ورودی x=4 به خانه 7 نگاشت شود برابر $\frac{1}{10}$ است

احتمال انکه دو ورودی مختلف به یک خانه نگاشت شود برابر $\frac{1}{10}$ است

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

87.

فرض کنید یک ارایه مرتب از n عدد صحیح در اختیار داریم. با چه تعداد مقایسه میتوانیم بفهمیم عددی بیش از n/5 بار در ارایه تکرار شده است یا خیر؟ (بهترین گزینه را انتخاب کنید)

$O (n)$

$O (lo g n)$

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

$O (lo g lo g n)$

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

88.

اعداد صحیح $x_{1}, ........, x_{n}$ را در یک درخت دودویی جستجو با ارتفاع h ذخیره کرده‌ایم. فرض کنید هزینه جستجوی $x_{i}$ ( تعداد مقایسه‌های لازم در درخت برای پیدا کردن $x_{i}$ ) برابر $c_{i}$ باشد. میدانیم است. کدام گزینه زیر درست است؟

$h = Ω (n)$

$h = O (lo g n)$

$h = O (n lo g n)$

میتواند مثالی زد که $h = Ω (n)$ باشد

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

89.

فرض کنید T(n) متوسط زمان اجرای الگوریتم مرتب‌سازی سریع به ازای همه جایگشت‌های ممکن ورودی از n عدد متمایز باشد. کدام رابطه بازگشتی زیر درست است؟

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

90.

فرض کنید T درخت جستجوی عمق اول گراف همبند و بدون جهت G است. دو راس u و v در این درخت بزرگ و در G دارای درجه حداقل 2 هستند . کدام یک از گزاره‌های زیر صحیح است؟

الف) باید یک راس w وجود داشته باشد که با u و v در G همسایع باشد.

ب) باید یک راس w وجود داشته باشد که حذف ان u را از v در Gجدا میکند

(الف) نادرست، (ب) نادرست

(الف) نادرست، (ب) درست

(الف) درست، (ب) نادرست

(الف) درست، (ب) درست

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

91.

فرض کنید ارایه $A [1... n]$ شامل n عدد صحیح متمایز است که به صورت صعودی مرتب شده‌اند. چند تا از مسائل زیر را میتوان با مرتبه زمانی O(log n) حل کرد؟

پبدا کردن یک اندیس i طوری که $A [i] = i$ شود
پبدا کردن یک اندیس i طوری که $A [i] = 3 i + 2$ شود
پبدا کردن یک اندیس i طوری که $A [i] = 4 i^{2} + 3 i + 5$ شود

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