1.आसान
कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?
- ABig Theta
- BLittle omega
- CBig Omega
- DBig O
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?
- AO(log n)
- BO(n)
- CO(n²)
- DO(2n)
3.आसान
मेमोइज़ेशन (memoisation) क्या है?
- Aफ़ंक्शन कॉल के परिणाम संग्रहीत करना ताकि दोहराई गई कॉल का उत्तर मेमोरी से मिले
- Bफ़ंक्शन लौटने के बाद मेमोरी मुक्त करना
- Cरिकर्शन को अपने आप समतुल्य लूप में बदलना ताकि कॉल स्टैक की आवश्यकता न रहे
- Dकोड की हर पंक्ति के आगे टिप्पणियाँ लिखना
4.मध्यम
m और n लंबाई की स्ट्रिंग्स के लॉन्गेस्ट कॉमन सबसीक्वेंस के लिए मानक डायनेमिक प्रोग्रामिंग एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(mn)
- BO(m + n)
- CO(mn log n)
- DO(2m+n)
5.मध्यम
रिकरेंस T(n) = T(n/2) + O(1) का हल क्या है?
- AO(1)
- BO(n log n)
- CO(n)
- DO(log n)
6.मध्यम
गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?
- Aहर स्थिति में Bellman–Ford आवश्यक है
- BDijkstra का एल्गोरिदम
- Cडेप्थ-फ़र्स्ट सर्च (DFS)
- DKruskal का एल्गोरिदम
7.कठिन
क्लास NP की कौन-सी परिभाषा सही है?
- Aसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं
- Bनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
- Cसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
- Dसमस्याएँ जो बहुपदी नहीं हैं
8.कठिन
P और NP के बारे में कौन-सा कथन सही है?
- Aयह सिद्ध हो चुका है कि P ≠ NP
- BNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
- CNP का अर्थ है "not polynomial"
- DP की हर समस्या NP में भी है
उत्तर कुंजी
- 1. D · Big O
- 2. C · O(n²)
- 3. A · फ़ंक्शन कॉल के परिणाम संग्रहीत करना ताकि दोहराई गई कॉल का उत्तर मेमोरी से मिले
- 4. A · O(mn)
- 5. D · O(log n)
- 6. B · Dijkstra का एल्गोरिदम
- 7. B · निर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
- 8. D · P की हर समस्या NP में भी है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।