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

Last updated on Jun 10, 2025

पाईये Sorting उत्तर और विस्तृत समाधान के साथ MCQ प्रश्न। इन्हें मुफ्त में डाउनलोड करें Sorting MCQ क्विज़ Pdf और अपनी आगामी परीक्षाओं जैसे बैंकिंग, SSC, रेलवे, UPSC, State PSC की तैयारी करें।

Latest Sorting MCQ Objective Questions

Sorting Question 1:

मर्ज सॉर्ट एल्गोरिथम और बाइनरी सर्च एल्गोरिथम की काल जटिलता क्रमशः __________ हैं।

  1. O(log2 n) और O(n log2 n)
  2. O(n log2 n) और O(log2 n)
  3. O(n2) और O(log2 n)
  4. O(2n) और O(n2)
  5. उपर्युक्त में से कोई नहीं

Answer (Detailed Solution Below)

Option 2 : O(n log2 n) और O(log2 n)

Sorting Question 1 Detailed Solution

मर्ज सॉर्ट​ 

यह डिवाइड और कान्क्वर के दृष्टिकोण पर आधारित है।

मर्ज सॉर्ट के लिए पुनरावर्ती संबंध निम्न बन जाएगा:

T(n) = 2T (n/2) + Θ (n)

मास्टर प्रमेय का उपयोग करके

T (n) = n × log2n

इस प्रकार, मर्ज सॉर्ट की काल जटिलता θ(nlogn) है।

बाइनरी सर्च​

सर्च अंतराल को बार-बार आधे में विभाजित करके क्रमबद्ध सरणी खोजें।

बाइनरी सर्च के लिए पुनरावर्ती T(n) = T(n/2) + θ(1)

मास्टर प्रमेय का उपयोग करके

T (n) = log2n

इनपुट सूची के केवल आधे हिस्से पर विचार करें और दूसरे आधे को हटा दें। इसलिए काल जटिलता O(log n) है।

Sorting Question 2:

निम्नलिखित में से किस एल्गोरिथम डिज़ाइन तकनीक का उपयोग त्वरित लघु एल्गोरिथम को डिज़ाइन करने में किया जाता है?

  1. गतिशील प्रोग्रामिंग विधि
  2. पश्च ट्रैकिंग रणनीति
  3. डिवाइड-एंड-कॉन्कर रणनीति
  4. ग्रीडी रणनीति
  5. उपर्युक्त में से कोई नहीं

Answer (Detailed Solution Below)

Option 3 : डिवाइड-एंड-कॉन्कर रणनीति

Sorting Question 2 Detailed Solution

प्रमुख बिंदु
  • क्विकसॉर्ट एक डिवाइड-एंड- कॉनकॉर एल्गोरिथम है जिसमें पिवट तत्व चुना जाता है, और इस पिवट तत्व ने दी गई समस्या को दो छोटे सेटों में कम कर दिया है।
  • त्वरित सॉर्ट सरणियों को छाँटने के लिए उपयोगी है।
  • अदक्ष कार्यान्वयन त्वरित सॉर्ट एक स्थिर प्रकार नहीं है, जिसका अर्थ है कि समान प्रकार की वस्तुओं का सापेक्ष क्रम संरक्षित नहीं है।
  • त्वरित सॉर्ट की समग्र समय जटिलता O(nLogn) है। सबसे खराब स्थिति में, यह O(n2) तुलना करता है, हालांकि यह व्यवहार दुर्लभ है।
  • त्वरित सॉर्ट की अंतरिक्ष जटिलता O(nLogn) है। यह एक इन-प्लेस सॉर्ट है (यानी इसे किसी अतिरिक्त संग्रहण की आवश्यकता नहीं है)।

इसलिए सही उत्तर डिवाइड-एंड-कॉन्कर रणनीति है

Sorting Question 3:

निम्नलिखित में से कौन सी तुलनात्मक छंटाई नहीं है?

  1. अंतर्वेशन छंटाई
  2. बुलबुली छंटाई
  3. बकेट छंटाई
  4. उपर्युक्त में से एक से अधिक
  5. उपर्युक्त में से कोई नहीं

Answer (Detailed Solution Below)

Option 3 : बकेट छंटाई

Sorting Question 3 Detailed Solution

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

Sorting Question 4:

