سوالات آزمون دکتری مهندسی کامپیوتر ۱۴۰۳ با پاسخ تشریحی

سوالات دکتری مهندسی کامپیوتر 1403 ، کلید سوالات آزمون دکتری مهندسی کامپیوتر ، سوالات کنکور دکتری مهندسی کامپیوتر با پاسخ تشریحی

سوالات آزمون دکتری مهندسی کامپیوتر ۱۴۰۳ با پاسخ تشریحی

کلید اولیه سوالات آزمون دکتری مهندسی کامپیوتر (کد 2354) سال ۱۴۰۳ که در سایت سازمان سنجش منتشر شده است.

گروه امتحانی	شماره پاسخنامه	نوع دفترچه	عنوان دفترچه
مهندسي و فني	3	C	مهندسي كامپيوتر

شماره سوال	گزینه صحیح
1	3
2	4
3	3
4	1
5	1
6	3
7	2
8	2
9	4
10	2
11	1
12	2
13	1
14	3
15	4
16	3
17	1
18	1
19	2
20	3
21	1
22	2
23	1
24	3
25	4
26	2
27	3
28	1
29	3
30	4

شماره سوال	گزینه صحیح
31	3
32	1
33	1
34	3
35	2
36	4
37	1
38	2
39	4
40	1
41	4
42	2
43	4
44	4
45	2
46	2
47	2
48	4
49	4
50	2
51	3
52	4
53	3
54	1
55	3
56	4
57	1
58	4
59	2
60	3

شماره سوال	گزینه صحیح
61	3
62	2
63	4
64	2
65	3
66	4
67	3
68	1
69	1
70	2
71	4
72	2
73	3
74	1
75	3
76	2
77	3
78	3
79	2
80	1
81	4
82	2
83	3
84	3
85	2
86	1
87	4
88	2
89	1
90	4

شماره سوال	گزینه صحیح
91	2
92	3
93	3
94	4
95	1
96	2
97	4
98	4
99	1
100	2
101	1
102	3
103	4
104	4
105	1
106	4
107	2
108	3
109	1
110	3
111	4
112	2
113	4
114	1
115	1
116	3
117	1
118	4
119	3
120	4

شماره سوال	گزینه صحیح
121	2
122	1
123	4
124	1
125	4

*

کلید سوالات دکتری ۱۴۰۳ داده الگوریتم:

۱. حذف و به احتمال زیاد گزینه 3 درست است

حداقل مرتبه لازم برای حل این مسئله یا کران پایین آن Ω(nlogn) است چرا؟

می‌دانیم هدف یافتن دو عنصر است که کمینه و بیشینه باشند (آن‌ها را a و b بنامید) و تفاضل آن‌ها کمینه گردد.
فرض کنید در نسخه ساده تر این مسئله حتی مقدار تفاضل را می‌دانیم به عبارتی b-a=k
الان فرض کنید حتی آرایه هم افراز نشده است و می‌خواهیم از آرایه n عنصری a و b را پیدا کنیم که شرط بالا را داشته باشد
طبق کلاس می‌دانیم هزینه این مسئله حداقل Ω(nlogn) است.

پس جواب در گزینه‌ها نیست!!!!!!

۲. گزینه چهار

FFT مرتبه رو میاره رو nlogn

۳. حذف و به احتمال زیاد گزینه 3 درست است
تعداد درختان دودویی که پیمایش pre و pos برابر است ورودی مسئله است دو به توان ۳۴ است. در کلید اولیه حذف نخواهد شد اما کلید نهایی چرا.

۴. گزینه یک
همین در کلاس حل تست عیناً حل شد (مسئله یافتن محل قرار گیری مربی)
شماها آن را با میانه میشناسید که همان n می‌شود

۵. گزینه اول

مسئله جوزف که در کلاس گفته شده. پاسخ ۷۵۷ است چون ابتدا عنصر دوم، عنصر چهار… حذف می‌کند.

۶. گزینه سوم

در کلاس حل شده، چون اعداد یکتا و از 1 تا n هستند کافیه جمع کنید و مجموعش باید بشه

مجموع عناصر آرایه=n(n+1)/2

