. . .
: کارشناسی و کارشناسی ارشد --- - - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱ عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها
رشته تحصیلی /کد درس : مهندسی کامپیوتر(نرم افزار)، مهندسی کامپیوتر(گرایش نرم افزار) ۱۱۱۵۰۷۸ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۵۱۴۲ - ، علوم کامپیوتر، علوم کامپیوتر ۱۱۱۵۱۶۶
۱- کدام گزینه تعداد مراحل اجرای خطوط برنامه را به درستی بیان می کند؟ x=0; for(i=0; ion; it #) for(j=0; joi; j++)
x++; Yn' + n + \ ' Yn' + Yn + Y Y n' + xn + y \ п + n + v \ Y– مرتبه زمانی قطعه کد زیر کدام است؟ i=n; while(ix-1){ j=i;
while(j<=n){ //some statements require O(1) times j=j*2;
}
i= is2;
}
T(n)e 6(log n) Y T(n) e 6((log n)') .)
T(n) e 6(log(log n)) . ; T (n)e 6(n log n) . Y |n if η < \ οοοο –r
T(n( = 引 کدام گ: دیز است؟
کر n) if n > \ ooo( مکزینه صحیح
Τ(n)Ε θ(n). * T(n) e O(n") ". T (n)e 6(no) , V T(n) e Q(n') : ) い・い・ハ・Y・)%YY نیمسال دوم ۹۱-۱۳۹۰ صفحه ۱ از ۱۰











***
. . .
: کارشناسی و کارشناسی ارشد --- - - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها
رشته تحصیلی /کد درس : مهندسی کامپیوتر(نرم افزار)، مهندسی کامپیوتر(گرایش نرم افزار) ۱۱۱۵۰۷۸ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۵۱۴۲ - ، علوم کامپیوتر، علوم کامپیوتر ۱۱۱۵۱۶۶
f— در برنامه زیر مقدار )5,?funcs برابر است با: int funcsint n, int m){
if(n==1 || m==1) return 1; else return (func[n-1, m)+func[n,m-1)); } \\ , t 2 . " A Y A . )
۵- تابع زیر چه عملی بر روی یک درخت دودایی انجام می دهد؟ int functnode * root){ if(!root) return 0; else return functroot->left) + funcsroot->right) + 1;
}
۱. تعداد برگهای درخت را شمارشی می کند. ۲. تعداد گره های دو فرزندی را شمارش می کند.
۳. تعداد گره های درخت را شمارش می کند. ۴. عمق درخت را محاسبه می کند.
۶- صفحه ای به ابعاد n×۲ موجود است. اگر این صفحه را با موزاییک های ۱×۲ فرش کنیم، کدام رابطه بازگشتی بیانگر تعداد
روش های انجام این کار است؟
YT (n — \) +T (n — Y) n > Y -‘ [, YT (n — \) n > \ .\ T(n) = T(n) =} \ Pl = \ \ n = \ lv γη = γ T (n — \) +T (n — Y) n > x - * {T (n — \) +Y n > \ . Y T(n) = T(n)={\ n = \ \ n = \ |v η = γ い・い・ハ・Y・)%YY نیمسال دوم ۹۱-۱۳۹۰ صفحه ۲ از ۱۰









***
. . .
: کارشناسی و کارشناسی ارشد --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها رشته تحصیلی /کد درس : مهندسی کامپیوتر(نرم افزار)، مهندسی کامپیوتر(گرایش نرم افزار) ۱۱۱۵۰۷۸ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۵۱۴۲ - ، علوم کامپیوتر، علوم کامپیوتر ۱۱۱۵۱۶۶
W— اگر رابطه بازگشتی T(n)=۲ () + n log n را با قضیه اصلی حل کنیم کدام گزینه صحیح است؟
T(n) e O(n log n) : )
ャ
T(n) e O(n log n) .
r
T(n) e O(n log n) ۴. این رابطه بازگشتی را توسط قضیه اصلی نمی توان حل کرد. ۸- رابطه بازگشتی زیر از کدام مرتبه است؟ T(n) = YT (Wn)+ log. 'n
T(n)e O(log n x log, log n) " T(n)e O(Vn log n) ... ) T(n)e O(Vn log n) . Y. T(n)e O(log n x log, log n) "
۹- اگر الگوریتم جستجوی دودویی را برای جستجوی عناصر آرایه زیر به کار ببریم، میانگین تعداد مقایسه ها برای جستجوی ناموفق تقریبا کدام است؟
V V| V N| V.|| 9 y“|| NV| No M| Y“ f|| YʻA|| Yʻwʻ| \V| Y\F| Y\|| V| Y“
ו. yןץ f */A . Y Y/१ . Y. מו"ץ
い・い・ハ・Y・)%YY
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۳ از ۱۰


***
. . .
藥 کارشناسی و کارشناسی ارشد مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک
عن-وان درس : طراحی الگوریتمها، طراحی و تحلیل الگوریتمها رشته تحصیلی /کد درس : مهندسی کامپیوتر(نرم افزار)، مهندسی کامپیوتر(گرایش نرم افزار) ۱۱۱۵۰۷۸ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۵۱۴۲ - ، علوم کامپیوتر، علوم کامپیوتر ۱۱۱۵۱۶۶
.W— الگوریتم تقسیم و غلبه زیر برای حل مسئله P با اندازہ n طراحی شده است. result Dandc{P}{ if(size(P) == 1) return S(P); else's divide P into 5 instances P1, P2, P3, P4, P5 where size(Pi)= n/3 for i=1,2,3,4,5 return combine(Dandc(P1), Dandc(P2), Dandc(P3), Dandc(P4), Dandc(P5)); }
} اگر زمان لازم برای (O(n) S(P و زمان لازم برای تقسیم P و ترکیب راه حل ها، (O(n باشد، مرتبه الگوریتم فوق کدام است ؟ T(n)e 6(n log, n) " T (n)e 6(n") " T(n)e 9(n”) ' T(n)e 6(n ) '
۱۱- در الگوریتم مرتب سازی سریع پس از اجرای تابع partition بر روی آرایه زیر نتیجه حاصل کدام است؟ (ترتیب اعداد در
سوال و در گزینه ها از راست به چپ است)
A \\ | YN | \. γ. γγ ^\ | "וץ
) . | \\ W γ. γ.Δ γγ W. A \ | "וץ
V \\ \. л | Ү \ | .ץ | A ו ו \ \ | "וץ
ΥΔ γγ' γ. γΛ γγ γγ Л ). . "
? - | V \\ \. л \ | .ץ | W \ | מז | "וץ
۱۲- چند عمل ضرب در هنگام یافتن حاصلضرب دو ماتریسی ۴×۴ با استفاده از الگوریتم استراسن مورد نیاز است؟
\ १/\ . ि \ YA . Yo ** .Y 所人.1
صفحه ۴ از ۱۰
ᏉᎵᎸ•-ᎸᏉ نیمسال دوم い・い・ハ・Y・)%YY


***