k-Means एल्गोरिथ्म एक _______ एल्गोरिथ्म है।

  1. सुपरवाइज्ड लर्निंग
  2. अनसुपरवाइज्ड लर्निंग
  3. सेमी-सुपरवाइज्ड लर्निंग
  4. रिइंफोर्समेंट लर्निंग
  5. इनमे से कोई भी नहीं

Answer (Detailed Solution Below)

Option 2 : अनसुपरवाइज्ड लर्निंग

Sorting Question 4 Detailed Solution

सही उत्तर अनसुपरवाइज्ड लर्निंग है।

Key Points 

1. पर्यवेक्षित शिक्षण:

  • पर्यवेक्षित शिक्षण में, एल्गोरिदम को एक लेबल वाले डेटासेट पर प्रशिक्षित किया जाता है, जहां इनपुट डेटा को संबंधित आउटपुट लेबल के साथ जोड़ा जाता है।
  • लक्ष्य इनपुट से आउटपुट तक मैपिंग फ़ंक्शन को सीखना है ताकि एल्गोरिदम नए, अनदेखे डेटा पर भविष्यवाणियां या वर्गीकरण कर सके।

2. बिना पर्यवेक्षण के सीखना:

  • बिना पर्यवेक्षित शिक्षण में, एल्गोरिदम को बिना किसी स्पष्ट निर्देश के डेटा दिया जाता है कि इसके साथ क्या करना है।
  • एल्गोरिदम स्वयं डेटा के भीतर पैटर्न, संबंध या संरचना ढूंढने का प्रयास करता है।
  • क्लस्टरिंग एल्गोरिदम, जैसे के-मीन्स, बिना पर्यवेक्षित शिक्षण के अंतर्गत आते हैं क्योंकि वे लेबल किए गए आउटपुट जानकारी का उपयोग किए बिना समान डेटा बिंदुओं को एक साथ समूहित करते हैं।

3. अर्ध-पर्यवेक्षित शिक्षण:

  • अर्ध-पर्यवेक्षित शिक्षण पर्यवेक्षित और गैर-पर्यवेक्षित शिक्षण का एक संयोजन है।
  • इसमें एक डेटासेट शामिल होता है जिसमें लेबल किए गए और बिना लेबल वाले दोनों उदाहरण होते हैं।
  • एल्गोरिदम को लेबल किए गए डेटा पर प्रशिक्षित किया जाता है, और फिर यह लेबल किए गए डेटा से सीखे गए पैटर्न का लाभ उठाकर गैर-लेबल वाले डेटा पर भविष्यवाणियां करने का प्रयास करता है।

4. सुदृढीकरण सीखना:

  • सुदृढीकरण सीखने में एक एजेंट पर्यावरण के साथ बातचीत करता है और पुरस्कार या दंड के रूप में प्रतिक्रिया प्राप्त करके निर्णय लेना सीखता है।
  • एजेंट ऐसे कार्य करना सीखता है जो समय के साथ संचयी इनाम को अधिकतम करते हैं।
  • पर्यवेक्षित शिक्षण के विपरीत, जहां एल्गोरिदम को स्पष्ट लेबल वाले उदाहरण प्रदान किए जाते हैं, सुदृढीकरण सीखने में, एल्गोरिदम परीक्षण और त्रुटि से सीखता है।

के-मीन्स एल्गोरिदम के मामले में, यह बिना पर्यवेक्षित शिक्षण है क्योंकि यह लेबल किए गए आउटपुट डेटा पर निर्भर नहीं करता है। इसके बजाय, इसका लक्ष्य पूर्वनिर्धारित वर्ग लेबल का उपयोग किए बिना, समानता के आधार पर इनपुट डेटा को क्लस्टर में विभाजित करना है।

Sorting Question 5:

n तत्वों वाली सूची को सॉर्ट करने के लिए सेलेक्शेन सॉर्ट _________ संख्या में सूची में अदला बदली करता है।

  1. n2
  2. 1
  3. n - 1
  4. n + 1

Answer (Detailed Solution Below)

Option 3 : n - 1

Sorting Question 5 Detailed Solution

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

