Binary Heap MCQ Quiz in हिन्दी - Objective Question with Answer for Binary Heap - मुफ्त [PDF] डाउनलोड करें

The correct answer is Inorder

Key Points

• Inorder Traversal: ✅ Inorder traversal of a Binary Search Tree (BST) visits the nodes in the following sequence: Left subtree → Root → Right subtree. This traversal technique lists the nodes of a BST in ascending order if the BST property is maintained.
• Postorder Traversal: ❌ Postorder traversal visits the nodes in the order: Left subtree → Right subtree → Root. This does not guarantee ascending order in a BST.
• Preorder Traversal: ❌ Preorder traversal visits the nodes in the order: Root → Left subtree → Right subtree. This also does not guarantee ascending order in a BST.
• None of the above: ❌ This is incorrect as Inorder traversal is a valid option for listing nodes in ascending order in a BST.

Additional Information

• A Binary Search Tree (BST) is a binary tree where the left subtree of a node contains only nodes with values less than the node's key, and the right subtree contains only nodes with values greater than the node's key.
• Inorder traversal is particularly useful for BSTs as it produces a sorted sequence of node values.
• Other traversal techniques (preorder, postorder) are used for different purposes, such as tree reconstruction or evaluating expressions represented by trees.

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 की संरचना और गुणों को समझना विभिन्न अनुप्रयोगों में खोज संचालन को अनुकूलित करने के लिए महत्वपूर्ण है।

सही उत्तर 14 है।

व्याख्या:

n अलग-अलग कुंजियों के साथ बनाए जा सकने वाले अलग-अलग द्विआधारी खोज वृक्ष (BST) की संख्या n-वें केटालन संख्या द्वारा दी जाती है, जिसकी गणना सूत्र का उपयोग करके की जा सकती है:

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$

n = 4 के लिए:

$C_4=\frac{1}{4+1}(\genfrac{}{}{0ex}{}{2\times 4}{4})=\frac{1}{5}(\genfrac{}{}{0ex}{}{8}{4})$

अब, हम $(\genfrac{}{}{0ex}{}{8}{4})$ की गणना करते हैं:

