صفحه اصلی

تست لایک

کنکور دکتری

مهندسی کامپیوتر - نرم افزار

ساختمان داده ها و طراحی الگوریتم ها

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

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

درباره آزمون ساختمان داده ها و طراحی الگوریتم ها(20 سوال)مدار منطقی و معماری کامپیوتر(20 سوال)سیستم های عامل پیشرفته(15 سوال)پایگاه داده های پیشرفته(10 سوال)شناسایی الگو - یادگیری ماشین(25 سوال)شبکه های پیشرفته(10 سوال)معماری کامپیوتر پیشرفته - VLSI پیشرفته(25 سوال)

سوالات ساختمان داده ها و طراحی الگوریتم ها

20 سوال

1.

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

1)

O(nk)

2)

O(n+k)

3)

O(nlogk)

4)

O(klog n)

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

2.

فرض کنید a یک بردار n مؤلفه ای باشد، اگر تبدیل فوریه گسسته آن یعنی DFT(a) را با استفاده از تبدیل فوریه سریع FFT محاسبه کنیم، آنگاه مرتبه زمانی یک الگوریتم کارا برای این منظور کدام است؟

1)

O(n)

2)

$O (n^{2})$

3)

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

4)

O(nlogn)

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

3.

چنانچه پیمایش درخت دودویی را در دو حالت Postorder و Preorder داشته باشیم، هرگاه تعداد رئوس درخت برابر n=35 باشد، در این صورت تعداد درختان دودویی ممکن، کدام است؟

1)

30

2)

31

3)

32

4)

33

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

4.

فرض کنید n نقطه روی خط حقیقی با طول های $x_{1}, x_{2}, \dots, x_{n}$ داریم، می خواهیم نقطه ای از این نقاط را روی این خط بیابیم که مجموع فواصل آن تا سایر نقاط حداقل باشد. بهترین الگوریتم برای انی منظور از چه مرتبه زمانی است؟

1)

o(n)

2)

$O (n^{2})$

3)

O(logn)

4)

O(nlogn)

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

5.

اعداد 1 تا 1402 را به ترتیب به عنوان داده های یک صف حلقوی Q که به صوت پیوندی با شروع از P پیاده سازی شده است قار داده ایم، خروجی شبه کد زیر کدام است؟

$w hi l e (P! = p \to n e x t)$

$P \to n e x t = p \to n e x t \to n e x t;$

$co u t << p \to d a t a;$

1)

757

2)

758

3)

1023

4)

1024

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

6.

آرایه شامل n-1 عدد صحیح داریم. این آرایه شامل اعداد 1 تا n بدون تکرار است، اما یکی از اعداد حذف شده است. پیچیدگی زمانی سریع ترین الگوریتم برای پیدا کردن عدد حذف شده در بدترین حالت کدام است؟

1)

$θ (lo g n)$

2)

$θ (n lo g n)$

3)

$θ (n)$

4)

$θ (n^{2})$

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

7.

آرایه ای به طول n از اعداد داریم، می خواهیم زیر آرایه ای متوالی به طول k از این آرایه استخراج کنیم که مجموع عناصر آن حداکثر باش. مرتبه الگوریتم مناسب برای حل این مسئله کدام است؟

1)

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

2)

$O (n)$

3)

$O (nk)$

4)

$O (n + k)$

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

8.

در شبکه جریان زیر، حداکثر جریان عبوری از s به t با توجه به مقادیر ظرفیت جریان مشخص شده، کدام است؟

1)

10

2)

13

3)

15

4)

16

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

9.

حداقل تعداد مقایسه های لازم برای یافتن کوچکترین و بزرگترین عنصر در یک آرایه n عنصری، کدام است؟

1)

n-1

2)

2n-3

3)

n log n

4)

$[\frac{3 n}{2}] - 2$

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

10.

آرایه نامرتب T[1..n] از اعداد مفروض است. بک پنجره به طول $n$ داریم که آن را با $w in d o w (n)$ نشان می دهیم. این پنجره اگر روی آرایه T[1..n] از اندیس iام باز شود، آن گاه زیر آرایه $T [i .. i + n - 1]$ مرتب خواهد شد. با یک الگوریتم کارا، حداکثر با چند بار فراخوانی این پنجره می توان آرایه T را مرتب کرد؟

1)

$2 n^{2}$

2)

4n

3)

$2 n n$

4)

$4 n lo g n$

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

11.

مرتبه جواب رابطه بازگشتی $T (n) = T (\frac{n}{9}) + T (\frac{7 n}{9}) + 1$ ، کدام است؟

1)

O(n)

2)

$O (n^{l o g_{9} 2})$

3)

O(n log n)

4)

$O (n^{l o g_{\frac{9}{7}} 2})$

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

12.

فرض کنید یک کاهش چند جمله ای از مسئله A به مسئله B از کلاس NP داشته باشیم. کدام مورد درست است؟

1)

اگر مسئله B، از کلاس P باشد، آن گاه P=NP است.

2)

