1.आसान
डायरेक्टेड ग्राफ़ (directed graph) क्या है?
- Aऐसा ग्राफ़ जिसके किनारों की एक शीर्ष से दूसरे शीर्ष की ओर दिशा होती है
- Bऐसा ग्राफ़ जिसमें कोई चक्र (cycle) नहीं
- Cऐसा ग्राफ़ जिसके सभी किनारों के भार हों
- Dऐसा ग्राफ़ जिसमें हर दो भिन्न शीर्षों का युग्म एक किनारे से जुड़ा हो
2.आसान
ऐरे के तत्व मेमोरी में कैसे संग्रहीत होते हैं?
- Aहैश द्वारा चुने यादृच्छिक स्थानों पर
- Bमेमोरी पेजों के ट्री में
- Cबिखरे हुए, पॉइंटरों से जुड़े
- Dएक लगातार (contiguous) ब्लॉक में, एक के बाद एक
3.आसान
अनडायरेक्टेड ग्राफ़ में किसी शीर्ष की डिग्री क्या है?
- Aउससे जुड़े किनारों की संख्या
- Bएडजेसेंसी लिस्ट में उसकी स्थिति
- Cउससे सबसे लंबे पथ की लंबाई
- Dग्राफ़ में शीर्षों की संख्या
4.मध्यम
लिंक्ड लिस्ट में सेंटिनल (डमी) नोड का उद्देश्य क्या है?
- Aलिस्ट को नोडों की एक निश्चित अधिकतम संख्या से आगे बढ़ने से रोकना
- Bतत्वों की संख्या संग्रहीत करना
- Cलिस्ट को सॉर्टेड बनाना
- Dहेड या टेल पर विशेष मामलों को हटाकर कोड को सरल बनाना
5.मध्यम
बाइनरी सर्च ट्री में न्यूनतम कुंजी कैसे खोजते हैं?
- Aरूट से दाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई दायाँ चाइल्ड न रहे
- Bहर लीफ़ पर जाकर उनकी तुलना करें
- Cकेवल रूट को देखें
- Dरूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे
6.मध्यम
बाइनरी हीप में नया तत्व कैसे डाला जाता है?
- Aपूरे हीप को फिर से शुरू से बनाएँ
- Bउसे ऐरे के अंत में रखें और जब तक वह हीप गुण का उल्लंघन करे, ऊपर sift करें
- Cउसे रूट पर रखें और नीचे sift करें
- Dसभी बड़े तत्वों को एक स्थान दाएँ खिसकाकर उसे उसकी सॉर्टेड स्थिति में डालें
7.कठिन
union by rank और path compression के साथ union-find (डिसजॉइंट सेट) संरचना की प्रति ऑपरेशन परिशोधित (amortised) लागत क्या है?
- AO(α(n)), व्युत्क्रम एकरमान फ़ंक्शन, जो व्यवहार में लगभग स्थिर है
- BO(n²)
- CO(n)
- Dठीक O(log n)
8.कठिन
आपको O(k) मेमोरी से n संख्याओं की एक धारा (stream) से k सबसे छोटे मान रखने हैं। कौन-सा तरीका O(n log k) समय में काम करता है?
- Aअंतिम k मानों की FIFO क्यू
- Bसभी n मान रखने वाला मिन-हीप, जिससे अंत में k सबसे छोटे मान निकाले जाते हैं
- Cआकार k का मैक्स-हीप, छोटा मान आने पर उसका रूट बदलते हुए
- Dसभी n मानों का सॉर्टेड ऐरे
उत्तर कुंजी
- 1. A · ऐसा ग्राफ़ जिसके किनारों की एक शीर्ष से दूसरे शीर्ष की ओर दिशा होती है
- 2. D · एक लगातार (contiguous) ब्लॉक में, एक के बाद एक
- 3. A · उससे जुड़े किनारों की संख्या
- 4. D · हेड या टेल पर विशेष मामलों को हटाकर कोड को सरल बनाना
- 5. D · रूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे
- 6. B · उसे ऐरे के अंत में रखें और जब तक वह हीप गुण का उल्लंघन करे, ऊपर sift करें
- 7. A · O(α(n)), व्युत्क्रम एकरमान फ़ंक्शन, जो व्यवहार में लगभग स्थिर है
- 8. C · आकार k का मैक्स-हीप, छोटा मान आने पर उसका रूट बदलते हुए
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।