$(\genfrac{}{}{0ex}{}{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

सही उत्तर 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

सही उत्तर दायाँ उपवृक्ष है।

Key Points

• एक द्विआधारी खोज वृक्ष (BST) में, प्रत्येक नोड में अधिकतम दो चाइल्ड होते हैं, जिन्हें बाएँ और दाएँ उपवृक्ष के रूप में जाना जाता है।
• किसी दिए गए नोड के बाएँ उपवृक्ष में नोड्स का मान हमेशा दिए गए नोड के मान से कम होता है।
• इसी तरह, किसी दिए गए नोड के दाएँ उपवृक्ष में नोडों का मान हमेशा दिए गए नोड के मान से अधिक होता है।
• इस प्रकार, प्रश्न का सही उत्तर दायाँ उपवृक्ष है।

Additional Information

• विकल्प 1: बायाँ उपवृक्ष - यह गलत है क्योंकि बाएँ उपवृक्ष में ऐसे तत्व होते हैं जो नोड के मान से कम होते हैं।
• विकल्प 3: दोनों उपवृक्ष - यह गलत है क्योंकि केवल दाएँ उपवृक्ष में नोड के मान से अधिक तत्व होते हैं।

सही उत्तर " विकल्प 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

15 में से 12 बचता है जो बाइनरी सर्च ट्री गुण का उल्लंघन करता है।

कथन III: 2, 7, 10, 8, 14, 16, 20

14, 10 में से बचा है जो बाइनरी सर्च ट्री गुण का उल्लंघन करता है।

कथन IV: 4, 6, 7, 9 18, 20, 25

यह बाइनरी सर्च ट्री गुण का उल्लंघन नहीं करता है और इसलिए यह ट्रैवर्सल का सही क्रम है।

सही उत्तर "विकल्प 3" है।

संकल्पना:

बाइनरी संचय (हीप) एक पूर्ण बाइनरी ट्री है जिसमें संचय गुण होते हैं।

बाइनरी संचय (हीप) या तो अधिकतम संचय (हीप) (रूट मान > सभी प्रमुख मान) या न्यूनतम संचय (हीप) (मूल मान < सभी प्रमुख मान)।

स्पष्टीकरण:

बाइनरी संचय (हीप) घटकों को सूचकांक मान i (i < = n) के साथ एक सरणी का उपयोग करके दर्शाया जा सकता है,

घटक का मूल नोड सूचकांक: floor (i / 2) पर होगा 

बायांं शिशु नोड (लेफ्ट चाइल्ड नोड) सूचकांकः 2 * i पर होगा

दायां शिशु नोड (राइट चाइल्ड नोड) सूचकांक: 2 * i + 1 पर होगा

इसलिए,मूल (पेरेंट) का सूचकांक floor (i / 2) है।

सही उत्तर विकल्प 4 है।

संकल्पना:

दी गयी जानकारी,

पुर्वक्रम = ABCDEF

क्रमबद्ध = BADCFE

चक्रमण के लिए बाइनरी ट्री निम्न है,

उपरोक्त ट्री के लिए पश्चक्रम निम्न है,

BDFECA

अतः सही उत्तर BDFECA है।

संकल्पना:

अधिकतम संचय: मूल नोड मान संतति नोड्स से अधिक होना चाहिए।

जब भी हम संचय में नया घटक डालते हैं, तो हम संचय के अंतिम स्तर पर डालेंगे।

घटक डालने के बाद यदि अधिकतम संचय गुणधर्म का पालन नहीं करता है तो हम अधिकतम संचय प्राप्त होने तक हीपिफाई एल्गोरिदम लागू करेंगे।

स्पष्टीकरण:

प्रारंभिक संचय

1 निवेशित करने के बाद:

7 निवेशित करने के बाद:

यह अधिकतम संचय गुणधर्म का पालन नहीं करता है क्योंकि 7, 5 से अधिक है इसलिए हम नोड 7 पर हीपिफाई एल्गोरिदम लागू करेंगे।

हीपिफाई एल्गोरिदम लागू करने के बाद:

स्तर क्रम: 10, 8, 7, 3, 2, 1, 5

इस प्रकार विकल्प 1 सही उत्तर है।

संकल्पना:

AVL ट्री एक ऊंचाई संतुलित बाइनरी सर्च ट्री है।

AVL प्रविष्टि में Θ (log n) समय लगता है और n नोड्स वाले AVL ट्री की ऊंचाई लॉग n होती है।

गणना:

दिए गए AVL ट्री में पहले से ही n नोड हैं। अब प्रत्येक क्रमिक सम्मिलन में दो ऑपरेशन शामिल होंगे: Θ(log n) डालने के लिए उपयुक्त स्थान खोजने के लिए और दूसरा Θ(log n) यदि आवश्यक हो तो कोई रोटेशन करने के लिए। तो सबसे खराब स्थिति में, प्रत्येक लगातार प्रविष्टि के लिए 2 log n ऑपरेशन यानी Θ (log n) की आवश्यकता होती है।

इसलिए, n² सम्मिलन के लिए Θ (n2 log n) की आवश्यकता होगी।

सही उत्तर विकल्प 1 है।

संकल्पना:

एक बाइनरी सर्च ट्री (BST) एक नोड-आधारित बाइनरी ट्री डेटा संरचना है और यह निम्नलिखित बिंदुओं का अनुसरण करती है:

1. बायां सब-ट्री नोड्स कुंजी मान केवल तभी मौजूद होगा जब मूल नोड कुंजी मान से कम हो।
2. दायां सब-ट्री नोड कुंजी मान केवल तभी मौजूद होगा जब मूल नोड कुंजी मान से अधिक हो।
3. बायां सब-ट्री और दायां सब-ट्री एक बाइनरी सर्च ट्री होना चाहिए।
    

स्पष्टीकरण:

चरण 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 का मूल नोड 

सही उत्तर विकल्प 2 है।

संकल्पना:

बाइनरी ट्री:

बाइनरी ट्री एक ऐसा ट्री है जिसमें किसी भी नोड में दो से अधिक संतति नहीं हो सकती हैं। प्रत्येक बाइनरी ट्री में मूल,संतति, भाई-बहन, पत्ते और आंतरिक नोड होते हैं।

बाइनरी ट्री की ऊँचाई:

बाइनरी ट्री की ऊंचाई जड़ से सबसे दूर पत्ती के नोड तक किनारों की सबसे बड़ी संख्या के बराबर होती है।

स्पष्टीकरण:

इस प्रकार सही उत्तर 2 है।

सही उत्तर विकल्प 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 है।

अवधारणाएं:

ट्री की न्यूनतम ऊंचाई तब होती है जब BST के सभी स्तर पूरी तरह से भर जाते हैं।

बाइनरी सर्च ट्री (BST) की अधिकतम ऊंचाई सबसे वर्स्ट केस है जब नोड्स विषम तरीके से होते हैं।

सूत्र:

n नोड्स के साथ BST की न्यूनतम ऊंचाई ⌈log2 (n + 1)⌉ - 1 है

n नोड्स के साथ BST की अधिकतम ऊंचाई n - 1 है।

अधिकतम ऊंचाई के साथ BST:

इंसर्शन:

BST को अधिकतम ऊंचाई तक ट्रैवर्स करें

इंसर्शन की सबसे सबसे वर्स्ट केस समय जटिलता = θ (n - 1) ≡ θ (n)

डिलीटेशन:

BST को अधिकतम ऊंचाई तक ट्रैवर्स करें

θ (n - 1) की सबसे वर्स्ट केस समय जटिलता = ≡ θ (n)