راهنمایی در مورد برخی از سئوالهای ارشد

سلام
یه سری از سئوالهای ارشد رو از بین درسهای مختلف اینجا لیست میکنم. لطفا فقط به صورت تشریحی کمک کنید.

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

بحث سر هر کدوم از این سوالها چندین صفحه جا و کلی وقت میبره ولی بطور خلاصه
سوال 7 که ایراد داره چون سوال مبهمه و معلوم نیست منظور طراح از تعداد تغییرات چیه از یه طرف میشه گفت 2تا تغییر میکنن 2تا هم مقدار جدید میگیرین ولی قسمت ب سوال خوب ساده است و ترکیب 2 از 4 میشه که برابر 6 هست
سوال 9 هم که خیلی آسونه و thrashing میشه عین همین جمله تو کتاب استالینگ هست

سوال 10 به نظر من logn در مبنای 2 میشه چون n/2 پردازنده اگه n عدد رو بهشون بدی به هرکدوم 2تا میرسه و در مرحله اول هر پردازنده 2تا عدد رو با هم جمع میکنه مرحله بعدی هم به همین ترتیب پس در هر مرحله اعداد تقسیم به 2 میشن تا مرحله آخر که فقط 2 تا باقی میمونه، البته از نوع سوال معلومه که طراح میخواسته نظر داوطلب رو به گزینه های 1 و 3 جلب کنه و یه جورایی تو تله بندازه!

نقل قول:

---

منظورت از ترکیب 2 از 4 چیه ؟ فرمولش چیه ؟

---

    4!

------------

2!(4-2)!

جواب هم گزینه 3 میشه ،اما سوال به نظر من هم مبهم است

سوال 10 همان Log N میشه در مبنای 2 ،دلیل هم که بیان شد

جواب سوال6 به نظر من هم n میشه، چون برای تشخیص یک رشته در ماشین تورینگ ابتدا باید n رشته a بر روی نوار نوشته بشه و با برخورد به b به ازای هر b یک رشته a پیمایش بشه.

جواب سوال 5 : ای کاش الگوریتم را اضافه می کردید ،اما فکر کنم جواب برابر n/2 است چون برعکس مرتب شده بار اول دو عنصر در جای خود قرار می گیرند بار دوم دو عنصر و ... یعنی با هر بار فقط محور جای خود را عوض می کند که وقتی به وسط رشته رسید دیگر تغییر انجام نمی شود.

جواب سوال 4 باید گزینه nlogn باشه چون هزینه پیمایش هر گره log n و برای بدست آوردن درخت در بدترین حالت باید به تعداد گره ها آنرا پیمایش کنیم. (دقیقا مطمئن نیستم)

سوال 2 : اگر بازیها را بصورت یک درخت کامل بگیرید در هر سطح تعداد بازی های انجام شده را در نظر بگیرید، در سطح اول 64 بازی انجام می شود ،در سطح دوم تعداد بازیهای بین برندگان برابر 32 و بین بازندگان برابر 32 و ... که فرمولی شبیه زیر می شود
R=64+2*32+4*16+8*8+16*4+32*2+64=448

لطفا جواب ها را با کلید سوالات چک کنید
موفق باشید

با سلام
من هم توی این فرصت کم به شما می پیوندم و در باره سوال 7 باید صحبت دوستمون رو کامل کنم که همونطور که گفته شد ترکیب m,n تعداد حالات مجاز است و همچنین تعداد تغییر پیوندها 4 تا است که دوتا برای عنصر جدید به ادامه لیست و دوتا هم از عنصر قبلی به عنصر جدید که به واقع تصحیح می شوند .

8- ج سایر موارد عملیات خواندن است و مجاز می باشد و بخش دال هم اصلا بی ربط است (انحرافی)
9- د که به trashing اصطلاحا کوبیدگی هم گفته می شه .
5- ب البته منتظر سایر جواب های دوستان هم هستم چون همینطور که می دونید انتخاب محل pivot مهم است .


موفق باشید

با تشکر از همه دوستان؛ (علی الخصوص از WhiteHat جان واسه حل سئوال 2)

کلید بعضی از سئوالات رو لیست میکنم. اما فعلا کلید اولیه هستن و بعضی هاشون مثل سئوال 6 واسه من غیر قابل قبول هستن. بعضی هاشون رو هم که نمیتونم حل کنم...!
خواهشا به کلیدها، نگاه نکنین؛ میخوایم خودمون با همفکری هم حل کنیم.

1) د
2) ب
3) ب
4) د
5) الف
6) ب
8) ج - آخه از کی تا حالا تنظیم ساعت، کرنل رو درگیر کرده ؟! :افسرده:
11) ج - چرا ؟!
12) الف
13) الف - دو به توان n/2 چند جمله ای به حساب نمیاد؟!
14) الف

نقل قول:

---

8) ج - آخه از کی تا حالا تنظیم ساعت، کرنل رو درگیر کرده ؟!

---

به جواب آقای هخامنش دقت کنید

نقل قول:

---

ج - چرا ؟!

---

اگر درخت آنرا رسم کنید مشاهده می کنید از نود 01 به نود 111 مسیری به طول 5 وجود دارد

