مبانی و ساختارهای داده در مهندسی کامپیوتر: عملیات درج در لیست پیوندی - کوییز

1. تخصیص حافظه برای گره جدید، تنظیم اشاره گر next گره جدید به گره فعلی سر (head)، و به روزرسانی سر لیست به گره جدید.
2. پیمایش لیست تا رسیدن به انت های آن، تنظیم اشاره گر next آخرین گره به گره جدید، و تنظیم اشاره گر next گره جدید به null.
3. تخصیص حافظه برای گره جدید، یافتن گره قبل از موقعیت درج، تنظیم اشاره گر next گره قبل به گره جدید، و تنظیم اشاره گر next گره جدید به گره اصلی بعد از گره قبل.
4. تخصیص حافظه برای گره جدید، تنظیم اشاره گر prev گره جدید به گره قبلی، و تنظیم اشاره گر next گره جدید به گره بعدی.

گزینه صحیح: 1

توضیح: درج در ابتدای لیست پیوندی یک طرفه ساده ترین حالت است. ابتدا حافظه برای گره جدید تخصیص داده می شود. سپس، اشاره گر next این گره جدید به گره ای که قبلاً سر لیست بوده است، اشاره می کند. در نهایت، سر لیست به این گره جدید به روزرسانی می شود تا گره جدید اولین عنصر لیست باشد.

1. پیمایش لیست تا رسیدن به آخرین گره و سپس تنظیم اشاره گر next آن به گره جدید.
2. تنظیم اشاره گر next گره جدید به null و سپس به روزرسانی سر لیست.
3. تخصیص حافظه برای گره جدید و تنظیم اشاره گر next آن به سر لیست.
4. یافتن گره قبل از موقعیت درج و تنظیم اشاره گر next آن به گره جدید.

گزینه صحیح: 1

توضیح: برای درج در انت های لیست پیوندی یک طرفه، ابتدا باید آخرین گره لیست را پیدا کنیم. این کار با پیمایش لیست از سر تا زمانی که اشاره گر next گره فعلی null باشد، انجام می شود. پس از یافتن آخرین گره، اشاره گر next آن به گره جدید تنظیم می شود.

1. پیمایش لیست تا گره k ام، تخصیص حافظه برای گره جدید، تنظیم اشاره گر next گره جدید به گره k+1 ام، و تنظیم اشاره گر next گره k ام به گره جدید.
2. تخصیص حافظه برای گره جدید، تنظیم اشاره گر next گره جدید به گره k ام، و به روزرسانی سر لیست.
3. پیمایش لیست تا گره k+1 ام، تنظیم اشاره گر next گره جدید به گره k+1 ام، و تنظیم اشاره گر next گره k ام به گره جدید.
4. تنظیم اشاره گر next گره جدید به null و سپس یافتن گره k ام.

گزینه صحیح: 1

توضیح: درج در میانه لیست پیوندی یک طرفه نیازمند یافتن گره ای است که قبل از موقعیت درج قرار دارد (گره k ام). پس از تخصیص حافظه برای گره جدید، اشاره گر next آن به گره ای که در حال حاضر بعد از گره k ام قرار دارد (گره k+1 ام) اشاره داده می شود. سپس، اشاره گر next گره k ام به گره جدید تنظیم می شود.

1. اشاره گر prev گره جدید و اشاره گر prev گره قبلی.
2. اشاره گر next گره قبلی و اشاره گر prev گره بعدی.
3. اشاره گر prev گره جدید و اشاره گر next گره بعدی.
4. اشاره گر prev گره جدید و اشاره گر next گره قبلی.

گزینه صحیح: 3

توضیح: در لیست پیوندی دو طرفه، هر گره هم اشاره گری به گره بعدی (next) و هم اشاره گری به گره قبلی (prev) دارد. هنگام درج یک گره جدید، باید اشاره گر prev گره جدید به گره قبلی و اشاره گر next گره جدید به گره بعدی اشاره کند. هم چنین، اشاره گر next گره قبلی باید به گره جدید و اشاره گر prev گره بعدی باید به گره جدید اشاره داده شود.

1. نیاز به به روزرسانی اشاره گر prev گره جدید و اشاره گر prev آخرین گره فعلی دارد.
2. همیشه نیاز به پیمایش کامل لیست دارد، حتی اگر اشاره گر به انت های لیست موجود باشد.
3. پیچیدگی زمانی آن همیشه O(n) است، در حالی که در لیست یک طرفه می تواند O(1) باشد.
4. نیازی به دسترسی به آخرین گره ندارد.

گزینه صحیح: 1

توضیح: در لیست پیوندی دو طرفه، هنگام درج در انت ها، علاوه بر تنظیم اشاره گر next آخرین گره به گره جدید، باید اشاره گر prev گره جدید نیز به آخرین گره فعلی تنظیم شود. هم چنین، اشاره گر prev آخرین گره فعلی باید به گره جدید اشاره داده شود.

1. گره جدید به عنوان اولین و آخرین گره لیست در نظر گرفته می شود و اشاره گر های next و prev آن به null تنظیم می شوند. هم چنین سر و انت های لیست به این گره جدید اشاره می کنند.
2. گره جدید در انت های لیست درج می شود و سر لیست به آن اشاره می کند.
3. گره جدید در ابتدای لیست درج می شود و انت های لیست به آن اشاره می کند.
4. عملیات درج امکان پذیر نیست تا زمانی که حداقل یک گره در لیست وجود داشته باشد.

گزینه صحیح: 1

توضیح: هنگام درج اولین گره در یک لیست پیوندی (چه یک طرفه و چه دو طرفه)، آن گره هم سر (head) و هم انت های (tail) لیست خواهد بود. بنابراین، اشاره گر های next و prev آن به null تنظیم می شوند و هر دو اشاره گر head و tail به این گره جدید اشاره می کنند.

1. تنظیم next گره جدید به گره i ام، prev گره جدید به گره i-1 ام، next گره i-1 ام به گره جدید، و prev گره i ام به گره جدید.
2. تنظیم next گره جدید به گره i-1 ام، prev گره جدید به گره i ام، next گره i ام به گره جدید، و prev گره i-1 ام به گره جدید.
3. تنظیم next گره جدید به گره i ام، prev گره جدید به گره i-1 ام، next گره i ام به گره جدید، و prev گره i-1 ام به گره جدید.
4. تنظیم next گره جدید به گره i-1 ام، prev گره جدید به گره i ام، next گره i-1 ام به گره جدید، و prev گره i ام به گره جدید.

گزینه صحیح: 1

توضیح: برای درج گره جدید در موقعیت i ام (بعد از گره i-1 ام)، ابتدا گره جدید باید به گره i ام (بعدی) و گره i-1 ام (قبلی) اشاره کند. سپس، گره i-1 ام باید به گره جدید اشاره کند و گره i ام نیز باید اشاره گر prev خود را به گره جدید به روز کند.

1. گره جدید هم head و هم tail لیست می شود.
2. گره جدید به عنوان دومین عنصر لیست درج می شود.
3. اشاره گر next گره جدید به null تنظیم می شود.
4. عملیات درج مجاز نیست.

گزینه صحیح: 1

توضیح: اگر لیست پیوندی خالی باشد (head برابر با null)، درج اولین گره در ابتدای لیست به این معنی است که این گره جدید هم head و هم tail لیست خواهد شد. بنابراین، اشاره گر next آن به null تنظیم می شود و head و tail هر دو به این گره جدید اشاره می کنند.