نمونه سوالات ساختمان داده – 36 سوال

در این نوشته نمونه سوالات ساختمان داده را به تفکیک هر فصل طراحی شده است.

نمونه سوالات ساختمان داده

مرتبه زمانی و تحلیل الگوریتم

1- کدام یک از گزاره های زیر درست هستند؟

2- در انتهای ویدیوی آموزش پیچیدگی زمانی، ترتیب رشد چند تابع مهم بیان شد. در لیست زیر چند تابع جدید مشاهده می‌کنید. این توابع را به ترتیب رشد مرتب کنید:

3- مرتبه زمانی شبه کدهای زیر را محاسبه کنید:

for(i=1;i<=n;i++)
	for(j=1;j<=n;j++){
		x++;
		n--;
	}

برای تحلیل الگوریتم بالا به دستور خط 5 توجه کنید.

4- مرتبه زمانی شبه کد زیر را محاسبه کنید:

for(i=1;i<=n;i++){
	
	for(j=1;j<=n;j++)
		x++;
	
	j=1;
	
	while(j<n){
		x++;
		j=j*2
	}
	
}
	

5- مرتبه زمانی شبه کد زیر را محاسبه کنید:

for(i=1;i<=n;i++)
	for(j=1;j<=3*i;j++)
		for(k=1;k<=3*n;k++)
			cout<<"*";

راهنمایی: برای تحلیل الگوریتم بالا از ایده مثال سوم (روش دوم) و مثال چهارم که در ویدیو ی آموزش تحلیل الگوریتم توضیح داده شده است استفاده کنید.

6- مرتبه زمانی شبه کد زیر را محاسبه کنید:

for(i=1;i<=n;i=i*2)
	for(j=1 ; j<=n; j++)
		cout<< "*";

7- مرتبه زمانی شبه کد زیر را محاسبه کنید:

for(i=1;i<=n;i=i*2)
	for(j=1;j<=n;j=j*2)
		for(k=1;k<=j;k++)
			cout<<"*";

8- مرتبه زمانی شبه کد زیر را محاسبه کنید:

i=2;
while(i<=n){
	cout<<i;
	i = i*i;
}

شما می‌توانید حل سوالات این نوشته را در کانال یوتیوب سایت مشاهده کنید

پشته و صف

9- اگر اعداد زیر را به ترتیب وارد پشته کنیم کدام یک از خروجی های زیر را نمی‌توان با هیچ ترتیبی به دست آورد (اعداد را از چپ به راست بخوانید)
1,2,3,4,5,6
الف) 123564      ب) 324651       ج) 432165        د) 215364

10-عبارت پسوندی معادل عبارت (A+B) * D + E / (F + A * D)
الف) AB+D*E+F/A+D* ب) AB+D*EFAD*+/+
ج) ABDEFAD+*+/+* د) AB+DE+FAD*+/

11- حداقل اندازه پشته برای تبدیل عبارت میانوندی a/(b-c*(d+e)) به معادل پسوندی کدام است؟
(اگر الگوریتم تبدیل میانوندی به  پسوندی را با ورودی بالا اجرا کنیم حداکثر چند خانه از پشته اشغال می‌شود؟)

الف) 4 ب)5 ج) 6 د)3

12- برنامه ای بنویسید که با استفاده از پشته ها جفت بودن علامتهای { } و ( ) و  [ ]در یک رشته شامل حروف و علامت بررسی کند.
مثال: رشته  {AB(C)[EFG]} یک رشته قابل قبول و ({BC}} یک رشته غیرقابل قبول است.

13- برنامه ای بنویسید که با استفاده از ساختمان داده صف، محتویات یک پشته را معکوس کند.

14- در شبه کد زیر تابع push عملیات اضافه کردن به پشته، تابع pop عملیات حذف از پشته و تابع isEmpty خالی بودن پشته را چک میکند. تابع زیر چه عملی را انجام می‌دهد؟

