مقاله ساختارهای درختی

اختصاصی از حامی فایل مقاله ساختارهای درختی دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود در "پایین مطلب"

فرمت فایل: word (قابل ویرایش و آماده پرینت)
تعداد صفحات:37

بسمه تعالی

امتحان میان ترم درس آمار و احتمال2

دانشگاه پیام نور رضوانشهر

سؤال 1) فرض کنیدX1, X2,…,Xn متغیرهای تصادفی مستقل و هم توزیع از یک توزیع یکنواخت وY1,Y2,…,Yn آماره های ترتیبی مربوط به این نمونهn تایی باشند در این صورت توزیع توام را به دست آورید. (2نمره)

سؤال2) طول عمر قطعات تولیدی یک کارخانه دارای میانگین 5 با واریانس1می باشد. این کارخانه محصولات خود را در بسته های 36 تایی به مشتریان خود عرضه می کند. یکی از مشتریان کارخانه محصولات را در صورتی قبول می کند که حداقل 25 درصد از بسته های ارسالی میانگین طول عمری بیشتر از21/5 داشته باشند. احتمال آن را به دست آورید که یک محموله 12 تایی ارسال شده برای این مشتری پذیرفته شود. (2 نمره)

سؤال3) اگرY,X متغیرهای تصادفی با تابع چگالی توام زیر باشند، توزیعZ=X-Y را به دست آورید. (2 نمره)

استفاده از جدول آماری آزاد است

سربلند و پیروز باشید.

ساختارهای درختی

فایل با ساختار درخت جستجوی دودویی

در فایل با ساختار ترتیبی لازمه استفاده از الگوریتم جستجوی دودویی این است که بلاک های داده ای به طور پیوسته ذخیره شده اند اگر بلاک ها به طور ناپیوسته ذخیره و به هم پیوند شده باشند یافتن آدرس بلاک میانی ناممکن است.

فایل با ساختار درخت جستجوی دودویی باn رکورد و کلید اصلیi=1,2,…,n,ki گونه‌ای از درخت دودویی است که دو خاصیت زیر را دارد.

1- هر گره درخت، بسته به طرز پیاده سازی، حداقل سه یا چهار فیلد در هر دو حالت دو تا از فیلدها حاوی نشانه رو به گره های سمت چپ و سمت راست هستندRPTR, LPTR در حالت وجود سه فیلد، فیلد سوم حاوی خود رکورد است. در غیر این صورت در فیلد سوم کلید رکورد قرار دارد و فیلد چهارم حاوی نشانه روی به بلاک داده ای حاوی رکورد است.

2- اگرki کلید یک رکورد باشد کلید تمام رکوردهای موجود در گره های زیردرخت سمت چپ ازki کوچکتر و کلید تمام رکوردهای موجود در گره های زیر درخت سمت راست، از ki بزرگترند،

عملیات در فایل

واکنش رکورد

الگوریتم واکنشی خیلی ساده است سیستم ابتدا به گره ریشه دستیابی پیدا می کند عمل مقایسه بین کلید رکورد مورد نظر و کلید رکورد موجود در گره ریشه انجام می شود، اگر تساوی برقرار باشد، رکورد پیدا شده است وگرنه، یکی از دو گره سمت راست یا سمت چپ گره ریشه مورد دستیابی قرار می گیرد و عمل مقایسه انجام می شود، این عملیات تا پایان یافتن رکورد مورد نظر یا برخورد به نشانه روی تهی تکرار می شود اگر رکورد مورد نظر در سطحk باشد در حافظه اصلی ذخیره شود برای واکنش رکوردk+1 بار دستیابی مستقیم لازم است.

کارایی این ساختار در واکنشیس رکورد وقتی حداکثر است که ژرفای حداقل باشد و زمانی حداقل است که ژرفای درخت حداکثر باشد.

ژرفای درخت زمانی حداکثر است که در هر سطح تنها یک گره وجود داشته باشد در این حالت ژرفای درختN است و متوسط دستیابی (ANA) مستقیم برای واکنشی رکورد برابر است با:

از طرف دیگر ژرفای درخت زمانی در حداقل است که در هر سطح مثلاً سطحk ام، غیر از سطح ریشه دقیقاًk2 گروه وجود داشته باشد. اگر ژرفای درخت راx فرض کنیم با فرض پربودن تمام درخت داریم:

n=2x-1

و متوسط زمان دستیابی لازم برای واکنشی رکورد برابر است با:

می توان نشان داد که عبارت بالا برابر است با:

عمل درج

اگر درخت خالی باشد، رکورد درج شدنی به آسانی درج می شود. اگر درخت خالی نباشد و کلید رکورد کوچکتر ازکلید رکورد و ریشه باشد، رکورد در سمت چپ ریشه درجه می شود و اگر کلید رکورد از کلید ریشه بزرگتر باشد رکورد در سمت راست ریشه درج می شود. این مقایسه کلیدها در هر سطح دیگر هم تکرار می شود تا نقطه منطقی درج رکورد پیدا شود و عمل جایابی زمانی متوقف می شود که با نشانه روی تهی برخورد شود. بدین ترتیب با درج هر رکورد جدید، یک گره در انتهای یکی از مسیرها ایجاد می شود.

عملیات لازم برای درج رکورد چنین است:

یافتن نقطه منطقی درج

خواندن بلاکی که رکورد باید در آن درج شود (یک بلاک از فضای آزاد)

بازنویسی همین بلاک

بنابراین داریم:

T1=TF+r+s+btt+TRW

حذف رکورد