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

सही उत्तर: 2) एकल वृत्तीय लिंक्ड लिस्ट है।

स्पष्टीकरण:

• एकल वृत्ताकार लिंक्ड सूची में, प्रत्येक नोड का एक आनुक्रमिक होता है, तथा अंतिम नोड का अगला सूचक पहले नोड की ओर संकेत करता है, इस प्रकार यह सुनिश्चित होता है कि प्रत्येक नोड का एक आनुक्रमिक है।

• एकल लिंक्ड सूची में, अंतिम नोड का अगला पॉइंटर शून्य होता है, इसलिए इसका कोई आनुक्रमिक नहीं होता।

• दोहरी लिंक सूची में, नोड्स में आनुक्रमिक और पूर्ववर्ती दोनों होते हैं, लेकिन पुनः, अंतिम नोड का अगला नोड शून्य होता है, इसलिए सभी नोड्स में आनुक्रमिक नहीं होता है।

• इसलिए, एकमात्र सही विकल्प जहां प्रत्येक नोड (अंतिम सहित) का एक आनुक्रमिक होता है:

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

व्याख्या:

दिए गए शब्दों (banana, peach, apple, pear, coconut, mango, और papaya) से वर्णमाला क्रम में निर्मित एक बाइनरी सर्च ट्री (BST) की ऊँचाई निर्धारित करने के लिए, हम BST सम्मिलित नियमों के अनुसार शब्दों को एक-एक करके BST में सम्मिलित करेंगे।

1. "banana" सम्मिलित करें:

(ऊँचाई = 0, क्योंकि यह एकमात्र नोड और रूट है)

2. "peach" सम्मिलित करें:

(ऊँचाई = 1, रूट का दायाँ बच्चा)

3. "apple" सम्मिलित करें:

(ऊँचाई = 1, apple banana का बायाँ बच्चा है)

4. "pear" सम्मिलित करें:

(ऊँचाई = 2, pear peach का दायाँ बच्चा है)

5. "coconut" सम्मिलित करें:

(ऊँचाई = 2, coconut peach का बायाँ बच्चा है)

6. "mango" सम्मिलित करें:

(ऊँचाई = 3, mango coconut का दायाँ बच्चा है)

7. "papaya" सम्मिलित करें:

(ऊँचाई = 4, papaya mango का दायाँ बच्चा है)

इसलिए, परिणामी बाइनरी सर्च ट्री की ऊँचाई 4 है, जो रूट से सबसे गहरे लीफ नोड तक किनारों की संख्या है।

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

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

संकल्पना:

द्विआधारी ट्री:

• द्विआधारी ट्री एक अरेखीय डेटा संरचना है।
• पेड़ के पदानुक्रम के शीर्ष पर स्थित नोड को रूट नोड कहा जाता है।
  अन्य उप-नोड रखने वाले नोड पैत्रक नोड हैं।
• एक ट्री में आमतौर पर एक रूट नोड और उप-ट्री होते हैं जो कि बच्चा नोडों द्वारा उसके मूल नोड से बनते हैं।
• एक द्विआधारी ट्री में, प्रत्येक पैत्रक नोड में अधिकतम दो बच्चे होते हैं जिन्हें बायाँ बच्चा और दायाँ बच्चा कहा जाता है।

B-Tree (B-ट्री):

• B-पेड़ एक बहुस्तरीय पहुंच संरचना प्रदान करते हैं जो एक संतुलित वृक्ष संरचना है जिसमें प्रत्येक नोड कम से कम आधा भरा होता है। क्रम p के B-वृक्ष में प्रत्येक नोड में अधिकतम p-1 खोज मान हो सकते हैं।
• B-ट्री एक द्विआधारी खोज ट्री का सामान्यीकरण है जिसमें एक नोड में दो से अधिक बच्चे हो सकते हैं।
• 
• इसलिए, B-tree एक द्विआधारी ट्री नहीं है।       

Additional Information

Heap (हीप):

• द्विआधारी हीप एक पूर्ण द्विआधारी ट्री है जिसमें हीप गुण होते हैं।
• एक द्विआधारी हीप या तो अधिकतम हीप (रूट मान > सभी प्रमुख मान) या न्यूनतम हीप (मूल मान < सभी प्रमुख मान) है।

