سوالات

در مورد الگوریتم فلوید (برای محاسبه کوتاه‌ترین مسیر در گراف وزن‌دار) کدام گزینه صحیح است؟

در الگوریتم مرتب‌سازی ادغامی (Merge sort) برای مرتب‌سازی لیست‌های زیر ۲۰ عنصری از الگوریتم مرتب‌سازی درجی (Insertion sort) استفاده می‌کنیم، در این‌صورت پیچیدگی زمانی الگوریتم چه خواهد شد؟

کمترین تعداد محاسبات برای ضرب دنباله‌ای از چهار ماتریس زیر کدام است؟ A_(۲× ۵) × B_(۵× ۴) × C_(۴× ۲۰) × D_(۲۰× ۱۰)

مرتبه زمانی الگوریتم زیر کدام است؟ f(n) x = ۲; y = ۱; while (y <= n) y = y × x; x = x × x;

فرض کنید در برنامه زیر C = aux(A,B) دو ماتریس A و B با اندازه n×n را در هم ضرب کرده و نتیجه را در C برمی‌گرداند. مقدار برگشتی تابع زیر برای ماتریس M کدام است؟ Mat(M) P = M ; Q = M for i = ۱ to n-۱ do…

در صورتی که جدول فراوانی نسبی کاراکترهای زیر را داشته باشیم، با استفاده از روش رمزگذاری هافمن معادل رمزگذاری‌شدهٔ کلمهٔ DATA کدام است؟ (به پیوند چپ مقدار صفر و به پیوند راست مقدار یک را نسبت دهید). A…

در یک گراف دوبخشی که هر بخش آن n/2 رأس داشته باشد مسأله پوشانی کمینه درخت (MST) را می‌توان در چه زمانی حل کرد؟

رابطه دنباله عددی G که توسط تابع زیر تولید می‌شود با دنباله عددی فیبوناچی کدام است؟ G(۰) = ۰ G(n) = n - G(G(n-۱)) n > ۱

فرض کنید SAT نشان‌دهندهٔ مسئله تصمیم‌گیری صدق‌پذیری و HAM نشان‌دهندهٔ مسئله تصمیم‌گیری گراف هامیلتونی باشد. در این صورت همه جملات زیر صحیح‌اند، به جز:

اگر T(n) = 2T(n/4) + θ(1) از مرتبه θ(√n) باشد، آنگاه T(n) = 2T(n/4) + θ(√n) از کدام مرتبه است؟

اگر U(m) = T(r^m) و T(n) = T(n/۲) + log n باشد، آنگاه رابطه بازگشتی U کدام است؟

یک گراف وزن‌دار در نظر بگیرید که وزن تمام یال‌های آن ۱ است. برای یافتن مسیر کمینه بین دو رأس u و v استفاده از کدام الگوریتم بیشترین کارآیی را دارد؟

آرایه n عضوی A را k چرخش مرتب شده می‌گوییم اگر بتوان اعداد آن را با k چرخش مرتب نمود. برای مثال [۳۵،۴۲،۵،۱۵،۲۷،۲۱] یک ۲ چرخش مرتب شده است. بهترین الگوریتم برای پیدا کردن ماکزیمم در چنین آرایه‌ای…

فرض کنید می‌خواهیم n داده را با عوض کردن داده‌ها مرتب کنیم. در الگوریتم این محدودیت را اعمال می‌کنیم که عناصر A[i] با A[j] نمی‌تواند با هم عوض بشود مگر اینکه n√ > i − j باشد. بهترین حد پایین زمانی…

اگر f_k نشان‌دهندهٔ kامین عدد در دنبالهٔ فیبوناچی باشد، بهترین زمان برای محاسبه f_(n^۲) چیست؟

می‌خواهیم در یک آرایه از اعداد صحیح به طول n اندیس‌های i و j و k را پیدا کنیم که x[i]^Y + x[j]^Y = x[k]^Y باشد. بهترین زمان ممکن برای این کار کدام است؟

در یک گراف غیرجهت‌دار با n رأس و e یال جمع درجه تمام رئوس کدام است؟

اگر به یک آرایه عددی مرتب شده یک عنصر تصادفی اضافه کنیم، کدام الگوریتم بـرای مرتـب‌سـازی آن دارای بهترین زمان است؟

تابع زمانی قطعه برنامه زیر کدام است؟ r = ۰ for i = ۱ to n for j = ۱ to i for k = j to i+j r = r + ۱

در یک آرایهٔ عددی A به طول m برخی از عناصر ۱ تا n که m<n است، ظاهر شده‌اند. بهترین الگوریتم برای یافتن بزرگ‌ترین عنصری که در آرایه ظاهر نشده است، دارای چه مرتبه زمانی است؟

