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

सही विकल्प हैशिंग के द्वारा सर्च है।

संकल्पना:

रैखिक सर्च में, दी गई सूची के प्रत्येक घटक की तुलना किसी भी घटक को छोड़े बिना दी गई कुंजी(की) के साथ एक-एक करके की जाती है।

यह तब उपयोगी होता है जब हमें एक छोटी सी अवर्गीकृत सूची में किसी आइटम को खोजने की आवश्यकता होती है, लेकिन सूची के आकार में वृद्धि के साथ सूची को खोजने में समय लगता है।

उदाहरण के लिए, लंबाई 5 की एक सूची पर विचार करें और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 5

यदि हम उसी सूची का आकार बढ़ाते हैं (मान लीजिए 15) और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 15

बाइनरी सर्च में, खोजी जाने वाली कुंजी(की) की तुलना वर्गीकृत सूची के बीच के घटक से की जाती है, इसके परिणामस्वरूप तीन में से कोई भी संभावना हो सकती है:

i) यदि मध्य स्थिति का घटक कुंजी(की) से मेल खाता है तो खोज सफल होती है।

ii) यदि मध्य स्थिति का घटक कुंजी(की) से बड़ा है तो मुख्य घटक सूची के बाएं भाग में मौजूद हो सकता है।

iii) यदि मध्य स्थान पर स्थित घटक कुंजी(की) से छोटा है, तो कुंजी घटक सूची के दाहिने हिस्से में मौजूद हो सकता है।

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

इस प्रकार जैसे-जैसे सूची का आकार बढ़ता है, सूची को खोजने में लगने वाला समय बढ़ता जाता है। लेकिन यह रैखिक सर्च के लिए आवश्यक समय जितना बड़ा नहीं होगा।

हैश-आधारित सर्चिंग के लिए कुंजी(की) की स्थिति का पता लगाने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है, बशर्ते कि प्रत्येक घटक हैश फलन द्वारा तय की गई अपनी निर्दिष्ट स्थिति में मौजूद हो।

उदाहरण के लिए, लंबाई 5 और हैश फलन की सूची पर विचार करें:

फलन: h(element) = element % size(list)

हैशिंग फलन एक गणितीय फलन है जो स्थिर समय में हैश फलन को प्रदान किए गए प्रत्येक अद्वितीय मान के लिए अद्वितीय परिणाम उत्पन्न करता है।

उदाहरण के लिए: लंबाई 5 की एक सूची पर विचार करें और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 2 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है। 

उसी तरह सूची का आकार बढ़ाना (15 मान लें) और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 12 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी तुलना की आवश्यकता है।

इस प्रकार यह सूची की लंबाई से स्वतंत्र होता है।

प्राथमिक क्लस्टरिंग:

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

द्वितीयक क्लस्टरिंग:

द्वितीयक क्लस्टरिंग आम तौर पर रैखिक संबोधन और द्विघात प्रोबिंग सहित ओपन एड्रेसिंग मोड के साथ होता है जिसमें प्रोब अनुक्रम कुंजी और साथ ही हैश श्रृंखलन में भी स्वतंत्र होता है,।

दोहरी हैशिंग:

दोहरी हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग हैश आघात को हल करने के लिए हैश टेबलों में ओपन-एड्रेसिंग के साथ किया जाता है, जब आघात होता है तो ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके।

दोहरी हैशिंग तकनीक क्लस्टिंग समस्याओं से मुक्त है

संकल्पना:

स्टैक एक डेटा संरचना है जिसमें तत्वों को केवल एक छोर यानी स्टैक के ऊपर से डाला और हटाया जा सकता है। यह LIFO प्रॉपर्टी यानी लास्ट इन फर्स्ट आउट का अनुसरण करता है।

व्याख्या:

(a) एक ऐरे में बाइनरी सर्च

स्टैक की मदद से किसी ऐरे में बाइनरी सर्च किया जा सकता है। बाइनरी सर्च डिवाइड एंड कॉनकॉर अप्रोच पर काम करता है और मध्य तत्व को सर्च करता है और फिर बाईं ओर सर्च करता है यदि तत्व मध्य तत्व से छोटा है अन्यथा सर्च मध्य तत्व के दाईं ओर आगे बढ़ता है।

(b) ब्रेड्थ फर्स्ट सर्च

चौड़ाई फर्स्ट सर्च ग्राफ़ ट्रैवर्सल एल्गोरिथम है। यह ग्राफ या ट्री को पार करने के लिए क्यू डेटा संरचना का उपयोग करता है। इसका उपयोग ग्राफ में जुड़े घटकों को खोजने के लिए भी किया जाता है।

(c) फ़ंक्शन कॉल लागू करना

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

(d) प्रक्रिया शेड्यूलिंग

प्रक्रिया शेड्यूलिंग को क्यू डेटा संरचना का उपयोग करके कार्यान्वित किया जाता है। निष्पादन के लिए तैयार प्रक्रियाओं के लिए तैयार क्यू को बनाए रखा जाता है।

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

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

Key Points 

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

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

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

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

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

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

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

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

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

चूंकि हम यादृच्छिक प्रोबिंग का उपयोग कर रहे हैं:

इन्सर्ट 15:

(15)%7 = 1

इन्सर्ट 11:

(11)%7 = 4

इन्सर्ट 25:

(25)%7 = 4 / संघट्‍टन:

i = 4

 i = (i + 5) % 7    / यादृच्छिक फ़ंक्शन का उपयोग करना

i = (4 + 5)%7 = 2

अत: 25 की स्थिति 2nd है 

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

Key Points 

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

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

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

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

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

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

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

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

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

अवधारणा:

• एक लीनियर सर्च (रैखिक खोज) या ​(सिक्वेंशियल सर्च) अनुक्रमिक खोज एक ऐरे या लिंक्ड सूची या किसी डेटा संरचना के भीतर एक घटक खोजने के लिए एक विधि है।
• यह अनुक्रमिक रूप से सूची के प्रत्येक घटक की तब तक जांच करता है जब तक कि कोई मैच नहीं मिलता है या पूरी सूची सर्च कर ली गई है।

स्पष्टीकरण:

int A[ ] = {2, 1, 4, 5 , 6, 7}

ऐरे का नाम: A

सर्च: 2

पहली तुलना में, 2 पाया जाता है

सर्वोत्तम-केस समय जटिलता O(1) है

संकल्पना:

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

व्याख्या:

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

चरण 1

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

चरण 2:

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

चरण 3:

चरण 4:

चरण 5:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Key Points

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

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) समय जटिलता देता है।

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

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

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

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

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

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

इंसर्शन सॉर्ट में, सर्वश्रेष्ठ मामले में Θ (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:

• यह सरणी के मध्य तत्व को ढूंढता है और खोजे जाने वाले तत्व के साथ तत्व की तुलना करता है, यदि यह मेल खाता है तो सत्य प्राप्त होता है।

चरण 2:

• यदि नहीं, तो सरणी को दो हिस्सों में विभाजित कीजिये जिसमें खोज के लिए तत्व मध्य तत्व से कम है, तो खोज बाएं भाग में होती है अन्यथा दाएं आधे में खोजें।

चरण 3:

इस प्रक्रिया को तब तक दोहराएं जब तक आपको तत्व न मिल जाए।

व्याख्या:

सबसे खराब स्थिति के लिए 52

सबसे खराब स्थिति: नीचे दिए गए सरणी में 50 खोजें

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)

50 > 32

\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)

50 < 63

\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)

मिल गया 

T(n) = O(log n)

इसके अलावा, औसत स्थिति के लिए:

T(n) = O(log n)

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

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

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

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

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

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