void function(int n)
{
    Stack S;  // Say it creates an empty stack S
    while (n < 0)
    {
      // This line pushes the value of n%2 to stack S
      push(&S, n%2);
 
      n = n/2;
    }
 
    // Run while Stack S is not empty
    while (!isEmpty(&S))
      cout<<pop(&S)); // pop an element from S and print it
}

16 – در شبه کد زیر S پشته و Q صف حلقوی است. تابع TOP(S)  مقدار بالای پشته را برمیگرداند (بدون اینکه مقدار بالای پشته را حذف کند) و تابع HEAD(Q)   مقدار ابتدای صف را برمیگرداند (بدون اینکه آن مقدار را حذف کند.) همچنین توابع Enqueue و  Dequeue به ترتیب به عملیات درج و حذف از صف را انجام می‌دهد. به طور مشابه Push و Pop به ترتیب عملیات اضافه و حذف را از صف انجام می‌دهند.
ابتدا مشخص کنید با فرض اینکه در ابتدای انجام الگوریتم صف Q شامل مقادیری عدد و S یک پشته خالی است، این الگوریتم چه عملی انجام می‌دهد و مرتبه زمانی آن چقدر است؟
راهنمایی : بهتر است الگوریتم را با یک صف 4 تایی trace کنید

15 – فرض کنید که می‌خواهیم با استفاده از آرایه A که اندازه آن MAXSIZE است به طور همزمان دو پشته را پیاده سازی کنیم. دو پشته به صورت مخالف هم رشد خواهند کرد، یعنی پشته 1 از ابتدای آرایه به سمت انتها پر می‌شود و پسته دوم از انتهای پشته به سمت ابتدا پر می‌شود. دو متغیر top1 و top2 به عناصر بالای پشته 1 و پشته 2 اشاره می‌کنند. (top1 < top2) بهترین شرط برای پر بودن پشته ها کدام گزینه است؟

الف)(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
ب) top1 + top2 = MAXSIZE
ج) MAXSIZE
د) top1= top2 -1

17- در شبه کد زیر S پشته و Q صف حلقوی است. تابع TOP(S)  مقدار بالای پشته را برمیگرداند (بدون اینکه مقدار بالای پشته را حذف کند) و تابع HEAD(Q)   مقدار ابتدای صف را برمیگرداند (بدون اینکه آن مقدار را حذف کند.) همچنین توابع Enqueue و  Dequeue به ترتیب به عملیات درج و حذف از صف را انجام می‌دهد. به طور مشابه Push و Pop به ترتیب عملیات اضافه و حذف را از صف انجام می‌دهند.
ابتدا مشخص کنید با فرض اینکه در ابتدای انجام الگوریتم صف Q شامل مقادیری عدد و S یک پشته خالی است، این الگوریتم چه عملی انجام می‌دهد و مرتبه زمانی آن چقدر است؟
راهنمایی : بهتر است الگوریتم را با یک صف 4 تایی trace کنید

شما می‌توانید حل سوالات این نوشته را در کانال یوتیوب سایت مشاهده کنید

لیست پیوندی

18- فرض کنید یک لیست پیوندی یک طرفه داریم که هر گره آن شامل نام، نام‌خانوادگی و معدل دانشجوست. تابعی بنویسید که میانگین معدل دانشجویان و نام دانشجویی که بیشترین معدل را دارد چاپ کند.
تذکر: این لیست پیوندی از استراکچری به نام student استفاده می‌کند که شامل فیلدهای name، family،avg و link است که لینک اشاره گر به عنصر بعدی است.

19 تابعی بنویسید که دو لیست پیوندی مرتب را دریافت کند و آن را در یک لیست پیوندی به طوری ادغام کند که لیست پیوندی حاصل نیز مرتب باشد.

20- تابع زیر با دریافت آدرس اولین گره از لیست پیوندی چه کاری انجام میدهد؟

