زمان کنونی: ۰۵ دى ۱۴۰۳, ۰۸:۲۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

آی تی- سراسری ۸۵

ارسال:
  

Eng_Sara پرسیده:

آی تی- سراسری ۸۵

عبارت زیر درسته بچه ها؟

"حذف عنصر آخر در یک لیست زنجیره ای یک طرفه، با داشتن اشاره گره های First و Last از مرتبه (۱) O است."

اگه لیست فقط یه دونه گره داشته باشه، یعنی گره اول همون گره آخر باشه این عمل در زمان (۱) O انجام نمیشه؟
یه جا این جمله رو درست در نظر گرفته یه جا غلط!!
ممنون میشم راهنماییم کنید. Shy
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Amir V پاسخ داده:

Re: آی تی- سراسری ۸۵

سلام سارا جان وقت بخیر.

ببین به نظرم غلطه.و از مرتبه n میشه.

چون شما آدرس آخر لیست که به دردت نمیخوره. باید یه اشاره گر از اول بیاری به آخر لیست روی عنصر یکی مونده با آخر و بعد اشاره گر next اون خونه رو nil کنی. که انجام این کار یعنی آوردن یه اشاره گر از اول به اخر لیست وابسته اس به تعداد عناصر لیست و بنابراین از مرتبه O(n) هست.


Sent from my Google Galaxy Nexus using Tapatalk 2.4
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

javadem پاسخ داده:

آی تی- سراسری ۸۵

میشه یه پیاده سازی برای حذف عنصر داشت که [tex]\Theta (1)[/tex] باشه اما بعیده که طراح سوال این پیاده سازی رو مد نظر قرار بده!
میشه یه بیت حذف به ساختمان داده اضافه کرد(به هر نود یک بیت اضفه کنید) و برای حذف کردن گره آخر فقط کافیه این بیت برای گره ای که last در حال اشاره به اونه برابر مقدار حذف(مثلا ۱) قرار بگیره و last به عنصر اول لیست اشاره کنه و first هم به عنصر بعد خودش . حالا هر بار که در پیمایش به رأسی رسیدیم که رأس بعدی اون علامت حذف داشت ترتیب حذف کامل رو میدیم!
حالا اگه یه عنصر داشتیم که سریعا اشاره گر last و first رو null میکنیم.
البته این پیاده سازی برای صف که عنصر اول و آخر مهم اند بدرد نمیخوره و فقط برای لیست کار برد داره!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Eng_Sara پاسخ داده:

RE: آی تی- سراسری ۸۵

Amir V ممنونم بابت توضیحات
چرا بن شدی؟ Sad

javadem ممنونم. Shy
پس کلاً غلطه دیگه این جمله؟!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

javadem پاسخ داده:

آی تی- سراسری ۸۵

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

۰
ارسال:
  

Eng_Sara پاسخ داده:

آی تی- سراسری ۸۵

ممنونم بابت توضیحاتتون.
موفق باشید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  ۸۵۵ نرم افزار farhad_vr32 ۴ ۳,۰۱۱ ۲۱ تیر ۱۳۹۵ ۱۲:۵۱ ب.ظ
آخرین ارسال: farhad_vr32
  ۸۵۲ آی تی و تجارت. ۲۰۰۰ امنیت و شبکه، پشت کنکوری همچنان!!!! م. رجبی ۲ ۴,۰۲۰ ۱۱ آبان ۱۳۹۲ ۱۲:۳۹ ق.ظ
آخرین ارسال: م. رجبی
  تناقض در پاسخ به تست کنکور ۸۵و۸۶ در کتب پارسه و پوران tredex ۱ ۲,۳۹۴ ۱۲ آبان ۱۳۹۰ ۰۸:۴۸ ب.ظ
آخرین ارسال: Masoud05

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close