سوالات

فرض کنید p(x) چندجمله‌ای درونیاب تابع جدولی (n, n^۴) : n = ۱,۲,...,۵ باشد. نقاط (۵,۶۲۵) و (۴,۲۵۶) را از تابع جدولی حذف کرده و چندجمله‌ای درونیاب تابع جدولی جدید را p_۱(x) می‌نامیم. حاصل عبارت…

با اعداد ۱ تا ۵ چند عدد حداکثر ۱۰ رقمی می‌توانیم بسازیم؟

اگر P(A B) > P(A) باشد. آنگاه کدام‌یک از موارد زیر درست است؟

از بین ۳ مرد و ۲ زن می‌خواهیم ۳ نفر را به تصادف انتخاب کنیم. احتمال این‌که اکثریت با مردها باشد چقدر است؟

در یک مهمانی ۵ نفر کلاه‌های خود را روی هم می‌ریزند و هر کدام به‌طور تصادفی یک کلاه بر می‌دارد. احتمال این‌که دقیقاً دو نفر کلاه خود را بردارند، چقدر است؟

نمودار جعبه‌ای خوشه‌ای برای میزان چاقی به تفکیک جنسیت به‌صورت زیر رسم شده است. کدام مورد درخصوص این نمودار درست است؟ (نمودار جعبه‌ای: محور عمودی میزان چاقی با درجه‌بندی ۱۰، ۲۰، ۳۰، ۴۰ است. برای مردها…

آرایه A حاوی n بیت است. فرض کنید A یکی از دو گونه زیر است: گونه ۱: نیمی از درایه‌های A حاوی بیت صفر و نیم دیگر حاوی بیت ۱ (بدون ترتیب) است. گونه ۲: A در مجموع ۲/۳n صفر و ۱/۳n یک دارد. به‌شما آرایه A…

آرایه A شامل n عدد صحیح در مکان A[۱]⋯ A[n-۱] و A[۰] است. لازم است عناصر آرایه به‌صورت چرخه‌ای به‌اندازه k مکان به سمت چپ منتقل شوند، که در آن ۰ ≤ k ≤ n-۱ است. یک الگوریتم ناقص برای انجام این کار در…

فرض کنید P یک لیست تک‌پیوندی باشد و همچنین Q اشاره‌گری به گره‌ی میانی X در لیست باشد. پیچیدگی زمانی بهترین الگوریتم شناخته شده برای حذف گره Q از لیست چیست؟

فرض کنید G یک گراف بدون جهت وزن‌دار و e یالی با حداکثر وزن در G باشد. فرض کنید یک درخت پوشای با حداقل وزن در G وجود دارد که شامل یال e است. کدام‌یک از عبارات زیر همواره درست است؟

بدترین حالت پیچیدگی زمانی درج n^۲ عنصر در یک درخت AVL با n عنصر اولیه چیست؟

هنگام جستجوی مقدار کلید ۶۰ در یک درخت جستجوی دودویی، گره‌های حاوی مقادیر کلید ۱۰، ۲۰ و ۴۰ و ۵۰ و ۷۰ و ۸۰ و ۹۰ پیمایش می‌شوند. (نه لزوماً به‌ترتیب داده شده). چند ترتیب مختلف ممکن است که با این مقادیر…

یک درخت دودویی کامل را درنظر بگیرید که زیر درخت‌های چپ و راست ریشه ماکزیمم ـ هیپ هستند. حد پایین برای تعداد عملیات تبدیل درخت به ماکزیمم ـ هیپ برابر است با:

یک جدول هش به‌طول ۱۰ از آدرس‌دهی باز با تابع هش h(k) = k mod 10 و کاوش خطی استفاده می‌کند. پس از قراردادن ۶ مقدار در یک جدول هش خالی، جدول به‌صورت زیر در می‌آید. اندیس مقدار --- --- ۰ ۱ ۲ ۴۲ ۳ ۲۳ ۴…

فرض کنید یک درخت جستجوی دودویی (BST)، با n گره داریم که اعداد ۱ تا n را به‌صورت نامرتب در خود ذخیره کرده است. الگوریتم بازگشتی زیر روی این درخت اجرا می‌شود: Algorithm mys(node): if node == NULL…

در یک گراف همبند بدون وزن می‌خواهیم کم‌تعدادترین یال‌ها را از یک گره مبدأ به گره مقصد طی کنیم. کدام روش زیر کمترین یال‌ها را تضمین می‌کند؟

پیچیدگی زمانی الگوریتم زیر را بیابید؟ Void func(int n) if (n <= 1) return; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) Printf(""); func(n/2); func(n/2);

الگوریتم عقب‌گرد برای تعیین همهٔ دورهای هامیلتونی در یک گراف همبند و بدون جهت G با n رأس را درنظربگیرید. تعداد گره‌ها در درخت فضای حالت این الگوریتم کدام است؟

منابع شما هم به‌میزان محدود R = ۵۰ می‌باشد. اطلاعات این پروژه‌ها در جدول زیر داده شده است. اگر از الگوریتم حریصانه براساس نسبت بیشترین سود به منابع استفاده کنیم کدام پروژه‌ها انتخاب و سود کل چقدر…

تعداد (۹) فایل مرتب‌شده با اندازه‌های ۳ و ۷ و ۸ و ۹ و ۱۵ و ۱۶ و ۱۷ و ۲۰ و ۲۳ مفروض است. می‌خواهیم این ۹ فایل را سه‌به‌سه با هم ادغام کرده و فایل مرتب‌شده واحدی به‌دست آوریم. حداقل تعداد جابه‌جایی‌ها…