اگر مسئله A، NP-Hard باشد آن گاه مسئله B ، NP-Complete است.

3)

اگر مسئله B، NP-Hard باشد، آن گاه مسئله A نیز NP-Complete است.

4)

موارد 1 و 3

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

13.

تابعی بازگشتی زیر را در نظر بگیرید. تابع g با تعریف g(x,y) برای درچ y تا علامت o در محل x استفاده می شود. خروجی تابعی f برای f(0,8,3) کدام مورد است؟

f(int,int b , int c)

}

int m=(a+b)/2;

if (c>0)

}

g(m,c);

f(a,m,c-1);

f(m,b,c-1);

{

{

1)

2)

3)

4)

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

14.

یک مجتمع آموزشی تصمیم دارد برای برگزاری کلاس های درسی یک روز معین، از کمترین کلاس فیزیکی استفاده کند. برنامۀ درسی یک روز معین، شامل n درس متمایز موجود است، زمان شروع و خاتمه هر درس از قبل مشخص شده است. سریع ترین الگوریتم برای تعیین حداقل تعداد کلاس های فیزیکی اختصاص داده شده، از چه ساختمان داده و مرتبه زمانی برخوردار است؟

1)

استفاده از صف، در مرتبه اجرایی O(n)

2)

استفاده از هرم فیبوناچی، در مرتبه اجرایی O(n)

3)

استفاده از پشته، در مرتبه اجرایی O(n log n)

4)

استفاده از درخت جستجو، در مرتبه O(n log n)

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

15.

چه تعداد از موارد زیر درست است؟

از یک آرایه دلخواه می توان در مرتبه O(n) یک هرم دودویی مینیمم تولید کرد.
بهترین مرتبه زمان اجرا برای پیاده سازی الگوریتم پریم جهت درخت پوشای کمینه یک گراف، استفاده از ساختمان داده هرم فیبوناچی مینیمم است.
اگر یک درخت AVL با ارتفاعh، حداقل دارای T(h) گره باشد آنگاه $T (h) = T (h - 1) + T (h - 2) + 1$

1)

صفر

2)

1

3)

2

4)

3

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

16.

فرض کنید G=(V,E) یک گراف همبند وزن دار که وزن تمام یال‌های آن برابر مقدار ثابت C است. چند مورد از گزاره‌های زیر در مورد این گراف، درست است؟

درخت پوشای کمینه (MST) این گراف را می توان در مرتبه $O (∣ E ∣)$ محاسبه کرد.
می توان طول کوتاه‌ترین مسیر از یک رأس تا تمام رئوس را در مرتبه $O (∣ V ∣)$ ، نه در مرتبه $O (∣ E ∣)$ محاسبه کرد.
می توان تعداد مؤلفه‌های هم‌بند گراف را در مرتبه $θ (∣ V ∣ + ∣ E ∣)$ محاسبه کرد.

1)

صفر

2)

1

3)

2

4)

3

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

17.

فرض کنید بخواهیم عدد n را به k جمعوند طبیعی تبدیل کنیم. رابطه بازگشتی که تعداد حالات ممکن را مشخص می کند، کدام است؟ (تعداد حالات مورد نظر را با P(n,k) نشان می‌دهیم)

به عنوان مثال عدد 6 را می توان به صورت‌های زیر به 3 جمعوند طبیعی تبدیل کرد.

$6 = 1 + 1 + 4$

$6 = 2 + 2 + 2$

$6 = 3 + 1 + 2$

1)

$P (n, k) = P (n - 1, k - 1) + P (n - k, k)$

2)

$P (n, k) = P (n - 1, k - 1) + P (n, k - 2)$

3)

$P (n, k) = P (n - 1, k) P (\frac{n}{2}, \frac{k}{2})$

4)

$P (n, k) = P (\frac{n}{2}, k) + P (n, \frac{k}{2})$

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

18.

آرایه A به طول n مفروض است. می‌داینم عنصری در این آرایه بیش از $\frac{2 n}{3}$ بار، تکرار شده است. بهترین الگوریتم برای یافتن این عنصر، از چه مرتبه زمانی است؟

1)

O(n)

2)

$O (n^{2})$

3)

O(n log n)

4)

O(log n)

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

19.

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

1)

$\frac{5}{18}$

2)

$\frac{7}{18}$

3)

$\frac{8}{18}$

4)

$\frac{10}{18}$

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

20.

چند مورد از عبارت زیر درست است؟

برای مرتب‌سازی توپولوژیکل رأس‌ها در گراف جهت‌دار، حتمأ باید از دوبار الگوریتم DFS استفاده شود.
برای محاسبه قطر یک گراف غیر جهت‌دار و ساده و بدون دور، از دوبار الگوریتم BFS استفاده می کنیم.
هرگاه G یک گراف غیر جهت دار ساده باشد، مسئله تشخیص دور در این گراف را می‌توان در مرتبه زمانی $O (∣ V ∣)$ پاسخ داد. ( $∣ V ∣$ تعداد رئوس گراف G است.)

1)

3

2)

1

3)

2

4)

صفر

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