Key Points

  • चयन क्रम एक इन-प्लेस तुलना क्रम एल्गोरिथम है जो इनपुट सूची को दो भागों में विभाजित करता है: आइटमों की एक क्रमबद्ध उपसूची जो बाएँ से दाएँ बनती है और शुरू में खाली होती है, और शेष असंक्रमित मदों की एक उपसूची जो सूची के बाकी हिस्से पर कब्जा कर लेती है।
    • एल्गोरिथम असंक्रमित उपसूची में सबसे छोटे (या सबसे बड़े, सॉर्टिंग क्रम के आधार पर) तत्व को ढूंढकर आगे बढ़ता है, इसे सबसे बाएँ असंक्रमित तत्व के साथ बदलता (स्वैप करता) है (इसे क्रमबद्ध क्रम में रखता है), और उपसूची सीमाओं को एक तत्व दाईं ओर ले जाता है।
    • n तत्वों की सूची को क्रमबद्ध करने के लिए, चयन क्रम सूची के माध्यम से n - 1 पास करता है। ऐसा इसलिए है क्योंकि, प्रत्येक पास में, यह एक तत्व को अपनी सही स्थिति में रखता है, और n - 1 पास के बाद, शेष तत्व पहले से ही अपनी सही स्थिति में है।
    • प्रत्येक पास के दौरान, एल्गोरिथम असंक्रमित उपसूची से सबसे छोटे (या सबसे बड़े) तत्व का चयन करता है और इसे सबसे बाएँ असंक्रमित तत्व के साथ स्वैप करता है, प्रभावी रूप से क्रमबद्ध उपसूची को एक तत्व से बढ़ाता है।

Additional Information

  • चयन क्रम में प्रविष्‍ट पाशों के कारण O(n^2) की समय जटिलता होती है: एक पास के लिए और दूसरा न्यूनतम तत्व खोजने के लिए।
  • हालाँकि यह बड़ी सूचियों के लिए सबसे कुशल क्रमबद्ध एल्गोरिथम नहीं है, यह छोटी सूचियों पर अच्छा प्रदर्शन करता है और इसे समझने और लागू करने में आसान होने का लाभ है।
  • चयन क्रम एक स्थिर क्रम नहीं है, जिसका अर्थ है कि यह समान तत्वों के सापेक्ष क्रम को संरक्षित नहीं करता है।
  • यह एक इन-प्लेस क्रमबद्ध एल्गोरिथम है, जिसके लिए केवल अतिरिक्त मेमोरी स्थान की एक निरंतर मात्रा की आवश्यकता होती है।

Top Sorting MCQ Objective Questions

k-Means एल्गोरिथ्म एक _______ एल्गोरिथ्म है।

  1. सुपरवाइज्ड लर्निंग
  2. अनसुपरवाइज्ड लर्निंग
  3. सेमी-सुपरवाइज्ड लर्निंग
  4. रिइंफोर्समेंट लर्निंग

Answer (Detailed Solution Below)

Option 2 : अनसुपरवाइज्ड लर्निंग

Sorting Question 6 Detailed Solution

Download Solution PDF

सही उत्तर अनसुपरवाइज्ड लर्निंग है।

Key Points 

1. पर्यवेक्षित शिक्षण:

  • पर्यवेक्षित शिक्षण में, एल्गोरिदम को एक लेबल वाले डेटासेट पर प्रशिक्षित किया जाता है, जहां इनपुट डेटा को संबंधित आउटपुट लेबल के साथ जोड़ा जाता है।
  • लक्ष्य इनपुट से आउटपुट तक मैपिंग फ़ंक्शन को सीखना है ताकि एल्गोरिदम नए, अनदेखे डेटा पर भविष्यवाणियां या वर्गीकरण कर सके।

2. बिना पर्यवेक्षण के सीखना:

  • बिना पर्यवेक्षित शिक्षण में, एल्गोरिदम को बिना किसी स्पष्ट निर्देश के डेटा दिया जाता है कि इसके साथ क्या करना है।
  • एल्गोरिदम स्वयं डेटा के भीतर पैटर्न, संबंध या संरचना ढूंढने का प्रयास करता है।
  • क्लस्टरिंग एल्गोरिदम, जैसे के-मीन्स, बिना पर्यवेक्षित शिक्षण के अंतर्गत आते हैं क्योंकि वे लेबल किए गए आउटपुट जानकारी का उपयोग किए बिना समान डेटा बिंदुओं को एक साथ समूहित करते हैं।

3. अर्ध-पर्यवेक्षित शिक्षण:

  • अर्ध-पर्यवेक्षित शिक्षण पर्यवेक्षित और गैर-पर्यवेक्षित शिक्षण का एक संयोजन है।
  • इसमें एक डेटासेट शामिल होता है जिसमें लेबल किए गए और बिना लेबल वाले दोनों उदाहरण होते हैं।
  • एल्गोरिदम को लेबल किए गए डेटा पर प्रशिक्षित किया जाता है, और फिर यह लेबल किए गए डेटा से सीखे गए पैटर्न का लाभ उठाकर गैर-लेबल वाले डेटा पर भविष्यवाणियां करने का प्रयास करता है।

