راهنمایی در مورد برخی از سئوالهای ارشد
سلام
یه سری از سئوالهای ارشد رو از بین درسهای مختلف اینجا لیست میکنم. لطفا فقط به صورت تشریحی کمک کنید.
1) الگوریتم pancake sort براساس رفتار آشپزها با پن کیک بنا شده. فرض کنید n تا پن کیک رو هم قرار گرفته اند و بر روی هر کدام عددی نوشته شده. تنها کار ممکن فرو کردن کفگیر، قبل از یک پن کیک خاص و وارون کردن همه پن کیک ها است. هدف از این اگوریتم مرتب کردن صعودی اعداد با استفاده از کم ترین تعداد وارون است. اگر تعداد n>=6 باشد با چه تعداد عمل وارون میتوان یقینا اعداد رو مرتب کرد؟ ( کمترین گزینه رو علامت بزنین) - سراسری ارشد 86
الف) n ب) n-1 ج) 2n-1 د) 2n-2
2) در باشگاهی قرار است مسابقات والیبال برگذار شود. به این ترتیب که بین n=2^k تیم شرکت کننده اول n/2 مسابقه صورت میگیرد. سپس بین تیم های برنده و بازنده به همین ترتیب مسابقاتی برگذار میشود.( در هر مرحله هر تیم برنده با یک تیم برنده از همان مرحله مسابقه میدهد و همینطور برای تیم های بازنده آن مرحله) و در هر مرحله مسابقات، به همین نحود ادامه پیدا میکمد تا زمانی که به گروه های تک تیمی برسیم. تعداد کل بازیها برای n=128 چند است ( نتیجه مساوی نداریم) - سراسری ارشد 86
الف) 320 ب) 448 ج) 576 د) 704
3) n عدد نامرتب و نامساوی داده شده. میخواهیم جمع کوچکترین رادیکال n عددهای این اعداد رو پیدا کنیم. الگوریتم کارا در چه زمانی این مساله را حل میکند؟ - سراسری ارشد 86
الف) رادیکال n ب) n ج) nlogn د) logn * رادیکال n
4) در درخت AVL، اگر این درخت را از گره دلخواه (مثل x) اسپلیت (split) کنیم. کمترین هزینه برای حفط دو درخت به وجود آمده با ساختار AVL چقدر است؟ (n : تعداد عناصر درخت) -سراسری ارشد 86
الف) n ب) n^2 ج) nlogn د) logn
5) در الگوریتم QuickSort (متن الگوریتم در بین سوالهای اسکن شده امسال هست) اگر آرایه A با n عنصر نامساوی ،برعکس مرتب شده باشد. تعداد تعویض ها دقیقا چند است؟ -سراسری ارشد 86
الف) [n/2] ب) n ج) n-1 د) 2n-2
6) برای تشخیص زبانL=a^n b^n یک ماشین تورینگ ساختیم. حداقل هزینه تشخیص عضویت رشته، در چه حدی است؟ -سراسری 86
الف) n ب) n^2 ج) n^3 د) نمایی
7) در اضافه کردن یک گره به لیست پیوندی دو طرفه، چند اشاره گر باید تغییر کند و تعداد حالات مجاز برای تغییر آنها چیست ؟ -آزاد 85
الف) 4 اشاره گر و 8 حالت مجاز ب) 2 اشاره گر و 6 حالت ج) 4 اشاره گر و 6 حالت د) 2 اشاره گر و 8 حالت مجاز
8) کدام یک از دستورات زیر فقط قادر به اجرا در مود کرنل هست ؟ -سراسری 86
الف) خواندن ساعت سیستم ب) خواندن PSW ج) تنظیم ساعت سیستم د) نوشتن در ثبات IR
9) اگر فرایندی اکثر زمانهایش رو به جای اجرا، به صفحه بندی اختصاص بده. این عمل چه نام داره؟ - آزاد 85
الف) PrePaging ب) demand paging ج) local aloction د) thrashing
10) یک کامپیوتر با n/2 پردازنده مفروض است. اگر بخواهیم با استفاده از این کامپیوتر، اعداد موجود در یک آرایه n عنصری رو جمع کنیم. زمان مورد نیاز چند است ؟ - آزاد 85
الف) logn در مبنای 10 ب) logn در مبنای 2 ج) nlogn در مبنای 10 د) n/2
11) کد پیشوندی یک درخت {01و10و111}میباشد طول بزرگترین مسیر اصلی در این دخت چند است؟- سراسری 86
الف) 3 ب) 4 ج) 5 د) 6
12) کدام یک در مورد درخت 5تایی کامل با 95 گره صحیح است؟(ریشه گره اول است و در هر عمق گره ها از چپ به راست در نظر گرفته شود)
-سراسری 86
الف) 76 برگ دارد و گره 15 آن پدر گره 72 است ب) 76 برگ دارد و گره 14 پدر گره 72 است
ج) درخت 77 برگ دارد و گره 14 پدر گره 72 است د) درخت 77 برگ دارد و گره 15 پدر گره 72 است
13) رابطه های بازگشتی زیر برای اعداد صحیح n>2 تعریف شده اند؛ و داریم t(o)=1 و t(1)=1 کدامیک از روابط زیر چند جمله ای ندارد؟ -سراسری 86
الف) T(n)=2T(n-2)+1
ب) T(n)=T(7n/8) +8n-1
ج) T(n)=3T([n/2])+n^2
د) T(n)=T(n-1) +n^2
14) حالت خاصی از برج هانوی را درنظر بگیرید. 100 سکه با شماره های( واندازه های) 1 تا 100 موجودند. از این تعداد n1 عدد در میله شماره یک( با هر شماره دلخواه) با ترتیب از بزرگ به کوچک( از پایین به بالا) و بقیه در میله شماره 3 با همین نظم و ترتیب قرار دارند. میخواهیم با حفط همه مقرارت برج هانوی، همه سکه ها رو به میله 3 منتقل کنیم. حداقل تعداد حرکت ها در بدترین حالت حرکت سکه ها چندتا است؟
الف) (2به توان100) -1
ب) (2به توان100) +1
ج) (2به توان101) -1
د) (2به توان101) +1
پاسخ با نقل قول