کدام مورد درخصوص الگوریتم عقب‌گرد درست نیست؟

الگوریتم زیر، اندیس بزرگ‌ترین عنصر آرایه A را توسط j برمی‌گرداند. با فرض آن که عناصر آرایه A ، اعداد صحیح متمایز و متساوی‌الاحتمال باشند در این صورت میانگین زمان اجرای دستورالعمل d یعنی j = i کدام…

چند تا از گزاره‌های زیر درست است؟ الف) f(n) = o(g(n)) اگر و تنها اگر g(n) = ω(f(n)) ب) f(n) = O(g(n)) اگر و تنها اگر g(n) = Ω(f(n)) ج) n = ω(log n) د) dfrac n^۳ log n = θ(n^۲)

فرض کنید الگوریتم DFS روی گراف ارائه شده اجرا شده و همیشه راس‌ها به‌ترتیب الفبایی انتخاب می‌شوند. در پایان اجرای الگوریتم DFS زودترین خروج تا دیرترین خروج کدام است؟ (منظور از خروج، اتمام ملاقات راس…

مسئله زمان‌بندی فعالیت‌ها با مهلت که در آن n فعالیت داریم را درنظربگیرید. برای فعالیت i یک مهلت d_i و یک ارزش P_i منصوب است. برای فعالیت i ارزش P_i زمانی حاصل می‌شود که این فعالیت در مهلت d_i به…

اگر در روش کدگذاری هافمن، فراوانی داده اول از مجموع فراوانی n-1 داده دیگر بیشتر بوده و فراوانی n-1 عضو ذکر شده با هم برابر باشند، آنگاه طول کد تولید شده حداکثر چقدر است؟

فرض کنیم L زبان عبارت منظم r = (۰^۱۰^)(۱۰^۱۰^)^ باشد. با فرض β = (۰۱)^۱۴۰۴ ∘ (۱۰۱)^۱۴۰۵ و α = (۱۰۰)^۱۴۰۴ ، کدام گزینه درست است؟

فرض کنیم L زبان اتوماتای متناهی معیّن (DFA) زیر روی الفبای ۰,۱ باشد. این اتوماتا چهار حالت دارد: حالت آغازین q_0 (پذیرنده) با گذارهای q_0xrightarrow ۰ q_0 و q_0xrightarrow ۱ q_1 ؛ حالت q_1 (پذیرنده)…

فرض کنیم L زبان گرامر زیر با متغیر شروع S باشد: S → ES ε E → aEb ε اگر α = (a^۲b^۲)^۱۴۰۴(a^۳b^۳)^۱۴۰۵ و β = (a^۳b^۳)^۱۴۰۴(a^۲b^۲)^۱۴۰۵ کدام گزینه درست است؟

فرض کنیم L_1 = w a^2k w ∈ a, b ^, w = k و L_2 = a^k w w ∈ a, b ^, w = k . از این دو زبان کدام منظم است؟

فرض کنیم L_1 = a^n b^m : n ≠ 2m و L_2 = a^n b^m : n ≤ m^2 . از این دو زبان کدام مستقل از متن است؟

فرض کنید دو زبان زیر روی الفبای a,b,c تعریف شده باشند: L_1 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = n_c(w) L_2 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = 2^(n_c(w)) از این دو زبان کدام مستقل از متن است؟

زبان L_1 روی a,b به‌صورت بازگشتی با دو قانون زیر تعریف می‌شود: الف ـ λ ∈ L_1 ب ـ اگر x ∈ L_1 آنگاه aabx ∈ L_1 و xbb ∈ L_1 . به‌علاوه فقط رشته‌هایی در L_1 هستند که از دو قانون بالایی به‌دست آمده…

(… نماد c جایگزین بالای پشته شود. ) شکل زیر یک ماشین پشته‌ای (PDA) است که زبان L_۱ را می‌پذیرد؛ برچسب هر یال به‌صورت «ورودی، بالای پشته / جایگزین» خوانده می‌شود: حالت شروع q_0 با دو حلقه: a, a/aa و…

ماشین تورینگ زیر براساس الفبای ورودی a, b (با نماد تهی □ و نماد نشانه‌گذاری x ) به‌صورت زیر تعریف شده است (نمودار حالت‌ها): q_0 xrightarrow a → □, R q_1 q_1 xrightarrow a → a, R q_1 ، q_1 xrightarrow…

اگر A متغیر و S متغیر شروع باشد، از دو گرامر زیر کدام‌یک در فرم نرمال چامسکی هستند؟ گرامر «الف»: S → AS a A → SA b گرامر «ب»: S → AS a A → SA aa

از این دو استدلال کدام معتبر است؟ a ـ تمام اعداد حقیقی، عدد منفی هستند. بعضی اعداد حقیقی مثبت هستند. بنابراین: بعضی اعداد منفی، مثبت هستند. b ـ هیچ عدد منفی، عدد مثبت نیست. بعضی اعداد مثبت، عدد طبیعی…

کدام مورد معادلِ عبارت زیر است؟ چنین نیست که (پذیرفته شدن علی در دانشگاه شرط لازم برای موفقیت علی است.)

فرض کنید B(x) : x باهوش است A(x) : x آدم است کدام مورد معادل عبارت زیر است: چنین نیست که (تمام آدم‌ها باهوش هستند.)

فرض کنید S(x) : x ورزشکار است. M(x) : x مربی است. E(x, y) : x مورد اعتماد y است. کدام مورد بهترین ترجمه برای عبارت زیر است: «هرکسی مورداعتماد ورزشکاران است، مورداعتماد حداقل یک مربی است.»