نمونه سوالات ساختمان دادهها — نیمسال دوم ۱۴۰۰-۱۴۰۱
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. کدام یک از توابع زمانی زیر از پیچیدگی زمانی بالاتری برخوردار است؟
2. مرتبه اجرایی قطعه برنامه زیر چیست؟ for (int i=n; i>=1; i/=2) X++;
3. آرایه a به صورت int a[10] تعریف شده است. اگر آدرس اولین خانه آرایه در حافظه 5200 باشد، با فرض اینکه هر داده int دو بایت اشغال کند، آدرس a[4] کدام است؟
4. اعداد 1 تا 5 به ترتیب وارد پشته میشوند. کدام یک از دنبالههای زیر را نمیتوان در خروجی نمایش داد؟
5. پشته به کمک آرایه s پیاده سازی شده است. کدام دستور برای حذف یک عنصر از پشته صحیح است؟
6. یک صف حاوی تعدادی عدد صحیح مفروض است. کدام گزینه مجموع اعداد درون صف را محاسبه میکند؟ (مقدار اولیه sum را صفر درنظر بگیرید)
7. تابع زمانی یک تابع بازگشتی مطابق زیر است. پیچیدگی زمانی این تابع از چه مرتبهای است؟ T(n)=c اگر n=2؛ T(n)=T(n-2)+d اگر n>2
8. معادل پسوندی عبارت a+b*c-d/e کدام است؟
9. در یک ساختار صف حلقوی با N=8 اگر front=4 و rear=4 باشد، صف در چه حالتی قرار دارد؟
10. اگر first اشاره گر به اول یک لیست پیوندی یکطرفه باشد، دستورات زیر چه عملی انجام میدهند؟ for (p=first; p!=NULL; p=p->next) p->info++;
11. در یک لیست پیوندی یکطرفه، گره p، گره q ماقبل p میباشد. کدام گزینه روش صحیح حذف گره q است؟ (p و q غیرتهی هستند)
12. پیچیدگی زمانی اضافه کردن یک آیتم جدید به صف حلقوی (پیاده سازی با آرایه) و صف پیوندی (پیاده سازی با لیست پیوندی) از چه مرتبه هایی می باشند؟
13. کدام گزینه لیست پیوندی L را معکوس می کند؟ (مقدار اولیه m برابر NULL است)
14. گره های یک درخت دودویی کامل از 1 تا n اندیس گذاری شده اند. پدر گره شماره 7 کدام است؟
15. تابع زیر چه پیمایشی روی درخت دودویی T انجام می دهد؟ void traverse(node* T){ if (T==NULL) return; cout << T->info; traverse(T->left_child); traverse(T->right_child); }
16. پیمایش پیش ترتیب (PreOrder) یک درخت دودویی ABDCE و پیمایش میان ترتیب (InOrder) آن BDAEC می باشد. پیمایش پس ترتیب (PostOrder) درخت، کدام گزینه است؟
17. می خواهیم با استفاده از یک heap تعداد n داده را به طور صعودی مرتب کنیم. کدام روش صحیح است؟
18. پیمایش inorder یک درخت جستجوی دودویی (BST) چه ویژگی دارد؟
19. تابع زیر کدام ویژگی درخت دودویی T را محاسبه می کند؟ int f(node* T){ if (T==NULL) return 0; if (T->Left==Null) && (T->Right==Null) return 1; return f(T->Left)+f(T->Right); }
20. یک درخت دودویی با 20 گره مفروض است. اگر تعداد گره های درجه 2 برابر 7 باشد تعداد برگها کدام است؟
21. حاصل پیمایش عرضی (BFS) گراف زیر با شروع از رأس A کدام است؟ (گره ها به ترتیب حروف الفبا ملاقات می شوند)
22. هزینه احداث جاده برای شهرهای یک استان، مطابق جدول زیر است. کمترین هزینه برای اینکه از هر شهری به هر سایر شهرها مسیری وجود داشته باشد کدام است؟ (از درخت پوشای کمینه استفاده کنید)
23. استفاده از کدام ساختار برای حذف عناصر تکراری از یک لیست مناسب است؟
24. کدام یک از روش های مرتب سازی زیر در تمام شرایط (بهترین، بدترین و متوسط) از پیچیدگی زمانی O(nlogn) برخوردار است؟
25. در یک روش مرتب سازی برای n داده، در مرحله i ام، کوچکترین عنصر لیست را در بازه [i..n-1] پیدا کرده و جای آن را با اندیس i تعویض می کنیم (i از صفر تا n-2 می باشد). این روش چه نام دارد؟
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. تابع بازگشتی فاکتوریل را نوشته و با روش تکرار جای گذاری پیچیدگی زمانی آن را محاسبه کنید.
2. الگوریتم تبدیل عبارت میانوندی به پسوندی را به کمک پشته بنویسید.
3. کلاسی برای ساختمان داده صف با استفاده از آرایه تعریف نموده و عملگرهای Add و Delete آن را پیاده سازی کنید.
4. تابعی بنویسید که اشاره گر first ابتدای یک لیست پیوندی یکطرفه را دریافت کرده و میانگین داده های موجود در لیست را برگرداند.
5. برای عبارت ریاضی زیر یک درخت دودویی رسم نموده، سپس پیمایش پیش ترتیب و پس ترتیب درخت را نشان دهید. A×B+D/(C-K)