ساختمان داده

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

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

درباره آزمون ساختمان داده(10 سوال)طراحی الگوریتم(10 سوال)سیستم‌های عامل پیشرفته(15 سوال)پایگاه داده پیشرفته(10 سوال)

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

10 سوال

فرض کنید متنی به‌طول n در اختیار داریم. در خصوص گزاره‌های زیر کدام گزینه صحیح است؟

الف) کد هافمن یک کاراکتر یک بیتی است، اگر و فقط اگر تعداد تکرار آن کارکتر کمتر از جمع تعداد تکرار بقیه کارکترها نباشد.

ب) اگر کاراکتری بیشترین تکرار را داشته باشد و تعداد تکرارهای آن بیش از $\frac{n}{3}$ باشد، آنگاه کد هافمن آن کاراکتر تک بیتی است.

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

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

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

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

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

یک گراف کامل 10 رأسی را در نظر بگیرید، که رأس‌های آن از 1 تا 10 شماره‌گذاری شده‌اند. فرض کنید وزن یال بین i و j برابر i+j است. آخرین یال درخت پوشای کمینه که توسط الگوریتم پریم با شروع از رأس 10 اضافه می‌شود، چه وزنی دارد؟

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

کدام الگوریتم مرتب‌سازی در بهترین حالت، زمان اجرای کمتری دارد؟

Insertion Sort

Selection Sort

Merge Sort

Quick Sort

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

برای پیاده‌سازی یک لیست پیوندی حلقوی، کدام ساختمان داده قابل استفاده است؟

پشته

صف

صف و پشته

هیچ‌یک از صف و پشته

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

در پیاده‌سازی متعارف جستجوی عمق اول و جستجوی سطح اول، به‌ترتیب از کدام داده ساختارها استفاده می‌شود؟

پشته و صف

صف و پشته

پشته و لیست

لیست و پشته

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

مسئله جمع زیر مجموعه بدین شکل تعریف می‌شود: یک مجموعه از اعداد مثبت $S = {a_{1} \dots a_{n}}$ به همراه عدد W داده شده است. آیا زیر مجموعه‌ای از S پیدا می‌شود که جمع اعضای آن W شود؟

برای حل این مسئله به‌روش برنامه‌ریزی پویا یک آرایه دو بعدی $X [1.. n, 0.. W]$ تعریف می‌کنیم که $X [i, j]$ برابر True است. اگر زیر مجموعه‌ای از $S = {a_{1} \dots a_{i}}$ وجود داشته باشد که جمع اعضای آن j شود، در این خصوص کدام رابطه درست است؟

$X [i, j] = X [i - 1, j] \lor X [i, j - a_{i}]$

$X [i, j] = X [i - 1, j] \land X [i, j - a_{i}]$

$X [i, j] = X [i - 1, j] \lor X [i - 1, j - a_{i}]$

$X [i, j] = X [i - 1, j] \land X [i - 1, j - a_{i}]$

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

برای گراف بدون جهت G با n رأس دو مسئله زیر را در نظر بگیرید:

مسئله A : آیا G یک زیر مجموعه مستقل 4 رأسی دارد؟
مسئله B : آیا G یک زیرمجموعه مستقل n-4 رأسی دارد؟

در خصوص این دو مسئله کدام مورد درست است؟

مسئله A عضو کلاس P و مسئله B عضو کلاس NP-Complete است.

مسئله A عضو کلاس NP-Complete و مسئله B عضو کلاس P است.

هر دو مسئله عضو کلاس NP-Complete هستند.

هر دو مسئله عضو کلاس P هستند.

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

فرض کنید G=(V,E) یک گراف بدون جهت و گراف $G^{'} = (V^{'}, E^{'})$ یک زیرگراف G است. یال‌های G را بدین شکل وزن‌دار می‌کنیم: اگر $c \in E^{'}$ باشد، وزن آن را صفر و در غیر اینصورت 1 می‌گذاریم. از رأس دلخواه $v \in v^{'}$ الگوریتم دایکسترا را برای محاسبه کوتاهترین مسیر به بقیه رئوس اجرا می‌کنیم. کدام مسئله را می‌توان با استفاده از طول کوتاهترین مسیرهای محاسبه شده، حل کرد؟

آیا $G^{'}$ درخت است؟

آیا $G^{'}$ همبند است؟

آیا $G^{'}$ تشکیل خوشه می‌دهد؟

تعداد یال‌ها در کوتاهترین مسیر از v به بقیه رئوس چند است؟

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

فرض کنید در داخل یک درخت دودویی جستجو، اعداد 1 تا 1000 ذخیره شده‌اند و ما می‌خواهیم دنبال عدد 365 بگردیم. کدام دنباله (از چپ به راست) نمی‌تواند مسیر جستجو باشد؟

4,401,389,221,268,384,383,280,365

926,222,913,246,900,260,364,365

4,254,403,400,332,346,399,365

927,204,913,242,914,247,365

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

10.

فرض کنید یک آرایه مرتب از n عدد در اختیار داریم. به ازای یک k داده شده، می‌خواهیم دو عدد a و b از آرایه را پیدا کنیم که $∣ a - b ∣ = k$ شود. سریع‌ترین الگوریتم برای حل این مسئله دارای چه مرتبه زمانی است؟

O(n)

$O (n^{2})$

O(logn)

O(nlogn)

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