سوالات

زمان بدترین حالت برای یافتن عنصر مینیمم در یک درخت جستجوی دودویی (binary search tree) چیست؟

کدام مورد درخصوص یک درخت جستجوی دودویی برای n عدد صحیح است؟

کدام مورد درخصوص درخت جستجوی دودویی بهینه نادرست است؟

اعداد ۱ تا ۶ را به‌ترتیب وارد یک پشته (انباره، Stack) کرده‌ایم. ترتیب خروجی اعداد از پشته از کدام گزینه نمی‌تواند باشد؟ (اعداد را از راست به چپ بخوانید.)

«الف» و «ب» به‌ترتیب از راست به چپ چه داده ساختاری هستند؟ درخت الف (راست): 5 / 3 2 / 1 درخت ب (چپ): 5 2 / 1 3

مرتبه زمانی لازم برای تبدیل یک heap با n کلید (عدد) به یک درخت جستجوی دودویی (BST) کدام است؟

چه تعداد از گزاره‌های زیر درست است؟ الف) زمان پیداکردن یک عنصر در یک لیست پیوندی مرتب با n عضو، Θ(n) است. ب) زمان پیداکردن یک عنصر در یک آرایه نامرتب با n عضو، Θ(n) است. ج) زمان پیداکردن یک عنصر در…

یک آرایه n تایی داریم به‌طوری‌که هر خانه آرایه حاوی یک لیست پیوندی یک‌طرفه از n عدد صعودی است. همچنین همه اعداد هر خانه آرایه، کوچک‌تر از همه اعداد خانه بعدی آرایه است. زمان لازم برای جستجو…

عدد طبیعی n و عدد طبیعی a_1, …, a_n داده شده است. قصد داریم بدانیم دو اندیس i و j وجود دارد که 0 < a_i - a_j ≤ 5 یا خیر. زمان متوسط لازم برای این منظور با استفاده از درهم‌سازی (Hashing) از چه…

کدام گزاره یا گزاره‌ها درست است؟ الف) سومین بزرگ‌ترین کلید در یک MAX heap با کلیدهای متمایز می‌توان با اندیس ۲ باشد در درایه. ب) سومین بزرگ‌ترین کلید در یک MAX heap با کلیدهای متمایز می‌توان با اندیس…

کدام درخت یا درخت‌ها را می‌توان با یک چرخش (rotation) به درخت AVL تبدیل کرد؟ درخت AVL، درختی است که در آن برای هر رأس، قدر مطلق اختلاف ارتفاع زیر درخت‌های راست و چپ، حداکثر یک است. همچنین چرخش…

حداقل حافظه کمکی لازم برای دو عمل زیر، به‌ترتیب از چپ به راست از چه مرتبه‌ای است؟ برعکس کردن یک لیست پیوندی (linked list) یک طرفه n عضوی برعکس کردن یک لیست پیوندی (linked list) دو طرفه n عضوی

کدام گزاره یا گزاره‌ها درست است؟ الف) ارتفاع یک درخت جستجوی دودویی (binary search tree) با ۱۰ کلید می‌تواند ۹ باشد. ب) اگر داده‌های کلیدی اعداد ۷،...،۲،۱ باشند فقط یک درخت جستجوی دودویی به ارتفاع ۲…