int function( node  *ptr){
	if(ptr == null) 
		return 0;
	else
		return (1 + function(ptr -> link));
}

21- ساختار لیست دو پیوندی به صورت زیر است:

typedef structure node  *node_pointer;
typedef structure node {
	node_pointer llink;
	int data;
	node_pointer rlink;
}

  تابع درج  و حذف  این ساختار را بنویسید به گونه ای که در تابع insert قرار است item را به بعد نود p اضافه کنیم و در تابع delete نود p را حذف کنیم. الگوی تابع insert و delete را مشاهده می‌کنید:

void insert (node_pointer p,int item)
int delete(node_pointer p)

درخت (درخت دودویی، درخت max heap، درخت دودویی جستجو)

22- در یک درخت دودویی با 25 گره، در صورتی که 6 گره 2 فرزندی وجود داشته باشد تعداد گره های تک فرزندی کدام است؟
1) 12
2)13
3) 6
4) هیچکدام

23- در یک درخت دودویی کامل با 100 گره، چه تعداد برگ (گره پایانی) وجود دارد؟
1) 500
2) 501
3) 250
4) هیچکدام

24 – پیمایش میانوندی، پیشوندی و پسوندی درخت های زیر را بنویسید

25- درصورتی که پیمایش میانوندی یک درخت کامل به صورت زیر باشد، پیمایش پیشوندی آن را بنویسید.
                                                      BACEDIGHF

26- پیمایش پیشوندی و میانوندی درخت T به صورت زیر است، درخت T را رسم کنید.
پیمایش پیشوندی: ABEDCFG  
پیمایش میانوندی: BACDEFG  

27 – یک درخت دودویی به نام T با n گره داریم. اگر اولین گره در پیمایش PostOrder درخت با آخرین گره از پیمایش PreOrder درخت یکسان باشد کدام گزینه را می‌توان نتیجه گرفت؟

الف – زیر درخت چپ T خالی است
ب – درخت T حداکثر 3 گره دارد
ج – زیر درخت راست T خالی است.
د – ارتفاع درخت T برابر n است

28- درخت دودویی T را در نظر بگیرید که همه‌ی نودهای آن اعداد حقیقی هستند. تابعی بنویسید که ریشه‌ی درخت T را از ورودی بگیرد و مجموع اعداد حقیقی ذخیره شده در درخت را برگرداند.

29- درخت max_heap با n عنصر به صورت آرایه پیاده سازی شده است. الگوریتم پیدا کردن عنصر مینیمم در این درخت را بنویسید.

30- تابعی بنویسید که یک آرایه n تایی به عنوان پارامتر ورودی دریافت کند و تشخیص دهد که آیا آرایه max_heap است یا خیر

26- پیمایش پیشوندی و میانوندی درخت T به صورت زیر است، درخت T را رسم کنید.
پیمایش پیشوندی: ABEDCFG  
پیمایش میانوندی: BACDEFG  

27 – یک درخت دودویی به نام T با n گره داریم. اگر اولین گره در پیمایش PostOrder درخت با آخرین گره از پیمایش PreOrder درخت یکسان باشد کدام گزینه را می‌توان نتیجه گرفت؟

الف – زیر درخت چپ T خالی است
ب – درخت T حداکثر 3 گره دارد
ج – زیر درخت راست T خالی است.
د – ارتفاع درخت T برابر n است

28- درخت دودویی T را در نظر بگیرید که همه‌ی نودهای آن اعداد حقیقی هستند. تابعی بنویسید که ریشه‌ی درخت T را از ورودی بگیرد و مجموع اعداد حقیقی ذخیره شده در درخت را برگرداند.

29- درخت max_heap با n عنصر به صورت آرایه پیاده سازی شده است. الگوریتم پیدا کردن عنصر مینیمم در این درخت را بنویسید.

