1.आसान
एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(E log V)
- BO(V + E)
- CO(V × E)
- DO(V²)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
ब्रूट-फ़ोर्स एल्गोरिदम क्या है?
- Aवह जो सभी संभावित उम्मीदवार समाधान आज़माता है
- Bवह जो हमेशा रिकर्शन का उपयोग करता है
- Cवह जो कई प्रोसेसरों पर चलता है
- Dवह जो यादृच्छिक रूप से उत्तर का अनुमान लगाता है
3.आसान
3n² + 5n + 2 का Big O क्या है?
- AO(5n)
- BO(3n²)
- CO(n²)
- DO(n³)
4.मध्यम
मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?
- Aमर्ज सॉर्ट की कोई रिकर्सिव संरचना नहीं है
- Bइसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
- Cडायनेमिक प्रोग्रामिंग केवल ग्राफ़ समस्याओं पर काम करती है, ऐरे पर नहीं
- Dमर्ज सॉर्ट पहले से ही O(n) है
5.मध्यम
रिकरेंस T(n) = 2T(n/2) + O(n) का हल क्या है?
- AO(log n)
- BO(n²)
- CO(n)
- DO(n log n)
6.मध्यम
रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?
- AO(n log n)
- BO(2ⁿ)
- CO(n²)
- DO(n)
7.कठिन
P और NP के बारे में कौन-सा कथन सही है?
- AP की हर समस्या NP में भी है
- Bयह सिद्ध हो चुका है कि P ≠ NP
- CNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
- DNP का अर्थ है "not polynomial"
8.कठिन
कौन-सी तकनीक किसी भी इनपुट पर क्विकसॉर्ट को अपेक्षित (expected) O(n log n) रनिंग टाइम देती है?
- Aपिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना
- Bहमेशा पहला तत्व चुनना
- Cक्विकसॉर्ट चलाने से पहले इनपुट को सॉर्ट करना
- Dकेवल बाईं ओर रिकर्शन का उपयोग करना
उत्तर कुंजी
- 1. B · O(V + E)
- 2. A · वह जो सभी संभावित उम्मीदवार समाधान आज़माता है
- 3. C · O(n²)
- 4. B · इसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
- 5. D · O(n log n)
- 6. C · O(n²)
- 7. A · P की हर समस्या NP में भी है
- 8. A · पिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।