1.आसान
कौन-सा सॉर्टिंग एल्गोरिदम एक पिवट चुनकर ऐरे को छोटे और बड़े तत्वों में विभाजित करता है?
- Aइंसर्शन सॉर्ट
- Bबबल सॉर्ट
- Cमर्ज सॉर्ट
- Dक्विकसॉर्ट (Quicksort)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
एक O(n) एल्गोरिदम n = 10 लाख के लिए 3 सेकंड लेता है। n = 20 लाख के लिए लगभग कितना समय लगेगा?
- A6 सेकंड
- B9 सेकंड
- C3 सेकंड
- D12 सेकंड
3.आसान
रिकर्शन (recursion) क्या है?
- Aएक सॉर्टिंग विधि
- Bएक फ़ंक्शन जो छोटे इनपुट पर स्वयं को कॉल करता है
- Cएक प्रकार की डेटा संरचना
- Dएक लूप जो कभी समाप्त नहीं होता
4.मध्यम
n तत्वों के ऐरे के लिए मर्ज सॉर्ट के रिकर्शन में कितने स्तर होते हैं?
- Aलगभग log₂ n
- Bलगभग n / 2
- Cलगभग √n
- Dलगभग n
5.मध्यम
भर जाने पर अपनी क्षमता दोगुनी करने वाले डायनेमिक ऐरे में तत्व जोड़ने (append) की एमॉर्टाइज़्ड (amortised) टाइम कॉम्प्लेक्सिटी क्या है?
- AO(1)
- BO(n)
- CO(n²)
- DO(log n)
6.मध्यम
डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:
- Aकेवल एक लूप
- Bकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
- Cकेवल यादृच्छिक इनपुट
- Dओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
7.कठिन
हेल्ड–कार्प डायनेमिक प्रोग्रामिंग एल्गोरिदम ट्रैवलिंग सेल्समैन समस्या को ठीक-ठीक हल करता है। n शहरों के लिए इसका रनिंग टाइम क्या है?
- AO(n!)
- BO(n³)
- CO(2n²)
- DO(n² 2ⁿ)
8.कठिन
कोई समस्या NP-complete होती है यदि वह:
- Aबहुपद समय में हल की जा सकती है
- BNP से बाहर है लेकिन सभी NP समस्याओं से कठिन है, जैसे हॉल्टिंग समस्या
- Cहल करना असंभव है
- DNP में है और हर NP समस्या बहुपद समय में उसमें रिड्यूस होती है
उत्तर कुंजी
- 1. D · क्विकसॉर्ट (Quicksort)
- 2. A · 6 सेकंड
- 3. B · एक फ़ंक्शन जो छोटे इनपुट पर स्वयं को कॉल करता है
- 4. A · लगभग log₂ n
- 5. A · O(1)
- 6. D · ओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
- 7. D · O(n² 2ⁿ)
- 8. D · NP में है और हर NP समस्या बहुपद समय में उसमें रिड्यूस होती है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।