1.आसान
रिकर्शन (recursion) क्या है?
- Aएक लूप जो कभी समाप्त नहीं होता
- Bएक फ़ंक्शन जो छोटे इनपुट पर स्वयं को कॉल करता है
- Cएक सॉर्टिंग विधि
- Dएक प्रकार की डेटा संरचना
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
एवरेज-केस रनिंग टाइम क्या बताता है?
- Aबेस्ट-केस और वर्स्ट-केस रनिंग टाइम के बीच का मध्य मान
- Bऔसत लंबाई वाले इनपुट का समय
- Cn आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
- Dसबसे आम कंप्यूटर पर समय
3.आसान
यदि कोई ऑपरेशन O(1) समय में चलता है, तो इसका क्या अर्थ है?
- Aवह रनिंग टाइम के प्रति सेकंड ठीक एक तत्व संसाधित करता है
- Bउसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
- Cउसे केवल एक बार चलाया जा सकता है
- Dउसमें हमेशा ठीक एक सेकंड लगता है
4.मध्यम
क्या यह कहना सही है कि एक O(n²) एल्गोरिदम O(n³) भी है?
- Aनहीं, क्योंकि Big O को हमेशा फ़ंक्शन की सटीक वृद्धि दर बतानी चाहिए
- Bनहीं, क्योंकि बड़े n के लिए n³, n² से छोटा है
- Cहाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
- Dहाँ, पर केवल तब जब n 100 से छोटा हो
5.मध्यम
Big O में, जैसे O(log n) में, लघुगणक का आधार सामान्यतः क्यों छोड़ दिया जाता है?
- Aआधार केवल छोटे n के लिए मायने रखता है
- Bलघुगणक हमेशा पूर्णांकों में पूर्णांकित किए जाते हैं
- Cभिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं
- Dकंप्यूटर विज्ञान में सभी लघुगणकों का आधार 10 होता है, इसलिए वह निहित है
6.मध्यम
फ़्लॉयड–वॉर्शल एल्गोरिदम क्या गणना करता है, और कितनी तेज़ी से?
- Aएक टोपोलॉजिकल क्रम, O(V²) में
- Bशीर्षों के सभी युग्मों के बीच सबसे छोटे पथ, O(V³) में
- Cएक मिनिमम स्पैनिंग ट्री, O(E log V) में
- Dएक स्रोत शीर्ष से बाकी सभी तक सबसे छोटे पथ, O(V + E) में
7.कठिन
अनिर्णेय (undecidable) समस्या और दुःसाध्य (intractable) समस्या में क्या अंतर है?
- Aदोनों का अर्थ है कि समस्या का कोई एल्गोरिदम ही नहीं है
- Bअनिर्णेय समस्याएँ NP में हैं, जबकि दुःसाध्य समस्याएँ P में हैं
- Cअनिर्णेय समस्या के लिए सभी इनपुट पर कोई एल्गोरिदम नहीं होता; दुःसाध्य के लिए होता है, पर बहुत धीमा
- Dदुःसाध्य समस्याएँ किसी भी एल्गोरिदम से हल नहीं हो सकतीं, जबकि अनिर्णेय समस्याओं को केवल घातांकी समय चाहिए
8.कठिन
P और NP के बारे में कौन-सा कथन सही है?
- ANP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
- Bयह सिद्ध हो चुका है कि P ≠ NP
- CNP का अर्थ है "not polynomial"
- DP की हर समस्या NP में भी है
उत्तर कुंजी
- 1. B · एक फ़ंक्शन जो छोटे इनपुट पर स्वयं को कॉल करता है
- 2. C · n आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
- 3. B · उसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
- 4. C · हाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
- 5. C · भिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं
- 6. B · शीर्षों के सभी युग्मों के बीच सबसे छोटे पथ, O(V³) में
- 7. C · अनिर्णेय समस्या के लिए सभी इनपुट पर कोई एल्गोरिदम नहीं होता; दुःसाध्य के लिए होता है, पर बहुत धीमा
- 8. D · P की हर समस्या NP में भी है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।