4. सुदृढीकरण सीखना:

  • सुदृढीकरण सीखने में एक एजेंट पर्यावरण के साथ बातचीत करता है और पुरस्कार या दंड के रूप में प्रतिक्रिया प्राप्त करके निर्णय लेना सीखता है।
  • एजेंट ऐसे कार्य करना सीखता है जो समय के साथ संचयी इनाम को अधिकतम करते हैं।
  • पर्यवेक्षित शिक्षण के विपरीत, जहां एल्गोरिदम को स्पष्ट लेबल वाले उदाहरण प्रदान किए जाते हैं, सुदृढीकरण सीखने में, एल्गोरिदम परीक्षण और त्रुटि से सीखता है।

के-मीन्स एल्गोरिदम के मामले में, यह बिना पर्यवेक्षित शिक्षण है क्योंकि यह लेबल किए गए आउटपुट डेटा पर निर्भर नहीं करता है। इसके बजाय, इसका लक्ष्य पूर्वनिर्धारित वर्ग लेबल का उपयोग किए बिना, समानता के आधार पर इनपुट डेटा को क्लस्टर में विभाजित करना है।

सरणी A = <4, 1, 3, 2, 16, 9, 10, 14, 8, 7> पर विचार करें। सरणी A से हीप बनाने के बाद, हीप की गहराई और मैक्स-हीप का राइट चाइल्ड क्रमशः _______ और _____ हैं। (रूट स्तर 0 पर है)।

  1. 3, 14 
  2. 3, 10
  3. 4, 14
  4. 4, 10

Answer (Detailed Solution Below)

Option 2 : 3, 10

Sorting Question 7 Detailed Solution

Download Solution PDF

संकल्पना:

मैक्स-हीप: मैक्स-हीप में, रूट नोड हमेशा ट्री के अन्य नोड से बड़ा या बराबर होता है।

व्याख्या:

A = <4, 1, 3, 2, 16, 9, 10, 14, 8, 7> है।

चरण 1

F2 R.S Madhu 13.04.20 D1

अब, चूंकि 2 1 से बड़ा है, इसलिए नोड की पुनर्व्यवस्था की आवश्यकता है।

चरण 2:

F2 R.S Madhu 13.04.20 D2

फिर से 16 को 2 के साथ एक्सचेंज करें। मैक्स-हीप के गुण के अनुसार शेष नोड इन्सर्ट करें।

चरण 3:

F2 R.S Madhu 13.04.20 D3

चरण 4:

F2 R.S Madhu 13.04.20 D4

चरण 5:

इस तरह से सभी नोड इन्सर्ट करने के बाद, अंतिम मैक्स - हीप है:

F2 R.S Madhu 13.04.20 D5

जैसे, रूट 0 के स्तर पर है, इसलिए, इस मैक्स - हीप में कुल 3 स्तर हैं। साथ ही, रूट नोड का राइट चाइल्ड 10 है।

बबल सॉर्ट का उपयोग करते हुए आरोही क्रम में संख्या 8, 22, 7, 9, 31, 5, 13 को क्रमबद्ध करने के लिए आवश्यक अदला-बदली (स्वैप) की संख्या क्या है?

  1. 11
  2. 12
  3. 13
  4. 10

Answer (Detailed Solution Below)

Option 4 : 10

Sorting Question 8 Detailed Solution

Download Solution PDF

बबल सॉर्ट बार-बार वर्गीकृत करने के लिए सूची के माध्यम से जाता है, आसन्न वस्तुओं की प्रत्येक जोड़ी की तुलना करता है और यदि वे गलत क्रम में हैं तो उन्हें बदल देता है। सूची के माध्यम से पास तब तक दोहराया जाता है जब तक कि कोई अदला बदली की आवश्यकता न हो, जो इंगित करता है कि सूची को क्रमबद्ध किया गया है।

सरणी घटक: 8, 22, 7, 9, 31, 5, 13

1st पास= 8, 7, 9, 22, 5, 13, 31

4 अदला बदली (स्वैप्स)

2nd पास= 7, 8, 9, 5, 13, 22, 31

3 अदला बदली (स्वैप्स)

