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

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

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

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

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

6 سوال

61.

گراف جهت دار و وزن دار G=(E,V) با n راس و O(n) یال و زیرمجموعه $S \subset V$ از راس های گراف با اندازه حداقل $\frac{n}{2}$ داده شده است. فرض کنید وزن تمام یال های گراف مثبت است. به ازای هر راس u از گراف، فاصله راس u از مجموعه S که ان را با d(u,S) نمایش میدهیم عبارت است از:

$d (u, S) = min δ (u, v)$

که در ان $δ (u, v)$ برابر با طول کوتاه ترین مسیر جهت دار از u به v در گراف G است. در چه مرتبه زمانی می توان مقادیر d(u,s) را به ازای تمام راس های u از گراف محاسبه کرد؟ دقت کنید که خروجی شامل n مقدار d(u,S) به ازای تمام راس های u از گراف است.(بهترین گزینه را انتخاب کنید)

$O (n^{3})$

$O (n^{2})$

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

$O (n lo g n)$

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

62.

فرض کنید گراف G یک گراف وزن دار و مسطح با n راس است.درخت پوشای کمینه G را درچه زمانی می توان محاسبه کرد؟ توجه کنید لزومی ندارد از الگوریتم های معروف برای محاسبه درخت پوشای کمینه استفاده شود.(بهترین گزینه را انتخاب کنید)

$Θ (n)$

$Θ (n lo g n)$

$Θ (n lo g lo g n)$

$Θ (n^{2})$

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

63.

ارایه A شامل n عدد داده شده است. هدف پیدا کردن تعداد جفت اندیس i و j است، به گونه ای که $A [i] \cdot A [j] > i > j$ . این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید)

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

$O (n^{2})$

$O (n lo g n)$

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

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

64.

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

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

65.

فرض کنید سه ارایه A و B و C هر کدام شامل n عدد داده شده است، عناصر داخل ارایه‌ها متمایز هستند. ارایه A و C بصورت صعودی و ارایه B بصورت نزولی مرتب است. اگر بخواهیم ارایه D را بسازیم که شامل عناصر $(A \cup B) \cap C$ باشد و به صورت صعودی مرتب شده باشد و عضو تکراری نیز نذداشته باشد، بهترین پیچیدگی زمانی ممکن برای اینکار کدام مورد است؟(توجه: ممکن است عناصری، در دو یا سه ارایه باشند.)

$O (n^{2})$

$O (n lo g n)$

$O (lo g n)$

$O (n)$

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

66.

در کدام مورد، توابع به ترتیب صعودی ( و نه اکیدا صعودی) بر مبنای رشد تابع از سمت چپ به راست ، مرتب شده اند؟

$lo g n, lo g^{2} n, lo g n^{2}, n lo g^{2} n, lo g n!, lo g n^{n}$

$lo g n, lo g n^{2}, lo g^{2} n, n lo g^{2} n, lo g n^{n}, lo g n!$

$lo g n, lo g^{2} n, lo g n^{2}, lo g n!, lo g n^{n}, n lo g^{2} n$

$lo g n, lo g n^{2}, lo g^{2} n, lo g n^{n}, lo g n!, n lo g^{2} n$

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