نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۳۹۶-۹۷
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرایی تکه کد زیر چه مقداری است؟ for(k=1; k>=1; k/=2) f=f+n;
2. با توجه به زمان اجرای الگوریتم زیر مرتبه یا پیچیدگی زمانی آن چه مقداری می باشد؟ T(n)=4n+5nlog(n)+10
3. معادل پسوندی عبارت a+b×c−d/e کدامیک از گزینه های زیر است؟
4. اگر در آرایه A[495] بخواهیم 4 پشته بسازیم، آدرس ابتدای هر پشته کدام مجموعه زیر می باشد؟
5. عبارت محاسباتی S که بصورت پسوندی می باشد به شکل زیر در نظر گرفته شده، حاصل آن را با استفاده از پشته محاسبه نمایید؟ S: 5 6 2 + * 12 4 / -
6. کدام یک از مجموعه های زیر از توابع عضو کلاس پشته می باشند؟
7. اگر دنباله ی اعداد 1 و 3 و 4 و 5 و 7 را به ترتیب از چپ به راست وارد پشته نماییم کدامیک از خروجی های زیر از پشته امکان پذیر نیست؟
8. کدامیک از قطعه کدهای زیر پیاده سازی تابع حذف کردن یک عنصر از صف می باشد؟ (گزینه ۲): elementtype deletequeue(struct q *queue){ if(*queue.front == *queue.rear) queue.front == *queue.rear) queueempty() else return queue->items[++queue->front] }
9. قطعه کد زیر پیاده سازی کدامیک از عملیات گزینه ها می باشد؟ int queue::addq(int &x, int &overflow){ if(rear==Maxsize-1) overflow=1; else { overflow=0; item[++rear]=x; } }
10. برای یک ساختار صف حلقوی با n=7 شرط پر بودن صف کدامیک از گزینه های زیر است؟
11. کدامیک از موارد زیر در ارتباط با مقایسه آرایه با لیست پیوندی نادرست است؟
12. قطعه تابع زیر چه عملی انجام می دهد؟ p=getnode(); p->next=10; p->next=first; first=p;
13. قطعه کد زیر چه عملی را انجام می دهد؟ void pop(node *top){ node *ptr; ptr=top; top=top->next; freenode(ptr); }
14. مجموعه طول های تمام مسیرها از ریشه به تمام گره های درخت چه نام دارد؟
15. کدامیک از موارد زیر از مزیت های درخت دودویی کامل با آرایه نیست؟
16. در ساخت درخت دودویی به صورت یکتا با داشتن پیمایش میانوندی و یکی از پیمایش های پسوندی یا پیشوندی کدام گزینه درست است؟
17. تابع زیر چه عملیاتی انجام می دهد؟ void a(t *p){ if(p!=null){ b(p->son); cout<<p->info; b(p->next); } }
18. کدام درخت نشان داده شده در زیر یک max Heap است؟
19. درختی که مقدار کلید هر گره آن کمتر از مقادیر کلید فرزندانش نباشد چه نام دارد؟
20. زمان اجرای برنامه در لیست پیوندی نامرتب برای عملیات حذف کدامیک از گزینه های زیر می باشد؟
21. نمایش postordes درخت زیر کدام یک از گزینه ها می باشد؟
22. اگر بین هر دو راس از گراف مسیری وجود داشته باشد گراف چه نام دارد؟
23. فرض کنید A(V,E) یک گراف غیر جهت دار باشد کدامیک از گزینه های زیر درست می باشد؟
24. پیچیدگی الگوریتم مرتب سازی انتخابی کدامیک از گزینه های زیر می باشد؟
25. پیچیدگی الگوریتم Quick sort در بهترین حالت چقدر است؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. عبارت پیشوندی زیر را به عبارت پسوندی معادل تبدیل کنید؟
2. توابعی بنویسید که دو گره m ام و n ام یک لیست پیوندی را با هم عوض کند؟
3. اگر طول درخت دودویی چهار باشد (از چهار عنصر تشکیل شده باشد)، تعداد حالات مختلف آن چند تاست؟ ارتفاع درخت چقدر است؟
4. تابعی بنویسید که الگوریتم پریم را برای ساخت درخت پوشا پیاده سازی نماید.
5. برای اعداد زیر مرتب سازی درجی را دنبال کنید؟ 1- 13,57,85,70,22,64,48 2- 70,57,99,34,56,89