صفحه اصلی

تست لایک

کنکور دکتری

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

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

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

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

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

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

20 سوال

1.

الگوریتم فلوید - وارشال از یک الگوریتم ........................ برای حل مسئله کوتاه‌ترین مسیرهای تمام جفت رئوس در یک گراف جهت‌دار G=(V,E) در زمان ........................ استفاده می‌کند.

1)

حریصانه، $Θ (V^{3})$

2)

حریصانه، $Θ (V^{2} lo g E)$

3)

برنامه‌نویسی پویات، $Θ (V^{3})$

4)

برنامه نویسی پویا، $Θ (V^{2} lo g E)$

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

2.

فرض اینکه $P \neq = NP$ باشد، کدام مورد درست است؟

1)

NP-hard=NP

2)

NP-complete=P

3)

NP-complete=NP

4)

$NP - co m pl e t e \cap P = ϕ$

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

3.

کم‌ترین تعداد مقایسه مورد نیاز برای تعیین اینکه یک عدد صحیح بیش از $\frac{n}{2}$ مرتبه در یک آرایه مرتب از اعداد صحیح به طول n ظاهر می‌شود، از کدام مرتبه است؟

1)

$Θ (1)$

2)

$Θ (lo g n)$

3)

$Θ (n)$

4)

$Θ (n lo g n)$

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

4.

آرایه نامرتب $A_{1}, \dots, A_{n}$ را در نظر بگیرید (n عددی فرد است. ) هر کدام از این آرایه‌ها دارای n عنصر متمایز است. هیچ عنصر مشترکی میان هیچ دو آرایه‌ای وجود ندارد. کمترین پیچیدگی زمانی الگوریتمی برای محاسبه میانه این آرایه‌ها از چه مرتبه‌ای است؟

1)

$Θ (n)$

2)

$Θ (n lo g n)$

3)

$Θ (n^{2})$

4)

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

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

5.

فرض کنید $W (n)$ و A(n)، به‌ترتیب، نشان‌دهنده بدترین حالت و میانگین زمان اجرای الگوریتم اجرا شده بر روی ورودی با اندازه n باشند، کدام مورد همواره درست است؟

1)

$A (n) = O (W (n))$

2)

$A (n) = Θ (W (n))$

3)

$A (n) = Ω (W (n))$

4)

$A (n) = o (W (n))$

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

6.

یک آرایه مرتب شده از اعداد داریم. می‌خواهیم دو عدد در این آرایه پیدا کنیم که جمع آن دو عدد مساوی یک عدد شده x باشد. کمترین پیچیدگی زمانی حل این مسئله کدام است؟

1)

$Θ (n)$

2)

$Θ (n^{2})$

3)

$Θ (lo g n)$

4)

$Θ (n lo g n)$

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

7.

فرض کنید آرایه‌ای از اعداد صحیح $A = [a_{1}; a_{2}; \dots a_{n}]$ داده شود. فرض کنید یک اندیس (ناشناخته) k وجود دارد به‌طوری که زیر آرایه $A = [a_{1}; a_{2}; \dots a_{k}]$ به‌ترتیب اکیدا افزیشی مرتب شده است و زیر آرایه $A = [a_{k}; a_{k + 1}; \dots a_{n}]$ به‌ترتیب اکیدا نزولی مرتب شده است (یعنی اگر $1 \leq i < j \leq k$ آنگاه $a_{i} < a_{j}$ ، و اگر $k \leq i < j \leq n$ ، آنگاه $a_{i} > a_{j}$ هدف شما تعیین k است. یک الگوریتم بهینه برای حل این مسئله چه زمان اجرایی دارد؟

1)

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

2)

$Θ (n lo g n)$

3)

$Θ (n)$

4)

$Θ (lo g n)$

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

8.

کدام یک از موارد زیر درست است؟

1)

آرایه $A = [10; 3; 5; 1; 4; 2]$ یک max است.

2)

هر مسئله محاسباتی با اندازه ورودی n را می‌توان با یک الگوریتمی با زمان چند جمله‌ای برحسب n حل کرد.

3)

برای تمام توابع مثبت f(n)، g(n) و h(n)، اگر f(n)=O(g(n)) و $f (n) = Ω (h (n))$ باشد، آنگاه $g (n) + h (n) = Ω (f(n))$ است.

4)

اگر هر رقم جداگانه در RADIX SORT را با استفاده از INSERTION به‌جای COUNTING SORT مرتب کنیم، آنگاه PADIX SORT به‌درستی کار نمی‌کند (یعنی خروجی صحیح را تولید نمی‌کند).

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

9.

کدام مورد زیر مطمئنا عبارت $f (n) = Ω (g (n))$ را پشتیبانی می‌کند؟

1)

برای تمام $n \geq 1$ $f (n) \leq 4 \cdot g (n)$

2)

برای تمام $n \geq 136$ $f (n) \geq 4 \cdot g (n)$

3)

برای تمام $n \geq 100$ $f (n) \leq 4 \cdot g (n)$

4)

$lim_{n \to \infty} \frac{F ( n )}{g ( n )}$

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

10.

کدام یک از گزاره‌های زیر درست است؟

الف- اگر مسئله $P_{1}$ بتواند به مسئله $P_{2}$ در زمان خطی کاهش (reduce) باید، آنگاه اگر $P_{2}$ یک مسئله NP-hard باشد، می‌توان نتیجه گرفت $P_{1}$ نیز NP-hard است.