30- تابعی بنویسید که یک آرایه n تایی به عنوان پارامتر ورودی دریافت کند و تشخیص دهد که آیا آرایه max_heap است یا خیر

31- از درخت دودویی جستجوی زیر ابتدا عدد 50 را حذف کنید.
بعد از حذف عدد 50، عدد 40 را حذف کنید.
و در نهایت عدد 10 را حذف کنید (و درخت نهایی بعد از حذف این سه عدد را رسم کنید)

32 – تابعی بنویسید که ریشه یک درخت دودویی (که شامل اعداد صحیح است) دریافت کند و تشخیص دهد که آیا این درخت دودویی جستجو است یا خیر.
33- اگر دنباله A=a1,a2,…an داده شده باشد ، الگوریتمی بنویسید که تشخیص دهد A یک دنباله جستجو است یا خیر. (توضیح مربوط به دنباله جستجو در دقیقه 31 از آموزش ویدیویی بالا ارائه شده است.)
34-   تابعی بنویسید که یک نود به عنوان ریشه یک درخت دریافت کند و یک کپی از درخت ایجاد کند.
tree_pointer copy (tree_pointer  orginal);
35- دو درخت دودویی را معادل یا برابر گویند اگر دارای توپولوژی یکسان و داده های مساوی در نودهایمتناظر داشته باشند. تابعی بنویسید که ریشه دو درخت را دربافت کند و برابری این دو درخت را با هم چک کنند.
bool equal (tree_pointer  first, tree_pointer second);

مهمانی شرکت

36- شرکتی n کارمند دارد که  هر کدام از آنها با شماره‌های 1 تا n شماره‌گذاری شده‌اند. هر کارمند می‌تواند مدیر نداشته باشد [فرض کنید که فقط یک کارمند داریم که مدیر نداشته باشد] یا  فقطیک مدیر داشته باشد. (که مدیرش یکی از کارمندان دیگر است.)  کارمند A مدیر ارشد کارمند B  است، اگر یکی از دو شرط زیر برقرار باشد:
کارمند A مدیرِ کارمند B باشد.
کارمند A مدیر کارمند C باشد و کارمند C مدیر کارمند B باشد.

این شرکت می‌خواهد در یک هتل مهمانی برگزار کند  و در نظر دارد کارمندانش را به گونه‌ای در تالارهای این هتل پخش کند که در هیچ تالاری کارمند و مدیر ارشدش با هم در یک تالار نباشند.
(توجه داشته باشید که این شرکت، دارای دورِ مدیریتی نیست. به این معنی که هیچ کارمندی وجود ندارد که مدیرِ مدیر ارشدش باشد)
الف) با ذکر دلیل، توضیح دهید که برای ذخیره‌ی اطلاعات کارمندان شرکت بهتر است از چه ساختمان داده‌ای استفاده شود. (صف، پشته، لیست پیوندی، درخت عمومی، درخت دودویی، درخت جست و جوی دودویی، max heap ، Min heap، B Tree)  
ب) [فرض کنید که هر کارمند، می‌تواند حداکثر مدیر دو کارمند دیگر باشد] در بهترین حالت ممکن، با داشتن n کارمند، تعداد تالار مورد نیاز را با ذکر دلیل بنویسید. 
ج) برنامه‌ای بنویسید که خط اول ورودی n (تعداد کارمندان) را از ورودی دریافت کند.
سپس در n خط بعدی، p_i(1<=p_i<=p_n) را بگیرد. هر p_i  نشان‌دهنده‌ی مدیر کارمند i  است. در صورتی p_i منفی یک باشد، به این معنی‌ست که کارمند i مدیر ندارد.
برنامه باید در خروجی مینیمم تعداد تالارهای مورد نیاز را چاپ کند.

input: 4
1-
1
2
1

output:
3

شما می‌توانید حل سوالات این نوشته را در کانال یوتیوب سایت مشاهده کنید