نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۴۰۲-۱۴۰۳
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. کدام یک از موارد زیر در خصوص پیچیدگی زمانی کد زیر صحیح است؟ S=0; for(i=0;i<n;i++) for(j=0;j<i;j++) S++;
2. پیچیدگی زمانی جستجوی دودویی در یک آرایه با طول n چیست؟
3. گزارههای زیر را در نظر بگیرید: ۱- اگر T(n)∈Ω(G(n)) آنگاه G(n)∈O(T(n)). ۲- اگر T(n)∈θ(G(n)) آنگاه G(n)∈θ(T(n)). ۳- اگر T(n)∈O(G(n)) آنگاه G(n)∈Ω(T(n)). کدام گزارهها صحیح هستند؟
4. توابع زیر را در نظر بگیرید: G(n)=n^2, F(n)=2^n, K(n)=n!, Z(n)=n^n, Q(n)=nlogn. با توجه به این توابع کدام یک از موارد زیر صحیح است؟
5. کدامیک از موارد زیر برقرار است؟ ۱) 4n^2-7n+2 ∈ θ(n^2) ۲) n^3+n^2logn ∈ θ(n^3) ۳) n!+4n^5 ∈ θ(n^n) ۴) 4n^2·2^n+5n^2logn ∈ θ(n^2·2^n)
6. گرافی بدون جهت با ۱۰ گره حداکثر چند یال میتواند داشته باشد (بدون در نظر گرفتن یال از یک گره یال به گره خودش)؟
7. تابع زیر چه کاری انجام میدهد؟ node *f(node* list){ node *m,*t; m=NULL; while(list){ t=m; m=list; list=list->next; m->next=t; } return m; }
8. یک ماتریس اسپارس به نام A به صورت زیر نمایش داده شده است. کوچکترین عدد ستون با اندیس ۳ و میانگین اعداد ماتریس A چیست؟ (اندیسهای آرایه از صفر شروع میشوند)
9. اگر آرایه دوبعدی به نام A از نوع int با ابعاد ۳۰ سطر و ۴۰ ستون به صورت سطری ذخیره شود و آدرس آن در حافظه ۱۰۰۰ باشد، آدرس خانه A[10][20] چیست؟ (اندیس آرایه از صفر شروع میگردد و هر متغیر int دوبایت حافظه مصرف میکند.)
10. معادل پیشوندی عبارت پسوندی زیر را بنویسید. Ab+cd-*
11. پیچیدگی زمانی درج و حذف در پشته چیست؟
12. اگر اعداد ۶۵۴۳۲۱ به ترتیب از راست به چپ در پشته وارد شوند، کدام یک از خروجیهای زیر (از راست به چپ) امکانپذیر نیست؟
13. برای پیاده سازی عملیات Undo در نرم افزاری مانند Word، کدام ساختار مناسبتر است؟ (Undo گزینهای است که باهر بار انتخاب آن، آخرین عملیاتی که کاربر انجام داده است لغو میگردد.)
14. کدام یک از موارد زیر مربوط به پشته است؟
15. کدام گزینه صحیح است؟
16. کد زیر چه کاری انجام میدهد؟ void f(node* list){ if(list!=NULL){ f(list->next); cout<<list->info; } }
17. در یک صف حلقوی که با آرایه پیاده سازی شده است اگر f=6 و r=2 باشد و ظرفیت آرایه ۲۰ باشد، تعداد عناصر داخل صف حلقوی چیست؟ (f نشان گر سر صف و r نشانگر ته صف است)
18. پیمایش گراف زیر به روش BFS با شروع از گره a چیست؟
19. پیمایش preorder درختی که پیمایش postorder و inorder آن به صورت زیر است چیست؟ inorder: bfdaegc — postorder: fdbgeca
20. حداقل و حداکثر تعداد گره ها در یک درخت دودویی کامل با ۴ سطح چیست؟
21. اگر تعداد گرههای درجه صفر درخت دودویی ۲۰ باشد، تعداد گرههای درجه دو این درخت چند است؟
22. پیچیدگی زمانی حذف از درخت maxheap چیست؟
23. یک درخت maxheap به صورت زیر در آرایهای پیاده سازی شده است. بعد از درج عدد ۱۵ چه عددی در خانه آرایه با اندیس ۵ قرار میگیرد؟ (اندیس ۱ تا ۱۰: 16,14,10,8,7,9,3,2,4,1)
24. درخت زیر چه نوع درختی است؟ (ریشه ۶۰، فرزندان ۴۱ و ۷۴؛ زیر ۴۱: ۱۶ و ۵۳؛ زیر ۵۳: ۴۶ و ۵۵؛ زیر ۱۶: ۲۵؛ زیر ۲۵: ۴۲؛ زیر ۷۴: ۶۵؛ زیر ۶۵: ۶۳ و ۷۰؛ زیر ۶۳: ۶۲ و ۶۴)
25. پیچیدگی زمانی مرتب سازی انتخابی چیست؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. یک تابع بازگشتی برای محاسبه سری فیبوناچی ارائه دهید.
2. قطعه کدی بنویسید که نودی که p به آن اشاره میکند را از یک لیست دوپیوندی حذف کند.
3. فرض کنید دو لیست یک پیوندی موجود است و firsta، firstb به ابتدای این دو لیست اشاره میکنند. قطعه کدی بنویسید که این دو لیست را ترکیب کند به طوریکه لیست دوم در انتهای لیست اول قرار گیرد.
4. درخت پوشای کمینه گراف زیر را رسم کنید. (گراف شامل گرههای A,B,C,D,E,F با یالهای وزندار: A-B=1، A-D=4، A-E=3، B-E=2، B-C=4، C-F=5، D-E=4، E-F=7)
5. تابعی بنویسید که یک آرایه را به روش انتخابی به صورت صعودی مرتب کند.