Binary Heap MCQ Quiz in हिन्दी - Objective Question with Answer for Binary Heap - मुफ्त [PDF] डाउनलोड करें
Last updated on Apr 30, 2025
Latest Binary Heap MCQ Objective Questions
Binary Heap Question 1:
एक पूर्ण विषम (बाएँ दाएँ) बाइनरी सर्च ट्री जिसमे n एलिमेंट हैं उसमे एक एलिमेंट को खोजने की वर्स्ट केस टाइम कॉम्प्लेक्सिटी क्या होगी ?
Answer (Detailed Solution Below)
Binary Heap 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 Heap Question 2:
4 अलग-अलग कुंजियों से कितने अलग-अलग द्विआधारी खोज वृक्ष बनाए जा सकते हैं?
Answer (Detailed Solution Below)
Binary Heap 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 Heap Question 3:
द्विआधारी खोज वृक्ष का प्रीऑर्डर पथक्रमन 15, 10, 12, 11, 20, 18, 16, 191 निम्नलिखित में से कौन सा वृक्ष का पोस्टऑर्डर पथक्रमन है?
Answer (Detailed Solution Below)
Binary Heap 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 Heap Question 4:
द्विआधारी खोज वृक्ष, कौन सा उपवृक्ष एक नोड में ऐसे तत्व होते हैं जो नोड के मान से अधिक ?
Answer (Detailed Solution Below)
Binary Heap Question 4 Detailed Solution
सही उत्तर दायाँ उपवृक्ष है।
Key Points
- एक द्विआधारी खोज वृक्ष (BST) में, प्रत्येक नोड में अधिकतम दो चाइल्ड होते हैं, जिन्हें बाएँ और दाएँ उपवृक्ष के रूप में जाना जाता है।
- किसी दिए गए नोड के बाएँ उपवृक्ष में नोड्स का मान हमेशा दिए गए नोड के मान से कम होता है।
- इसी तरह, किसी दिए गए नोड के दाएँ उपवृक्ष में नोडों का मान हमेशा दिए गए नोड के मान से अधिक होता है।
- इस प्रकार, प्रश्न का सही उत्तर दायाँ उपवृक्ष है।
Additional Information
- विकल्प 1: बायाँ उपवृक्ष - यह गलत है क्योंकि बाएँ उपवृक्ष में ऐसे तत्व होते हैं जो नोड के मान से कम होते हैं।
- विकल्प 3: दोनों उपवृक्ष - यह गलत है क्योंकि केवल दाएँ उपवृक्ष में नोड के मान से अधिक तत्व होते हैं।
Binary Heap Question 5:
एक बाइनरी सर्च ट्री T में n विशिष्ट तत्व होते हैं। T में एक तत्व को चुनने की समय जटिलता क्या है जो T में अधिकतम तत्व से छोटा है?
Answer (Detailed Solution Below)
Binary Heap Question 5 Detailed Solution
व्याख्या:
- यदि बाइनरी सर्च ट्री में कोई तत्व बाइनरी सर्च ट्री में किसी अन्य तत्व से छोटा है तो यह अधिकतम तत्व से छोटा है।
- बाइनरी सर्च ट्री के सभी तत्व अलग हैं।
- ऐसे तत्वों को खोजने के लिए बाइनरी सर्च ट्री में केवल दो तत्वों की तुलना करें।
- इसलिए समय जटिलता θ(1) है।
Top Binary Heap MCQ Objective Questions
द्विआधारी सर्च ट्री का प्रीऑर्डर ट्रैवर्सल क्रम 30, 20, 10, 15, 25, 23, 39, 35, 42 है। निम्नलिखित में से कौन सा उसी ट्री का पोस्टऑर्डर ट्रैवर्सल अनुक्रम है?
Answer (Detailed Solution Below)
Binary Heap 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 Heap 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
यह बाइनरी सर्च ट्री गुण का उल्लंघन नहीं करता है और इसलिए यह ट्रैवर्सल का सही क्रम है।
एक n घटक बाइनरी संचय (हीप) की एक सरणी निरुपण पर विचार करें जहां घटकों को सूचकांक 1 से सूचकांक n तक सरणी में संग्रहीत किया जाता है। सरणी के सूचकांक i (i < = n) पर संग्रहीत घटक के लिए, मूल (पेरेंट) का सूचकांक ________ है।
Answer (Detailed Solution Below)
Binary Heap Question 8 Detailed Solution
Download Solution PDFसही उत्तर "विकल्प 3" है।
संकल्पना:
बाइनरी संचय (हीप) एक पूर्ण बाइनरी ट्री है जिसमें संचय गुण होते हैं।
बाइनरी संचय (हीप) या तो अधिकतम संचय (हीप) (रूट मान > सभी प्रमुख मान) या न्यूनतम संचय (हीप) (मूल मान < सभी प्रमुख मान)।
स्पष्टीकरण:
बाइनरी संचय (हीप) घटकों को सूचकांक मान i (i < = n) के साथ एक सरणी का उपयोग करके दर्शाया जा सकता है,
घटक का मूल नोड सूचकांक: floor (i / 2) पर होगा
बायांं शिशु नोड (लेफ्ट चाइल्ड नोड) सूचकांकः 2 * i पर होगा
दायां शिशु नोड (राइट चाइल्ड नोड) सूचकांक: 2 * i + 1 पर होगा
इसलिए,मूल (पेरेंट) का सूचकांक floor (i / 2) है।
एक प्राथमिकता पंक्ति को अधिकतम-संचय(हीप) के रूप में लागू किया जाता है। प्रारंभ में, इसमें 5 घटक होते हैं। संचय का स्तर-क्रम चक्रमण: 10, 8, 5, 3, 2 है। उस क्रम में दो नए घटक 1 और 7 संचय में डाले जाते हैं। घटकों को सम्मिलित करने के बाद संचय का स्तर-क्रम चक्रमण _______________ है।
Answer (Detailed Solution Below)
Binary Heap Question 9 Detailed Solution
Download Solution PDFसंकल्पना:
अधिकतम संचय: मूल नोड मान संतति नोड्स से अधिक होना चाहिए।
जब भी हम संचय में नया घटक डालते हैं, तो हम संचय के अंतिम स्तर पर डालेंगे।
घटक डालने के बाद यदि अधिकतम संचय गुणधर्म का पालन नहीं करता है तो हम अधिकतम संचय प्राप्त होने तक हीपिफाई एल्गोरिदम लागू करेंगे।
स्पष्टीकरण:
प्रारंभिक संचय
1 निवेशित करने के बाद:
7 निवेशित करने के बाद:
यह अधिकतम संचय गुणधर्म का पालन नहीं करता है क्योंकि 7, 5 से अधिक है इसलिए हम नोड 7 पर हीपिफाई एल्गोरिदम लागू करेंगे।
हीपिफाई एल्गोरिदम लागू करने के बाद:
स्तर क्रम: 10, 8, 7, 3, 2, 1, 5
इस प्रकार विकल्प 1 सही उत्तर है।
एक बायनरी ट्री T का पोस्ट ऑर्डर ट्रेवर्सल क्या होगा, यदि T का प्रीऑर्डर तथा इनऑर्डर ट्रेवर्सल क्रमशः ABCDEF तथा BADCFE हैं?
Answer (Detailed Solution Below)
Binary Heap Question 10 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 4 है।
संकल्पना:
दी गयी जानकारी,
पुर्वक्रम = ABCDEF
क्रमबद्ध = BADCFE
| ट्री पथक्रमन | |||
| विधि अनुक्रम | क्रमबद्ध | पुर्वक्रम | पश्चक्रम |
| बायां उप-ट्री | मूल | बायां उप-ट्री | |
| मूल | बायां उप-ट्री | दायां उप-ट्री | |
| दायां उप-ट्री | दायां उप-ट्री Sub-tree | मूल | |
चक्रमण के लिए बाइनरी ट्री निम्न है,
उपरोक्त ट्री के लिए पश्चक्रम निम्न है,
BDFECA
अतः सही उत्तर BDFECA है।
शुरुआत में n तत्वों के साथ AVL-ट्री में n2 तत्वों को सम्मिलित करने की सबसे खराब स्थिति वाली समय जटिलता क्या है?
Answer (Detailed Solution Below)
Binary Heap Question 11 Detailed Solution
Download Solution PDFसंकल्पना:
AVL ट्री एक ऊंचाई संतुलित बाइनरी सर्च ट्री है।
AVL प्रविष्टि में Θ (log n) समय लगता है और n नोड्स वाले AVL ट्री की ऊंचाई लॉग n होती है।
गणना:
दिए गए AVL ट्री में पहले से ही n नोड हैं। अब प्रत्येक क्रमिक सम्मिलन में दो ऑपरेशन शामिल होंगे: Θ(log n) डालने के लिए उपयुक्त स्थान खोजने के लिए और दूसरा Θ(log n) यदि आवश्यक हो तो कोई रोटेशन करने के लिए। तो सबसे खराब स्थिति में, प्रत्येक लगातार प्रविष्टि के लिए 2 log n ऑपरेशन यानी Θ (log n) की आवश्यकता होती है।
इसलिए, n2 सम्मिलन के लिए Θ (n2 log n) की आवश्यकता होगी।
खाली बाइनरी सर्च ट्री में निम्नलिखित संख्याऐं दिए गए क्रम 10, 1, 3, 5, 15, 12, 16 में डाली जाती हैं। बाइनरी सर्च ट्री की ऊंचाई क्या है?
Answer (Detailed Solution Below)
Binary Heap Question 12 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 Heap Question 13 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 2 है।
संकल्पना:
बाइनरी ट्री:
बाइनरी ट्री एक ऐसा ट्री है जिसमें किसी भी नोड में दो से अधिक संतति नहीं हो सकती हैं। प्रत्येक बाइनरी ट्री में मूल,संतति, भाई-बहन, पत्ते और आंतरिक नोड होते हैं।
बाइनरी ट्री की ऊँचाई:
बाइनरी ट्री की ऊंचाई जड़ से सबसे दूर पत्ती के नोड तक किनारों की सबसे बड़ी संख्या के बराबर होती है।
स्पष्टीकरण:
इस प्रकार सही उत्तर 2 है।
बाइनरी सर्च के लिए लिखा गया प्रोग्राम, अवधि के मध्य बिंदु की गणना mid : = (Low + High)/2 के रूप में करता है। यदि सूची में घटकों की संख्या कम है (लगभग 32,000) तो प्रोग्राम अच्छी तरह से कार्य करता है, लेकिन घटकों की संख्या बड़ी होने पर यह असामान्य रूप से व्यवहार करता है। इससे ____________ के रुप में निष्पादित करके बचा जा सकता है।
Answer (Detailed Solution Below)
Binary Heap Question 14 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 Heap Question 15 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)