چند تا از گزاره‌های زیر درست است؟ الف) زمان درج یک عنصر در یک لیست پیوندی مرتب Θ(lg n) است. ب) زمان درج یک عنصر در یک آرایه نامرتب Θ(1) است. ج) زمان درج یک عنصر در یک درخت کمینه (یا درخت بیشینه) Θ(lg…

n عدد طبیعی a₁,a₂,...,aₙ داده شده است. در جستجوی دو عدد مانند aᵢ و aⱼ هستیم که aᵢ = ۲aⱼ بهترین زمان متوسط برای این مسأله از چه مرتبه‌ای است؟ (استفاده از درهم‌سازی)

در یک درخت جستجوی باینری، الگوریتم یافتن median دارای چه مرتبه زمانی است؟

در درخت AVL زیر با حذف کدام گره درخت هنوز AVL باقی می‌ماند؟

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

کدام‌یک از جملات زیر صحیح است؟

فرض کنید ‪( x = (x_1, x_2, ..., x_n‬ و ‪( y = (y_1, y_2, ..., y_m‬ دو لیست پیوندی خطی ساده باشند. مرتبه زمانی الگوریتمی که دو لیست را در لیست z ترکیب می‌کند، کدام است؟ z = (x_1, y_1, x_2, y_2, ……

در درخت جستجوی باینری زیر با حذف ریشه‌یک از عناصر زیر جایگزین می‌شود؟

اعداد ۱ تا ۶ به ترتیب از کوچک به بزرگ در ورودی یک پشته خالی (Stack) داده شده است و اعمال زیر بر روی پشته قابل انجام است: Push: کوچک‌ترین عدد ورودی را برداشته و در پشته قرار می‌دهد. Pop: عضو بالای…

تابع زیر آدرس ریشه یک درخت را دریافت می‌کند. این تابع چه عملی انجام می‌دهد؟ int func(TreeNode T) if (T == NULL) return(۰); else m۱ = ۱ + func(T → leftChild); m۲ = ۱ + func(T → rightChild); if(m۱ >…

فرض کنید با استفاده از تابع هش همانی h(x) = x که با استفاده از linear probing پیاده‌سازی شده است داده‌هایی را در یک آرایه قرار داده‌ایم و نتیجه به صورت زیر شده است. ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸…

اگر یک درخت AVL با یک گره دارای عمق صفر باشد، آنگاه کمترین و بیشترین تعداد گره در یک درخت AVL بالانس با عمق ۵ چقدر است؟

در یک هیپ (heap) با اندازه n حداکثر تعداد گره‌های چپ ریشه چند است؟

اگر در ذخیره‌سازی یک ماتریس آدرس خانه‌ی A[۰,۱] برابر 7A00 و آدرس خانه‌ی A[۱,۱] برابر 7A10 باشد (در مبنای ۱۶)، آن‌گاه ذخیره‌سازی ماتریس به چه صورتی است؟

الگوریتم زیر چه عملی روی لیست پیوندی با آدرس شروع 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 =…

فرض کنید که درخت دودویی T را یک بار پیمایش inorder و یک بار پیمایش postorder کرده‌ایم. آخرین عنصر در این دو پیمایش یکسان می‌باشد. درباره این درخت کدام مورد صحیح است؟

در کدام‌یک از درختان زیر ارتفاع دو زیر درخت هر گره‌ای حداکثر دارای فاصله ۱ است؟

الگوریتم زیر برای آرایهٔ x با n عنصر چه عملی انجام می‌دهد؟ f() s = new AVL-Tree for i = 1 to n do if s.member(x[i]) s.delete(x[i]) else s.insert(x[i]) for i = 1 to n do if not s.member(x[i])…

درخت جستجوی دودویی بهینه برای نمونه زیر کدام است؟ اعداد ۱ ۲ ۳ ۴ ۵ --- --- --- --- --- --- احتمال جستجو ۰/۲ ۰/۴ ۰/۰۵ ۰/۱ ۰/۲۵

فرض کنید L یک لیست پیوندی با n گره به‌صورت زیر باشد. L → ۱ → ۲ → ⋯ → n X (گره NO. i در فیلد info مقدار i و در فیلد link اشاره‌گر به گره بعدی را دارد.) قطعه کد زیر را در نظر بگیرید. x = 0; cur = L…

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

فرض کنید یک پشته (Stack) پیاده‌سازی شده با استفاده از یک لیست پیوندی با عناصر یکتا داریم. این پشته به عمل اصلی push و pop را پشتیبانی می‌کند. حال می‌خواهیم تابعی اضافه کنیم که عنصر مینیمم (کوچک‌ترین…

فرض کنید می‌خواهیم یک داده‌ساختار طراحی کنیم که هم‌زمان قابلیت‌های یک صف معمولی و یک صف اولویت (Priority Queue) را داشته باشد. این داده‌ساختار باید بتواند عملیات‌های زیر را انجام دهد: افزودن یک عنصر…

فرض کنید می‌خواهیم یک عبارت ریاضی را که شامل پرانتزهای باز و بسته، عملگرهای ریاضی (+, -, ×, div) و اعداد است، به یک عبارت پسوندی (Postfix) تبدیل کنیم و برای این کار از ترکیبی از پشته و صف استفاده…

فرض کنید L_n زیرمجموعه‌ای از ZtimesZ به‌صورت زیر باشد: L_n= (i,j) middle i+j≤ n, i≥ ∘, j≥ ∘ همچنین برای هر (i,j) در L_n مجموعه همسایه‌های (i,j) را به‌صورت زیر تعریف کنیم: N_n(i,j)= (k,m)∈ L_n: ۱≤ i-k…

فرض کنید نتیجه یک ماتریس ریشه R از درخت جستجوی دودویی بهینه به‌صورت جدول زیر حاصل شده است و I_۱ < I_۲ < I_۳ < I_۴ کلیدها و p_۱ = p_۳ = ۳/۸ و p_۲ = p_۴ = ۱/۸ احتمال جستجوی این درخت دودویی هستند. کدام…

آرایه A شامل n عدد صحیح در مکان A[۱]⋯ A[n-۱] و A[۰] است. لازم است عناصر آرایه به‌صورت چرخه‌ای به‌اندازه k مکان به سمت چپ منتقل شوند، که در آن ۰ ≤ k ≤ n-۱ است. یک الگوریتم ناقص برای انجام این کار در…