تالار گفتمان مانشت

نسخه‌ی کامل: حل و بررسی سوالات ساختمان داده و الگوریتم- نرم افزار و هوش مصنوعی 93
شما در حال مشاهده‌ی نسخه‌ی متنی این صفحه می‌باشید. مشاهده‌ی نسخه‌ی کامل با قالب بندی مناسب.
صفحه‌ها: 1 2 3 4
(16 اسفند 1392 09:11 ب.ظ)morelo نوشته شده توسط: [ -> ]سوال ۲ یه درخت BST هست که ابتدا باید ۱۳ وارد شه، بعدش ۶ یا ۱۴ میتونن وارد شن یعنی !۲، ۱ و ۹ و ۲۲ هم با !۳ میتونن وارد شن که میشه !۳ * !۲ برابر ۱۲/ به نظرم گزینه ۱ میشه

من حالت ها رو کشیدم 20 حالت میشه
اگه در قسمت دوم 6 را وارد کنی در مرحله بعد 14 هم می تواند وارد شود و به حالت ها اضافه می شود
سوال ۴:
جواب میشه یک درخت مورب. چون برچسب ها ۱ تا n هستند، فقط میشه به ترتیب ۱ تا n را نوشت تا درخت خاصیت درخت جستجوی دودویی را داشته باشه، بنابراین به نظر من جواب فقط یک درخت خواهد بود!

اگر اشتباه گفتم تصحیح کنید.


برای سوال ۲ من دقیقا راه حل morelo رو رفتم... و ۱۲ رو زدم.
(16 اسفند 1392 09:58 ب.ظ)Mansoureh نوشته شده توسط: [ -> ]سوال ۴:
جواب میشه یک درخت مورب. چون برچسب ها ۱ تا n هستند، فقط میشه به ترتیب ۱ تا n را نوشت تا درخت خاصیت درخت جستجوی دودویی را داشته باشه، بنابراین به نظر من جواب فقط یک درخت خواهد بود!

اگر اشتباه گفتم تصحیح کنید.


برای سوال ۲ من دقیقا راه حل morelo رو رفتم... و ۱۲ رو زدم.

سوال 4 هیچ حرفی از BST نزده. خیلی پیجیده نیست این سوال مثلاً با سه کلید 1 و 2 و 3 می توان 6 درخت مورب چپ رسم کرد.
(16 اسفند 1392 09:11 ب.ظ)morelo نوشته شده توسط: [ -> ]سوال ۲ یه درخت BST هست که ابتدا باید ۱۳ وارد شه، بعدش ۶ یا ۱۴ میتونن وارد شن یعنی !۲، ۱ و ۹ و ۲۲ هم با !۳ میتونن وارد شن که میشه !۳ * !۲ برابر ۱۲/ به نظرم گزینه ۱ میشه

جوابا تو فایل ببینید
(16 اسفند 1392 10:07 ب.ظ)morelo نوشته شده توسط: [ -> ]
(16 اسفند 1392 09:58 ب.ظ)Mansoureh نوشته شده توسط: [ -> ]سوال ۴:
جواب میشه یک درخت مورب. چون برچسب ها ۱ تا n هستند، فقط میشه به ترتیب ۱ تا n را نوشت تا درخت خاصیت درخت جستجوی دودویی را داشته باشه، بنابراین به نظر من جواب فقط یک درخت خواهد بود!

اگر اشتباه گفتم تصحیح کنید.


برای سوال ۲ من دقیقا راه حل morelo رو رفتم... و ۱۲ رو زدم.

سوال ۴ هیچ حرفی از BST نزده. خیلی پیجیده نیست این سوال مثلاً با سه کلید ۱ و ۲ و ۳ می توان ۶ درخت مورب چپ رسم کرد.

درست میگید! من خواندم «چه تعداد درخت جستجوی دودویی»!!!! نمیدونم چرا دقت نمیکنم!!!

من روی این حساب که دو ساله از طراحی الگوریتم سوال ندادن، این درس رو نخواندم، فقط ساختمان داده خواندم!!!

سوال ۵ گزینه ی ۴ درسته؟
منم طبق سوالاتی که حل کردم و جوابای شما که دیدم، گزینه‌های زیر فکر می‌کنم درسته (سبزا تقریباً قطعی!)

1- 4
2- 2
۳- ۳
۴- ۴
5- 4

۶- ؟
۷- ۲
8- 1
۹- ۲
10- 3
۱۱- ۴

12- 4
۱۳- ۳
۱۴- ۲
۱۵- ۴
۱۶- ۲

