نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۷-۹۸
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرایی تابع زمانی زیر کدام گزینه است؟ T(n)=n^5 logn+6n+2^n
2. مرتبه زمانی الگوریتم جستجوی دودویی و الگوریتم جستجوی ترتیبی در بهترین حالت به ترتیب کدام گزینه است؟
3. تعداد درخت های جستجوی دودویی با n گره و تعداد عمل ضرب حاصل از ضرب n ماتریس در یکدیگر به ترتیب از کدام رابطه بدست می آید؟
4. مرتبه زمانی شبه کد زیر چیست؟ j=n; for(i=1;i<n;i++) while(j>1) j/=2;
5. الگوریتم مرتب سازی سریع در بدترین حالت چه مرتبه زمانی دارد و این بدترین حالت چه موقع رخ می دهد؟
6. می خواهیم یک ماتریس پایین مثلثی را در یک آرایه یک بعدی ذخیره سازی نماییم که عضو آن با اندیس یک بعدی k مشخص می شود. بین اندیس دو بعدی i,j و اندیس یک بعدی k در آرایه کدام گزینه درست است؟
7. اگر در یک صف حلقوی front=-1 و rear=-1 باشد این صف دارای چند عنصر است؟
8. کدام گزینه یک عمل اصلی در مورد آرایه می باشد؟
9. شرط پر و خالی بودن صف حلقوی به ترتیب از چپ به راست کدام گزینه است؟
10. مرتبه زمانی درج یک عنصر در یک آرایه مرتب و مرتبه زمانی درج یک عنصر در آرایه نامرتب به ترتیب برابر است با.......
11. در الگوریتم جستجوی دودویی زمانیکه عنصر مورد جستجو در داخل آرایه مورد جستجو قرار ندارد (L اشاره به اولین عنصر آرایه و h اشاره به آخرین عنصر آرایه دارد) در مراحل اجرای الگوریتم در نهایت به چه صورت خواهد شد؟
12. جهت تبدیل عبارت میانوندی زیر به عبارت پسوندی با استفاده از پشته، حداکثر سایز پشته مورد نیاز برابر است با: a×b+c/d^e
13. تعداد سطرها و ستون ها در ذخیره سازی یک ماتریس اسپارس به ترتیب به چه صورت است؟
14. اگر دنباله اعداد 9،7،5،3،1 را به ترتیب از چپ به راست در پشته وارد کنیم کدامیک از خروجی های زیر از این پشته امکان پذیر نیست؟
15. پیمایش میان ترتیب (inorder) یک درخت جستجوی دودویی (BST) چه ویژگی دارد؟
16. یک درخت دودویی با 20 گره مفروض است. اگر تعداد گره های درجه 2 برابر 8 گره باشد، تعداد گره های برگ و تعداد گره های درجه 1 به ترتیب چند تاست؟
17. در کدام نوع درخت های دودویی همه گره ها به جز گره های سطح آخر، ماکزیمم تعداد فرزندان را دارند؟
18. درخت متوازن درختی است که........
19. معادل پیشوندی عبارت زیر کدام است؟ (^ علامت توان است.) a+b×c^d^e
20. پیمایش پس ترتیب (postorder) و میان ترتیب (inorder) یک درخت به صورت زیر است. پیمایش پیش ترتیب (preorder) آن کدام گزینه است؟ میانوندی: BAEGFC — پسوندی: BGFECA
21. مرتبه زمانی کدام الگوریتم مرتب سازی در همه شرایط یکسان است و برابر با کدام گزینه است؟
22. کدامیک از الگوریتم های مرتب سازی زیر در همه حالات (بهترین حالت، بدترین حالت و حالت میانگین) دارای مرتبه زمانی یکسانی نیستند؟
23. مجموع وزن های درخت پوشای مینیمم با استفاده از الگوریتم پریم بر روی گراف زیر کدام گزینه است؟
24. حاصل عبارت پسوندی زیر چیست؟ 1 2 + 3 × 14 4 1 3 × + / +
25. از کدامیک از درخت های زیر می توان برای مرتب سازی مجموعه ای از عناصر استفاده کرد؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. مرتبه زمانی عبارت بازگشتی زیر را به روش جایگذاری با تکرار بدست آورید؟ T(n)=2T(n/2)+nc اگر n>2؛ T(n)=d اگر n=2
2. شبه کد الگوریتم جستجوی دودویی را بنویسید و در مورد مرتبه زمانی آن در بدترین حالت، بهترین حالت و حالت میانگین بحث کنید.
3. داده های زیر را با استفاده از heapsort به ترتیب صعودی مرتب نمایید. 40،70،20،30،20،5
4. دو عملگر push، pop پشته را با استفاده از لیست پیوندی پیاده سازی نمایید.
5. متنی شامل 5000 حرف از حروف جدول زیر به همراه فرکانس تکرار هر حرف موجود است. چنانچه کدی بهینه برای حروف جدول انتخاب نماییم تعداد کل بیت های لازم برای تبدیل متن مذکور به مجموعه ای از بیت ها چقدر است؟ a=1000 b=700 c=800 d=600 e=1000 f=900