1.आसान
दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?
- AO(n)
- BO(n²)
- CO(2n)
- DO(log n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
कौन-सा सॉर्टिंग एल्गोरिदम गलत क्रम में मौजूद आसन्न तत्वों को बार-बार आपस में बदलता है?
- Aक्विकसॉर्ट (Quicksort)
- Bहीप सॉर्ट (Heap sort)
- Cबबल सॉर्ट (Bubble sort)
- Dमर्ज सॉर्ट (Merge sort)
3.आसान
n तत्वों वाले अनसॉर्टेड ऐरे में लीनियर सर्च (linear search) की टाइम कॉम्प्लेक्सिटी (वर्स्ट केस) क्या है?
- AO(n²)
- BO(1)
- CO(n)
- DO(log n)
4.मध्यम
वर्स्ट केस में तुलना-आधारित (comparison-based) सॉर्टिंग की निचली सीमा क्या है?
- AΩ(n log n)
- BΩ(n)
- CΩ(n²)
- DΩ(log n)
5.मध्यम
कौन-सा सॉर्टिंग एल्गोरिदम स्थिर (stable) है?
- Aक्विकसॉर्ट (सामान्य इन-प्लेस संस्करण)
- Bसेलेक्शन सॉर्ट (सामान्य संस्करण)
- Cहीप सॉर्ट
- Dमर्ज सॉर्ट
6.मध्यम
क्विकसॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n²)
- BO(n)
- CO(n log n)
- DO(log n)
7.कठिन
यह दिखाने के लिए कि कोई नई समस्या X NP-hard है, आपको क्या करना होगा?
- Aदिखाना कि X बहुपदी समय में सत्यापित हो सकती है
- Bकिसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना
- CX को बहुपदी समय में किसी ज्ञात NP-hard समस्या में रिड्यूस करना
- Dदिखाना कि छोटे इनपुट के लिए X का कोई बहुपदी एल्गोरिदम नहीं है
8.कठिन
नैपसैक के किस रूप के लिए ग्रीडी नियम "वस्तुओं को प्रति भार मूल्य के क्रम में लें" हमेशा इष्टतम उत्तर देता है?
- Aदोनों रूप
- Bकोई भी रूप नहीं
- Cफ़्रैक्शनल नैपसैक, जिसमें वस्तुएँ बाँटी जा सकती हैं
- D0/1 नैपसैक, जिसमें वस्तुएँ हमेशा पूरी ली जानी चाहिए
उत्तर कुंजी
- 1. B · O(n²)
- 2. C · बबल सॉर्ट (Bubble sort)
- 3. C · O(n)
- 4. A · Ω(n log n)
- 5. D · मर्ज सॉर्ट
- 6. A · O(n²)
- 7. B · किसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना
- 8. C · फ़्रैक्शनल नैपसैक, जिसमें वस्तुएँ बाँटी जा सकती हैं
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।