۱۷- ؟
۱۸- ۱
19- 1
۲۰- ۳
با سلام دوستان گرامی
سوال یک رو سه زدم .
به ترتیب از سطح بالا به پایین و از سمت چپ به راست VLR
سوال دوم هم تا 18 حالت بدست آوردم Smile یکی یکی درخت کشیدم . زور زدم تا 20 برسه نرسید . با این حال گزینه 4 رو زدم .
3- 3
2- 4
5-1
گزینه 6 رو فکر کنم 1 زدم .
من کنکورم ارشد بود ولی نشستم الان اینا روحل کردم الان می نویسم که بعدا چک کنم وضعم چطورهBig Grin
البته به جز سوال 13 و 17 و 19 که شک داشتم بقیه رو مطمئنمTongue
که 13 یا 3 یا 4 میشه
19 هم شبیه 13
17 هم بین گزینه ی 2 و 3 شک دارم
سوال1 _ 4
سوال2 _ 2
سوال3 _ 3
سوال4 _ 4
سوال5 _ 4
سوال6 _ 1
سوال7 _ 4
سوال8 _ 1
سوال9 _ 2
سوال10 _ 1
سوال11 _ 4
سوال12 _3
سوال13 _4
سوال14 _1
سوال15 _2
سوال16 _2
سوال17 _2
سوال18 _1
سوال19 _4
سوال20 _4

(17 اسفند 1392 01:48 ق.ظ)mmpf نوشته شده توسط: [ -> ]دلیلتون برای سوال ۱۶ چیست؟ چون گزینه ۲ و ۴ یه جورایی برای برای یعضی مقادیر یک جواب می دهند. گزینه اول هم که k مورد اشتباه. در کل احتمال بیشتر از عدد ۱ که نمی شد و حداکثر ۹۹% مثلا. مثلا برای k=128 که احتمال میشه حدود ۰/۹ باید الگوریتم ۷ بار اجرا بشه؟
در مورد سوال ۱۳ هم گزینه یا ۳ است یا ۴/ اگر پوشش راسی اشتباه باشد می شود گزینه ۳/ ولی فکر کنم گزینه ۴ درست باشه چون پوشش راسی np-complete.
در مورد سوال ۷ چطور؟ چرا این گزینه؟من دقیقا روی سوال رو نفهمیدم مگر با مقایشه حداقل نباید از nlgn شود؟
در مورد سوال 16 شما k را برابر 1000000 قرار بده پس ما باید شرط زیر رو برقرار کنیم
[tex](\frac{1}{4})^n<\frac{1}{1000000}[/tex]
که n برابر با 10 خواهد شد که جواب میشه log با پایه ی 4
فکر کنم پیدا کردن حداکثر پوشش راسی اگه می گفت درست بودن البته بازم هم مسئله یه جواری میتونه np کامل باشه
سوال 7 هیچکدام میشه و اینجوری اثبات میشه
[tex]\log\: (\frac{n!}{x})[/tex]
حالا ما باید مقداری جای x قرار دهیم که حاصل بشه n که جواب هیچکدامه

(16 اسفند 1392 11:22 ب.ظ)ashkan_d13 نوشته شده توسط: [ -> ]منم طبق سوالاتی که حل کردم و جوابای شما که دیدم، گزینه‌های زیر فکر می‌کنم درسته (سبزا تقریباً قطعی!)
12- 4
۱۴- ۲
۱۵- ۴
19- 1
۲۰- ۳

سوال 12 راس های مربع بزرگ 4 تا و بقیه یکی (چون میشه از هر نقطه ایش به یه نقطه ی دیگه اش رفت)
سوال 14 گفته گراف مسطح یعنی تعداد یال ها از پیچیدگی راس هاست پس بهترین الگوریتم با دایجسترا که میشه اجرای n بار nlogn
سوال 15 چرا 2 نمیشه؟
سوال 19 فکر کنم اشتباه حل کردین هر گزینه ای بشه مطمئنا 1 نمی شه چون راس های مجاور معمولا درخت هاشون خیلی تفاوت ندارند
سوال 20 فرض کن تعداد پردازنده ها 9 تا هستن با 4 بار اجرا حل میشه نه 5 تا
(16 اسفند 1392 10:07 ب.ظ)morelo نوشته شده توسط: [ -> ]
(16 اسفند 1392 09:58 ب.ظ)Mansoureh نوشته شده توسط: [ -> ]سوال ۴:
جواب میشه یک درخت مورب. چون برچسب ها ۱ تا n هستند، فقط میشه به ترتیب ۱ تا n را نوشت تا درخت خاصیت درخت جستجوی دودویی را داشته باشه، بنابراین به نظر من جواب فقط یک درخت خواهد بود!

