نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۸-۹۹
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. یک ماتریس 100×100 حاوی 99 داده عددی صحیح می باشد. اگر این ماتریس را به صورت اسپارس (خلوت) ذخیره کنیم، نسبت فضای اشغالی ماتریس اسپارس به ماتریس معمولی چه کسری خواهد شد؟ (فرض کنید هر سه نوع عددی row,col,value صحیح می باشند.)
2. اعداد 1 تا 5 به ترتیب وارد پشته می شوند. کدام یک از دنباله های زیر را نمی توان در خروجی نمایش داد؟
3. پشته به کمک آرایه s پیاده سازی شده است. کدام دستور برای حذف یک عنصر از پشته صحیح است؟
4. کدام گزینه تمام داده های موجود در پشته s را بازیابی کرده و در خروجی چاپ می کند؟
5. یک صف حاوی تعدادی عدد صحیح مفروض است. کدام گزینه مجموع اعداد درون صف را محاسبه می کند؟ (مقدار اولیه sum را صفر درنظر بگیرید)
6. تابع زمانی یک تابع بازگشتی مطابق زیر است. پیچیدگی زمانی این تابع از چه مرتبه ای است؟ T(n)=c اگر n=2؛ T(n)=T(n-2)+d اگر n>2
7. دو پشته غیر خالی s1 و s2 و صف خالی q و پشته خالی s مفروض است. پشته s1 را در q خالی کرده و مجددا q را خالی کرده و در s1 خالی می کنیم. پشته s2 را نیز در s خالی می کنیم و دوباره پشته s را در s2 خالی می کنیم. کدام گزینه صحیح است؟
8. در یک ساختار صف حلقوی با N=8 اگر front=4 و rear=4 باشد، صف در چه حالتی قرار دارد؟
9. شرط خالی بودن و شرط پر بودن صف حلقوی کدام است؟
10. صف های Q1 و Q2 با داده های زیر (از چپ به راست) و صف خالی Q3 مفروض است. پس از اجرای قطعه کد زیر، صف Q3 چگونه خواهد بود؟ Q1: 4,3,1,2,9,5 — Q2: 1,8,6,7 — while(!Empty(Q1)&&!Empty(Q2)){ a=Delete(Q1); b=Delete(Q2); Add(Q3,a+b); }
11. اگر first اشاره گر به اول یک لیست پیوندی یکطرفه باشد، دستورات زیر چه عملی انجام می دهند؟ for (p=first; p!=NULL; p=p->next) p->info++;
12. اگر بخواهیم عمل Process صف را در پشته شبیه سازی کنیم با ترکیب کدام اعمال پشته این کار امکان پذیر است؟
13. در یک لیست پیوندی یکطرفه، گره p، گره q ماقبل p می باشد. کدام گزینه روش صحیح حذف گره q است؟ (p و q غیرتهی هستند)
14. پیچیدگی زمانی اضافه کردن یک آیتم جدید به صف حلقوی (پیاده سازی با آرایه) و صف پیوندی (پیاده سازی با لیست پیوندی) از چه مرتبه هایی می باشند؟
15. تابع زیر چه کاری انجام می دهد؟ void f(node* p){ node* n=new node; n->next=p->next; n->prev=p; p->next->prev=n; p->next=n; }
16. تابع زیر چه کاری انجام می دهد؟ (first اشاره گر ابتدای لیست پیوندی است) double something(node* first){ node* p=first; double s=0,n=0; while(p){ n++; s+=p->info; p=p->next; } return s/n; }
17. تابع زیر چه کاری انجام می دهد؟ (first اشاره گر ابتدای لیست پیوندی است) void solve(node* first){ if(!first) return; cout<<first->info; solve(first->next); }
18. گره های یک درخت دودویی کامل از 1 تا n اندیس گذاری شده اند. پدر گره شماره 7 کدام است؟
19. اگر نمایش پرانتزی یک درخت عمومی به شکل A(B,C,D(S,T),E(P,Q,R),F) باشد، پس از تبدیل درخت عمومی به درخت دودویی کدام گره ها برگ خواهند بود؟
20. پیمایش پیش ترتیب درختی به صورت acbefd و پیمایش میان ترتیب آن به صورت bceafd می باشد. پیمایش پس ترتیب این درخت کدام است؟
21. در صورتی که بخواهیم یک پشته را با استفاده از لیست پیوندی پیاده سازی کنیم، تابع PUSH به چه شکلی باید نوشته شود؟
22. تابع زیر چه ویژگی از درخت دودویی T را محاسبه می کند؟ int compute(node* T){ if(!T) return 0; if(T->left_child==NULL && T->right_child==NULL) return 1; return compute(T->left_child)+compute(T->right_child); }
23. کدام ساختار برای حذف داده های تکراری موجود در یک لیست اولیه مناسب تر است؟
24. اعداد 1 تا 99 را بدون در نظر گرفتن ترتیب خاصی در یک درخت جستجوی دودویی درج می کنیم. سپس درخت ایجاد شده را به صورت میان ترتیب (InOrder) پیمایش می کنیم. کدام گزینه در مورد خروجی بدست آمده صحیح است؟
25. گراف غیر جهت دار G توسط ماتریس مجاورتی زیر تعریف شده است. وزن درخت پوشای کمینه (مینیمم) بدست آمده با استفاده از الگوریتم وارشال روی گراف G کدام است؟ (A-B=20, A-C=10, A-D=18, A-E=6, B-C=15, B-D=2, C-D=39, C-E=4)
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. تابع بازگشتی فاکتوریل را نوشته و با روش تکرار جای گذاری پیچیدگی زمانی آن را محاسبه کنید.
2. کلاسی برای ساختمان داده صف با استفاده از آرایه تعریف نموده و عملگرهای Add و Delete آن را پیاده سازی کنید.
3. تابعی بنویسید که اشاره گر به یک لیست پیوندی به همراه یک عدد را دریافت کرده و پس از جستجو در لیست پیوندی برای عدد داده شده، آدرس اولین گره حاوی داده مورد جستجو را برگرداند. در صورت عدم وجود داده در لیست، مقدار NULL برگشت داده شود.
4. تابعی بنویسید که اشاره گر ابتدای یک لیست پیوندی یکطرفه را دریافت کرده و میانگین داده های موجود در لیست را برمی گرداند.
5. برای عبارت ریاضی زیر یک درخت دودویی رسم نموده، سپس پیمایش پیش ترتیب و پس ترتیب درخت را نشان دهید. A×B+D/(C-K)