تالار گفتمان مانشت
ساختمان داده-مهندسی کامپیوتر ۹۴ - نسخه‌ی قابل چاپ

صفحه‌ها: ۱ ۲ ۳ ۴ ۵
ساختمان داده-مهندسی کامپیوتر ۹۴ - saber1366 - 17 بهمن ۱۳۹۳ ۰۲:۲۷ ب.ظ

سلام، لطفا اینجا فقط سوالات ساختمان داده را بزاریم و جواب بدیم.
یک سوال این بود
یک درخت متوازن با n راس. در هر گره تعداد عناصر موجود در زیر درخت را ذخیره کرده ایم، چند تا از اعمال زیر را میتوان در O(logn) انجام داد؟
- یافتن مرتبه عنصر داده شده.
- یافتن تعداد عناصر بین a و b که a<b
- یافتن جمع عناصر بین a و b که a<b

چند تا از اینا درست بودند؟ Confused

بررسی سوالات ساختمان داده - me_pro - 17 بهمن ۱۳۹۳ ۰۲:۳۷ ب.ظ

من زدم ۲تا چون اخریش ضایع n میشد

RE: ساختمان داده - Hamed_H8 - 17 بهمن ۱۳۹۳ ۰۳:۰۰ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۲:۳۷ ب.ظ)me_pro نوشته شده توسط:  من زدم ۲تا چون اخریش ضایع n میشد

من هم ۲ تا زدم !

RE: ساختمان داده - saber1366 - 17 بهمن ۱۳۹۳ ۰۳:۰۶ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۳:۰۰ ب.ظ)Hamed_H8 نوشته شده توسط:  
(17 بهمن ۱۳۹۳ ۰۲:۳۷ ب.ظ)me_pro نوشته شده توسط:  من زدم ۲تا چون اخریش ضایع n میشد

من هم ۲ تا زدم !

منم زدم دو تا.

ساختمان داده-مهندسی کامپیوتر ۹۴ - ziba.O - 17 بهمن ۱۳۹۳ ۰۳:۳۲ ب.ظ

می توو

ساختمان داده-مهندسی کامپیوتر ۹۴ - arash691 - 17 بهمن ۱۳۹۳ ۰۴:۰۰ ب.ظ

از حل رابطه بازگشتی سوال ندادن ؟ :دی

ساختمان داده-مهندسی کامپیوتر ۹۴ - m.teymourpour - 17 بهمن ۱۳۹۳ ۰۴:۰۲ ب.ظ

منم زدم ۲ تا

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - sourena - 17 بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ

اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - hadinahavandi - 17 بهمن ۱۳۹۳ ۰۴:۱۰ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

Log* اوردم من.

ساختمان داده-مهندسی کامپیوتر ۹۴ - sourena - 17 بهمن ۱۳۹۳ ۰۴:۱۲ ب.ظ

من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - newwink - 17 بهمن ۱۳۹۳ ۰۴:۱۳ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

من زدم :
Lg*n
درسته؟
چون این گزینه برای اعداد خیلی بزرگ میشه ۶ ؟؟

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - Masoud05 - 17 بهمن ۱۳۹۳ ۰۴:۲۴ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

جوابش بنظرم به سمت یه عدد میل میکنه. گزینه ها رو نمیدونم چیه اما *Log هم یه عدد ثابت فرض میشه.

ساختمان داده-مهندسی کامپیوتر ۹۴ - arash691 - 17 بهمن ۱۳۹۳ ۰۴:۲۵ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۴:۱۲ ب.ظ)sourena نوشته شده توسط:  من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

یعنی n تا لگاریتم تو در تو :-) ( زیاد درست نیست این تعریف )

تعریف درستش
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - Masoud05 - 17 بهمن ۱۳۹۳ ۰۴:۲۹ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۲:۲۷ ب.ظ)saber1366 نوشته شده توسط:  سلام، لطفا اینجا فقط سوالات ساختمان داده را بزاریم و جواب بدیم.
یک سوال این بود
یک درخت متوازن با n راس. در هر گره تعداد عناصر موجود در زیر درخت را ذخیره کرده ایم، چند تا از اعمال زیر را میتوان در O(logn) انجام داد؟
- یافتن مرتبه عنصر داده شده.
- یافتن تعداد عناصر بین a و b که a<b
- یافتن جمع عناصر بین a و b که a<b

چند تا از اینا درست بودند؟ Confused

اگر درخت صرفا متوازن باشه هیچ کدوم در زمان log n حل نمیشه مگه اینکه صورت سوال رو بد گذاشته باشید!! مثلا برای مورد ۲ در یک درخت متوازن وقتی ندونیم ترتیب کلیدها چطوره عملا یک جستجو خطی نیاز داریم که مرتبه اون در بدترین حالت خطی است . مورد ۳ هم که مشخصه که مرتبه خطی داره.

RE: ساختمان داده-مهندسی کامپیوتر ۹۴ - me_pro - 17 بهمن ۱۳۹۳ ۰۴:۳۶ ب.ظ

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

log*(n)=t درس بود