اگر T(n) = ∑_(i=۱)^n (i + ۱/i) باشد، حاصل نهایی T(n) کدام است؟

اگر A_(۶×۱۵) و B_(۱۵×۲۵) و C_(۲۵×۱۰) و D_(۱۰×۱۷) باشد، برای محاسبهٔ ABCD کدام پرانتزگذاری سریع‌تر است؟

در رابطه با استفاده از الگوریتم heapsort به‌عنوان الگوریتم مرتب‌سازی کمکی در مرتب‌سازی radix کدام جمله درست است؟

در نوشته‌ای تعداد تکرار حروف A، B، C، D، E و F به ترتیب ۲۰۰، ۱۸۰، ۱۵۰، ۴۰، ۳۰ و ۲۰ بار می‌باشد. چنانچه آن نوشته را با استفاده از روش هافمن کد کنیم، طول کد تولید شده چند بیت خواهد بود؟

فرض کنید A و B دو مسئلة تصمیم‌گیری بوده و A ≤_p B باشد ( A در زمان چندجمله‌ای به B کاهش یابد). کدام گزینه درست است؟

کدام یک از الگوریتم‌های زیر حریصانه می‌باشد؟ a = Fractional knapsack b = Dijkstra c = Bellman − ford d = kruskal

۸۴- در جستجوی عمق اول (Depth First Search) گراف زیر با فرض آنکه گره A گره مبدأ باشد و گره‌های مجاور به یک گره به ترتیب حروف الفبای انگلیسی ملاقات شوند، کدام مورد به ترتیب ملاقات گره‌ها را نمایش…

تابع زیر از چه مرتبه‌ای است؟ T(n) = ۲ T (⌊ √n ⌋) + log n

یک آرایه از اعداد صحیح به‌طول n و عدد x داده شده است. می‌خواهیم تعداد سه‌تایی‌هایی به فرم (i, j, k) که x = A[i]+A[j]+A[k] را بیابیم (آرایه ممکن است شامل اعداد منفی نیز باشد). پیچیدگی زمانی بهینه از…

کدام‌یک از الگوریتم‌های مرتب‌سازی زیر پایدار (Stable) است؟

در مورد الگوریتم هافمن کدام مورد درست است؟

مرتبه زمانی T(n) کدام است؟ T(۱) = ۵ ; T(n) = n + ۱ + T (n/۲)

n عدد صحیح k رقمی داریم ( k ثابت و مستقل از n هست) کدام مورد دقیق‌تر است؟

فرض کنید T(x) = ۱/۲T(x/۲) + θ(۱/x) . پیچیدگی رابطه T کدام است؟

یک گراف جهت‌دار G=(V,E) مدلی برای یک شبکه کامپیوتری با n رأس است. وزن w(u,v) روی یال (u,v) ، احتمال خراب‌نبودن (سالم‌بودن) لینک (u,v) است. فرض کنید لینک‌ها مستقل از یکدیگر خراب می‌شوند، بنابراین…

n فایل داریم که طول فایل i اُم L_i و احتمال دسترسی به آن P_i است که به ما داده شده است. می‌خواهیم این فایل‌ها را طوری پشت سرهم قرار دهیم که میانگین زمان دسترسی به فایل‌ها کمینه شود. به عبارت دیگر…

چند تا از گزاره‌های زیر صحیح است؟ اگر g(n) = o(f(n)) (نماد o کوچک) آنگاه f(n) = ω(g(n)) . اگر lim_(n → +∞) (f(n))/(g(n)) = ∘ آنگاه f(n) = o(g(n)) . برای هر ثابت c > ∘ و هر ثابت a > ۱ و هر تابع صعودی…

فرض کنید آرایه‌ای از n عنصر داده شده است و می‌خواهیم میانه (Median) آن را با استفاده از روش تقسیم و حل (Divide and Conquer) پیدا کنیم. کدام‌یک از گزینه‌های زیر درباره الگوریتمی که این مسئله را…

برای کدام‌یک از مسائل زیر، الگوریتم با زمان چندجمله‌ای پیدا شده است؟ الف ــ کوله‌پشتی کسری ب ــ تعیین نزدیک‌ترین زوج نقطه بین چند نقطه داده شده در صفحه

فرض کنید یک جدول n × n دارید و می‌خواهید در هر خانه از این جدول یک عدد بین ۱ تا k قرار دهید، به‌طوری‌که: هر عدد در هر سطر و هر ستون منحصربه‌فرد باشد (مانند جداول سودوکو). برخی خانه‌ها از قبل پر…