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

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

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

बड़े n के लिए कौन-सा कॉम्प्लेक्सिटी क्लास सबसे तेज़ी से बढ़ता है?

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

कौन-सा सॉर्टिंग एल्गोरिदम एक पिवट चुनकर ऐरे को छोटे और बड़े तत्वों में विभाजित करता है?

1. Aमर्ज सॉर्ट
2. Bक्विकसॉर्ट (Quicksort)
3. Cबबल सॉर्ट
4. Dइंसर्शन सॉर्ट

सरल रिकर्सिव फ़िबोनाची (fib(n) = fib(n−1) + fib(n−2)) की टाइम कॉम्प्लेक्सिटी क्या है?

1. Aघातांकी (Exponential)
2. Bलघुगणकीय (Logarithmic)
3. Cस्थिर (Constant)
4. Dरैखिक (Linear)

पहुँच योग्य बेस केस के बिना रिकर्सिव फ़ंक्शन के बारे में कौन-सा कथन सही है?

1. Aकंपाइलर हमेशा इसे ऐसे लूप में बदल देता है जो सुरक्षित रूप से समाप्त होता है
2. Bयह अपने आप 0 लौटाता है
3. Cयह O(1) समय में चलता है
4. Dयह तब तक स्वयं को कॉल करता रहता है जब तक कॉल स्टैक ओवरफ़्लो न हो जाए

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

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

यह सिद्ध करने के लिए कि कोई निर्णय समस्या X NP-complete है, कौन-सी दो बातें दिखानी होंगी?

1. AX, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है
2. BX का कोई बहुपदी एल्गोरिदम नहीं है, और X निर्णेय है
3. CX, P की किसी समस्या में रिड्यूस होती है, और X, NP में है
4. DX, P में है, और X, SAT में रिड्यूस होती है

यदि कोई किसी एक NP-complete समस्या के लिए बहुपदी-समय एल्गोरिदम खोज ले, तो क्या निष्कर्ष निकलेगा?

1. Aहॉल्टिंग समस्या निर्णेय हो जाएगी
2. Bकेवल वही एक समस्या P में चली जाएगी
3. CNP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
4. Dसभी घातांकी-समय एल्गोरिदम तुरंत रैखिक समय में चलने लगेंगे