1 - پیچیدگی زمانی قطعه کدهای زیر را با راه حل بدست آورید.
الف )
while (m!=n)
{
if (m>n)
m=m-n;
else
n=n-m;
}
ب )
for (i=1;i<=n;i=i*2)
{
for (j=1;j<=n;j=j*2)
{
for (k=1;k<=j;++k)
{
System.out.println.("*");
}
}
}
ج )
for (i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
x++;
j=1;
while (j<n)
{
x++;
j=j*2;
}
}
ت )
for (i=0;i*i<n;++i)
System.out.println.("*");
2 - فرض کنید یک آرایه به طول n که شامل اعداد طبیعی است در اختیار دارید. الگوریتم مرتب سازی این آرایه به صورت زیر عمل می کند.
ابتدا کوچکترین عنصر را در آرایه پیدا می کند ، سپس index مقدار کوچکتر عوض می شود. این عمل را وقتی که آرایه مرتب شود تکرار می گردد.
کد این الگوریتم را بنویسید.
3 - الگوریتم های زیر را توضیح دهید.
Quick Sort
Merge Sort
Insertion Sort
Selsction Sort
کدام یک از الگوریتم های بالا ، بهترین انتخاب برای مرتب سازی مقادیر بسیار زیادی از داده های نامرتب است؟ پیچیدگی زمانی آ را به صورت بازگشتی بدست آورید.
4 - نرخ رشد توابع زیر را از کمترین به بیشترین مرتب کنید.
\[ n!\;,\;nlg(n^5)\;,\;n^3\;,\;3^n\;,\;10^{lg\;n)}\;,\;(2n)^2\;,\;\sqrt{n}\;,\;\sqrt[4]{n}\]
5 - درستی یا نادرستی عبارات زیر را با ذکر دلیل بیان کنید.
\[ \begin{matrix}T(n)= 3n^2+3^n+n\;lg\;2\\T(n)= \theta (n^2) \\T(n)= \theta (3^n) \\T(n)= \Omega ((3^n)lg\;n) \\T(n)= O(n^3)\end{matrix}\]
6 - روابط بازگشتی زیر را حل کنید.
\[ \begin{matrix} T(n)=3T(\frac{n}{2})+n\\T(n)=2T(n-1)+\frac{n}{2}\end{matrix}\]
7 - روابط زیر را ثابت کنید.
8 - رابطه بازگشتی کدهای زیر را نوشته و سپس آن را حل کنید.
الف )
public static void func(int n){
if(n = = 1) return:
for(int i=0 ; i<4 ; i++)
func(n-1);
}
ب )
public static void func2(int n){
if(n<=1) return:
func2(n/2);
func2(n/3);
for(int i=0 ; i<n : i++)
func3();
} // func3 = O(1)
9 - کدام یک از گزینه های زیر صحیح و کدام غلط است؟
\[ \begin{matrix} n^3 log(n)=O(n^{3+\varepsilon })\;\;\;,\;\;\;\varepsilon >0\\\frac{n^2}{log(n)}=\Omega (n^2) \\ h(n)\in \Omega (g(n))\;\;,\;\; f(n) \in O(g(n))\;\;\Rightarrow \;\; f(n)\in \Theta(h(n))\\h(n)\in \Omega (g(n))\;\;,\;\; g(n) \in \Theta(h(n))\;\;\Rightarrow \;\; f(n)\in \Omega(h(n))\end{matrix}\]
10 - به ازای k>1 و 0.5>epsilon کدام صحیح است؟
11 - آرایه A حاوی n بیت است. فرض کنید A یکی از دو گونه زیر است:
گونه 1 : نیمی از درایه های A حاوی بیت 0 و نیم دیگر حاوی بیت 1 بدون ترتیب خاصی است
گونه 2 : A در مجموع 2/3 صفر و 1/3 یک دارد.
به شما یک آراه مانند A داده شده است که با احتمال یک سان یا از نوع 1 و یا نوع 2 است. در بهترین حالت خداقل چند تا درایه باید بررسی شود تا گونهی آن با اطمینان مشخص شود؟
12 - مرتبه رابطه های زیر را بدست آورید؟
\[ \begin{matrix} T(n)=4\sqrt{n}T(\sqrt{n})+2n^2\\ T(n)=2T(\left \lfloor \sqrt{n}\right \rfloor) +log(n)\\S(n)=4S(\frac{\sqrt{n}}{3})+log^2 n\end{matrix}\]
13 - نرخ رشد توابع زیر را به ترتیب صعودی مرتب کنید؟
14 - پیچیدگی قطعه کد زیر را بدست آورید؟
sum <-- 0
for i <-- 1 to n
do for j<--1 to i^2
if j mod i==0
then for k<-- 1 to j do sum<-- sum+1
15 - در قطعه کد زیر تعداد مقایسه ( اجرای خط 6 ) بر حسب n چند است؟
i و j به ترتیب ابتدا و انتهای آرایه A
FindMax(A,i,j)
n<--j-i+1
if n==1 then return A[i]
m1<-- FindMax(A,i,i+[n/2]-1)
m2=FinaMax(A,i+[n/2],j)
if m1<m2
return m2
else return m1
16 - در قطعه کد زیر ++x چندبار اجا می شود؟
for (i=3;i<=n;i=i*2)
x++;
17 - زمان مصرفی قطعه کد زیر در چه حالتی بدترین و بهترین می باشد. مرتبه آن را بنویسید ( توضیح دهید )
for i<-- 2 to n do
if k mod i==0 then
for j<--1 to n do
L<--L*k
18 - جستجوی دودویی را به صورت بازگشتی و غیربازگشتی نوشته و تابع زمانی آن ها را محاسبه نمایید. جهت تابع غیر بازگشتی پیچیدگی زمانی را هم محاسبه کنید.
19 - تابع محاسبه مجموع عناصر یک آرایه را محاسبه نمایید. جهت تابع غیربازگشتی پیچیدگی زمانی هم محاسبه کنید.
20 - خروجی تابع زیر به ازاء n=5 چند است؟ تابع زمانی آن را محاسبه کنید.
def f(n):
if n<=0:
return 1
else:
return f(n-1)+f(n//2)
| جهت سفارش پروژه ، تکلیف و آموزش ساختمان داده و طراحی الگوریتم ، مشاوره کنکور کارشناسی ارشد و دکتری کامپیوتر لطفا با متلب خونه تماس بگیرید، تا پس از بررسی هزینه خدمت شما اعلام گردد.
پشتیبانی ( تلفن ثابت دفتر متلب خونه ) : 02191307193
تلگرام و ایتا : 09364847193
