نمونه سوالات ساختمان دادهها — نیمسال اول ۱۳۹۶-۹۷
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. مرتبه اجرای قطعه برنامه زیر کدام است؟ s=0; for(x=1;x<=n;++x) for(y=1;y<=x;++y) for(z=1;z<=y;++z) s+=1;
2. پیچیدگی زمانی در بهترین حالت در الگوریتم جستجوی ترتیبی کدام است؟
3. کدامیک از روابط زیر نشان دهنده رابطه صحیح زمان محاسبات الگوریتم ها می باشد؟
4. فرض کنید آرایه B به صورت int B[15] تعریف شود و base(b) برابر با 5000 می باشد و با فرض اینکه هر عدد صحیح 2 بایت فضا از حافظه را اشغال می کند آدرس خانه B[9] را محاسبه کنید؟
5. زمان اجرا در بدترین حالت برای جستجوی ترتیبی و در بدترین حالت برای جستجوی دودویی از راست به چپ کدام است؟
6. تعداد عناصر آرایه یک بعدی بعدی کدام است؟
7. فرض کنید آرایه A 200 عنصری مرتب شده باشد. زمان اجرای بدترین حالت F(n) برای پیدا کردن عنصر معلوم x در آرایه A با استفاده از جستجوی دودویی چقدر است؟
8. کدام یک از ساختارهای داده زیر را LIFO می نامند؟
9. اگر دنباله اعداد 7 و 5 و 4 و 3 و 1 را به ترتیب از چپ به راست وارد پشته کنیم، کدام یک از خروجی های زیر از پشته امکان پذیر نیست؟
10. عبارت پسوندی (postfix) معادل عبارت ریاضی a/b-c+d*e-a*c/d را به دست آورید؟
11. پیچیدگی زمانی تابع اضافه کردن به صف و تابع حذف از صف کدام است؟
12. در ساختار داده صف، پربودن صف چگونه ارزیابی می شود؟
13. کدام یک در خصوص مقایسه آرایه با لیست پیوندی صحیح می باشد؟
14. قطعه کد زیر کدام یک از اعمال زیر را در ساختار داده صف انجام می دهد؟ { Node *ptr; ptr=front; front=front->next; freenode(ptr); }
15. کدام تعریف در خصوص درخت ها صحیح می باشد؟
16. درخت عمومی کدام است؟
17. بعد از حذف گره 20، درخت heap حاصل چگونه است؟
18. با مقادیر 1 و 2 و 3 چند درخت جستجوی دودویی می توان ساخت؟
19. کدام تعریف زیر در خصوص نظریه گراف صحیح می باشد؟
20. حداکثر تعداد یال های یک گراف جهت دار همبند کدام است؟
21. پیچیدگی الگوریتم Quick sort در بهترین حالت، حالت متوسط و بدترین حالت از راست به چپ کدام است؟
22. کدام یک در خصوص ویژگی های مرتب سازی هرمی صحیح می باشد؟
23. نمایش پیوند زیر، کدام یک از درخت ها را توصیف می کند؟ (مقدار گره، فرزند چپ، فرزند راست)
24. گراف زیر را در نظر بگیرید. پیمایش ردیفی یا BFS آن کدام گزینه می باشد؟
25. کدام مرتب سازی در بردار مرتب بهترین عملکرد و در بردار نامرتب بدترین عملکرد را دارد؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. اگر در آرایه S[495] بخواهیم 4 پشته درست کنیم، آدرس ابتدای هر پشته را به دست آورید؟
2. عناصر صف های Q1، Q2 از چپ به راست به صورت زیر باشند: Q1: 10,25,17,41,44,26,75 — Q2: 1,5,7,4,9,6. اگر x و y عناصر صف باشند پس از اجرای قطعه کد زیر، محتوای صف Q3 چه مقداری خواهد بود؟ i=0; while(!Empty(Q1) && Empty(Q2)){ i++; x=Delete(Q1); y=Delete(Q2); if(y=i) Add(Q3,x); }
3. تابعی بنویسید که لیست L را دریافت کرده، معکوس لیست پیوندی خطی را بدست آورد؟
4. پیمایش های inorder و preorder یک درخت دودویی به صورت زیر می باشد، درخت دودویی معادل را رسم نمایید؟ inorder: D B H E A I F J C G
5. گراف جهت دار G مانند شکل زیر است، ماتریس مجاورت آن را رسم نمایید؟