1.आसान
एक मानक ऐरे-आधारित मर्ज सॉर्ट कितनी अतिरिक्त मेमोरी का उपयोग करता है?
- AO(n)
- BO(n²)
- CO(1)
- DO(log n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
बड़े n के लिए कौन-सा कॉम्प्लेक्सिटी क्लास सबसे तेज़ी से बढ़ता है?
- AO(n log n)
- BO(n³)
- CO(2ⁿ)
- DO(n²)
3.आसान
दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?
- AO(2n)
- BO(n)
- CO(log n)
- DO(n²)
4.मध्यम
रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?
- AO(n²)
- BO(2ⁿ)
- CO(n)
- DO(n log n)
5.मध्यम
सरल रिकर्सिव फ़िबोनाची (fib(n) = fib(n−1) + fib(n−2)) की टाइम कॉम्प्लेक्सिटी क्या है?
- Aरैखिक (Linear)
- Bस्थिर (Constant)
- Cलघुगणकीय (Logarithmic)
- Dघातांकी (Exponential)
6.मध्यम
एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?
- Aयादृच्छिक इनपुट पर अपेक्षित लागत
- Bऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
- Cसबसे अच्छे इनपुट पर एल्गोरिदम की लागत
- Dपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
7.कठिन
कुक–लेविन प्रमेय ने क्या स्थापित किया?
- Aहर NP समस्या घातांकी समय में हल हो सकती है
- Bहॉल्टिंग समस्या अनिर्णेय (undecidable) है
- Cबूलियन संतुष्टि समस्या (SAT) NP-complete है
- DP, NP के बराबर नहीं है
8.कठिन
अनसॉर्टेड ऐरे का k-वाँ सबसे छोटा तत्व चुनने के बारे में कौन-सा कथन सही है?
- Aसिलेक्शन को हमेशा Ω(n log n) चाहिए क्योंकि उसे सॉर्टिंग चाहिए
- Bक्विकसिलेक्ट वर्स्ट केस में O(log n) में चलता है क्योंकि वह पिवट के केवल एक ओर रिकर्स करता है
- Cसिलेक्शन केवल O(n²) में संभव है
- Dक्विकसिलेक्ट अपेक्षित O(n) में चलता है, और मीडियन-ऑफ़-मीडियन्स वर्स्ट केस में O(n) की गारंटी देता है
उत्तर कुंजी
- 1. A · O(n)
- 2. C · O(2ⁿ)
- 3. D · O(n²)
- 4. A · O(n²)
- 5. D · घातांकी (Exponential)
- 6. B · ऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
- 7. C · बूलियन संतुष्टि समस्या (SAT) NP-complete है
- 8. D · क्विकसिलेक्ट अपेक्षित O(n) में चलता है, और मीडियन-ऑफ़-मीडियन्स वर्स्ट केस में O(n) की गारंटी देता है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।