سوالات

فرض کنید تابع f بر [a,b] انتگرال‌پذیر باشد و تابع F:[a,b]→ℝ با ضابطه F(x)=∫ₐˣ f(t)dt تعریف شود. کدام گزینه درست است؟

در یک دستگاه ممیز شناور نرمال شده برای نمایش اعداد حقیقی در مبنای ۸ با ۳ رقم مانتیس و روش گرد کردن، فاصله بین عدد ۱۳ (در مبنای ۱۰) و نزدیک‌ترین عدد قابل نمایش بزرگ‌تر از ۱۳ چقدر است؟

جواب مسئله min_x Ax - b _2 که در آن، A = A^T ، x^() است اگر و تنها اگر ............... باشد.

اگر f(x) = sin ۲x، آنگاه مقدار کسرهای تفاضلی [۰,۰,۰]f و f[π/۲ , π/۲ , π/۲ , π/۲] به‌ترتیب برابرند با .................

فرض کنید f(x) = x^m(x^p - x^n) که در آن m ، p و n اعداد صحیح مثبت هستند. q(x) را چند جمله‌ای درون‌یاب برای m+p+1 دادهٔ متمایز (x_i, f(x_i)) ، i = 0, …, m+p ، بگیرید. در این‌صورت، f(x) ≡ q(x) اگر…

فرض کنید تابع f بر بازه [a,b] مشتق‌پذیر، h = b−a و b)f'(b)‏‎ ‎ ∫_a^b f(x)dx ≈ hf(b) - (h^۲)/۲f'(b) ‎. درجه دقت فرمول و خطای آن عبارت‌است از ...

انحراف معیار و صدک مرتبه ۲۵‌ام برای ۲۰ داده به ترتیب برابر صفر و ۱۰ است. میانگین داده‌ها کدام است؟

n نفر به تصادف روی n صندلی در یک ردیف می‌نشینند. احتمال اینکه دو نفر مشخص A و B کنار هم قرار نگیرند، کدام است؟

فرض کنید A یک مجموعهٔ n = ۲k عضوی باشد. تعداد زیرمجموعه‌های غیرتهی A که تعداد اعضای آن‌ها زوج باشد، کدام است؟

کیسه‌ای شامل ۳ سکه است که یکی از آن‌ها سالم می‌باشد. احتمال پشت شدن رو دو سکه ناسالم ۳/۵ و ۱/۱۰ است. یک سکه را به تصادف از کیسه انتخاب و سه بار پرتاب می‌کنیم. احتمال مشاهده پیشامد رو، رو، پشت کدام…

در جعبهٔ شمارهٔ یک، ۳ مهرهٔ سفید و ۲ مهره سیاه و در جعبهٔ شمارهٔ دو، ۵ مهرهٔ سفید و ۵ مهرهٔ سیاه وجود دارد. یک تاس سالم را پرتاب می‌کنیم. اگر عدد رو شده مضرب ۳ باشد، مهره‌ای به تصادف از جعبهٔ یک و در…

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

فرض کنید ‪( x = (x_1, x_2, ..., x_n‬ و ‪( y = (y_1, y_2, ..., y_m‬ دو لیست پیوندی خطی ساده باشند. مرتبه زمانی الگوریتمی که دو لیست را در لیست z ترکیب می‌کند، کدام است؟ z = (x_1, y_1, x_2, y_2, ……

در درخت جستجوی باینری زیر با حذف ریشه‌یک از عناصر زیر جایگزین می‌شود؟

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

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

اعداد ۱ تا ۶ به ترتیب از کوچک به بزرگ در ورودی یک پشته خالی (Stack) داده شده است و اعمال زیر بر روی پشته قابل انجام است: Push: کوچک‌ترین عدد ورودی را برداشته و در پشته قرار می‌دهد. Pop: عضو بالای…

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

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

تابع زیر آدرس ریشه یک درخت را دریافت می‌کند. این تابع چه عملی انجام می‌دهد؟ int func(TreeNode T) if (T == NULL) return(۰); else m۱ = ۱ + func(T → leftChild); m۲ = ۱ + func(T → rightChild); if(m۱ >…

فرض کنید با استفاده از تابع هش همانی h(x) = x که با استفاده از linear probing پیاده‌سازی شده است داده‌هایی را در یک آرایه قرار داده‌ایم و نتیجه به صورت زیر شده است. ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸…

در یک گراف دوبخشی که هر بخش آن 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 استفاده از کدام الگوریتم بیشترین کارآیی را دارد؟

اگر یک درخت AVL با یک گره دارای عمق صفر باشد، آنگاه کمترین و بیشترین تعداد گره در یک درخت AVL بالانس با عمق ۵ چقدر است؟

در یک هیپ (heap) با اندازه n حداکثر تعداد گره‌های چپ ریشه چند است؟

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

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

دو گرامر زیر را در نظر بگیرید. آنگاه کدام مورد صحیح است؟ G۱ : S → aS S → aSbS S → c G۲ : S₁ → T S₁ → U T → aTbT T → c U → aS₁ U → aTbU

زبان L کدام است؟ با این شرط که ε ∈ L ∀x,y ∈ L axby , bxay ∈ L ( n_a(x) : تعداد کاراکتر a در رشته x )

فرض کنید L ⊆ a ^() باشد، کدام جمله زیر صحیح است؟

برای کدام یک از زبان‌های زیر می‌توان یک NFA بدون ε ارائه داد که فقط دارای یک حالت پذیرش باشد؟

زبان‌های B_1= 1^k y 1^k y∈ 0,1 ^() و k≥ 1 و y شامل حداقل k تا یک و B_2= 1^k y 1^k y∈ 0,1 ^() و k≥ 1 و y شامل حداکثر k تا یک را در نظر بگیرید. کدام گزینه درست است؟

تفاوت ماشین‌های تورینگی که فقط زبان‌های منظم را می‌پذیرند با ماشین‌های تورینگ استاندارد کدام است؟

کدام‌یک از جملات زیر صحیح است؟

همهٔ عبارات زیر صحیح‌اند، به جز:

کدام یک از زبان‌های زیر مستقل از متن هستند ولی زبان منظم نیستند؟