سوالات

فرض کنید یک الگوریتم با زمان اجرای f(n) برای تعیین میانه اعضای یک آرایه n عضوی موجود است. به کمک این الگوریتم بهترین زمان اجرای الگوریتم مرتب‌سازی سریع، چقدر است؟

کدام مورد، درخصوص پیمایش BFS یک گراف همبند n راسی با شروع از راس v درست است؟

در مورد ادغام i لیست مرتب با مجموع تعداد اعضای n ، کدام مورد درست است؟

کدام مورد، درخصوص الگوریتم دایکسترا برای یافتن کوتاه‌ترین مسیر از گره v به سایر گره‌ها برای یک گراف n راسی و شامل m یال، درست نیست؟

زمان اجرای دو برنامه A و B در بدترین حالت به‌ترتیب از 150 nlg n و n^2 بیشتر نیستند. کدام مورد، درست است؟

ماتریس وزن‌ها برای یک گراف در زیر داده شده است، وزن درخت فراگیر با کمترین وزن در این گراف چقدر است؟ 0, 18, 9, 3, 7, 12 ; 18, 0, 14, 20, 13, 18 ; 9, 14, 0, 25, 16, 4 ; 3, 20, 25, 0, 5, 22 ; 7, 13, 16…

بهترین الگوریتم برای یافتن کوتاه‌ترین مسیرها بین تمام جفت رئوس (all pair shortest path) در یک گراف داده شده کدام است؟

اگر n اندازه ورودی الگوریتم و c و d اعداد ثابت باشند، مرتبه تابع بازگشتی زیر چیست؟ T(1) = c ; T(n) = 2T(n-1) + d,, n ≥ 2

حداقل مرتبه زمانی الگوریتمی که در یک گراف داده شده با n رأس و تعداد یال دلخواه، تمام مسیرهای ممکن بین دو رأس i و j را به‌دست می‌آورد، چیست؟

آرایه A شامل n عنصر مرتب (از اندیس 1 تا n ) و k عنصر نامرتب (از اندیس n+1 تا n+k ) است و k مستقل از n و بسیار کمتر از آن می‌باشد. کدام‌یک از الگوریتم‌های زیر برای مرتب‌سازی این آرایه به کمترین تعداد…

در الگوریتم کروسکال برای گراف زیر، کدام یال انتخاب نخواهد شد؟ گراف یک گراف کامل K_5 روی پنج رأس است. رئوس را T (بالا)، UL (بالا-چپ)، UR (بالا-راست)، BL (پایین-چپ)، BR (پایین-راست) بنامید. وزن یال‌ها…

کدام‌یک درخصوص الگوریتم دایکسترا (Dijkstra) نادرست است؟ ۱) برچسب قطعی رأس‌ها در طول الگوریتم به‌ترتیب غیرنزولی است. ۲) برای گراف با n رأس، زمان اجرا O(n^2) است. ۳) فقط برای گراف‌هایی که دور جهت‌دار…

حاصل جمع مجموع اعضای همه زیرمجموعه‌های A = 1, 2, 3, 4 چند است؟

با استفاده از درخت فضای حالت، کدام روش‌ها به‌ترتیب برای حل سه مسئله زیر مناسب است؟ مسئله n وزیر در صفحه شطرنج n × n رنگ‌آمیزی گراف مجموع زیرمجموعه‌ها (Subset Sum)

اگر f(n) تابعی از n باشد، چند مورد (موارد) صحیح‌اند؟ I - f(n) + O(f(n)) ∈ Θ(f(n)) II - f(n) ∈ Ω(√(f(n))) III - f(n) + f^2(n) + √(f(n)) ∈ Θ(f(n))

کدام کدها نمی‌توانند طبق الگوریتم هافمن، به‌عنوان بخشی از کدگذاری برای کاراکترها همزمان تولید شوند؟

حاصل رابطه بازگشتی زیر چیست؟ T(n) = 2T(n/4) + n^(0/51), n > 1 ; T(1) = 1, n = 1

خروجی شبه کد زیر، از چه مرتبه‌ای است؟ k = 0 for(i = n , i > 0 , i--) for(j = i, j > 0, j--) k = k + i j print (k) ( x-- یعنی یک واحد کم‌کردن از x )

اگر n توان صحیحی از ۳ باشد، خروجی شبه‌کد زیر چند است؟ i = ۱ j = ۱ while (i < n) i = i ۳ j = j ۳ print(j)

با توجه به رابطه بازگشتی زیر، T(n) از چه مرتبه‌ای است؟ T(n^۳) = T((n-۱)^۳) + θ(n) ; T(۱) = ۱

الگوریتم مرتب‌سازی سریع (Quick Sort) روی دنباله ۱، ۲، ۳، ۴، ۵، ۶ و ۷ در کمترین حالت به چند مقایسه نیاز دارد؟ ( 7log_2 7 ≅ 19/6 )

