Linked Lists
مباحث لیست‌های پیوندی.
ساختمان داده کنکور ارشد علوم کامپیوتر
A linked list trades the array's O(1) random access for O(1) insert/delete at a known node, but pays Θ(n) to search — so binary search never applies, even on a sorted list.
یک آرایه n تایی داریم به‌طوری‌که هر خانه آرایه حاوی یک لیست پیوندی یک‌طرفه از n عدد صعودی است. همچنین همه اعداد هر خانه آرایه، کوچک‌تر از همه اعداد خانه بعدی آرایه است. زمان لازم برای جستجو…
حداقل حافظه کمکی لازم برای دو عمل زیر، به‌ترتیب از چپ به راست از چه مرتبه‌ای است؟ برعکس کردن یک لیست پیوندی (linked list) یک طرفه n عضوی برعکس کردن یک لیست پیوندی (linked list) دو طرفه n عضوی
چند تا از گزاره‌های زیر درست است؟ الف) زمان درج یک عنصر در یک لیست پیوندی مرتب Θ(lg n) است. ب) زمان درج یک عنصر در یک آرایه نامرتب Θ(1) است. ج) زمان درج یک عنصر در یک درخت کمینه (یا درخت بیشینه) Θ(lg…
فرض کنید ( x = (x_1, x_2, ..., x_n و ( y = (y_1, y_2, ..., y_m دو لیست پیوندی خطی ساده باشند. مرتبه زمانی الگوریتمی که دو لیست را در لیست z ترکیب می‌کند، کدام است؟ z = (x_1, y_1, x_2, y_2, ……
الگوریتم زیر چه عملی روی لیست پیوندی با آدرس شروع P انجام می‌دهد؟ list listraval(list P) list h if(P == null (P -> link == null)) return(P) h = listraval(P -> link) P -> link -> link = P P -> link =…
فرض کنید L یک لیست پیوندی با n گره به‌صورت زیر باشد. L → ۱ → ۲ → ⋯ → n X (گره NO. i در فیلد info مقدار i و در فیلد link اشاره‌گر به گره بعدی را دارد.) قطعه کد زیر را در نظر بگیرید. x = 0; cur = L…
فرض کنید یک لیست پیوندی یک‌طرفه داریم. می‌خواهیم گره دوم از انتها یعنی گره ماقبل آخر را حذف کنیم. بهترین روش برای انجام این کار چیست؟
فرض کنید P یک لیست تک‌پیوندی باشد و همچنین Q اشاره‌گری به گره‌ی میانی X در لیست باشد. پیچیدگی زمانی بهترین الگوریتم شناخته شده برای حذف گره Q از لیست چیست؟