اگر اشتباه گفتم تصحیح کنید.


برای سوال ۲ من دقیقا راه حل morelo رو رفتم... و ۱۲ رو زدم.

سوال ۴ هیچ حرفی از BST نزده. خیلی پیجیده نیست این سوال مثلاً با سه کلید ۱ و ۲ و ۳ می توان ۶ درخت مورب چپ رسم کرد.

به نام خدا

سلام.

در صورت سوال اگر دقت کنید نوشته "یک درخت تهی"، می دانیم BST می تواند درخت تهی باشد و درخت معمولی تهی معنی ندارد.
نکته دوم این سوال هم ترتیب قرار گیری اعداد هستش که نشان دهنده BST بودن درخت هست.

در نهایت، این سوال 20 حالت خواهد داشت که یک سوال شمارش به نسبت ساده هست و گزینه صحیح 20 عدد (گزینه 2) می باشد.
(راهنمایی: 13 اولین ورودی باید باشد، دومین ورودی در صورتی که 6 باشد، سومین ورودی ها 14، 1، 9 می توانند باشند،در صورتی که سومین ورودی 14 باشد، چهارمین ورودی 1یا 9 یا 22 می باشد و .....)

به نام خدا
بخش اول سوالات (DS) به نظرم این طوری میشه....
1) 4
2) 2
3) 3
4) 2
5) 4

8) 1
9) 2
10) 3
11) 4

14) 2
اینم جوابای من که نمیدونم درسته یا نه، حداکثر 3 ساعت خونده بودم برا ساختمان و با دانش 2 سال پیش رفتم سر جلسه! (فکر نمیکردم الگوریتم هم بدن!!)
1)4
2)1
3)3
4)2
5)2
6)1
8)3
9)1
10)1
11)4
12)3
13)3
14)1!!
15)4
16)3
18) فکر کنم 2 زدم
19)1
20)3


در مورد سوال 2 هم نگفته BST اما اگه قید خاصی رو درخت نزاریم بی معنی میشه خصوصا اینکه اگر درخت رو با آرایه پیاده کرده باشن چرا باید زیر درخت سمت راست کامل نشه!! و در ضمن فرم کلیدها BST رو به ما میداد. من اینطوری نوشتم که 13 که هیچ! بعدش 2 حالت داره برای سطح 2 و و در سطح 3 , 3 حالت داریم که میشه :
!3 * !2 = 12
(17 اسفند 1392 05:27 ق.ظ)izadan11 نوشته شده توسط: [ -> ]
(16 اسفند 1392 11:22 ب.ظ)ashkan_d13 نوشته شده توسط: [ -> ]منم طبق سوالاتی که حل کردم و جوابای شما که دیدم، گزینه‌های زیر فکر می‌کنم درسته (سبزا تقریباً قطعی!)
12- 4
۱۴- ۲
۱۵- ۴
19- 1
۲۰- ۳

سوال ۱۲ راس های مربع بزرگ ۴ تا و بقیه یکی (چون میشه از هر نقطه ایش به یه نقطه ی دیگه اش رفت)
سوال ۱۴ گفته گراف مسطح یعنی تعداد یال ها از پیچیدگی راس هاست پس بهترین الگوریتم با دایجسترا که میشه اجرای n بار nlogn
سوال ۱۵ چرا ۲ نمیشه؟
سوال ۱۹ فکر کنم اشتباه حل کردین هر گزینه ای بشه مطمئنا ۱ نمی شه چون راس های مجاور معمولا درخت هاشون خیلی تفاوت ندارند
سوال ۲۰ فرض کن تعداد پردازنده ها ۹ تا هستن با ۴ بار اجرا حل میشه نه ۵ تا

15 رو من دوتا مثال نوشتم هیچی نمیده
19 گراف کامل رو در نظر بگیرین که همه‌ی یال‌ها هم‌وزن هستند
20 فرض کن 5 تا هستن! 3 بار اجرا لازم داره


(17 اسفند 1392 10:45 ق.ظ)sharareh_moradi نوشته شده توسط: [ -> ]خیلی از دوستان سوال ۱۰ رو میگن گزینه ۳ !!!!
میشه دلایلتون رو هم بگین؟؟؟
چرا من این سوال رو متوجه نمیشم!!
آخه وقتی اندازه معطلی i برابر i میشه
پس اندازه معطلی کل میشه مجموع i از ۱ تا ۱۰ دیگه
که میشه n*(n+1)/2
که برای n=10 میشه ۵۵

