نمونه سوالات ساختمان دادهها — نیمسال اول ۱۴۰۱-۱۴۰۲
کد درس 1115112
پاسخها از پاسخنامه رسمی مرکز آزمون و سنجش دانشگاه پیامنور استخراج و تطبیق داده شدهاند.
پیشرفت شما بهصورت خودکار روی همین مرورگر ذخیره میشود و با رفرش کردن صفحه از بین نمیرود.
1. یک درخت دودویی پر با ارتفاع 8 موجود است. اگر ارتفاع این درخت را یک واحد کاهش دهیم به طوریکه همچنان پر بماند، حداکثر چند گره باید از درخت حذف گردد؟ (ارتفاع ریشه یک است)
2. یک آرایه مرتب با 500 عنصر وجود دارد در بدترین حالت برای پیدا کردن عنصر x با استفاده از الگوریتم جستجوی دودویی چند مقایسه انجام میشود؟
3. در مورد یک درخت کامل با ارتفاع چهار چند گزینه درست است؟ ارتفاع ریشه یک است. حداکثر چهار برگ دارد. حداکثر 15 گره دارد. تعداد گرههای تک فرزندی آن دو است. ارتفاع زیر شاخه راست ریشه از ارتفاع زیر شاخه چپ ریشه کمتر یا مساوی است.
4. یک درخت دودویی با هشت گره موجود است ارتفاع این درخت هشت میباشد کدام گزینه در مورد این درخت درست است؟ (ارتفاع ریشه یک است)
5. در یک صف دایرهای fron=30 و rear=12 میباشد تعداد خانه های پر در این صف کدام گزینه است؟
6. تعداد تکرار کاراکترهای زیر موجود است با استفاده از الگوریتم هافمن طول کلمه city را (بر حسب بیت) کدام گزینه است؟ t=2 i=3 c=4 y=6 d=2
7. داده های زیر از چپ به راست در یک درخت جستجوی باینری قرار میگیرد. کدام گزینه درست است؟ input=19,9,12,8,25,22,36,11
8. یک ماتریس بالا مثلثی با اندازه n×n موجود است. در این آرایه تمام عناصر زیر قطر صفر هستند و مابقی عناصر عدد میباشند. تعداد عناصر صفر این آرایه کدام گزینه است؟
9. چند گزینه از موارد زیر درست است؟ الف- اگر دوپیمایش پسوندی و پیشوندی از یک درخت باینری موجود باشد، آن درخت را میتوان به صورت یکتا رسم کرد. ب- اگر پیمایش پیشوندی و میانوندی درخت باینری موجود باشد، درخت آن را میتوان یکتا ساخت. ج- با داشتن دو پیمایش میان وندی و پسوندی، درخت آن را میتوان به شکل یکتا رسم کرد. د- داشتن پیمایش میان وندی فقط مکان ریشه و اولین برگ سمت چپ را میتوان مشخص کرد.
10. حاصل پیمایش میانوندی یک درخت به شکل زیر است کدام گزینه درست است؟ (از چپ بخوانید) inorder= 8,11,12,20,15,16,30,31,45,48
11. مرتبه زمانی شبه کد زیر کدام است؟ For(j=1; j<=n; j++) For(k=1; k<=n; k=k+j) C=c+1;
12. درج یک عنصر جدید در heap از چه مرتبه زمانی است؟
13. داده های زیر از چپ به راست در یک Max Heap قرار میگیرند. کدام گزینه درست است. از چپ به راست بخوانید. 12,17,4,15,13,3,20,14
14. کدام روش مرتبسازی غیردرجا است؟
15. یک لیست پیوندی با شش گره و با مقادیر 9,-4,11,2,-1,7 وجود دارد پس از اجرای قطعه کد زیر مجموع مقادیر لیست کدام گزینه خواهد شد؟ P=first; While(p!=Null){ If(p->info>0) p->info=0; else p->info=1; p=p->next;}
16. در کدام الگوریتم ابتدا یالهای گراف مرتب میشوند سپس ساخت درخت پوشای بهینه آغاز میگردد؟
17. در الگوریتم quick sort در چه حالتی بیشترین زمان اجرا رخ می دهد؟
18. پیچیدگی الگوریتم Heap sort در حالت میانگین کدام گزینه است؟
19. روی داده های زیر الگوریتم مرتب سازی حبابی اجرا میگردد در انتهای گذر اول کدام عنصر دوم در محل درست خود قرار میگیرد؟ 14,5,13,1,12
20. آرایه دوبعدی با اندازه 10×10، وجود دارد این آرایه رابه صورت سطری در حافظه قرار میدهیم آدرس پایه ادرس برابر با صفر و اندازه هر عنصر آرایه 4B میباشد. آدرس عنصر a[6][4] کدام گزینه میباشد؟
21. یک صف خطی یک طرفه با n عنصر موجود است میخواهیم مشکل یکبارقابل استفاده بودن صف را با شیفت دادن عناصر از انتها به ابتدای صف حل کنیم این روش در بدترین حالت چه هزینه زمانی نیاز دارد؟
22. چند گزینه از موارد زیر درست است؟ الف- حداکثرارتفاع درخت جستجوی باینری logn است. ب- حداقل ارتفاع درخت heap برابر با logn و حداکثر ارتفاع ان برابر با n خواهد بود. ج- مرتب سازی quick sort در بدترین حالت از مرتبه nlogn میباشد. د- در بهترین حالت هیچ الگوریتمی نمیتواند در زمانی کمتر از nlogn مرتب سازی را انجام دهد.
23. داده های زیر موجود است از چپ به راست بخوانید میانگین تعداد مقایسه در الگوریتم جستجوی دودویی کدام است؟ 10,15,20,30,40,50,55,60,70
24. داده های زیر از چپ به راست در یک درخت جستجوی باینری قرار میگیرد کدام گزینه درست است؟ 17,20,30,18,4,3,1
25. مرتبه زمانی قطعه کد زیر کدام است؟ K=n; While(j>=1){ For(i=1; i<=n; i++) Cout<<"Name"; K=[k/2]; }
سوالات تشریحی
این سوالات نیاز به پاسخ تشریحی (نوشتاری) دارند؛ گزینهای برای انتخاب ندارند. برای پاسخ کامل به جزوه یا کتاب درسی مراجعه کنید.
1. یک آرایه دوبعدی (ماتریس) با اندازه n×n وجود دارد در این آرایه سطر اول و سطر آخر عدد و مابقی صفر میباشند. میخواهیم این آرایه را با حذف صفرها در آرایه اسپارس ذخیره کنیم محاسبه کنید حداقل مقدار n چند باشد تا ذخیره آن به صورت اسپارس مقرون به صرفه باشد؟ اندازه هر عنصر آرایه را 4 بایت در نظر بگیرید.
2. با استفاده از الگوریتم هافمن تعداد کدهای بیتی لازم برای کلمه water را محاسبه کنید. (مراحل حل مساله ترسیم و توضیح داده شود) t=7 e=1 r=6 a=3 v=8 w=2 n=5
3. داده های زیر را در یک max-heap قرار دهید از چپ به راست بخوانید. الف- درخت را رسم کرده مراحل رسم درخت مورد نیاز است. ب- گره 16 را از درخت حذف کنید. 15,6,9,13,2,4,17,16
4. الگوریتم مرتب سازی انتخابی را شرح داده، شبه کد آن را بنویسید و زمان مرتب سازی آن را در بدترین و بهترین حالت ذکر کنید.
5. لیست دایرهای را شرح داده موارد زیر را انجام دهید: الف- شبه کد های خالی بودن و پربودن صف و حذف و اضافه به صف را بنویسید. ب- با مثال حذف و اضافه از صف را نشان دهید.