12 - معمولا این مسئله ها یک راه حل ساده دارند ، اگر درخت n کامل باشه (یعنی هر نود n فرزند داشته باشه) شماره هر گره ضربدر n یکی از فرزندان گره را می دهد شما این کار را برای ریشه انجام دهید و ببینید چندمین فرزند بدست می آید سپس می توانید قاعده کلی را پیدا کنید (البته فرمولهایی هم دارد که حفظ آنها توصیه نمیشه) مثلا در این مثال اگر 5 را در 1 ضرب کنید مشاهده می کنید که شماره 5 بدست می آید که گره فرزند چهارم نود ریشه است ، حالا عدد 15 را در 5 ضرب کنید که برابر 75 میشود پس فرزندان نود 15 باید شماره های 72 تا 76 را داشته باشند ، پس گزینه 2 و 3 حذف می شود. برای پیدا کردن تعداد برگها باید تعداد برگها در سطح آخر را پیدا کنید و سپس با برگهای سطح ما قبل آخر جمع کنید.
چون 25<95<125 یعنی 2^5<95<3^5 است پس ما باید برگهای سطح 2 و3 را پیدا کنید.
تعداد برگهای سطح اخر برابر(چون از چپ پر می شود)
95-(2^5+1^5+0^5) که برابر 64 است.
و تعداد برگهای سطح ماقبل آخر را می توانید بدین گونه حساب کنید
با توجه به اینکه تعداد برگها برابر 64 است باید دید این تعداد برگ چه تعداد پدری دارند برای 64 برگ ما نیاز به 13 پدر داریم (65/5) پس بقیه گره های سطح ماقبل آخر برگ هستند یعنی 13-25 = 12برگ داریم پس در کل ما برگ در سطح ماقبل آخر داریم پس کل برگها برابر 12+64 است.

13- اگر داشته باشیم

T(n)=q T(pn-k) +j

و q>p با شد حتما تابع بازگشتی نوع لگاریتمی دارد. (اثبات این مورد را می توانید به روش استقرا انجام دهید توجه داشته باشید برای حالت مساوی و یا بزرگتر نیز فرمولهایی وجود دارد)

موفق باشید

نقل قول:

---

اگر درخت آنرا رسم کنید مشاهده می کنید از نود 01 به نود 111 مسیری به طول 5 وجود دارد

---

ممکنه خواهش کنم، یه عکس از درختش ارسال کنید؟

نقل قول:

---

پس فرزندان نود 15 باید شماره های 72 تا 76 را داشته باشن

---

عذر میخوام، متوجه این قسمت نشدم.

نقل قول:

---

ممکنه خواهش کنم، یه عکس از درختش ارسال کنید؟

---

یک در خت دودوئی رسم کنید، فرزندان ریشه را صفر برای گره چپ و یک برای گره راست در نظر بگیرید ، حال همین کار را برای نود های فرزند تکرار کنید اما نام پدر را به عنوان پیشوند به آن اضافه کنید. گره 01 در سطح دوم و 111 در سطح سوم قرار خواهد گرفت که اگر بخواهید از کی به دیگری بروید باید مسیری به طول 5 را بگذرانید

نقل قول:

---

عذر میخوام، متوجه این قسمت نشدم.

---

با توجه به قسمتی که اشاره کردم اگر نود اول 1 باشد 1*5=5 که نودی با شماره 5 فرزند چهارم نود یک است. حال فرض کنید نود 15 را دارید، 15*5=75 که 75 فرزند چهارم نود 15 است پس سایر فرزندان دارای شماره ای بین 72 تا 76 هستند

White Hat جان ، به یه مشکل کوچولو در مورد بازی تورنمنت ها برخوردم.

ببین کتاب دکتر نقیب زاده میگه اگه نتیجه مساوی نداشته باشیم و بازنده ها باهم بازی نکنن؛ تعداد کل بازیها 2n-1 است.

یعنی برای 128 بازی اینطور محاسبه میکنه : 128+64+32+16+8+4+2+1 و این یه خورده با نحوه محاسبه شما فرق داره.چون مثلا 128 رو هم جمع میکنه؛ ضمن اینکه متوجه نمیشم چرا عدد 1 رو هم جمع میکنه. (مگه تیم برتر هم با کس دیگه بازی میکنه؟)

ممکنه لطفا یه راهنمایی بکنید؟

نقل قول:

---

ببین کتاب دکتر نقیب زاده میگه اگه نتیجه مساوی نداشته باشیم و بازنده ها باهم بازی نکنن؛ تعداد کل بازیها 2n-1 است.

---

برای تورنومنت های تک حذفی شما هر تیم را باید یک برگ بگیرید و درخت آنرا ترسیم کنید ، درخت بدست آمده یک درخت کامل دودوئی است .تعداد نود های داخلی (کل نود ها منهای برگها) برابر تعداد بازیها می شود. سعی کنید حتما برای کنکور جملات زیر را بخاطر بسپارید:
در این درخت تعداد نود ها برابر 2n-1 است (n تعداد برگها می باشد)
همیشه تعداد نودهای سطوح قبل برابر تعداد برگها منهای یک است.
تعداد یالها برابر 2/(v-1) است (v تعدا نود ها است)

نقل قول:

---

چرا عدد 1 رو هم جمع میکنه

---

شما همانطور که گفتم یک درخت را (بصور معکوس از برگ تا ریشه) ترسیم کنید ، عدد یک ریشه یا فینال مسابقات است.
این نکته را هم در نظر بگیرید که برای محاسبه بازیهای بین دوتیم سطح آخر یا برگها را نباید در نظر بگیرید و تعداد بازیها برابر تعداد برگها منهای یک است.
کل مطالبی که نوشتم برای n=2^k صحت دارد
موفق باشید

با سلام
1.برای معکوس کردن لیست پیوندی یک طرفه چرا به سه اشاره گر نیاز داریم؟
2.فراخوانی بازگشتی لیست پیوندی یک طرفه به چه صورت انجام می گیره؟