AVL Tree (AVL-ट्री):

• AVL ट्री द्विआधारी खोज ट्री (BST) के समान है लेकिन एक अंतर यह है कि बाएँ और दाएँ उप-वृक्षों की ऊँचाई अधिकतम 1 से भिन्न हो सकती है।
• नोड का संतुलन -1, 0, 1 है। इस प्रकार हमने इसे ऊंचाई-संतुलित द्विआधारी खोज ट्री भी कहा।
• संतुलित गुणक (bf) = बाएं उप पेड़ की ऊंचाई (hL) - दाएं उप पेड़ की ऊंचाई (hR)
• संतुलित गुणक (bf) -1, 0, 1 होना चाहिए।
• ऊंचाई को संतुलित करने के लिए AVL ट्री में घूर्णन तकनीक का उपयोग किया जाता है।

Key Points

एक बाइनरी ट्री, ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम दो चाइल्ड नोड होता है।

एक नोड के उपट्री की संख्या को नोड की डिग्री कहा जाता है। बाइनरी ट्री में सभी नोड में डिग्री 0, 1, और 2 हैं।

ट्री की डिग्री ट्री में नोडों की अधिकतम डिग्री है। बाइनरी ट्री डिग्री 2 की होती है। T में डिग्री 2 के नोडों की संख्या "n-1" है। 

अतः सही उत्तर n - 1 है। 

संकल्पना -

बाएं-> रूट-> दाएं के कालक्रम के बाद क्रम में अनुक्रम पाया जा सकता है।

क्रम में ट्रैवर्सल अनुक्रम को खोजने पर, हमें 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 मिलते हैं।

15 के बाद जो तत्व आता है वह उसका परवर्ती होता है। यह देखा जा सकता है कि 15 का परवर्ती 17 है।

व्याख्या -

• एक नोड के क्रम में परवर्ती नोड के सही उपट्री में न्यूनतम तत्व है।
• यहाँ, 15, 17 के दाएँ उपप्रकार में न्यूनतम मान वाला तत्व है। अत: 17, 15 का क्रमागत परवर्ती है।
• इसी तरह, नोड के क्रम में पूर्ववर्ती को खोजने के लिए, बाएं उप-ट्री में अधिकतम मूल्य वाला तत्व उत्तर है। यहाँ, 13, 15 का इन-ऑर्डर पूर्ववर्ती है।

महत्वपूर्ण बिंदु:

ट्रिक्स तभी काम करती है जब ट्री द्विआधारी सर्च ट्री हो।

अवधारणाएं:

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

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

सूत्र:

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

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

गणना:

15 नोड्स के साथ BST की अधिकतम ऊंचाई 15 - 1 = 14

आरेख:

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

आरेख:

अवधारणा:

• इन आर्डर चक्रमण:  Left -> Root -> Right
• प्री आर्डर चक्रमण:  Root -> Left -> Right
• पोस्ट आर्डर चक्रमणl :  Left -> Right -> Root

द्विआधारी ट्री​:

इन आर्डर चक्रमण: A, B, C, D, E, F, G, H, I 

संकल्पना:

एक द्विआधारी ट्री में, एक नोड में अधिकतम दो चिल्ड्रन हो सकते हैं। यदि द्विआधारी ट्री में n नोड हैं, तो द्विआधारी ट्री की अधिकतम ऊंचाई n-1 है।

अधिकतम ऊंचाई वाली ट्री: n = 6

ऊँचाई = 6 – 1 = 5

विकल्प 3: सही:

जब हम बाइनरी ट्री पर इन-ऑर्डर पथक्रमन करते हैं, तो हमें आरोही क्रम सरणी मिलती है।यह ट्री बाइनरी सर्च ट्री है।

यादृच्छिक बाइनरी सर्च ट्री

पोस्ट-ऑर्डर पथक्रमन 23, 18, 27, 25, 10, 60, 80, 70, 30.

इन-ऑर्डर पथक्रमन 10, 18, 23, 25, 27, 30, 60, 70, 80

पूर्वक्रमी पथक्रमन 30, 10, 25, 18, 23, 27, 70, 60 ,80 

बाइनरी सर्च ट्री का इन-ऑर्डर पथक्रमन आरोही क्रम में होता है।

