نمونه سوالات ساختمان دادهها — تابستان ۱۳۹۶
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه زمانی قطعه برنامه مقابل کدام است؟ for(i=1; i<=n-1; i++) for(j=1; j<=n+2; j++)
2. تابع زمانی یک تابع بازگشتی به شکل زیر است، مرتبه زمانی این تابع کدام است؟ T(n)=c اگر n=1؛ T(n)=T(n/2)-d اگر n>1
3. ماتریس a طبق دستور itemType a[12][4] تعریف شده است. با فرض اینکه طول داده itemType ۱۰ (ده) بایت باشد، و آدرس شروع آرایه ۳۰۰۰ باشد، آدرس داده a[5][2] کدام است؟ (نحوه ذخیره سازی ماتریس سطری است)
4. یک ماتریس ۱۰۰×۱۰۰ حاوی ۹۹ داده عددی صحیح می باشد. اگر این ماتریس را به صورت اسپارس (خلوت) ذخیره کنیم، نسبت فضای اشغالی ماتریس اسپارس به ماتریس معمولی چه کسری خواهد شد؟ (فرض کنید row, col, value هر سه از نوع عددی صحیح می باشند.)
5. کدام گزینه تمام داده های موجود در پشته s را بازیابی کرده و در خروجی چاپ می کند؟
6. اگر دنباله اعداد ۱ تا ۶ را از کوچک به بزرگ وارد پشته کنیم، کدام یک از خروجی های زیر از پشته، غیر قابل تولید است؟
7. معادل پسوندی عبارت a-b*c+d کدام است؟
8. دو پشته غیر خالی s1 و s2 و صف خالی q و پشته خالی s مفروض است. پشته s1 را در q خالی می کنیم و q را در s1 خالی می کنیم. پشته s2 را نیز در s خالی می کنیم و دوباره پشته s را در s2 خالی می کنیم. کدام گزینه صحیح است؟
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. اگر بخواهیم عمل Process صف را در پشته شبیه سازی کنیم با ترکیب کدام اعمال پشته این کار امکان پذیر است؟
12. تابع زیر چه عملی روی لیست دو پیوندی انجام می دهد؟ void f(node* p){ node* n=new node; n->next=p->next; n->prev=p; p->next->prev=n; p->next=n; }
13. تابع زیر چه کاری انجام می دهد؟ (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; }
14. تابع زیر چه کاری انجام می دهد؟ (first اشاره گر ابتدای لیست پیوندی است) void solve(node* first){ if(!first) return; cout<<first->info; solve(first->next); }
15. اگر نمایش پرانتزی یک درخت عمومی به شکل A(B,C,D(S,T),E(P,Q,R),F) باشد، پس از تبدیل درخت عمومی به درخت دودویی، کدام گره ها برگ خواهند بود؟
16. پیمایش پیش ترتیب درختی به صورت acbefd و پیمایش میان ترتیب آن به صورت bceafd می باشد. پیمایش پس ترتیب این درخت کدام است؟
17. در صورتی که بخواهیم یک پشته را با استفاده از لیست پیوندی پیاده سازی کنیم، تابع PUSH باید به چه شکلی نوشته شود؟
18. تابع زیر چه ویژگی از درخت دودویی 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); }
19. کدام ساختار برای حذف داده های تکراری موجود در یک لیست اولیه مناسب تر است؟
20. اعداد 1 تا 99 را بدون در نظر گرفتن ترتیب خاصی در یک درخت جستجوی دودویی درج می کنیم. سپس درخت ایجاد شده را به صورت میان ترتیب (InOrder) پیمایش می کنیم. کدام گزینه در مورد خروجی بدست آمده صحیح است؟
21. نتیجه جستجوی عمقی (DFS) روی گراف زیر با شروع از رأس 1 چیست؟
22. گراف غیر جهت دار 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)
23. اگر A ماتریس مجاورتی گراف G و B=A*A*A باشد، B[2][4] چه اطلاعاتی به ما می دهد؟
24. کدام یک از الگوریتم های مرتب سازی زیر غیر درجا است؟
25. در مرتب سازی سریع اگر اولین عنصر را به عنوان محور (Pivot) در نظر بگیریم، کدام گزینه بدترین شرایط را برای مرتب سازی نشان می دهد؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. یک تابع بازگشتی برای محاسبه فاکتوریل بنویسید و پیچیدگی زمانی آن را به روش تکرار با جایگذاری به دست بیاورید.
2. یک کلاس برای پشته طراحی کنید و تمامی توابع آن را پیاده سازی کنید.
3. تابعی بنویسید که اشاره گر یک لیست پیوندی به همراه یک عدد را دریافت کرده و پس از جستجو در لیست، آدرس اولین گره حاوی داده مورد جستجو را برگرداند. در صورت عدم وجود داده در لیست، مقدار NULL برگشت داده شود.
4. داده های زیر را به ترتیب از چپ به راست وارد یک Max Heap کنید و مراحل کار را با رسم شکل توضیح دهید. 40, 30, 50, 25, 60, 55, 75
5. داده های زیر را به روش مرتب سازی سریع مرتب کنید و مراحل مرتب سازی را نشان دهید. 40, 10, 50, 90, 11, 36, 22