1.आसान
एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(V + E)
- BO(V × E)
- CO(E log V)
- DO(V²)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
किसी एल्गोरिदम का वर्स्ट-केस रनिंग टाइम क्या बताता है?
- Aसबसे छोटे इनपुट पर लगने वाला समय
- Bधीमे कंप्यूटर पर लगने वाला समय
- Cआकार n के किसी यादृच्छिक इनपुट पर लगने वाला अपेक्षित समय
- Dn आकार के सभी इनपुट पर लगने वाला अधिकतम समय
3.आसान
सिलेक्शन सॉर्ट (selection sort) कैसे काम करता है?
- Aयह ऐरे को आधे भागों में बाँटकर उन्हें मर्ज करता है
- Bयह बार-बार ग़लत क्रम वाले पड़ोसी तत्वों को स्वैप करता है
- Cयह बार-बार अनसॉर्टेड भाग का न्यूनतम खोजकर उसे आगे की ओर स्वैप करता है
- Dयह हर तत्व को शिफ़्ट करके बढ़ते सॉर्टेड भाग में डालता है
4.मध्यम
1, 3 और 4 के सिक्कों और 6 की राशि के साथ, ग्रीडी "पहले सबसे बड़ा सिक्का" विधि इष्टतम की तुलना में कितने सिक्के उपयोग करती है?
- Aग्रीडी 2 सिक्के उपयोग करती है; इष्टतम 2 है
- Bग्रीडी 4 सिक्के उपयोग करती है; इष्टतम 3 है
- Cग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
- Dग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 3 है
5.मध्यम
डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:
- Aकेवल यादृच्छिक इनपुट
- Bकेवल एक लूप
- Cकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
- Dओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
6.मध्यम
कई लाइब्रेरी सॉर्टिंग रूटीन बहुत छोटे सबऐरे के लिए इंसर्शन सॉर्ट पर क्यों चली जाती हैं?
- Aइंसर्शन सॉर्ट वर्स्ट केस में O(n log n) है
- Bरिकर्सिव एल्गोरिदम 10 से कम तत्वों वाले ऐरे नहीं सँभाल सकते
- Cबड़े इनपुट पर इंसर्शन सॉर्ट किसी भी अन्य सॉर्टिंग एल्गोरिदम से कम मेमोरी उपयोग करता है
- Dइंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है
7.कठिन
क्लास NP की कौन-सी परिभाषा सही है?
- Aसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं
- Bनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
- Cसमस्याएँ जो बहुपदी नहीं हैं
- Dसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
8.कठिन
बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?
- Aप्रति वृद्धि O(n)
- Bप्रति वृद्धि O(log n)
- Cप्रति वृद्धि O(1)
- Dप्रति वृद्धि O(n log n)
उत्तर कुंजी
- 1. A · O(V + E)
- 2. D · n आकार के सभी इनपुट पर लगने वाला अधिकतम समय
- 3. C · यह बार-बार अनसॉर्टेड भाग का न्यूनतम खोजकर उसे आगे की ओर स्वैप करता है
- 4. C · ग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
- 5. D · ओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
- 6. D · इंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है
- 7. B · निर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
- 8. C · प्रति वृद्धि O(1)
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।