Binary Search Tree MCQ Quiz in हिन्दी - Objective Question with Answer for Binary Search Tree - मुफ्त [PDF] डाउनलोड करें
Last updated on Apr 30, 2025
Latest Binary Search Tree MCQ Objective Questions
Binary Search Tree Question 1:
एक पूर्ण विषम (बाएँ दाएँ) बाइनरी सर्च ट्री जिसमे n एलिमेंट हैं उसमे एक एलिमेंट को खोजने की वर्स्ट केस टाइम कॉम्प्लेक्सिटी क्या होगी ?
Answer (Detailed Solution Below)
Binary Search Tree Question 1 Detailed Solution
Key Points
- बाइनरी सर्च ट्री (BST) एक बाइनरी ट्री है जहाँ प्रत्येक नोड का मान उसके बाएँ सबट्री में सभी मानों से अधिक और उसके दाएँ सबट्री में सभी मानों से कम होता है।
- एक संतुलित BST में, खोज के लिए समय जटिलता O(log n) होती है क्योंकि ट्री की ऊँचाई log(n) होती है।
- हालांकि, एक पूरी तरह से विषम (बाएँ या दाएँ) BST में, ट्री अनिवार्य रूप से एक लिंक्ड लिस्ट की तरह व्यवहार करता है।
- इसका अर्थ है कि प्रत्येक नोड का केवल एक बच्चा होता है, और ट्री की ऊँचाई n (नोड्स की संख्या) हो जाती है।
- इसलिए, एक पूरी तरह से विषम BST में एक तत्व की खोज करने की सबसे खराब स्थिति समय जटिलता O(n) है क्योंकि आपको सभी नोड्स को पार करना पड़ सकता है।
Important Points
- एक संतुलित BST में, इंसर्शन, हटाना और सर्च जैसे संचालन की औसत समय जटिलता O(log n) होती है।
- एक पूरी तरह से विषम BST में, ये ऑपरेशन सबसे खराब स्थिति में O(n) तक कम हो जाते हैं।
Additional Information
- AVL ट्री और रेड-ब्लैक ट्री जैसे स्व-संतुलन BST अपनी ऊँचाई को log(n) के करीब बनाए रखते हैं, जिससे कुशल संचालन सुनिश्चित होता है।
- विभिन्न प्रकार के BST की संरचना और गुणों को समझना विभिन्न अनुप्रयोगों में खोज संचालन को अनुकूलित करने के लिए महत्वपूर्ण है।
Binary Search Tree Question 2:
4 अलग-अलग कुंजियों से कितने अलग-अलग द्विआधारी खोज वृक्ष बनाए जा सकते हैं?
Answer (Detailed Solution Below)
Binary Search Tree Question 2 Detailed Solution
सही उत्तर 14 है।
व्याख्या:
n अलग-अलग कुंजियों के साथ बनाए जा सकने वाले अलग-अलग द्विआधारी खोज वृक्ष (BST) की संख्या n-वें केटालन संख्या द्वारा दी जाती है, जिसकी गणना सूत्र का उपयोग करके की जा सकती है:
\(C_n = \frac{1}{n+1} \binom{2n}{n}\)
n = 4 के लिए:
\(C_4 = \frac{1}{4+1} \binom{2 \times 4}{4} = \frac{1}{5} \binom{8}{4}\)
अब, हम \(\binom{8}{4}\) की गणना करते हैं:
\(\binom{8}{4} = \frac{8!}{4!(8-4)!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = \frac{1680}{24} = 70\)
अब, इसे केटालन संख्या सूत्र में रखने पर:
\(C_4 = \frac{1}{5} \times 70 = 14\)
निष्कर्ष:
4 अलग-अलग कुंजियों से बनाए जा सकने वाले अलग-अलग द्वि आधारी खोज वृक्ष की संख्या है: 3) 14
Binary Search Tree Question 3:
द्विआधारी खोज वृक्ष का प्रीऑर्डर पथक्रमन 15, 10, 12, 11, 20, 18, 16, 191 निम्नलिखित में से कौन सा वृक्ष का पोस्टऑर्डर पथक्रमन है?
Answer (Detailed Solution Below)
Binary Search Tree Question 3 Detailed Solution
सही उत्तर 11, 12, 10, 16,19,18,20,15 है।
Key Pointsकिसी द्विआधारी खोज वृक्ष (BST) के पोस्टऑर्डर पथक्रमन को उसके प्रीऑर्डर पथक्रमन से निर्धारित करने के लिए, हमें पहले प्रीऑर्डर पथक्रमन मानों से BST का निर्माण करना होगा।
दिए गए BST का इनऑर्डर पथक्रमन संख्याओं का बढ़ता क्रम होगा अर्थात 10, 11, 12, 15, 16, 18, 19, 20. प्रीऑर्डर और इनऑर्डर पथक्रमन का उपयोग करके BST का निर्माण करने पर, हमें निम्नलिखित वृक्ष प्राप्त होता है:
पोस्टऑर्डर पथक्रमन करें: पोस्टऑर्डर पथक्रमन में, हम पहले बाएं उपवृक्ष पर जाते हैं, फिर दाएं उपवृक्ष पर जाते हैं, और अंत में रूट पर जाते हैं।
पोस्टऑर्डर पथक्रमन में छपे नोड का क्रम है: 11, 12, 10, 16, 19, 18, 20, 15
Binary Search Tree Question 4:
द्विआधारी खोज वृक्ष, कौन सा उपवृक्ष एक नोड में ऐसे तत्व होते हैं जो नोड के मान से अधिक ?
Answer (Detailed Solution Below)
Binary Search Tree Question 4 Detailed Solution
सही उत्तर दायाँ उपवृक्ष है।
Key Points
- एक द्विआधारी खोज वृक्ष (BST) में, प्रत्येक नोड में अधिकतम दो चाइल्ड होते हैं, जिन्हें बाएँ और दाएँ उपवृक्ष के रूप में जाना जाता है।
- किसी दिए गए नोड के बाएँ उपवृक्ष में नोड्स का मान हमेशा दिए गए नोड के मान से कम होता है।
- इसी तरह, किसी दिए गए नोड के दाएँ उपवृक्ष में नोडों का मान हमेशा दिए गए नोड के मान से अधिक होता है।
- इस प्रकार, प्रश्न का सही उत्तर दायाँ उपवृक्ष है।
Additional Information
- विकल्प 1: बायाँ उपवृक्ष - यह गलत है क्योंकि बाएँ उपवृक्ष में ऐसे तत्व होते हैं जो नोड के मान से कम होते हैं।
- विकल्प 3: दोनों उपवृक्ष - यह गलत है क्योंकि केवल दाएँ उपवृक्ष में नोड के मान से अधिक तत्व होते हैं।
Binary Search Tree Question 5:
एक बाइनरी सर्च ट्री T में n विशिष्ट तत्व होते हैं। T में एक तत्व को चुनने की समय जटिलता क्या है जो T में अधिकतम तत्व से छोटा है?
Answer (Detailed Solution Below)
Binary Search Tree Question 5 Detailed Solution
व्याख्या:
- यदि बाइनरी सर्च ट्री में कोई तत्व बाइनरी सर्च ट्री में किसी अन्य तत्व से छोटा है तो यह अधिकतम तत्व से छोटा है।
- बाइनरी सर्च ट्री के सभी तत्व अलग हैं।
- ऐसे तत्वों को खोजने के लिए बाइनरी सर्च ट्री में केवल दो तत्वों की तुलना करें।
- इसलिए समय जटिलता θ(1) है।
Top Binary Search Tree MCQ Objective Questions
द्विआधारी सर्च ट्री का प्रीऑर्डर ट्रैवर्सल क्रम 30, 20, 10, 15, 25, 23, 39, 35, 42 है। निम्नलिखित में से कौन सा उसी ट्री का पोस्टऑर्डर ट्रैवर्सल अनुक्रम है?
Answer (Detailed Solution Below)
Binary Search Tree Question 6 Detailed Solution
Download Solution PDFसही उत्तर " विकल्प 4" है।
अवधारणा:
एक द्विआधारी सर्च ट्री (BST) को ऑर्डर्ड ट्री या सॉर्ट किए गए द्विआधारी ट्री के रूप में भी जाना जाता है।
यह निम्नलिखित गुणों वाला एक द्विआधारी ट्री है:
1. किसी नोड के बाएँ सब-ट्री में केवल ऐसे नोड होते हैं जिनका कुंजी-मान नोड के कुंजी मान से कम होता है।
2. किसी नोड के दाएँ सबट्री में केवल ऐसे नोड होते हैं जिनका कुंजी-मान नोड के कुंजी मान से अधिक होता है।
तीन प्रकार के ट्रैवर्सल हैं:
1. इन-ऑर्डर ट्रैवर्सल: इस ट्रैवर्सल में, पहला बायां नोड ट्रैवर्स होगा, रूट नोड फिर दायां नोड ट्रैवर्स होगा।
2. प्री-ऑर्डर ट्रैवर्सल : इस ट्रैवर्सल में, पहला रूट नोड ट्रैवर्स होगा, बायां नोड फिर दायां नोड ट्रैवर्स होगा।
3. पोस्ट-ऑर्डर ट्रैवर्सल: इस ट्रैवर्सल में, पहला बायां नोड ट्रैवर्स होगा, दायां नोड फिर रूट नोड ट्रैवर्स होगा।
द्विआधारी सर्च ट्री का इन-ऑर्डर ट्रैवर्सल हमेशा प्रमुख मानों को आरोही क्रम में लौटाता है।
व्याख्या:
दिए गए BST का प्री-ऑर्डर ट्रैवर्सल निम्न है:
30, 20, 10, 15, 25, 23, 39, 35, 42.
तो, BST का इन-ऑर्डर ट्रैवर्सल है:
10, 15, 20, 23, 25, 30, 35, 39, 42.
द्विआधारी सर्च ट्री निम्न है:
तो ट्री का पोस्ट-ऑर्डर ट्रैवर्सल निम्न है:
15, 10, 23, 25, 20, 35, 42, 39, 30
इसलिए, सही उत्तर "विकल्प 4" है।
निम्नलिखित में से कौन सा/से बाइनरी सर्च ट्री का सही क्रम में ट्रैवर्सल अनुक्रम है/हैं?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9 18, 20, 25
Answer (Detailed Solution Below)
Binary Search Tree Question 7 Detailed Solution
Download Solution PDFकथन I: 3, 5, 7, 8, 15, 19, 25
यह बाइनरी सर्च ट्री गुण का उल्लंघन नहीं करता है और इसलिए यह ट्रैवर्सल का सही क्रम है।
कथन II: 5, 8, 9, 12, 10, 15, 25
15 में से 12 बचता है जो बाइनरी सर्च ट्री गुण का उल्लंघन करता है।
कथन III: 2, 7, 10, 8, 14, 16, 20
14, 10 में से बचा है जो बाइनरी सर्च ट्री गुण का उल्लंघन करता है।
कथन IV: 4, 6, 7, 9 18, 20, 25
यह बाइनरी सर्च ट्री गुण का उल्लंघन नहीं करता है और इसलिए यह ट्रैवर्सल का सही क्रम है।
एक बायनरी ट्री T का पोस्ट ऑर्डर ट्रेवर्सल क्या होगा, यदि T का प्रीऑर्डर तथा इनऑर्डर ट्रेवर्सल क्रमशः ABCDEF तथा BADCFE हैं?
Answer (Detailed Solution Below)
Binary Search Tree Question 8 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 4 है।
संकल्पना:
दी गयी जानकारी,
पुर्वक्रम = ABCDEF
क्रमबद्ध = BADCFE
| ट्री पथक्रमन | |||
| विधि अनुक्रम | क्रमबद्ध | पुर्वक्रम | पश्चक्रम |
| बायां उप-ट्री | मूल | बायां उप-ट्री | |
| मूल | बायां उप-ट्री | दायां उप-ट्री | |
| दायां उप-ट्री | दायां उप-ट्री Sub-tree | मूल | |
चक्रमण के लिए बाइनरी ट्री निम्न है,
उपरोक्त ट्री के लिए पश्चक्रम निम्न है,
BDFECA
अतः सही उत्तर BDFECA है।
खाली बाइनरी सर्च ट्री में निम्नलिखित संख्याऐं दिए गए क्रम 10, 1, 3, 5, 15, 12, 16 में डाली जाती हैं। बाइनरी सर्च ट्री की ऊंचाई क्या है?
Answer (Detailed Solution Below)
Binary Search Tree Question 9 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 1 है।
संकल्पना:
एक बाइनरी सर्च ट्री (BST) एक नोड-आधारित बाइनरी ट्री डेटा संरचना है और यह निम्नलिखित बिंदुओं का अनुसरण करती है:
- बायां सब-ट्री नोड्स कुंजी मान केवल तभी मौजूद होगा जब मूल नोड कुंजी मान से कम हो।
- दायां सब-ट्री नोड कुंजी मान केवल तभी मौजूद होगा जब मूल नोड कुंजी मान से अधिक हो।
- बायां सब-ट्री और दायां सब-ट्री एक बाइनरी सर्च ट्री होना चाहिए।
स्पष्टीकरण:
चरण 1: पहले 10 आता है और अब वह रूट नोड है।
चरण 2: अब 1 आया और 1 < 10 फिर नोड 10 के बाईं ओर नोड 1 निवेशित करें।
चरण 3: अब 3 आया और 3 < 10 नोड 10 के बाईं ओर जाएं
और 3 > 1 जांचें फिर नोड 1 के दाईं ओर नोड 3 को निवेश करें।
चरण 4: अब 5 आएगा और 5 < 10 नोड 10 के बाईं ओर जाएं
और 5 > 1 जांचें नोड 1 के दाईं ओर जाएं, फिर 5 > 3 चेक करें और फिरको नोड 3 के दाईं ओर नोड 5 को निवेश करें।
चरण 5: अब 15 आएगा और 15 > 10 फिर नोड 10 के दाईं ओर नोड 15 निवेशित करें।
चरण 6: अब 12 आएगा और 12 > 10 नोड 10 के दायीं ओर जाएं और 15 > 12 चेक करें और फिर नोड 15 के बाईं ओर नोड 12 को निवेशित करें।
चरण 7: अब 16 आएगा और 16 > 10 पर 10 की दाई ओर जाऐं और 16 > 15 चेक करें फिर नोड 15 की दाईं ओर 16 निवेशित करें।
चरण 7 के बाद, हम ट्री की ऊंचाई 3 के रूप में गिन सकते हैं।
Important Points
ट्री में सबसे लंबे पथ का अनुसरण करें और कोर की संख्या गिनें जो कि ऊंचाई हैं।
सीखने के लिए युक्तियाँ:
Left sub-tree(key)<Node(key)<Right sub-tree(key)
Node(key): Left sub-tree और Right sub-tree का मूल नोड
निम्नलिखित में से कौन सी एक दिए गए बाइनरी ट्री की ऊंचाई है?
संकेत:
बाइनरी ट्री की ऊंचाई जड़ से सबसे दूर पत्ती के नोड तक किनारों की सबसे बड़ी संख्या के बराबर होती है।
Answer (Detailed Solution Below)
Binary Search Tree Question 10 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 2 है।
संकल्पना:
बाइनरी ट्री:
बाइनरी ट्री एक ऐसा ट्री है जिसमें किसी भी नोड में दो से अधिक संतति नहीं हो सकती हैं। प्रत्येक बाइनरी ट्री में मूल,संतति, भाई-बहन, पत्ते और आंतरिक नोड होते हैं।
बाइनरी ट्री की ऊँचाई:
बाइनरी ट्री की ऊंचाई जड़ से सबसे दूर पत्ती के नोड तक किनारों की सबसे बड़ी संख्या के बराबर होती है।
स्पष्टीकरण:
इस प्रकार सही उत्तर 2 है।
बाइनरी सर्च के लिए लिखा गया प्रोग्राम, अवधि के मध्य बिंदु की गणना mid : = (Low + High)/2 के रूप में करता है। यदि सूची में घटकों की संख्या कम है (लगभग 32,000) तो प्रोग्राम अच्छी तरह से कार्य करता है, लेकिन घटकों की संख्या बड़ी होने पर यह असामान्य रूप से व्यवहार करता है। इससे ____________ के रुप में निष्पादित करके बचा जा सकता है।
Answer (Detailed Solution Below)
Binary Search Tree Question 11 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 1 है।
Key Points
- एक सामान्य परिदृश्य में, बाइनरी सर्च मध्य-मान की गणना, mid=(low+high)/2 के साथ की जाती है।
- हालांकि, घटकों की एक विशाल सूची के साथ, "उच्च" एक बहुत अधिक मान होगा। परिणामस्वरूप, यह संभव है कि यह पूर्णांक सीमा से अधिक हो। इसे पूर्णांक अतिप्रवाह के रूप में जाना जाता है।
- इस पूर्णांक अतिप्रवाह को रोकने के लिए, mid = (High - Low)/2 + Low का उपयोग करके 'मध्य' मान भी निर्धारित किया जा सकता है।
- इस रुप के साथ पूर्णांक अतिप्रवाह कभी कोई समस्या नहीं है।
स्पष्टीकरण
mid : = (High - Low)/2 + Low
mid : = High/2 - Low/2 + low
mid : = (High + Low)/2
Alternate Method
-
विकल्प D हटा दिया गया है क्योंकि यह गलत विकल्प के समान है।
-
ध्यान में रखते हुए निम्न सूचकांक 10 है, जबकि उच्च सूचकांक 15 है।
-
विकल्प B , 3 का मध्य-सूचकांक देता है जो उप-सरणी सूचकांक में भी नहीं है।
-
विकल्प C, 2 का मध्य-सूचकांक देता है जो उप-सरणी सूचकांक में भी नहीं है।
-
विकल्प A सबसे अच्छा हल है।
इस प्रकार सही उत्तर mid : = (High - Low)/2 + Low है।
बाइनरी सर्च ट्री में किसी कीय को इन्सर्ट और डिलीट करने की वर्स्ट केस जटिलताएं क्या है?
Answer (Detailed Solution Below)
Binary Search Tree Question 12 Detailed Solution
Download Solution PDFअवधारणाएं:
ट्री की न्यूनतम ऊंचाई तब होती है जब BST के सभी स्तर पूरी तरह से भर जाते हैं।
बाइनरी सर्च ट्री (BST) की अधिकतम ऊंचाई सबसे वर्स्ट केस है जब नोड्स विषम तरीके से होते हैं।
सूत्र:
n नोड्स के साथ BST की न्यूनतम ऊंचाई ⌈log2 (n + 1)⌉ - 1 है
n नोड्स के साथ BST की अधिकतम ऊंचाई n - 1 है।
अधिकतम ऊंचाई के साथ BST:
इंसर्शन:
BST को अधिकतम ऊंचाई तक ट्रैवर्स करें
इंसर्शन की सबसे सबसे वर्स्ट केस समय जटिलता = θ (n - 1) ≡ θ (n)
डिलीटेशन:
BST को अधिकतम ऊंचाई तक ट्रैवर्स करें
θ (n - 1) की सबसे वर्स्ट केस समय जटिलता = ≡ θ (n)
हम एक खाली बाइनरी सर्च ट्री में संख्या 1, 2, 3, 4, 5 डालकर एक बाइनरी सर्च ट्री B1 बनाते हैं। हम विपरीत क्रम में एक खाली बाइनरी सर्च ट्री में संख्या डालकर एक और बाइनरी सर्च ट्री B2 बनाते हैं। B1 के सबसे-दाएँ तत्व और B2 के सबसे-बाएँ तत्व में क्या अंतर है?
Answer (Detailed Solution Below)
Binary Search Tree Question 13 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 3 है।
संकल्पना:
एक बाइनरी सर्च ट्री, जिसे ऑर्डर या सॉर्ट किए गए बाइनरी ट्री के रूप में भी जाना जाता है, एक रूटेड बाइनरी ट्री डेटा संरचना है जिसमें प्रत्येक आंतरिक नोड एक कुंजी संग्रहीत करता है जो नोड के बाएं उपट्री में सभी कुंजियों से अधिक होती है लेकिन नोड के दाएं उपट्री से कम होती है।
B1 का सबसे दाहिना तत्व = 5
B2 का सबसे बायां तत्व = 1
दोनों B1-B2 के बीच का अंतर =5-1=4
अतः सही उत्तर 4 है।
Answer (Detailed Solution Below)
Binary Search Tree Question 14 Detailed Solution
Download Solution PDFसंकल्पना:
द्विआधारी खोज वृक्ष में
-
प्रत्येक नोड के बाएँ उप-वृक्ष (LST) में केवल ऐसे नोड होने चाहिए जिनका कुंजी मान नोड की कुंजी से कम हो
-
प्रत्येक नोड के दाएँ उप-वृक्ष (RST) में केवल ऐसे नोड होने चाहिए जिनका मुख्य मान नोड की कुंजी से अधिक या बराबर हो
व्याख्या:
सभी नोड्स (मान) डालने के बाद BST वृक्ष
∴ LST = 3 और RST = 5
एक बाइनरी सर्च ट्री T में n विशिष्ट तत्व होते हैं। T में एक तत्व को चुनने की समय जटिलता क्या है जो T में अधिकतम तत्व से छोटा है?
Answer (Detailed Solution Below)
Binary Search Tree Question 15 Detailed Solution
Download Solution PDFव्याख्या:
- यदि बाइनरी सर्च ट्री में कोई तत्व बाइनरी सर्च ट्री में किसी अन्य तत्व से छोटा है तो यह अधिकतम तत्व से छोटा है।
- बाइनरी सर्च ट्री के सभी तत्व अलग हैं।
- ऐसे तत्वों को खोजने के लिए बाइनरी सर्च ट्री में केवल दो तत्वों की तुलना करें।
- इसलिए समय जटिलता θ(1) है।