3rd पास= 7, 8, 5, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

4th पास= 7, 5, 8, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

5th पास= 5, 7, 8, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

चूँकि सरणी को पाँचवे पास के बाद वर्गीकृत किया जाता है

∴ आगे कोई अदला-बदली संभव नहीं है

अदला-बदली की कुल संख्या = 4 + 3 + 1 + 1 + 1 = 10 

 क्विक सॉर्ट एल्गोरिथ्म में उपयोग की गई एल्गोरिथ्म डिजाइन तकनीक ___________ है।

  1. गतिक क्रमादेशन(डायनामिक प्रोग्रामिंग)
  2. बैकट्रेकिंग
  3. डिवाइड एण्ड कान्क्वर
  4. ग्रीडी विधि
  5. उपरोक्त सभी

Answer (Detailed Solution Below)

Option 3 : डिवाइड एण्ड कान्क्वर

Sorting Question 9 Detailed Solution

Download Solution PDF

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

Key Points

  • क्विकसाॅर्ट एक कुशल वर्गीकरण एल्गोरिथ्म है जिसे विभाजन-विनिमय सॉर्ट के रूप में भी जाना जाता है।
  • क्विकसाॅर्ट एक तुलनात्मक साॅर्ट है, जिसका अर्थ है कि यह किसी भी प्रकार की वस्तुओं को सॉर्ट कर सकता है जिसके लिए "less-than" संबंध परिभाषित किया जाता है।
  • क्विकसाॅर्ट एक डिवाइड एण्ड कान्क्वर एल्गोरिथ्म है जिसमें पिवट घटक को चुना जाता है, और यह पिवट घटक दी गई समस्या को दो छोटे सेट में कम कर देता है।
  • कुशल कार्यान्वयन में, यह एक स्थिर साॅर्ट नहीं है, जिसका अर्थ है कि समान साॅर्ट वस्तुओं का सापेक्ष क्रम संरक्षित नहीं होता है।
  • क्विकसाॅर्ट एक सरणी पर  in-place को संचालित कर सकता है, जिससे छँटाई करने के लिए छोटी अतिरिक्त मात्रा में मेमोरी की आवश्यकता होती है।

Additional Information

क्विकसाॅर्ट :

क्विकसाॅर्ट में, निकृष्ठ प्रकरण में Θ (n2) समय लगता है। क्विकसाॅर्ट का निकृष्ठ प्रकरण तब होता है जब पहला या आखिरी घटक पिवट घटक के रूप में चुना जाता है।

आरेख

F2 R.S Madhu 17.12.19 D1

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

यह Θ (n2) समय जटिलता देता है।

क्विकसाॅर्ट एल्गोरिथ्म के लिए पुनरावृत्ति संबंध निम्न होगा

T (n) = T (n-1) + Θ (n)

यह निकृष्ठ प्रकरण समय जटिलता  Θ (n2) के रुप में देता है।

निम्नलिखित एल्गोरिथ्म में से कौन पूर्णांक की एक सरणी की सॉर्टिंग के लिए पुनरावृत्ति का उपयोग करता है?

  1. बबल सॉर्ट और इंसर्शन सॉर्ट
  2. बबल सॉर्ट और क्विक सॉर्ट
  3. बबल सॉर्ट और मर्ज सॉर्ट
  4. क्विकॉर्ट और मर्ज सॉर्ट

Answer (Detailed Solution Below)

Option 4 : क्विकॉर्ट और मर्ज सॉर्ट

Sorting Question 10 Detailed Solution

Download Solution PDF
  •  क्विक सॉर्ट और मर्ज सॉर्ट एल्गोरिथ्म डिवाइड और कॉन्कर एल्गोरिथ्म पर आधारित हैं जो पुनरावर्ती तरीके से काम करता है।
  • पुनरावृत्ति का उपयोग क्विक सॉर्ट और मर्ज सॉर्ट में किया जाता है।
  • क्विक सॉर्ट और मर्ज सॉर्ट में, बड़ी समस्या को छोटी समस्या में विभाजित किया जाता है फिर बाद में छोटी समस्या को हल करने के बाद हम सभी छोटे समाधानों को अंतिम समाधान में संयोजित करने करते हैं।


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

निम्नलिखित सरणी (ऐरे) पर विचार करें।

23

32

45

69

72

73

89

97


