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

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

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

0 से k की सीमा में n पूर्णांकों के लिए काउंटिंग सॉर्ट (counting sort) का रनिंग टाइम क्या है?

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

बाइनरी सर्च को अपने इनपुट से क्या चाहिए?

1. Aऐरे में 1000 से अधिक तत्व नहीं होने चाहिए
2. Bऐरे की लंबाई दो की घात होनी चाहिए
3. Cऐरे सॉर्टेड होना चाहिए
4. Dऐरे में केवल धनात्मक संख्याएँ होनी चाहिए

एक सरल रिकर्सिव फ़ैक्टोरियल फ़ंक्शन fact(n) = n × fact(n − 1) कितना स्टैक स्पेस उपयोग करता है?

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

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

1. Aयादृच्छिक इनपुट पर अपेक्षित लागत
2. Bसबसे अच्छे इनपुट पर एल्गोरिदम की लागत
3. Cपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
4. Dऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत

एक ग्रीडी एल्गोरिदम (greedy algorithm):

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

हॉल्टिंग समस्या (halting problem) क्या दर्शाती है?

1. Aहर प्रोग्राम अंततः रुक जाता है
2. Bलूप से बचना चाहिए
3. Cकोई भी एल्गोरिदम हर प्रोग्राम और इनपुट के लिए यह तय नहीं कर सकता कि वह रुकेगा या नहीं
4. Dकुछ प्रोग्राम तेज़ कंप्यूटरों पर तेज़ चलते हैं, इसलिए रुकना हार्डवेयर पर निर्भर करता है

नैपसैक के किस रूप के लिए ग्रीडी नियम "वस्तुओं को प्रति भार मूल्य के क्रम में लें" हमेशा इष्टतम उत्तर देता है?

1. Aफ़्रैक्शनल नैपसैक, जिसमें वस्तुएँ बाँटी जा सकती हैं
2. B0/1 नैपसैक, जिसमें वस्तुएँ हमेशा पूरी ली जानी चाहिए
3. Cकोई भी रूप नहीं
4. Dदोनों रूप