آخرین رأس انتخاب‌شونده با الگوریتم جستجوی سطح اول (BFS) و نیز با الگوریتم جستجوی عمق اول (DFS) روی گراف زیر و با شروع از S به‌ترتیب از راست به چپ کدام است؟ (هرگاه می‌توان بین چند رأس انتخاب داشت…

الگوریتم جستجوی عمق اول (DFS) را روی یک گراف با n رأس و m یال و با شروع از رأس s اجرا کرده‌ایم. چند بار با یال‌هایی مواجه می‌شویم (سروکار داریم) که یک سر آنها s است؟

با اجرای الگوریتم کروسکال روی گراف زیر و با شروع از رأس S وزن چهارمین یال انتخاب شونده در درخت چند است؟

مرتبه زمانی سریع‌ترین الگوریتم برای مسئله زیر، کدام است؟ ورودی: یک گراف G با n رأس و m یال و یک رأس S از G خروجی: تعداد رأس‌هایی از G که فاصله آنها از S برابر با ۲ است.

الگوریتم دایکسترا روی گراف زیر اجرا کرده‌ایم. وزن پنجمین یالی که در الگوریتم در نظر گرفته می‌شود (relax یا به‌روزرسانی می‌شود) کدام است؟

G یک گراف کامل صد رأسی وزن‌دار است. یک پاسخ مسئله فروشنده دوره‌گرد (TSP) را روی آن A می‌نامیم. وزن همه یال‌های G را در ۳ ضرب و سپس با ۵ جمع می‌کنیم. یک پاسخ مسئله فروشنده دوره‌گرد روی گراف حاصل را B…

T یک درخت ریشه‌دار با ریشه r است و هر رأس x به آن یک وزن w(x) دارد. کدام رابطه بازگشتی منجر به یک الگوریتم پویا (dynamic) برای محاسبه وزن مسیری که از r شروع می‌شود که از S شروع می‌شود و مجموع وزن…

مقدار برش کمینه (min cut) میان s و t در گراف زیر، کدام است؟ شبکه‌ی جهت‌دار دارای مبدأ s ، دو رأس میانی چپ a (بالا) و b (پایین)، دو رأس میانی راست c (بالا) و d (پایین)، و مقصد t است، با ظرفیت یال‌ها…

فرض کنیم P ≠ NP . کدام مسئله یا مسائل زیر دارای الگوریتم چندجمله‌ای است؟ الف) ورودی: عدد طبیعی n و اعداد حقیقی مثبت a_1, ⋯, a_n و b_1, ⋯, b_n . خروجی: یک مجموعهٔ I ⊆ 1, ⋯, n به‌طوری که ∑_(i ∈ I) b_i…

کدام گزاره یا گزاره‌ها، درست است؟ الف ـ مسائل تصمیم‌گیری (یعنی مسائلی که جوابشان بله یا خیر است) دارای الگوریتم تقریبی (تخمینی، approximation) با فاکتور (ضریب تقریب) ۲ نیستند. ب ـ اگر مسئله‌ای دارای…

خروجی الگوریتم زیر از چه مرتبه‌ای است؟ j = ۰ i = ۱ while(i ≤ n) j = j + ۲i i = ۴i print j

با توجه به رابطه بازگشتی زیر، (T(n از چه مرتبه‌ای است؟ T(۲^n) = T(۲^(n-1)) + Θ(n^۲) ; T(۱) = Θ(۱)

هنگامی‌که می‌خواهیم نشان دهیم زمان یا حافظه یک الگوریتم، حداقل از مرتبه تابعی مانند f : N → R^(+) است، از کدام نماد باید استفاده کنیم؟

الگوریتم مرتب‌سازی سریع (Quick sort) را روی آرایه‌ای شامل ۴ عدد اجرا می‌کنیم. تعداد مقایسه‌ها چه عددی نمی‌تواند باشد؟

دو الگوریتم BFS (جستجوی اول سطح) و DFS (جستجوی اول عمق) را روی گراف زیر و با شروع از رأس S اجرا می‌کنیم. در هر گام از BFS یا DFS اگر چند رأس برای انتخاب وجود داشت، رأسی را انتخاب می‌کنیم که از نظر…

پیاده‌سازی معمولی کدام مورد با داده ساختار پشته (stack) انجام می‌شود؟

G یک گراف همبند با n رأس و e یال است. همچنین می‌دانیم که وزن همه یال‌های G یکسان است. بهترین زمان برای یافتن یک زیردرخت فراگیر (پوشای) کمینه G از چه مرتبه‌ای است؟

می‌خواهیم تشخیص دهیم که آیا یک دنباله‌ی داده‌شده، دنباله‌ی مقایسه‌های یک جستجوی دودویی است یا خیر. بهترین زمان برای این کار از چه مرتبه‌ای است؟

الگوریتم دایکسترا را روی گراف زیر و با شروع از رأس s اجرا می‌کنیم. فاصله a از s در ابتدا ∞+ در نظر گرفته می‌شود. هنگام اجرای الگوریتم، فاصله a از s چند بار تغییر می‌کند؟