الگوریتم برنامه

شرح پروژه

۱. یک ساختمان داده مناسب برای نمایش مجموعه ها ارایه کنید.و الگوریتم هایی به نام UNION(اجتماع)،INTERSECTION(اشتراک)، SUBSET(تابع بولی برای بررسی زیر مجموعه بودن و EMPTY(برای بررسی تهی بودن )بنویسید؟

۲.اگر محل فرزندان چپ و راست هر گره در یک درخت دودویی راعوض کنیم .درخت دودویی حاصل را وارونه درخت اولیه مینامیم .الگوریتمی بنویسید که تشخیص دهد درخت دودویی A وارونه درخت دودویی B هست یا نه؟

۳.میگوییم درخت دودویی کامل است هرگاه تمامی گره های ان بجز برگ ها دقیقااا ۲ فرزند داشته باشند .الگوریتمی بنویسید که اشاره گر به یک درخت دودویی را بگیرد و تشخیص دهد که آن درخت کامل است یا نه؟

۴.هرم (heap) یک درخت دودویی است.که در آن مقدار هر گره بزرگتر یا مساوی مقدار فرزندانش (در صورت وجود )باشد.اگر T اشاره گری به یک درخت دودویی باشد .الگوریتمی بنویسید که بررسی کند T شرایط هرم را دارد یا نه؟

۵.الگوریتمی برای یافتن پدر یک گره در یک درخت دودویی نخ کشی شده طراحی کنید؟

۶.درخت دودوییT با n عنصر را در نظر بگیرید . که گر های غیر برگ آن همگی دارای دو فرزند باشند.فرض کنید E(t) و I(t) به ترتیب مجموع عمق برگ ها و مجموع عمق گره های غیر برگ در T باشد.چه رابطه ای بین E(t) و I(t) برقرار است؟ حدس خود را ثابت کنید؟

۷. آیا با در دست داشتن ترتیب ملاقات گره ها در یکی از روش های پیمایش میتوان شکل درخت را به دست آورد؟؟
آیا با در دست داشتن ترتیب ملاقات گره ها در دو روش پیمایش چطور ؟مهم است که کدام دو روش؟؟؟با در اختیار داشتن ترتیب ملاقات گره ها در هر ۳ روش چطور ؟؟در پیمایش پیش ترتیب یک درخت جستجوی دودویی میتوان شکل درخت را به دست اورد؟اگر پاسختان منفی است با یک مثال نشان دهید ؟وگرنه توضیح دهید چگونه؟

۸.در درخت T1 و T2 را ایزومتریک مینامیم چنانچه T1 با جابه جا کردن فرزندان چپ و راست برخی از گرهایش قابل تبدیل به T2 باشد.الگوریتمی بنویسید که تشخیص دهد دو درخت T1 و T2 ایزومورفیک هستند یا نه؟؟؟


۹.درخت دودویی را متوازن مینامیم چنانچه عمق زیردرخت های هر گره آن یکی بیشتر با هم تفاوت نداشته باشند‌.الگوریتمی بنویسید که تشخیص دهد درخت دودویی T متوازن است یا نه؟

۱۰.نشان دهید اگر گرهی در یک درخت جستجوی دودویی دارای دو فرزند باشد.در اینصورت گره بعدیش (در پیمایش میان ترتیب ) فرزند سمت چپ و گره قبلیش فرزند سمت راست ندارد؟

۱۱.اگرx آدرس یک گره در یک درخت نخ کشی شده باشد الگوریتمی بنویسیدکه نشانی گره قبلی x در پیمایش میان ترتیب را برگرداند؟



۱۲.قطر یک درخت برابر است با طول بلندترین مسیر از ریشه به برگ در آن درخت .الگوریتمی بنویسید که قطر درخت دودویی T را بدست آورد؟

مهارت ها و تخصص های مورد نیاز

درباره کارفرما

کاربر85918

عضویت شش سال پیش

86 پروژه ثبت شده ،

0 پروژه در حال انجام ،

0 پروژه آماده دریافت پیشنهاد ،

نرخ پذیرش پیشنهاد 57%