उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट

मुफ़्त प्रिंट करने योग्य एल्गोरिदम और जटिलता वर्कशीट: आसान से परीक्षा स्तर तक 8 प्रश्न, उत्तर कुंजी सहित। इसे प्रिंट करें या PDF के रूप में सहेजें।

नई वर्कशीटसंकेतों के साथ ऑनलाइन अभ्यास करें

शिक्षकों के लिए: कक्षा में मुफ़्त में प्रिंट, कॉपी और उपयोग करें। हर नई वर्कशीट में नए मान और उसकी अपनी उत्तर कुंजी होती है। अपने कोर्स पेज पर ExamProblems का लिंक देने के लिए धन्यवाद।

नाम: ____________________   दिनांक: ____________

1.आसान

दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(2n)
2.आसान

सिलेक्शन सॉर्ट (selection sort) कैसे काम करता है?

  1. Aयह हर तत्व को शिफ़्ट करके बढ़ते सॉर्टेड भाग में डालता है
  2. Bयह बार-बार ग़लत क्रम वाले पड़ोसी तत्वों को स्वैप करता है
  3. Cयह बार-बार अनसॉर्टेड भाग का न्यूनतम खोजकर उसे आगे की ओर स्वैप करता है
  4. Dयह ऐरे को आधे भागों में बाँटकर उन्हें मर्ज करता है
3.आसान

ब्रूट-फ़ोर्स एल्गोरिदम क्या है?

  1. Aवह जो हमेशा रिकर्शन का उपयोग करता है
  2. Bवह जो सभी संभावित उम्मीदवार समाधान आज़माता है
  3. Cवह जो यादृच्छिक रूप से उत्तर का अनुमान लगाता है
  4. Dवह जो कई प्रोसेसरों पर चलता है
4.मध्यम

बॉटम-अप तालिका से n-वीं फ़िबोनाची संख्या की गणना की टाइम कॉम्प्लेक्सिटी क्या है?

  1. AO(2ⁿ)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
5.मध्यम

एक ग्रीडी एल्गोरिदम (greedy algorithm):

  1. Aकेवल रिकर्शन का उपयोग करता है
  2. Bहर संभव समाधान आज़माता है
  3. Cहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
  4. Dहमेशा इष्टतम समाधान देता है
6.मध्यम

m और n लंबाई की स्ट्रिंग्स के लॉन्गेस्ट कॉमन सबसीक्वेंस के लिए मानक डायनेमिक प्रोग्रामिंग एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

  1. AO(mn log n)
  2. BO(mn)
  3. CO(m + n)
  4. DO(2m+n)
7.कठिन

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

  1. Aबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
  2. Bहर तुलना में लघुगणकीय समय लगता है
  3. Cn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
  4. Dहर तत्व की कम से कम एक बार तुलना होनी चाहिए
8.कठिन

क्लास NP की कौन-सी परिभाषा सही है?

  1. Aसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं
  2. Bसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
  3. Cसमस्याएँ जो बहुपदी नहीं हैं
  4. Dनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं

उत्तर कुंजी

  1. 1. C · O(n²)
  2. 2. C · यह बार-बार अनसॉर्टेड भाग का न्यूनतम खोजकर उसे आगे की ओर स्वैप करता है
  3. 3. B · वह जो सभी संभावित उम्मीदवार समाधान आज़माता है
  4. 4. C · O(n)
  5. 5. C · हर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
  6. 6. B · O(mn)
  7. 7. C · n संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
  8. 8. D · निर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं

पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।