उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट

एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(V × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V²)

किसी रिकर्सिव फ़ंक्शन का बेस केस क्या है?

1. Aवह स्थिति जिसका उत्तर बिना कोई और रिकर्सिव कॉल किए सीधे दिया जाता है
2. Bफ़ंक्शन की पहली पंक्ति
3. Cवह कॉल जो सबसे अधिक मेमोरी लेती है
4. Dसबसे बड़े इनपुट वाली स्थिति, जिसे किसी भी रिकर्सिव कॉल से पहले संभाला जाता है

मर्ज सॉर्ट कौन-सी डिज़ाइन रणनीति का उपयोग करता है?

1. Aडायनेमिक प्रोग्रामिंग
2. Bग्रीडी चयन
3. Cडिवाइड एंड कॉन्कर (विभाजन और विजय)
4. Dब्रूट फ़ोर्स

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

1. Aऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
2. Bयादृच्छिक इनपुट पर अपेक्षित लागत
3. Cपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
4. Dसबसे अच्छे इनपुट पर एल्गोरिदम की लागत

आधार k में d अंकों वाले n पूर्णांकों पर LSD रेडिक्स सॉर्ट का रनिंग टाइम क्या है?

1. AO(n²)
2. BO(dn log k)
3. CO(n log n)
4. DO(d(n + k))

n तत्वों के ऐरे के लिए मर्ज सॉर्ट के रिकर्शन में कितने स्तर होते हैं?

1. Aलगभग √n
2. Bलगभग n
3. Cलगभग n / 2
4. Dलगभग log₂ n

यह सिद्ध करने के लिए कि कोई निर्णय समस्या X NP-complete है, कौन-सी दो बातें दिखानी होंगी?

1. AX का कोई बहुपदी एल्गोरिदम नहीं है, और X निर्णेय है
2. BX, P में है, और X, SAT में रिड्यूस होती है
3. CX, P की किसी समस्या में रिड्यूस होती है, और X, NP में है
4. DX, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है

सबसे छोटे सरल पथ बहुपदी समय में खोजे जा सकते हैं। सामान्य ग्राफ़ में दो शीर्षों के बीच सबसे लंबा सरल पथ खोजने के बारे में क्या ज्ञात है?

1. Aयह हमेशा O(V + E) में हल होता है
2. Bइसे ऋणात्मक भारों के साथ डाइकस्ट्रा के एल्गोरिदम से हल किया जा सकता है
3. Cयह NP-hard है
4. Dयह अनिर्णेय है