निम्नलिखित विकल्पों में से कौन सा एल्गोरिदम आरोही क्रम में उपरोक्त सरणी को क्रमबद्ध करने के लिए (सरणी घटकों के बीच) तुलनाओं की न्यूनतम संख्या का उपयोग करती है?

  1. इंसर्शन सॉर्ट
  2. सेलेक्शन सॉर्ट
  3. पिवट के रूप में अंतिम घटक का उपयोग करके क्विकसॉर्ट
  4. मर्ज सॉर्ट

Answer (Detailed Solution Below)

Option 1 : इंसर्शन सॉर्ट

Sorting Question 11 Detailed Solution

Download Solution PDF

इंसर्शन सॉर्ट​:

इंसर्शन सॉर्ट में, सर्वश्रेष्ठ मामले में Θ (n) समय लगता है, इंसर्शन सॉर्ट का सर्वश्रेष्ठ मामला तब होता है जब घटकों को आरोही क्रम में सॉर्टेड किया जाता है। उस स्थिति में, तुलनाओं की संख्या n - 1 = 8 - 1 = 7 होगी

उपरोक्त सरणी को आरोही क्रम में क्रमबद्ध करने के लिए यह तुलना की न्यूनतम संख्या (सरणी घटकों के बीच) है:

आवश्यक स्वैप की संख्या शून्य है।

Additional Information

इंसर्शन सॉर्ट में, सबसे खराब मामले में Θ (n2) समय लगता है, इंसर्शन सॉर्ट का सबसे खराब मामला तब होता है जब घटकों को विपरीत क्रम में सॉर्टेड किया जाता है। उस स्थिति में, तुलनाओं की संख्या निम्न होगीः

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

यह Θ (n2) समय जटिलता देगा।

एक पूर्ण बाइनरी ट्री पर विचार करें जहाँ रूट के बाएँ और दाएँ उपट्री अधिकतम-हीप हैं। ट्री को हीप में बदलने के लिए संचालन की संख्या के लिए निचली सीमा क्या है?

  1. Ω (log n)
  2. Ω (n)
  3. Ω (n log n)
  4. Ω (n2)

Answer (Detailed Solution Below)

Option 1 : Ω (log n)

Sorting Question 12 Detailed Solution

Download Solution PDF

पूर्ण बाइनरी ट्री पर विचार करें जहाँ रूट के बाएँ और दाएँ उपट्री नीचे दिए गए अधिकतम-हीप हैं

F1 R.S Madhu 10.01.20 D 8

ट्री को हीप में बदलने के लिए जो रूट पर MAX-HEAPIFY को कॉल करना संभव होता है। MAX- HEAPIFY ऑपरेशन में ट्री की ऊंचाई के रूप में समय लगता है। यानी अगर हमारे पास ट्री में n तत्व हैं तो log(n) ट्री की ऊंचाई है।

चरण 1: स्वैप 10 और 40

F1 R.S Madhu 10.01.20 D 11

चरण 2: स्वैप 10 और 25

F1 R.S Madhu 10.01.20 D 9

उपरोक्त ट्री एक MAX-HEAP है

इसे अधिकतम हीप में बदलने के लिए केवल 2 स्वैप और 2  होती है जो कि ट्री की ऊंचाई के अलावा और कुछ नहीं है। तो, ट्री को हीप में बदलने के लिए log(n)  समय की आवश्यकता होती है।

माना H प्राथमिक मिन-हीप है जिसमें n तत्वों को एक सरणी के रूप में लागू किया गया हो। H में अधिकतम तत्व प्राप्त करने के लिए इष्टतम एल्गोरिदम की सबसे खराब स्थिति समय जटिलता क्या है?

  1. θ(log n)
  2. θ(n)
  3. θ(1)

  4. θ(n log n)

Answer (Detailed Solution Below)

Option 2 : θ(n)

Sorting Question 13 Detailed Solution

Download Solution PDF

Key Points

  • मिन-हीप एक पूर्ण बाइनरी ट्री डेटा संरचना है जिसमें पैरेंट नोड का मान उसके चिल्ड्रेन नोड से छोटा होता है।
  • मिन-हीप में, लीफ नोड या अंतिम स्तर में सरणी के अधिकतम मान होते हैं।

व्याख्या:

यदि हम पाशविक बल तकनीक का उपयोग करते हैं, तो बाइनरी मिन-हीप में सबसे बड़ा तत्व खोजने में O(n) समय लगेगा।

यदि हम मिन-हीप के गुण का उपयोग करते हैं:

