نمونه سوالات ساختمان دادهها — تابستان ۱۳۹۸
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. تابع زیر از چه مرتبه ای میباشد؟ a=n; While(a>1){ a/=2; b=n; while(b>1){ b/=3; x++; } }
2. زمان اجرای الگوریتم F(N) به صورت زیر برابر کدام گزینه است؟ F(N)=1 اگر n=1؛ F(N)=n+T(n-1) اگر n≥2
3. بهترین الگوریتم بازگشتی برای محاسبه x به توان y دارای چه مرتبه زمانی است؟
4. پیچیدگی زمانی قطعه برنامه زیر چیست؟ FOR i=1 to n do FOR j=1 to i do FOR k=1 to n do x:=x+1;
5. آرایه A به صورت زیر تعریف شده است: A=array[3...50] of integer; اگر آرایه در آدرس 1000 حافظه قرار داشته باشد آدرس A[14] به روش سطری کدام است؟
6. در صورتیکه آرایه مورد جستجو در جستجوی دودویی به صورت 7 6 5 4 3 2 1 0 -1 باشد متوسط تعداد مقایسه ها برای جستجوی موفق چیست؟
7. کدام راه برای نمایش ذخیره ماتریس های بالا مثلثی مناسب تر است؟
8. تعداد عناصر غیر صفر یک آرایه اسپارس سه قطری n×n چقدر است؟
9. پشته (STACK) ساختمان داده ای است از نوع:
10. اگر رشته اعداد 1-2-3-4-5 را به ترتیب به یک پشته STACK وارد کنیم کدام یک از خروجی های زیر از این پشته امکان پذیر نخواهد بود؟ (خروجی پشته را از سمت چپ به راست بخوانید.)
11. مناسب ترین ساختار داده جهت آدرس ثبت محل بازگشت در موقع فراخوانی زیر برنامه ها کدام است؟
12. عبارت پیشوندی (prefix) مقابل داده شده است: ++a/b-cd/-ab-+c*d5/a-bc معادل پسوندی آن کدام است؟
13. اگر a=2 b=4 c=8 d=10 باشد ارزش عبارت پسوندی ab*c+da-/ چیست؟
14. یک لیست خطی یک طرفه با دو اشاره گر F و R که به ترتیب به عنصر اول و آخر لیست اشاره می کند پیاده سازی شده است. هزینه کدام یک از عملیات زیر وابسته به تعداد عناصر لیست است؟
15. در اضافه کردن یک گره به لیست پیوندی دو طرفه چند اشاره گر باید تغییر یابد؟
16. در یک درخت جستجوی باینری کدام عمل در O(1) انجام می شود؟
17. در یک درخت دودویی کامل با 5 سطح حداکثر چند گره وجود دارد؟ (سطح ریشه برابر یک فرض شود)
18. پیمایش preorder درخت زیر کدام است؟ (ریشه A، فرزندان B و C؛ زیر B: D و E؛ زیر E: H و I؛ زیر C: F و G؛ زیر F: J و K)
19. کد هافمن عبارت AABAABAACAABAACACABA چند بیت دارد؟
20. بیشترین تعداد لبه در یک گراف غیر جهت دار با N راس عبارتند از:
21. الگوریتم InsertionSort زیر چه نوع مرتب سازی است؟ void InsertionSort(int[] A){ int N=A.length; for(i=1;i<N;i++){ key=A[i]; for(j=i-1;j>=0 && A[j]>key;j--) A[j+1]=A[j]; A[j+1]=key; } }
22. الگوریتم QUICK SORT یک رشته N تایی را در حالت متوسط به چه سرعتی مرتب میکند؟
23. در برنامه زیر خروجی F(3,6) چه می شود (تابع فیبوناچی)؟ int F(int m,int n){ if(m==1 || n==0 || m==n) return 1; else return F(m-1,n)-F(m-1,n-1); }
24. به درختی Heap گفته می شود که:
25. کدامیک از روشهای مرتب سازی زیر در بدترین حالت از o(n*n) است؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. آرایه A:ARRAY[5..20] OF REAL تعریف شده است. اگر این آرایه از آدرس 100 حافظه به بعد قرار گرفته باشد آدرس خانه A[16] کدام است؟ تعداد عناصر آرایه را نیز بدست آورید.
2. عبارت postfix معادل عبارت (A+B)*D+E/(F+A*D) را بدست آورید.
3. تابع اضافه کردن و حذف کردن یک عنصر به صف را پیاده سازی کنید.
4. تابعی بنویسید که اشاره گر لیست پیوندی را بگیرد و تعداد گره های لیست را برگرداند.
5. درخت شکل زیر را در نظر بگیرید و این درخت را به صورت درخت دودویی نشان دهید.