اندازه‌ی معطلی i میشه زمانی که سطل خود را پر می‌کند، نه زمانی که طول می‌کشد سطلش را پر کند!
پس زمانی که منتظر می‌مونه هم باید در نظر بگیرید


(17 اسفند 1392 11:46 ق.ظ)morelo نوشته شده توسط: [ -> ]راجع به سوال ۱۰، ترتیب قرار گرفتن شکی نیست که باید از ۱ تا ۱۰ باشه (حریصانه) اگر فقط زمان پرشدن رو معطلی بگیریم ۵۵ میشه اما اگر زمانی که تو صف هستند رو هم در نظر بگیریم گزینه ۳ میشه.

برای سوال ۱۲، ۴ مولفه نمیشه دوستان؟
یک گراف جهتدار را قویا همبند می‌گوییم اگر و تنها اگر به ازای هر دو راس u و v یک مسیر جهتدار از u به v و یک مسیر جهتدار از v به u وجود داشته باشد.

شکل رو یه نگاه بندازین.

6 تا داره
چهارتا 4 رأسی که واضحن و مشخص کردین
دو تا هم 8 رأسی از وسط، 8 تای وسط افقی و عمودی
سوال ۱۵ :
ایده : درخت کوتاهترین مسیرها : جستجوی اول سطح زمان V+E حال در تعداد راس ها ضرب می کنیم : EV می دانیم که در بدترین حالت تعداد یال ها به دوبرابر تعداد راس ها نزدیک است بنابراین گزینه دوم.

نظر شما ؟
سلام
------------------------
4-1
2-2
3-3
4-4
2-5
1-8
2-9
1-10
4-11
4-15
1-19
3-20
1-35
1-36
1-38
1-44
2-45
(17 اسفند 1392 10:03 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]در مورد سوال ۲ هم نگفته BST اما اگه قید خاصی رو درخت نزاریم بی معنی میشه خصوصا اینکه اگر درخت رو با آرایه پیاده کرده باشن چرا باید زیر درخت سمت راست کامل نشه!! و در ضمن فرم کلیدها BST رو به ما میداد. من اینطوری نوشتم که ۱۳ که هیچ! بعدش ۲ حالت داره برای سطح ۲ و و در سطح ۳ , ۳ حالت داریم که میشه :
!۳ * !۲ = ۱۲

به نام خدا.

"درخت تهی" به جز BST و هم خانواده هاش نداریم!

به نظرم خیلی شفاف نباید بگه که BST هست.

وقتی گفته درخت تهی! و بعدش شکل رو هم کشیده و نحوه قرارگیری عناصر، این دوتا سرنخ کافیه برای اینکه آدم متوجه بشه درخت باید BST باشه


موفق باشید
سلام
لطفا یکی از دوستان توضیح بده که چرا سوال 5 جوابش گزینه 2 یا گزینه 4 میشه. به نظر من گزینه 1 میشه. چون شما میتونید عنصر با اندیس 10 را در زیر ریشه قرار بدید سپس آخرین برگ که گره 100 باشد جایگزین آن میشود. حال مقایسه باید انجام شده تا عدد 100 به آخرین سطح برود. این مقایسه ابتدا بین 2 بچه انجام شده و سپس یک مقایسه با عدد 100 انجام میشود. یعنی برای پایین آمدن هر سطح 2 مقایسه لازم است. چون 5 سطح داریم 10 مقایسه میشود. البته شاید در آخرین سطح 1 مقایسه نیز کافی باشد بنابراین به نظرم جواب 9 میشود. البته تاکید میکنم چون در صورت سوال گفته شده بدترین حالت، سناریوی فوق بدترین حالت را میگوید.

در مورد سوال 14 بین گزینه دوم و اول (طبق نظرات قبلی) شک وجود دارد که لطفا یک نفر دقیقا توضیح دهد.

در مورد سوال 18 نیز بین گزینه اول و دوم شک وجود دارد. دوستانی که میگویند گزینه دوم میشود لطفا مثال نقضی بزنند و یکی از موارد را رد کنند یا دوستانی که میگویند گزینه 1 میشود لطفا استدلالی بگویند.

در مورد سوال 15 هم اکثرا گزینه 4 را میگویند اما یکی از دوستان گزینه 2 را بیان کرد. اگر کسی مثالی دارد که گزینه اول تا سوم را نقض میکند ارائه دهد.
با تشکر
صفحه‌ها: 1 2 3 4
لینک مرجع