डेटा

इनऑर्डर  BDAECF है

प्रीऑर्डर ABDCEF है

बाइनरी ट्री​

इस प्रकार पोस्ट क्रम DBEFCA है।

सूत्र:

L = I (n - 1) + 1

L =लीफ नोड्स की संख्या

I = आंतरिक नोड की संख्या

n = n - एरी ट्री

गणना:
I = 8

n = 5

L = 8(5 - 1) + 1

L = 32 + 1 = 33

लीफ नोड्स की संख्या = 33

आंतरिक नोड की संख्या = 8

उत्तर: विकल्प 1

स्पष्टीकरण:

कथन 1: प्रक्रिया कॉल का क्रम सक्रियण ट्री के पूर्वक्रमी पथक्रमन (प्रीऑर्डर ट्रैवर्सल) से मेल खाता है।

निम्नलिखित उदाहरण पर विचार करें

Fun( int n )

{

 if( n==0 || n==1) 

  return n;

else {

return Fun(n/2) + Fun(n/2) ;

}

माना कि फलन काॅल Fun(8) के रुप में बनाया गया है। अब प्रतिवर्तन ट्री होगा  

फलन कॉल अनुक्रम होगा (n के संदर्भ में): 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1 (ट्री के पूर्वक्रमी पथक्रमन (प्रीऑर्डर ट्रैवर्सल) के समान है)

फलन रिटर्निंग क्रम होगा : 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8 (ट्री के पश्चक्रर्मी पथक्रमन (पोस्ट-ऑर्डर ट्रैवर्सल) के समान है)

इस प्रकार कथन सही है।

कथन 2:

यह कथन भी सही है।

अवधारणा:

इन-ऑर्डर पथक्रमन विधि में, बाएं सबट्री को पहले देखा जाता है, फिर रूट और फिर दाहिने सबट्री। हर नोड अपने आप में एक सबट्री है।

स्पष्टीकरण:

दिया गया है एक द्विआधारी ट्री:

इसके लिए, हम सबसे पहले रूट के बाएं-सबट्री देखा जाता हैं।

1) यह पहले प्रिंट a करेगा। फिर रूट, +  (a + )

2) इसके बाद यह दाहिने सबट्री पर जाएगा, इसमें फिर से रूट * की बाएं-सबट्री में जाएंगा। यह b को प्रिंट करता है, then *, then d (a + b * d)

3) फिर यह "-" प्रिंट करता है। (a + b * d -)

4) फिर दाहिने सबट्री पर जाएं। पहले प्रिंट e, then /, then f .(e/f)

5) अंतिम आउटपुट होगा: a + b * d -  e/f

संकल्पना:

स्ट्रिक्टली बाइनरी ट्री:

• एक बाइनरी ट्री जिसमें प्रत्येक नोड में या तो दो या शून्य चिल्ड्रन होते हैं, स्ट्रिक्टली बाइनरी ट्री कहलाते हैं।

पूर्ण बाइनरी ट्री:

• एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें प्रत्येक स्तर, संभवतः अंतिम को छोड़कर पूर्ण रूप से भर जाता है और सभी नोड्स यथासंभव छोड़े जाते हैं।

व्याख्या:

ट्री A:

ट्री A में सभी नोड्स में या तो शून्य या दो चिल्ड्रन होते हैं, इसलिए यह स्ट्रिक्टली बाइनरी ट्री है। दूसरा और तीसरा स्तर अधूरा है (यहां रूट नोड को पहले स्तर के रूप में लिया गया है)।

ट्री B:

ट्री B में, एक नोड मौजूद होता है जिसके चिल्ड्रन के रूप में केवल एक नोड होता है, इसलिए यह स्ट्रिक्टली बाइनरी ट्री नहीं है। दूसरा और तीसरा स्तर अधूरा है (यहां रूट नोड को पहले स्तर के रूप में लिया गया है)।

ट्री C:

ट्री C में सभी नोड्स में या तो शून्य या दो चिल्ड्रन होते हैं, इसलिए यह स्ट्रिक्टली बाइनरी ट्री है। ट्री C पूर्ण बाइनरी ट्री है क्योंकि सभी स्तर पूरी तरह से भरे हुए हैं।

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