سوالات

آرایه نامتناهی A را در نظر بگیرید. فرض کنید در n خانه اول این آرایه n عدد صحیح متمایز به‌صورت مرتب شده (صعودی) قرار گرفته‌اند و بقیه خانه‌های آرایه با ∞ پر شده است. بازای عدد x داده شده می‌خواهیم…

فرض کنید G یک گراف بدون جهت و بدون وزن با n رأس و m یال باشد. مسئله زیر را در نظر بگیرید: به‌ازای دو رأس u و v داده شده و پارامتر ورودی k، آیا تعداد کوتاه‌ترین مسیرها بین u و v حداقل k است؟ کدام…

یک ماتریس ۶۴ در ۶۴ داریم که درایه‌های آن همه ۰ یا ۱ هستند. می‌خواهیم این ماتریس را به‌صورت مارپیچی مرتب کنیم، یعنی اگر در انتها، سطر اول از راست به چپ به سطر دوم از راست به چپ و … بچسبانیم یک آرایهٔ…

کدام‌یک از مسائل زیر را می‌توان در زمان O(n^(۲/۵)) حل کرد؟ الف) پیداکردن کوتاه‌ترین مسیر بین هر دو رأس در گراف وزن‌دار با n رأس ب) ضرب دو ماتریس n × n ج) پیداکردن تعداد جفت رئوسی که همسایهٔ مشترک…

فرض کنید ۱۰۰T در اختیار داریم. جدول نرخ تبدیل ارزها در زیر داده شده است. به‌عنوان نمونه طبق جدول زیر هر ۱E برابر ۳۰T می‌باشد. می‌خواهیم با چندین بار تبدیل پول و نهایتاً تبدیل آن به T درآمد کسب کنیم.…

متنی که هر حرف از چهار نویسه‌ی a,b,c,d است را با الگوریتم هافمن کدگذاری کرده‌ایم. طول کد هافمن این متن ۲۰۲۱ بیت شده است. طول کد چهار نویسه‌ی فوق در کدگذاری هافمن کدام است؟

گراف بدون جهت و وزن‌دار G و رأس مشخص s از این گراف را درنظر بگیرید. از الگوریتم دایکسترا برای محاسبه کوتاه‌ترین مسیر ساده از s به بقیه رئوس استفاده کرده‌ایم. به‌ازای چند حالت زیر این الگوریتم با وجود…

سالن مربعی شکل در اختیار داریم که مختصات گوشه چپ ـ پایین آن (۰,۰) و مختصات گوشه راست ـ بالا آن (۱۰,۱۰) است. چهار نفر در این سالن در مکان‌های (۹,۴) ، (۵,۸) ، (۴,۳) ، (۱,۷) قرار گرفته‌اند. می‌خواهیم از…

آرایه‌ای شامل n عدد را در نظر بگیرید. در هر پرسمان، می‌توانیم دو اندیس i و j را که اندیس شروع و پایان یک بازه از آرایه هستند به ما بدهیم و به ما مجموع اعداد بازه داده می‌شود. هدف پیداکردن بازه‌ای است…

دو دنباله که هر کدام یک جایگشت از اعداد ۱ تا n هستند، داده شده است. بزرگ‌ترین زیر دنبالهٔ مشترک این دو دنباله را در چه زمانی می‌توان به‌دست آورد؟

می‌خواهیم k لیست مرتب، هرکدام با n/k عنصر را در هم ادغام کنیم و لیست مرتب n تایی ایجاد کنیم. برای این کار ابتدا لیست ۱ را با لیست ۲ ادغام می‌کنیم. سپس لیست حاصل را با لیست ۳ و به همین روند ادامه…

آرایه A به طول n به‌صورت حلقوی مرتب است. یعنی اگر ابتدا و انتهای A را به هم بچسبانیم از یک درایه به بعد آرایه مرتب است. برای مثال آرایه [۶۰, ۷۰, ۸۰, ۱۰, ۲۰, ۳۰, ۴۰, ۵۰] به‌صورت حلقوی مرتب است. بهترین…

کدام گزینه مرتبه رابطه بازگشتی T(n) = 2T(⌊√n⌋) + log n را نشان می‌دهد؟

در گونه‌ای از مرتب‌سازی سریع، برای انتخاب محور از میان n عنصر ۲√n+۱ عنصر اول آرایه را انتخاب می‌کنیم و با یک الگوریتم ساده مانند مرتب‌سازی درجی آن را مرتب می‌کنیم. عنصر میانه این تعداد عنصر مرتب را…

[بخش ابتدایی صورت مسئله در تصویر برش خورده است؛ متن زیر بر پایهٔ گزینه‌ها بازسازی شده و جملهٔ پایانی عیناً همان چیزی است که در تصویر دیده می‌شود.] فرض کنید n کاراکتر با فراوانی‌های a, ۲a, ۴a, ……

در یک گراف بدون جهت و وزن‌دار، کدام‌یک از گزینه‌های زیر در مورد درخت پوشای کمینهٔ تولیدشده توسط الگوریتم Prim و Kruskal درست است؟

کاوشگری روی سیاره‌ای ناشناخته، سطح را به ۱۶ بخش تقسیم می‌کند. او می‌خواهد بداند کدام بخش بیشترین میزان ماده معدنی دارد. الگوریتم او ابتدا هر بخش را به دو نیمه تقسیم می‌کند، مقدار هر نیمه را می‌سنجد و…

تیمی از نجاتگران باید کوه بزرگی را برای یافتن گمشدگان جست‌وجو کنند. رهبر گروه منطقه را به چند بخش تقسیم می‌کند، هر تیم بخشی را جست‌وجو می‌کند، سپس گزارش‌ها جمع‌آوری می‌شوند تا تصمیم گرفته شود که در…

متنی شامل ۷۰۰۰ حرف از حروف a، b، c، d، e و f با دفعات تکرار به‌ترتیب ۱۰۰۰ و ۱۲۰۰، ۸۰۰، ۱۵۰۰، ۱۸۰۰ و ۷۰۰ موجود است. چنانچه بخواهیم کدی بهینه برای حروف بالا انتخاب کنیم تعداد کل بیت‌های لازم برای تبدیل…