ب- یک Clique در یک گراف بدون جهت لزوما یک vertex cover در گراف مکمل نیست.

1)

فقط گزاره "الف" درست است.

2)

فقط گزاره "ب" درست است.

3)

هر دو گزاره "الف" و "ب" درست است.

4)

هر دو گزاره "الف" و "ب" نادرست است.

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

11.

کدام یک از گزاره‌های زیر درست است؟

الف- اینکه زمان حل یک مسئله P حد پایین $Ω (n^{2})$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند فقط برخی از نمونه‌های P وقتی به‌عنوان ورودی به A داده شوند، باعث می‌شود A زمان $Ω (n^{2})$ صرف کند.

ب- اینکه زمان حل یک مسئله P حد پایین $Ω (n^{2})$ دارد به این معنی است که برای هر الگوریتم A که P را حل می‌کند هر نمونه از P که به‌عنوان ورودی به A داده شود، باعث می‌شود A زمان $Ω (n^{2})$ صرف کند.

1)

فقط گزاره "الف" درست است.

2)

فقط گزاره "ب" درست است.

3)

هر دو گزاره "الف" و "ب" درست هستند.

4)

هر دو گزاره "الف" و "ب" نادرست هستند.

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

12.

کدام یک از گزاره‌های زیر درست است؟

الف- اگر یک الگوریتم زمان چندجمله‌ای برای یک مسئله که NP-hard است ارائه شود، آنگاه می‌توان نتیجه گرفت P=NP است.

ب- اگر یک مسئله NP-complete است، آنگاه می‌توان نتیجه گرفت که آن مسئله هیچ راه‌حلی ندارد.

1)

فقط گزاره "الف" درست است.

2)

فقط گزاره "ب" درست است.

3)

هر دو گزاره "الف" و "ب" درست هستند.

4)

هر دو گزاره "الف" و "ب" نادرست هستند.

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

13.

کدام یک از گزاره‌های زیر درست است؟

الف- اگر یک مسئله که به کلاس NP تعلق دارد یک راه‌حل زمان چند جمله‌ای داشته باشد، آنگاه $P = NP$ است.

ب- اگر کسی یک حد پایین زمان نمایی برای یک مسئله که NP-complete است بدهد، آنگاه $P \neq = NP$ است.

1)

فقط گزاره "الف" درست است.

2)

فقط گزاره "ب" درست است.

3)

هر دو گزاره "الف" و "ب" درست هستند.

4)

هر دو گزاره "الف" و "ب" نادرست هستند.

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

14.

مسئله کوله‌پشتی 0-1 را در نظر بگیرید که n شی با وزن صحیح داریم و گنجایش کوله‌پشتی عدد صحیح M است. این مسئله دارای یک الگوریتم مبتنی بر روش برنامه‌ریزی پویا با زمان O(M.n) است. این مرتبه زمانی برحسب اندازه مسئله چگونه است؟

1)

خطی

2)

درجه دو

3)

نمایی

4)

شبه چندجمله‌ای

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

15.

برای پیدا کردن k امین عدد در میان n عدد که به‌عنوان کلید در گره‌های یک درخت جستجویی دودویی متوازن ذخیره شده‌اند، کمترین پیچیدگی زمانی ممکن کدام است؟ (هر گره درخت فقط شامل کلید و اشاره‌گر به پدر و فرزند چپ و راست است.)

1)

$Θ (n)$

2)

$Θ (lo g n)$

3)

$Θ (n lo g n)$

4)

$Θ (n lo g n)$

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

16.

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

1)

$Θ (lo g lo g n)$

2)

$Θ (lo g n)$

3)

$Θ (n)$

4)

$Θ (n lo g n)$

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

17.

در یک درخت قرمز - سیاه، طول طولانی‌ترین مسیر ساده از یک گره x به یک برگ در زیر درخت خودش حداکثر چند برابر طول کوتاهترین مسیر از گره x به یک برگ در زیر درخت خودش است؟

1)

4

2)

3

3)

2

4)

1

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

18.

کدام یک از گزاره‌های زیر درست است؟

الف- هر درخت جستجوی دودویی دلخواه با n گره می‌توان به یک درخت جستجوی دودویی دلخواه دیگر با n گره با انجام O(n) عمل rotation تبدیل شود.

برای هر دو تابع f(n) و g(n) یکی از سه حالت $f (n) \in o (g (n)) (1)$ ، $f (n) \in w (g (n))$ و $f (n) \in θ (g (n)) (3)$ برقرار است.

1)

فقط گزاره "الف" درست است.

2)

فقط گزاره "ب" درست است.

3)

هر دو گزاره "الف" و "ب" درست هستند.

4)

هر دو گزاره "الف" و "ب" نادرست هستند.

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

19.

کمترین پیچیدگی زمانی ممکن برای مرتب‌سازی n عدد طبیعی که مقادیر کمتر از $n^{2}$ دارند، کدام است؟

1)

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

2)

$Θ (n^{2})$

3)

$Θ (n lo g n)$

4)

$Θ (n)$

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

20.

اگر عدد 363 را در یک درخت جستجوی دودویی، جستجو کنیم، کدام دنباله زیر نمی‌تواند دنباله‌ای از کلید گره‌هایی باشد که بررسی می‌شوند؟ (ترتیب از راست به چپ است.)

1)

363،397،344،330،398،401،252،2

2)

363،362،258،898،244،911،220،924

3)

363،278،381،382،266،219،387،399،2

4)

363،245،912،240،911،202،925

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