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

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

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

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

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

1.आसान

किसी समस्या को सामान्यतः सुसाध्य (tractable) कब कहा जाता है?

  1. Aजब उसे स्थिर समय में हल किया जा सके
  2. Bजब उसे बहुपदी समय में हल किया जा सके
  3. Cजब उसे केवल हर संभावना आज़माकर हल किया जा सके
  4. Dजब उसका कोई समाधान न हो
2.आसान

पहले से सॉर्टेड ऐरे पर इंसर्शन सॉर्ट की बेस्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

एवरेज-केस रनिंग टाइम क्या बताता है?

  1. An आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
  2. Bऔसत लंबाई वाले इनपुट का समय
  3. Cबेस्ट-केस और वर्स्ट-केस रनिंग टाइम के बीच का मध्य मान
  4. Dसबसे आम कंप्यूटर पर समय
4.मध्यम

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

  1. Aसबसे अच्छे इनपुट पर एल्गोरिदम की लागत
  2. Bपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
  3. Cयादृच्छिक इनपुट पर अपेक्षित लागत
  4. Dऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
5.मध्यम

मानक तीन लूप से दो n × n मैट्रिक्स गुणा करने की टाइम कॉम्प्लेक्सिटी क्या है?

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

रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?

  1. AO(log n)
  2. BO(n²)
  3. CO(n)
  4. DO(2ⁿ)
7.कठिन

हैश टेबल में औसत लुकअप O(1) लेकिन वर्स्ट केस O(n) क्यों होता है?

  1. Aकुंजियों को पहले सॉर्ट करना पड़ता है
  2. Bकई कुंजियाँ एक ही बकेट में टकरा (collide) सकती हैं
  3. Cऐरे में एक्सेस O(n) होता है
  4. Dहैश फ़ंक्शन धीमे होते हैं
8.कठिन

इंसर्शन सॉर्ट सॉर्टेड इनपुट पर O(n) में चलता है। क्या यह तुलना-आधारित सॉर्टिंग की Ω(n log n) निचली सीमा का खंडन करता है?

  1. Aनहीं, क्योंकि इंसर्शन सॉर्ट तुलना-आधारित सॉर्ट नहीं है
  2. Bहाँ, इसलिए निचली सीमा ग़लत है
  3. Cहाँ, पर केवल 100 से छोटे ऐरे के लिए
  4. Dनहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं

उत्तर कुंजी

  1. 1. B · जब उसे बहुपदी समय में हल किया जा सके
  2. 2. D · O(n)
  3. 3. A · n आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
  4. 4. D · ऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
  5. 5. C · O(n³)
  6. 6. C · O(n)
  7. 7. B · कई कुंजियाँ एक ही बकेट में टकरा (collide) सकती हैं
  8. 8. D · नहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं

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