۱
subtitle
ارسال: #۱
سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
سلام.
تست ۴۹ از کنکور مهندسی کامپیوتر ۹۲.
![[تصویر: 230257_Q.png]](https://img.manesht.ir/230257_Q.png)
پاسخ گزینه ۲ است.
به نظر من گزینه ۳ صحیح است.
به نظر من الف را نمی توان ایجاد کرد. اگر می توان ایجاد نمود لطفا توضیح دهید چگونه است.
به نظر من ب را می توان ایجاد نمود. کافی است یک min heap داشته باشیم. ابتدا آرایه را در مرتبه [tex]O(n)[/tex] به مین هیپ تبدیل می کنیم و درج و حذف، با [tex]O(logn)[/tex] قابل انجام می باشد.
سپاس...
تست ۴۹ از کنکور مهندسی کامپیوتر ۹۲.
پاسخ گزینه ۲ است.
به نظر من گزینه ۳ صحیح است.
به نظر من الف را نمی توان ایجاد کرد. اگر می توان ایجاد نمود لطفا توضیح دهید چگونه است.
به نظر من ب را می توان ایجاد نمود. کافی است یک min heap داشته باشیم. ابتدا آرایه را در مرتبه [tex]O(n)[/tex] به مین هیپ تبدیل می کنیم و درج و حذف، با [tex]O(logn)[/tex] قابل انجام می باشد.
سپاس...
۰
ارسال: #۲
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
ارسال: #۳
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۱:۴۲ ب.ظ)izadan11 نوشته شده توسط: شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
تشکر.
اگر امکان دارد کمی در مورد چگونگی انجام ساختمان الف توضیح دهید. اینکه چطور درج و حذف از مرتبه logn است و چگونه یک بازه از مقادیر را می توان در زمان logn پیدا کرد.
ارسال: #۴
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۲:۲۶ ب.ظ)Morris نوشته شده توسط:هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)(21 آذر ۱۳۹۲ ۰۱:۴۲ ب.ظ)izadan11 نوشته شده توسط: شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
تشکر.
اگر امکان دارد کمی در مورد چگونگی انجام ساختمان الف توضیح دهید. اینکه چطور درج و حذف از مرتبه logn است و چگونه یک بازه از مقادیر را می توان در زمان logn پیدا کرد.
ارسال: #۵
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۲:۳۲ ب.ظ)izadan11 نوشته شده توسط: هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)
در مورد قسمت الف پرسیدم، فکر می کنم منظورتان از "درخت باینری متوازن" همان AVL می باشد. ممکن است توضیح دهید چطور یافتن مقادیر بین دو مقدار مثلا a و b را در logn می توان اجرا کرد؟
ارسال: #۶
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۱:۴۲ ب.ظ)izadan11 نوشته شده توسط: شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
دوست عزیز مگه AVL همه چیزش BIG O نیست؟ پس چرا مورد اولی که با small O هست میگی قابل قبوله؟
ی چیز دیگه من تو ویکی پدیا نگاه کردم زمان حذف هیپ فیبونانچی رو زده big O که .... موضوع چیه؟!!!
ارسال: #۷
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۰۸ بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ)zahra412 نوشته شده توسط:(21 آذر ۱۳۹۲ ۰۱:۴۲ ب.ظ)izadan11 نوشته شده توسط: شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه
دوست عزیز مگه AVL همه چیزش BIG O نیست؟ پس چرا مورد اولی که با small O هست میگی قابل قبوله؟
ی چیز دیگه من تو ویکی پدیا نگاه کردم زمان حذف هیپ فیبونانچی رو زده big O که .... موضوع چیه؟!!!
من اینجور برداشت کردم که نظر طراح اینه که فقط اون که کنارش نوشته (اوی کوچیک) اوی کوچیک هست و بقیه اش رو اوی بزرگ در نظر گرفتم
(۲۱ آذر ۱۳۹۲ ۰۷:۱۸ ب.ظ)Morris نوشته شده توسط:(21 آذر ۱۳۹۲ ۰۲:۳۲ ب.ظ)izadan11 نوشته شده توسط: هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)در مورد قسمت الف پرسیدم، فکر می کنم منظورتان از "درخت باینری متوازن" همان AVL می باشد. ممکن است توضیح دهید چطور یافتن مقادیر بین دو مقدار مثلا a و b را در logn می توان اجرا کرد؟
یه متغییر به عنوان تعداد فرزندان به پارامتر های نود اضافه کنیم
ارسال: #۸
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
واسه دومی ساختمان داده نمیشه طراحی کرد، چون اگه بشه ما میتونیم n بار حذف رو صدا بزنیم و بتونیم باهاش یه آرایه رو توی زمان [tex]o(n \lg n)[/tex] مرتب کنیم که این تناقض داره با این [tex]\Omega(n \lg n)[/tex].
ارسال: #۹
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
۰
ارسال: #۱۰
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
واسه الف شما از dynamic order statistic باید استفاده کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.
واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.
واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.
ارسال: #۱۱
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۷:۳۳ ب.ظ)Riemann نوشته شده توسط: واسه الف شما از dynamic order statistic باید استفاده کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.
واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.
تشکر فراوان !
این دو مورد "dynamic order statistic" و "Fibonacci heap" جایی ازش صحبت نشده لااقل من ندیدم. از چه منبعی این مواردو بررسی کنم ؟
تشکر.
ارسال: #۱۲
RE: سوال ساختمان داده : تست ۴۹ مهندسی ۹۲
(۲۱ آذر ۱۳۹۲ ۰۹:۵۸ ب.ظ)Morris نوشته شده توسط:(21 آذر ۱۳۹۲ ۰۷:۳۳ ب.ظ)Riemann نوشته شده توسط: واسه الف شما از dynamic order statistic باید استفاده کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.
واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.
تشکر فراوان !
این دو مورد "dynamic order statistic" و "Fibonacci heap" جایی ازش صحبت نشده لااقل من ندیدم. از چه منبعی این مواردو بررسی کنم ؟
تشکر.
من dynamic order statistic رو توی کتاب قدسی خوندم، Fibonacci heap هم در حد این که مرتبه زمانیاش چی میشه. توی کتاب clrs هم همه ی اینا هست توی فصل augmenting data structures فصل ۱۴ و فصل ۱۹ هم که Fibonacci heap هست ولی نیاز نیست بخونیدش مقاله ویگی پدیا بهتره.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close