1.आसान
0 से k की सीमा में n पूर्णांकों के लिए काउंटिंग सॉर्ट (counting sort) का रनिंग टाइम क्या है?
- AO(n + k)
- BO(n log n)
- CO(k log n)
- DO(n²)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
बड़े n के लिए कौन-सा कॉम्प्लेक्सिटी क्लास सबसे तेज़ी से बढ़ता है?
- AO(n³)
- BO(n log n)
- CO(2ⁿ)
- DO(n²)
3.आसान
एक O(n²) एल्गोरिदम n = 1000 के लिए 1 सेकंड लेता है। n = 2000 के लिए लगभग कितना समय लगेगा?
- A8 सेकंड
- B2 सेकंड
- C4 सेकंड
- D1 सेकंड
4.मध्यम
1, 3 और 4 के सिक्कों और 6 की राशि के साथ, ग्रीडी "पहले सबसे बड़ा सिक्का" विधि इष्टतम की तुलना में कितने सिक्के उपयोग करती है?
- Aग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 3 है
- Bग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
- Cग्रीडी 2 सिक्के उपयोग करती है; इष्टतम 2 है
- Dग्रीडी 4 सिक्के उपयोग करती है; इष्टतम 3 है
5.मध्यम
एक ग्रीडी एल्गोरिदम (greedy algorithm):
- Aहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
- Bहमेशा इष्टतम समाधान देता है
- Cकेवल रिकर्शन का उपयोग करता है
- Dहर संभव समाधान आज़माता है
6.मध्यम
गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?
- ADijkstra का एल्गोरिदम
- Bडेप्थ-फ़र्स्ट सर्च (DFS)
- CKruskal का एल्गोरिदम
- Dहर स्थिति में Bellman–Ford आवश्यक है
7.कठिन
मास्टर प्रमेय का उपयोग करके T(n) = 8T(n/2) + O(n²) का हल क्या है?
- AΘ(n² log n)
- BΘ(n²)
- CΘ(n³)
- DΘ(n log n)
8.कठिन
ट्रैवलिंग सेल्समैन समस्या का वर्गीकरण कैसे होता है?
- Aयह P में है क्योंकि डाइकस्ट्रा का एल्गोरिदम हर शहर को एक बार देखकर इसे हल करता है
- Bनिर्णय रूप P में है पर ऑप्टिमाइज़ेशन रूप NP-complete है
- Cयह अनिर्णेय है
- Dनिर्णय रूप NP-complete है और ऑप्टिमाइज़ेशन रूप NP-hard
उत्तर कुंजी
- 1. A · O(n + k)
- 2. C · O(2ⁿ)
- 3. C · 4 सेकंड
- 4. B · ग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
- 5. A · हर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
- 6. A · Dijkstra का एल्गोरिदम
- 7. C · Θ(n³)
- 8. D · निर्णय रूप NP-complete है और ऑप्टिमाइज़ेशन रूप NP-hard
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।