حل این معادله ساده عدد گمشده را خواهد داد.
کران پایین حل این مسئله در بدترین حالت n است چرا ؟

۷. گزینه‌ دوم

در کلاس حل شد عینا و مرتبه n هست. دقت کنید که
k<=n
پس مرتبه n هست.

۸. حذف

حداکثر جریان برابر است مین کات، مین کات برابر است با ۶. پس گزینه صحیح وجود ندارد

۹. گزینه چهارم

در کلاس گفته شده بود

۱۰. گزینه دوم

همان sqrtsort معروف است که در کلاس حل شد

۱۱. گزینه چهارم

با استقرا می‌توان نشان داد که گزینه دوم نیست پس بعد از رسم درخت با بازگشت آن به گزینه اخر خواهیم رسید.

۱۲. گزینه دوم

گزینه اول غلط است چون A میتواند جزو P باشد که از ان نمیتوان نتیجه گرفت که
P=NP

گزینه سوم غلط است طبق کلاس و گزینه چهار نیز غلط است.

۱۳. گزینه اول

درخت بازگشت آنرا رسم کنید!

۱۴. گزینه چهار

مرتبه الگوریتم حریصانه برای آن nlogn است و از هرم استفاده می‌کنید. استفاده از درخت جستجوی متوازن هم اوکی هست که منطور طراحی احتمال قوی همین بوده.

۱۵. گزینه چهارم

هر سه مورد در کلاس توضیح داده شده است.

۱۶. گزینه سوم

مورد اول درست است چون گراف همبند است تعداد یال‌ها E>=V-1 است

همچنین کوتاه‌ترین مسیر نیاز به BFS و خواندن حداقل یکبار یال‌ها می‌باشد پس این گزاره غلط است.
سومی صحیح است

۱۷. گزینه اول

این همان مسئله تعداد راه‌های انداختن n توپ در k سبد است که یک معادله بازگشتی فول هیستوری خواهد شد که با تفریق به گزینه اول خواهید رسید.

۱۸. گزینه اول

عنصر میانه همان عنصر است چرا؟
پس کافیست میانه را پیدا کنید

۱۹. گزینه دوم

تو حل تست گفته شده بود.

۲۰. گزینه سوم

مورد اول غلط است یکبار DFS لازم است.
مورد دوم صحیح است و در کلاس گفته شده بود
مورد سوم صحیح است گرافی دور دارد که بیش از V-1 یال داشته باشد پس کافیست V-1 یال و رأس بررسی شوند.( در گراف بدون جهت البته)

تحلیل سوالات ساختمان داده الگوریتم کنکور دکتری ورودی ۱۴۰۳

۱ – ۳ سخت و حل خلاقانه
۲ – ۴ سخت و از کتاب مرجع کورمن
۳ – ۳ تعداد گره تک فرزندی رو نداده ولی گزینه ۳ تنها گزینه ای است که توانی از ۲ است. البته با وجود ۵ گره تک فرزندی تعداد گره ها باید زوج باشد. می توانید اعتراض دهید ولی ای کاش به جای ۳۵ طراح ۳۴ می داد که سوالش با مزه بشه
۴ – ۱ سخت بحث میانه
۵ – کد داده شده غلطه ولی کلید گزینه ۱ خواهد بود. اعتراض برای حذف
۶ – ۳ ساده و‌ تکراری
۷ – ۲ متوسط و تکراری
۸ – ساده و متاسفانه غلط جواب ۶ که نیست
۹ – ۴ ساده و تکراری
۱۰ – ۲ ساده و‌ تکراری
۱۱ – ۴ متوسط
۱۲ – ۲ ساده و پرتکرار
۱۳ – ۱ تکراری
۱۴ – ۴ سخت و نیاز به کمی فکر
۱۵ – ۴ ساده و‌ پر تکرار
۱۶ – ۳ ساده و‌ پر تکرار
۱۷ – ۱ ساده از تست های گسسته ارشد
۱۸ – ۱ سخت
۱۹ – ۲ ساده و تکراری
۲۰ – ۳ ساده و بسیار گفته شده

با تشکر از جناب محمد رستمی

 

47 : گزینه

48 : گزینه دوم

60 : گزینه سوم