मिन-हीप गुण के लिए आवश्यक है कि पैरेंट नोड उसके चाइल्ड नोड से कम हो। इसके कारण, हम यह निष्कर्ष निकाल सकते हैं कि एक गैर-लीफ नोड अधिकतम तत्व नहीं हो सकता क्योंकि उसके चाइल्ड नोड का मान कम होता है।

इसलिए हम अपने खोज स्थान को केवल लीफ नोड्स तक सीमित कर सकते हैं। n तत्वों वाले मिन-हीप में, ceil(n/2) लीफ नोड्स होते हैं। समय और स्थान की जटिलता O(n) बनी रहती है क्योंकि 1/2 का एक स्थिर कारक स्पर्शोन्मुख जटिलता को प्रभावित नहीं करता है।

Additional Information

मिन-हीप में न्यूनतम तत्व θ(1) लेता है।

अन्य सॉर्टिंग तकनीकों की तुलना में बबल सॉर्ट का क्या लाभ है?

  1. यह तेज़ है
  2. कम मेमोरी लेता है
  3. यह पता लगाता है कि क्या इनपुट पहले से ही सॉर्टेड है
  4. उपरोक्त सभी

Answer (Detailed Solution Below)

Option 3 : यह पता लगाता है कि क्या इनपुट पहले से ही सॉर्टेड है

Sorting Question 14 Detailed Solution

Download Solution PDF

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

Key Points

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

Additional Information

  • जब इनपुट के तत्वों को पहले से ही सॉर्टेड किया जाता है, तो बबल सॉर्ट सर्वश्रेष्ठ समय जटिलता O(n) देता है।
  • बबल सॉर्ट आमतौर पर इसके पुनरावृत्त व्यवहार के कारण धीमा होता है।

तत्वों की निम्नलिखित सरणी पर विचार करें

<70, 23, 60, 19, 13, 16, 1, 4, 8, 12, 7, 10, 85>

अधिकतम-हीप में बदलने के लिए आवश्यक न्यूनतम लेन-देन की संख्या ____ है

  1. 2
  2. 4
  3. 3
  4. 1

Answer (Detailed Solution Below)

Option 3 : 3

Sorting Question 15 Detailed Solution

Download Solution PDF

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

संकल्पना:

अधिकतम-हीप:

अधिकतम-हीप एक पूर्ण बाइनरी ट्री है जिसमें प्रत्येक आंतरिक नोड का मान उस नोड के चिल्ड्रन के मूल्यों से अधिक या उसके बराबर होता है। एक हीप के तत्वों को एक सरणी में मैप करना नगण्य है: यदि एक नोड को एक इंडेक्स k संग्रहीत किया जाता है, तो उसके बाएं चिल्ड्रन को इंडेक्स 2k+1 और उसके दाहिने चिल्ड्रन को इंडेक्स 2k+2 पर संग्रहीत किया जाता है।

तत्वों की दी गई सरणी निम्न हैं,

<70, 23, 60, 19, 13, 16, 1, 4, 8, 12, 7, 10, 85> हीप ट्री निम्न बन जाता है,

F1 Harshita  Shraddha 17.02.2022 D 3

एक बाइनरी ट्री को हीप डेटा संरचना में बदलने की प्रक्रिया को 'हेपिफाई' के रूप में जाना जाता है। बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें अधिकतम दो चाइल्ड नोड होते हैं। यदि किसी नोड के चिल्ड्रन के नोड्स 'हेपिफाइड' हैं, तो उस नोड पर केवल 'हेपिफाई' प्रक्रिया लागू की जा सकती है। हीप हमेशा एक पूर्ण बाइनरी ट्री होना चाहिए। हेपिफाई विधि एक सरणी के तत्वों को पुनर्व्यवस्थित करती है जहाँ ith तत्व का बायाँ और दायाँ उप-वृक्ष हीप गुण का पालन करता हैहेपिफाई स्तर दर स्तर पत्तियों से जड़ नोड्स तक कर सकता है।

F1 Harshita  Shraddha 17.02.2022 D 4

 

F1 Harshita  Shraddha 17.02.2022 D 5

F1 Harshita  Shraddha 17.02.2022 D 6

F1 Harshita  Shraddha 17.02.2022 D 7

तो कुल 3 स्वैप की आवश्यकता है।

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

Get Free Access Now
Hot Links: teen patti real money app teen patti master 2025 teen patti apk teen patti gold apk