ساختمان داده

شرح پروژه

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

2.به سوالات زیر پاسخ دهید و برای پاسخ های خود توضیح مختصری بنویسید؟؟


الف) چگونه میتوان مرتب کردن مبنائی را برای مرتب کردن کلیدهای الفبا عددی به کار گرفت؟؟؟

ب) الگوریتم مرتب کردن ادغامی دوطرفه در بهترین و بدترین حالت به چند گذر نیاز دارد؟؟؟

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

ت)چه موقع استفاده از مرتب کردن شمارشی ایده خوبی نیست؟؟؟

ث) کارآمدترین روش برای مرتب کردن آرایه ای که تقریباااا مرتب باشد چیست؟؟؟؟

3.برای هر یک از کاربردهای زیر بگوئید کدام ساختمان داده مناسبتر است و برای پاسخ خود دلیل بیاورید؟؟؟


الف) نقشه راه های کشور که در آن فاصله بین هر دو شهر مشخص باشد.


ب)صفحه شطرنج

پ) ترتیب مراحل ساخت یک هواپیما

ت) لیست کلمات ۳ حرفی با معنی .میخواهیم به سرعت بررسی کنیم که یک کلمه ۳ حرفی در لیست وجود دارد یا نه

ث) گراف PERT

ج) مجموعه ها

چ) سابقه وبگاه های ملاقات شده توسط کاربر یک مرورگر وب با قابلیت عقب و جلو رفتن در آن لیست

ح)فرهنگ لغات (دیکشنری)

ن) صف اولویت

3.آیا میتوان مرتب کردن سریع را به گونه ای اصلاح کرد که در بهترین حالت زمانی معادل o(n)  بگیرد؟؟توضیح دهید؟؟؟



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


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

5. چند درخت AVL با کلیدهای ۱،۲،۳،۴،۵ میتوان ساخت؟؟؟؟


6.ثابت کنید برای هر عدد صحیح n>0 یک درخت دودویی با n برگ وجود دارد؟؟


7. اگر گرهی در یک درخت جستجوی دودویی دارای ۲ فرزند باشد ، در این صورت گره های قبلی و بعدی اش از نظر تعداد و نوع فرزند چه وضعیتی دارند .؟؟؟برای جواب خود دلیل بیاورید؟؟؟

8. نشان دهید در گراف جهت دار مجموع درجه ورودی کلیه گره ها برابر با مجموع درجه خروجی کلیه گره ها و این مجموع برابر با تعداد لبه ها؟؟؟


9.یک جدول درهم سازی (hash ) مناسب برای شماره ماشین ها که رشته ای  است به شکل ۹۹×۹۹۹ طراحی کنید.۹ نشانگر یک رقم و x نشانگر یکی از حروف الفبای فارسی است؟؟


10) الف ) کدام یک از روش های مرتب کردن که در کلاس بحث شد توازی پذیرند؟؟ و چگونه؟؟؟( مرتب کردن درجی....انتخابی....انتخابی دو طرفه....مربعی .....حبابی.....حبابی دوطرفه....سریع ....ادغامی...... شِل....مبنائی.....هرمی)
یعنی اگر کامپیوتر دارای چند پردازنده باشد،میتوان قسمتهایی از عمل مرتب کردن را بطور همزمان و مستقل از هر قسمت دیگر اجرا کرد.???

ب) کدامیک از الگوریتم های مرتب سازی کمترین وابستگی را به ترتیب اولیه عناصر دارند؟؟؟؟ به طور مختصر توضیح دهید؟؟؟

11) با در نظر گرفتن نمایش ماتریس همجواری و لیست های همجواری برای گراف ها به دقت توضیح دهید که برای گراف های زیر کدام روش نمایش را انتخاب میکنید؟؟؟

الف) گراف شبکه راه های کشور

ب) گراف هزینه های تلفن راه دور بین کشورهای مختلف جهان

 12.الف ) در ۲یا۳جمله بطور واضح توضیح دهید که مرتب کردن هرمی چگونه کار میکند؟؟

ب) دو دلیل برای اینکه درخت دودویی زیر یک هرم نیست بنویسید؟؟؟


13. استفاده از تکنیک های جستجو در جداول hash چه مزیتی بر جستجو در درختهای جستجوی دودوئی دارد؟؟؟

14. الف)چرا هر گراف PERT باید حداقل یک مسیر بحرانی از مبدا به مقصد داشته باشد؟؟؟


ب) چرا مسیر بحرانی در گراف PERT طولانی ترین مسیر از مبدا به مقصد نیز هست؟؟؟

15.پیمایش درخت های دودویی ریسه ای چه مزیتی بر پیمایش درخت های دودوئی دارد؟؟؟


16.توضیح دهید که چگونه الگوریتم رمزگذاری نامتقارن میتواند برای دستیابی به اهداف زیر مورد استفاده قرار گیرد:

الف)احراز هویت: گیرنده بداند که فرستنده تنها کسی است که میتوانسته پیام را تولید کند.


ب)محرمانگی: تنها گیرنده بتواند پیام را رمزگشایی کند.


پ) احراز هویت و محرمانگی: تنها گیرنده بتواند پیام را رمزگشایی کند و گیرنده بداند که فرستنده تنها کسی است که میتوانسته پیام را تولید کند.

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

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

کاربر85918

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

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

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

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

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