ساختار داده

شرح پروژه

۱.برای هر یک از کاربردهای زیر بگویید کدام ساختمان داده مناسبتر است؟؟وبرای پاسخ خود دلیل بیاورید؟؟؟؟(صف،پشته،آرایه،لیست پیوندی،گراف،درخت،جدول درهم سازی)
الف.نقشه راه های کشور که در آن فاصله بین دوشهر مشخص باشد.
ب.صفحه شطرنج
پ‌.گراف PERT
ج.مجموعه ها
د.مسابقه وبگاه های ملاقات شده توسط کاربر یک مرورگر وب با قابلیت عقب و جلو رفتن در آن لیست
ی.فرهنگ لغات (دیکشنری)
و.لیست کلمات ۳حرفی با معنی میخواهیم به سرعت بررسی کنیم که یک کلمه ی ۳ حرفی در این لیست وجود دارد یا نه
ن.ترتیب ساخت یک هواپیما

۲.اعداد زیر را به ترتیب از چپ به راست در یک درخت جستجوی دودویی قرار دهید و سپس درخت بدست آمده را رنگ آمیزی کنید بطوری که ویژگی یک درخت سرخ و سیاه را پیدا کند


13     17    8    11   15    1    25   22   6    27


۳.آیا میتوان الگوریتمی از o)n) داشت که n عدد موجود در یک هرم را به ترتیب در یک آرایه بنویسد؟؟برای پاسخ خود دلیل کافی بیاورید؟؟؟

ب) آیا میتوان یک هرم را در o)n) به یک درخت جستجوی دودویی تبدیل کرد؟برای پاسخ خود دلیل کافی بیاورید؟؟؟

۴.یک جدول درهم سازی به طول ۸(HT(8)) و وارسی خطی برای رفع برخورد را در نظر بگیرید .فرص کنید تمام مقادیر تابع درهم سازی دارای احتمال یکسانی باشند .اگر خانه های ۱،۲،۴،۶ جدول پرباشند،میانگین تعداد مقایسه های لازم برای قرار دادن کلید بعدی در جدول چقدر است؟؟؟

ب)آیا جدول درهم سازی برای پیاده سازی فرهنگ لغات (دیکشنری)مناسب است؟؟؟توضیح دهید؟؟


پ)جستجو در جداول درهم سازی چه مزیتی بر جستجو در درخت های VAL دارد؟؟؟

۵.میدانیم که در استفاده از جدول hash بکارگیری تکنیک وارسی خطی برای رفع تصادم از نظر مساله رفع عناصر اشکلاتی به بار اورد ..یکی از روش هایی که برای رفع این مشکل وجود دارد تکنیک پیوند داخلی است..در این روش تمام کلیدهایی را که دارای مقدار تابع hash یکسانی هستند در داخل بردار پیوند قرار میدهیم...

آ)کارایی این تکنیک را در مقایسه با تکنیک پیوند خارجی ارزیابی کنید؟؟

ب)نشان دهید که چگونه استفاده از این تکنیک مشکل حدف عنصر را از بین میبرد؟؟؟


پ)استفاده از این تکنیک به هنگام تصادم دو کلید چه مشکلی را میتواند به وجود اورد؟؟؟؟وچه راهی برای رفع آن پیشنهاد میکنید؟؟؟

۶.اعداد زیر را از چپ به راست در یک جدول درهم سازی به طول m=11 با تابع درهم سازی h۱(k) =kmod(m) وارد کنید؟؟؟


59  88  17  28  15  4  31  22  10

الف)جدول را پس از قرار دادن اعداد رسم کنید .برای رفع برخورد از وارسی خطی استفاده کنید؟

ب)جدول را پس از قرار دادن اعداد رسم کنید.برای رفع برخورد از درهم سازی دوگانه h۲(k) =1+(kmod(m-1))  استفاده کنید ...بیشترین وارسی برای کدام کلید اتفاق می افتد؟؟و مقدار آن چقدر است؟؟

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




۷.یک جدول درهم سازی ۱۱عنصری و تابع h(i)=(2i+5) و کلیدهای زیر از چپ به راست را در نظر بگیرید

12 44  13  88  23  94  11  39  20  16  5

الف)جدول را پس از قرار گرفتن کلیدها رسم کنید برای رفع برخورد از درهم سازی دوگانه استفاده کنید و به عنوان تابع دوم h`(i)=7-(imod 7) را در نظر بگیرید؟؟

ب)بیشترین وارسی برای کدام کلید اتفاق می افتد و مقدار ان چقدر است؟؟


۸.گراف متصل G و راس s در آن داده شده است .الگوریتمی طراحی کنید که راسی که از همه به s دورتر است(از نظر تعداد لبه ها )را پیدا کنید؟؟؟نیازی به نوشتن برنامه نیست فقط الگوریتم خود را به دقت توضیح دهید؟؟؟


بعلاوه دو سوال دیگر که مربوط به پیدا کردن مسیر بحرانی در گراف است.

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

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

کاربر85918

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

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

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

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

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