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

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

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

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

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

1.आसान

log₂ 1024 क्या है?

  1. A10
  2. B32
  3. C512
  4. D12
2.आसान

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

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

किसी एल्गोरिदम का रनिंग टाइम O(n) है। इस वृद्धि को क्या कहते हैं?

  1. Aस्थिर (constant)
  2. Bरैखिक (linear)
  3. Cद्विघाती (quadratic)
  4. Dलघुगणकीय (logarithmic)
4.मध्यम

बिना वेट वाले ग्राफ़ पर ब्रेड्थ-फ़र्स्ट सर्च (BFS) क्या खोजता है?

  1. Aसभी ग्राफ़ों में एक टोपोलॉजिकल क्रम
  2. Bमिनिमम स्पैनिंग ट्री
  3. Cऋणात्मक एज वेट वाले ग्राफ़ में सबसे छोटे पथ
  4. Dप्रारंभिक नोड से एज की संख्या के अनुसार सबसे छोटे पथ
5.मध्यम

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

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

आप n तत्वों का ऐरे एक बार सॉर्ट करते हैं और फिर बाइनरी सर्च से k सदस्यता प्रश्नों के उत्तर देते हैं। कुल लागत क्या है?

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

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

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

सिंगली लिंक्ड लिस्ट पर बाइनरी सर्च O(log n) समय क्यों नहीं देती?

  1. Aबीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है
  2. Bलिंक्ड लिस्ट नोड पर तुलनाएँ धीमी होती हैं
  3. Cलिंक्ड लिस्ट सॉर्ट नहीं की जा सकतीं
  4. Dबाइनरी सर्च को कम से कम दोगुनी मेमोरी चाहिए

उत्तर कुंजी

  1. 1. A · 10
  2. 2. A · n आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
  3. 3. B · रैखिक (linear)
  4. 4. D · प्रारंभिक नोड से एज की संख्या के अनुसार सबसे छोटे पथ
  5. 5. B · O(2ⁿ)
  6. 6. B · O(n log n + k log n)
  7. 7. C · नहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं
  8. 8. A · बीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है

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