Paper - II (vi) — Data structures and Algorithms MCQ — 45 अभ्यास प्रश्न उत्तर सहित

Explanation

दो बच्चों वाले नोड का इनऑर्डर उत्तराधिकारी उसके दाएँ उपवृक्ष की सबसे छोटी कुंजी होता है। परिभाषा से उस नोड का बायाँ बच्चा नहीं हो सकता, क्योंकि बायाँ बच्चा उससे भी छोटी और फिर भी जेड से बड़ी कुंजी रखता। इसलिए उत्तराधिकारी की कुंजी जेड में रखने के बाद वास्तविक रूप से जिस नोड को हटाना है, उसके अधिकतम एक बच्चा होगा। मामला एक सरल जोड़-तोड़ वाली हटाने की क्रिया में बदल जाता है।

Explanation

विरल ग्राफ में किनारे वी² की तुलना में बहुत कम होते हैं, इसलिए आसन्नता मैट्रिक्स अनुपस्थित किनारों पर स्थान बर्बाद करता है। आसन्नता-सूची निरूपण हर शीर्ष के लिए पड़ोसियों की सूची रखता है, अनिर्देशित ग्राफ में थीटा(वी + ई) स्थान लेता है, और किसी शीर्ष के सभी पड़ोसियों को केवल उसी शीर्ष की सूची चलाकर देखने देता है।

Explanation

स्टैक अंतिम-आया-पहले-गया नियम पर चलता है। पुश(४), पुश(७), पुश(१) के बाद पहली पॉप १ हटाती है। पुश(९) से ९ ऊपर आता है और अगली पॉप ९ हटा देती है। बचा हुआ स्टैक नीचे से ऊपर ४, ७ है, इसलिए अंतिम पॉप ७ लौटाती है।

Explanation

प्रतीक-सारणी शब्दकोश-जैसे अमूर्त डेटा प्रकार की तरह होती है: यह बंधन जमा करती है और उन्हें कुंजी से वापस ढूँढ़ती है। क्रम जरूरी न हो तो हैश सारणी सबसे उपयुक्त रहती है, क्योंकि अच्छे फैलाव वाला हैश फलन और टकराव-नियंत्रण खोज, जोड़ने और हटाने को अपेक्षित ओ(१) समय देता है। क्रमबद्ध सरणी में ओ(लॉग एन) खोज मिलती है, पर अद्यतन महंगे होते हैं; स्टैक मनमानी खोज के लिए बहुत सीमित है।

Explanation

आसन्नता मैट्रिक्स दो-आयामी सारणी है, इसलिए धारा (यू, वी) की मौजूदगी एक सूचकांकित देख-लेने से जाँची जा सकती है। साधारण आसन्नता सूची विरल ग्राफ़ में स्थान बचाती है, पर किसी खास धारा को जाँचने के लिए यू के पड़ोसियों में खोज करनी पड़ सकती है। इसलिए सीधे धारा-मौजूदगी परीक्षण में मैट्रिक्स आगे रहता है, जबकि विरल स्थान-उपयोग में सूची सामान्यतः बेहतर रहती है।