نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۳۹۳-۹۴
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرای الگوریتم زیر چیست؟ X=0; For(j=0; j<n-1; j++) For(k=n-1; k>=j+1; k--) X++;
2. پیچیدگی عمل درج و عمل حذف را از لیست پیوندی به ترتیب برابر کدام گزینه است؟
3. کدام روش برای ذخیره ماتریس های پایین مثلثی مناسب تر است؟
4. فرض کنید آرایه A با row سطر و col ستون به صورت float A[row][col] در زبان ++c تعریف شده باشد. اگر آدرس پایه این آرایه برابر 200 باشد و هر float چهار بایت اشغال کند، آنگاه آدرس A[i][j] به روش ستونی توسط کدام یک از روابط زیر به دست می آید؟
5. عبارت infix معادل عبارت زیر کدام است؟ /-/a*bcdg
6. اعداد 1 تا 6 به ترتیب وارد پشته می شوند. کدام یک از گزینه ها را نمی توان در خروجی نمایش داد؟
7. کدام گزینه در ساختار صف حلقوی با n=5 بیان کننده خالی یا پر بودن صف است؟
8. برای پیاده سازی کلاس پشته در ++c تابعی به نام ()stack همنام با نام کلاس پشته تعریف می شود که به آن سازنده (constructor) گویند. کدام یک از عمل های زیر در سازنده ()stack انجام می شود؟
9. صف خالی q و پشته خالی s را در نظر بگیرید. قطعه برنامه زیر چه داده ای را در خروجی چاپ می کند؟ Cin>>n; While(n){ q.Add(n%10); n/=10; } While(!q.isEmpty()){ m=q.Delete(); if(m!=0) s.push(m); } while(!s.isEmpty()) cout<<s.pop();
10. تابع زیر چه عملی را انجام می دهد؟ List x(node* L){ if(L!=null){ x(L->next); cout<<L->info; } }
11. برای اضافه کردن یک گره به یک لیست پیوندی دوطرفه چند جای گزینی لازم است؟
12. حاصل قطعه کد مقابل کدام گزینه می تواند باشد؟ P=first; Sum=0; While(p!=null){ If(p->info%2==0) Sum=sum+p->info; P=p->next; }
13. قطعه کد زیر چه کاری انجام می دهد؟ P=getnode(); p->info=x; p->next=start; start=p;
14. اگر در یک درخت با حداکثر درجه 2 تعداد کل گره ها 17 باشد و تعداد گره ها با درجه 2 دوبرابر تعداد گره ها با درجه 1 باشد، تعداد گره ها با درجه 1 برابر است با:
15. حداقل تعداد عناصر یک درخت دودویی کامل کدام است؟
16. دوشرط HEAP بودن یک درخت دودویی کدام است؟
17. کاربرد درخت جستجوی دودویی چیست؟
18. کدام گزینه الگوریتم های مرتب سازی ای را نشان می دهد که از لحاظ درجا بودن هم مانند هم هستند؟
19. در مرتب سازی سریع، دومین دو عددی که جای آنها با یکدیگر عوض می شود کدام است؟ 68, 81, 61, 93, 55, 100, 78, 98, 84, 65, 70, 75
20. در گراف مقابل نتیجه جستجوی عمقی برابر است با.........
21. اگر یک لیست مرتب شده (با n خانه) را با استفاده از الگوریتم Binary search برای یک مقدار خاص جستجو کنیم تعداد دفعات مقایسه چه خواهد بود؟
22. تابع بازگشتی زیر را در نظر بگیرید: مقدار برگشتی rec(3) برابر است با: int f(int n){ if(n==1) return 2; else return(f(n-1)*f(n-1)); }
23. آرایه زیر را در نظر بگیرید. بعد از یک مرحله اجرای مرتب سازی سریع، آرایه چه شکلی پیدا می کند؟ 25 57 48 37 12 92 86 33
24. عمق درخت دودویی معادل عبارت محاسباتی (-a)*b*c-d/e*g+h برابر است با:
25. کدام گزینه نادرست است؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. با استفاده از الگوریتم هافمن، درخت رمزگذاری زیر را محاسبه کنید. طول کلمات bee و disable را به دست بیاورید. (کاراکتر: L s i a e d b — تعداد تکرار: 12 4 2 8 9 4 5)
2. تابعی بنویسید که برگ های درخت دودویی را محاسبه کند.
3. ساختمان داده پشته و تمام عملگرهای آن را پیاده سازی کنید.
4. الگوریتم بازگشتی، برای سری فیبوناچی را نوشته و مرتبه اجرایی آن را محاسبه نمایید.
5. الگوریتم مرتب سازی درجی را نوشته و پیچیدگی زمانی آن را محاسبه نمایید. آیا این الگوریتم پایدار است؟