1.आसान
n तत्वों वाले अनसॉर्टेड ऐरे में लीनियर सर्च (linear search) की टाइम कॉम्प्लेक्सिटी (वर्स्ट केस) क्या है?
- AO(log n)
- BO(n²)
- CO(1)
- DO(n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
बाइनरी सर्च को अपने इनपुट से क्या चाहिए?
- Aऐरे में केवल धनात्मक संख्याएँ होनी चाहिए
- Bऐरे की लंबाई दो की घात होनी चाहिए
- Cऐरे में 1000 से अधिक तत्व नहीं होने चाहिए
- Dऐरे सॉर्टेड होना चाहिए
3.आसान
n बड़ा होने पर इनमें से कौन सबसे धीमा बढ़ता है?
- AO(n log n)
- BO(log n)
- CO(n²)
- DO(n)
4.मध्यम
रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?
- AO(n log n)
- BO(n²)
- CO(2ⁿ)
- DO(n)
5.मध्यम
गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?
- Aहर स्थिति में Bellman–Ford आवश्यक है
- BKruskal का एल्गोरिदम
- Cडेप्थ-फ़र्स्ट सर्च (DFS)
- DDijkstra का एल्गोरिदम
6.मध्यम
बिना वेट वाले ग्राफ़ पर ब्रेड्थ-फ़र्स्ट सर्च (BFS) क्या खोजता है?
- Aमिनिमम स्पैनिंग ट्री
- Bसभी ग्राफ़ों में एक टोपोलॉजिकल क्रम
- Cऋणात्मक एज वेट वाले ग्राफ़ में सबसे छोटे पथ
- Dप्रारंभिक नोड से एज की संख्या के अनुसार सबसे छोटे पथ
7.कठिन
इंसर्शन सॉर्ट सॉर्टेड इनपुट पर O(n) में चलता है। क्या यह तुलना-आधारित सॉर्टिंग की Ω(n log n) निचली सीमा का खंडन करता है?
- Aहाँ, पर केवल 100 से छोटे ऐरे के लिए
- Bनहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं
- Cहाँ, इसलिए निचली सीमा ग़लत है
- Dनहीं, क्योंकि इंसर्शन सॉर्ट तुलना-आधारित सॉर्ट नहीं है
8.कठिन
मास्टर प्रमेय का उपयोग करके T(n) = 8T(n/2) + O(n²) का हल क्या है?
- AΘ(n³)
- BΘ(n² log n)
- CΘ(n²)
- DΘ(n log n)
उत्तर कुंजी
- 1. D · O(n)
- 2. D · ऐरे सॉर्टेड होना चाहिए
- 3. B · O(log n)
- 4. B · O(n²)
- 5. D · Dijkstra का एल्गोरिदम
- 6. D · प्रारंभिक नोड से एज की संख्या के अनुसार सबसे छोटे पथ
- 7. B · नहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं
- 8. A · Θ(n³)
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।