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

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

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

एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(V + E)
2. BO(E log V)
3. CO(V × E)
4. DO(V²)

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

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

Big O में, जैसे O(log n) में, लघुगणक का आधार सामान्यतः क्यों छोड़ दिया जाता है?

1. Aआधार केवल छोटे n के लिए मायने रखता है
2. Bलघुगणक हमेशा पूर्णांकों में पूर्णांकित किए जाते हैं
3. Cकंप्यूटर विज्ञान में सभी लघुगणकों का आधार 10 होता है, इसलिए वह निहित है
4. Dभिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं

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

1. AO(2ⁿ)
2. BO(n²)
3. CO(log n)
4. DO(n)

गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?

1. AKruskal का एल्गोरिदम
2. BDijkstra का एल्गोरिदम
3. Cडेप्थ-फ़र्स्ट सर्च (DFS)
4. Dहर स्थिति में Bellman–Ford आवश्यक है

बड़े n के लिए n! और 2ⁿ की तुलना कैसी है?

1. Aदोनों एक ही दर से बढ़ते हैं
2. B2ⁿ, n! से तेज़ बढ़ता है
3. Cn!, 2ⁿ से तेज़ बढ़ता है
4. Dn!, O(n²) है

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

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