MCQ
एल्गोरिदम और डेटा स्ट्रक्चर MCQ - उत्तर सहित अभ्यास प्रश्न
RAS/RPSC तैयारी के लिए एल्गोरिदम और डेटा स्ट्रक्चर के 45 प्रश्न हल करें।
अभ्यास प्रश्न
प्र.1बाइनरी सर्च ट्री में दो बच्चों वाले नोड z को हटाते समय उसकी कुंजी को उसके इनऑर्डर उत्तराधिकारी की कुंजी से बदल दिया जाता है और फिर उस उत्तराधिकारी नोड को हटाया जाता है। कौन-सा गुण दूसरी हटाने की क्रिया को z को सीधे हटाने से सरल बनाता है?
दो बच्चों वाले नोड का इनऑर्डर उत्तराधिकारी उसके दाएँ सबट्री की सबसे छोटी कुंजी होता है। परिभाषा से उस नोड का बायाँ बच्चा नहीं हो सकता, क्योंकि बायाँ बच्चा उससे भी छोटी और फिर भी z से बड़ी कुंजी रखता। इसलिए उत्तराधिकारी की कुंजी z में रखने के बाद वास्तविक रूप से जिस नोड को हटाना है, उसके अधिकतम एक बच्चा होगा। मामला एक सरल जोड़-तोड़ वाली हटाने की क्रिया में बदल जाता है।
प्र.2V शीर्षों और E किनारों वाले अनिर्देशित ग्राफ के लिए विरल ग्राफ में सामान्यतः कौन-सा निरूपण कम स्थान लेता है और फिर भी किसी शीर्ष के सभी पड़ोसियों पर चलना उसकी डिग्री के अनुपातिक समय में कराता है?
विरल ग्राफ में किनारे V² की तुलना में बहुत कम होते हैं, इसलिए आसन्नता मैट्रिक्स अनुपस्थित किनारों पर स्थान बर्बाद करता है। आसन्नता-सूची निरूपण हर शीर्ष के लिए पड़ोसियों की सूची रखता है, अनिर्देशित ग्राफ में Θ(V + E) स्थान लेता है, और किसी शीर्ष के सभी पड़ोसियों को केवल उसी शीर्ष की सूची चलाकर देखने देता है।
प्र.3स्टैक S पर ये क्रियाएँ की जाती हैं: push(4), push(7), push(1), pop(), push(9), pop(), pop()। अंतिम pop क्रिया कौन-सा मान लौटाएगी?
स्टैक अंतिम-आया-पहले-गया नियम पर चलता है। push(4), push(7), push(1) के बाद पहली pop 1 हटाती है। push(9) से 9 ऊपर आता है और अगली pop 9 हटा देती है। बचा हुआ स्टैक नीचे से ऊपर 4, 7 है, इसलिए अंतिम pop 7 लौटाती है।
प्र.4कंपाइलर की प्रतीक-सारणी के लिए शब्दकोश जैसा अमूर्त डेटा प्रकार लागू करना है। इसमें पहचान-नाम के आधार पर जोड़ना, हटाना और खोजना होना चाहिए, और काम में बहुत-सी असफल खोजें भी आती हैं। पहचान-नामों को क्रमबद्ध रखे बिना अपेक्षित स्थिर-समय खोज सबसे अच्छी तरह किससे बनी रहेगी?
प्रतीक-सारणी शब्दकोश-जैसे अमूर्त डेटा प्रकार की तरह होती है: यह बंधन जमा करती है और उन्हें कुंजी से वापस ढूँढ़ती है। क्रम ज़रूरी न हो तो हैश सारणी सबसे उपयुक्त रहती है, क्योंकि अच्छे फैलाव वाला हैश फ़ंक्शन और टकराव-नियंत्रण खोज, जोड़ने और हटाने को अपेक्षित O(1) समय देता है। क्रमबद्ध सरणी में O(log n) खोज मिलती है, पर अद्यतन महंगे होते हैं; स्टैक मनमानी खोज के लिए बहुत सीमित है।
प्र.5V शीर्षों और E धारों वाले अनिर्देशित सरल ग्राफ़ में, 'क्या धारा (u, v) मौजूद है' इस क्रिया के लिए आसन्नता मैट्रिक्स और आसन्नता सूची की सही तुलना कौन-सी है?
आसन्नता मैट्रिक्स दो-आयामी सारणी है, इसलिए धारा (u, v) की मौजूदगी एक सूचकांकित देख-लेने से जाँची जा सकती है। साधारण आसन्नता सूची विरल ग्राफ़ में स्थान बचाती है, पर किसी खास धारा को जाँचने के लिए u के पड़ोसियों में खोज करनी पड़ सकती है। इसलिए सीधे धारा-मौजूदगी परीक्षण में मैट्रिक्स आगे रहता है, जबकि विरल स्थान-उपयोग में सूची सामान्यतः बेहतर रहती है।
आपने 45 में से 5 नमूना प्रश्न देख लिए हैं
एल्गोरिदम और डेटा स्ट्रक्चर पर अनलिमिटेड अभ्यास RAS टेस्ट सीरीज़ + प्रैक्टिस पैक या गेट पास में मिलता है।
और प्रश्न
6m आकार के एरे में मुख और पिछला सूचकांकों से क्यू लागू किया गया है, और खाली तथा भरी अवस्था अलग पहचानने के लिए जानबूझकर एक एरे-स्थान खाली छोड़ा जाता है। क्यू भरा होने की सही शर्त कौन-सी है?
71,024 क्रमबद्ध रिकॉर्ड वाली फाइल ऐरे में रखी है। खोजी जाने वाली कुंजी मौजूद नहीं है। यदि मानक द्विआधारी खोज समावेशी निम्न और उच्च सूचकांकों से लागू की गई है, तो असफलता बताने से पहले अधिकतम कितनी कुंजी-तुलनाएं होंगी?
8एक अनिर्देशित सरल ग्राफ में 10 शीर्ष और 12 किनारे हैं। इस ग्राफ के लिए आसन्नता मैट्रिक्स और आसन्नता सूची निरूपण की कौन-सी तुलना सही है?
9पोस्टफ़िक्स व्यंजक 8 2 3 ^ / 2 3 * + पर विचार कीजिए, जहां ^ पहले ही पोस्टफ़िक्स में बदल चुका है और मूल्यांकन सामान्य स्टैक विधि से किया जाता है। कौन-सा मान निकलेगा?
10n शीर्षों और e धारों वाले सरल अनिर्देशित ग्राफ़ के लिए परीक्षक पूछता है कि जब e, n^2 से बहुत कम हो, तब हर शीर्ष के सभी पड़ोसियों को ठीक एक बार सूचीबद्ध करने के लिए आकार-वृद्धि के लिहाज़ से कौन-सा निरूपण बेहतर है। सबसे सटीक उत्तर कौन-सा है?
11इन्फ़िक्स व्यंजक को पोस्टफ़िक्स में बदलने की शंटिंग-यार्ड शैली में, इनपुट टोकन एक ऑपरेटर op है। सामान्य प्राथमिकता वाले बाएँ-सहचारी ऑपरेटरों के लिए कौन-सा नियम सही है?
12एक अनुक्रम में n अभिलेख रखे गए हैं। काम का बोझ 90% क्रमांक के आधार पर रैंडम एक्सेस, 9% अंत में जोड़ना, और 1% बीच से हटाना है, जबकि स्थान पहले से ज्ञात है। मेमोरी-स्थानीयता महत्त्वपूर्ण है। सामान्यतः कौन-सा निरूपण सबसे उपयुक्त रहेगा?
13रिकॉर्डों के गतिशील क्रम को रखने के लिए सरणी और एकल-लिंक्ड सूची की तुलना में कौन-सा कथन सही है?
14दो कतारों Q1 और Q2 से एक स्टैक बनाया गया है। रचनाकार चाहता है कि पुश O(1) रहे और पॉप सबसे हाल में पुश किया गया तत्व लौटाए। जब Q1 में स्टैक के तत्व सामान्य कतार-क्रम में रखे हों, तो पॉप लागू करने की सही विधि कौन-सी है?
15कंपाइलर की प्रतीक सारणी अलग चेनिंग वाले हैशिंग से बनाई गई है। यदि हैश फलन किसी प्रोग्राम के हर पहचानकर्ता को उसी एक बकेट में भेज दे, तो संग्रहित n पहचानकर्ताओं में से किसी एक को खोजने की सबसे खराब समय-लागत क्या होगी?