Searching MCQ Quiz in हिन्दी - Objective Question with Answer for Searching - मुफ्त [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

• हैशिंग द्वारा खोज में, हैश टेबल का आकार वास्तव में सूची के आकार (तत्वों की संख्या) से बड़ा हो सकता है।
• एक हैश टेबल को एक हैश फ़ंक्शन का उपयोग करके बकेट या स्लॉट की एक सरणी में एक इंडेक्स की गणना करके डेटा तक कुशल पहुँच प्रदान करने के लिए डिज़ाइन किया गया है।
• हैश टेबल का आकार (बकेट की संख्या) अक्सर टकराव को कम करने और कुशल डेटा पुनर्प्राप्ति सुनिश्चित करने के लिए तत्वों की संख्या से अधिक चुना जाता है।
• आकार में यह अंतर खोज, सम्मिलित और हटाने के संचालन के लिए O(1) की औसत समय जटिलता को बनाए रखने में मदद करता है।
• एक बड़ा हैश टेबल होने से तत्वों को फैलाने और एक ही इंडेक्स में कई तत्वों के हैश होने की संभावना को कम करने में मदद मिलती है।

Additional Information

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

सही उत्तर सूची में केवल एक तत्व है। 

Key Points

• रैखिक खोज के लिए सर्वोत्तम स्थिति परिदृश्य में, खोजा जा रहा तत्व सूची का पहला तत्व होता है।
  • इसका अर्थ है कि केवल एक तत्व की जाँच करने के बाद खोज पूरी हो जाती है।
  • रैखिक खोज, जिसे क्रमिक खोज के रूप में भी जाना जाता है, सूची के प्रत्येक तत्व को एक-एक करके तब तक जांचकर काम करती है जब तक कि वांछित तत्व नहीं मिल जाता या सूची समाप्त नहीं हो जाती।
  • इसलिए, रैखिक खोज के लिए सर्वोत्तम प्रदर्शन O(1) है, यह दर्शाता है कि केवल एक तुलना की आवश्यकता है।
  • यह एक रैखिक खोज एल्गोरिथम के लिए इष्टतम परिदृश्य है।

Additional Information

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

def linear_search(lst, target):
    for index, element in enumerate(lst):
        if element == target:
            return index  # Return the index of the target element
    return -1  # Return -1 if the element is not found

# Example usage:
lst = [10, 20, 30, 40, 50]
target = 30
result = linear_search(lst, target)
if result != -1:
    print(f'Element found at index {result}')
else:
    print('Element not found')

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

इन्सर्ट 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 है 

अवधारणा:

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

स्पष्टीकरण:

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

ऐरे का नाम: A

सूचक (index)	0	1	2	3	4	5
घटक (element)	2	1	4	5	6	7

 

सर्च: 2

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

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

बाइनरी सर्च एल्गोरिथ्म:

• बाइनरी सर्च एल्गोरिथम का उपयोग पहले से क्रमबद्ध सरणी में एक तत्व को खोजने के लिए किया जाता है।

चरण 1:

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

चरण 2:

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

चरण 3:

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

व्याख्या:

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

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

11

12

15

24

35

50

51

63

 

\({\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)

सर्चिंग:

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

• अनुक्रमिक खोज: इसमें सूची या ऐरे को क्रमिक रूप से ट्रेस किया जाता है और प्रत्येक तत्व की जाँच की जाती है।
• बाइनरी सर्च: ये एल्गोरिदम विशेष रूप से सॉर्ट किए गए डेटा-स्ट्रक्चर में खोज के लिए डिज़ाइन किए जाते हैं।

अतः विकल्प 2 सही है।

महत्वपूर्ण तथ्य:

सॉर्टिंग एल्गोरिथ्म का उपयोग तत्वों पर तुलना ऑपरेटर के अनुसार किसी दिए गए ऐरे या सूची तत्वों को पुनर्व्यवस्थित करने के लिए किया जाता है। तुलना ऑपरेटर का उपयोग संबंधित डेटा संरचना में तत्वों के नए क्रम को तय करने के लिए किया जाता है।

ट्रावर्सल ट्री के सभी नोडों पर जाने की वाली एक प्रक्रिया है और यह उनके मानों को भी प्रिंट कर सकता है। क्योंकि सभी नोड किनारों (लिंक) के माध्यम से जुड़े होते हैं, इसलिए हम सदैव रूट (हेड) नोड से शुरू करते हैं। अर्थात् हम यादृच्छिकता से ट्री में एक नोड तक नहीं पहुंच सकते हैं। ट्री को पार करने के लिए हम तीन तरीकों का इस्तेमाल करते हैं -

• इन-आर्डर ट्रावर्सल
• पोस्ट-आर्डर ट्रावर्सल
• प्री-आर्डर ट्रावर्सल

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

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

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

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

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

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

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

अवधारणा:

सजातीय डेटा संरचना (HDS):

• HDS जिसमें केवल पूर्णांक या केवल फ्लोट मान जैसे समान प्रकार के डेटा होते हैं।
• सजातीय डेटा संरचना का मूल उदाहरण सरणी है।

 

व्याख्या

प्रश्न में हमें आदेश दिया गया कि परिमित HDS जो कुछ भी नहीं है, लेकिन सरणी लेकिन सरणी में मौजूद नहीं है

विकल्प इसलिए हमें उनमें से सबसे अच्छा विकल्प चुनना है। विकल्प के अनुसार चलते है

विकल्प 1: अनबद्ध सूची

अनबद्ध सूची HDS है, लेकिन परिमित नहीं है क्योंकि अनबद्ध सूची आकार रन टाइम पर तय किया गया है।

विकल्प 2: ग्राफ़

ग्राफ़ HDS है लेकिन परिमित नहीं है क्योंकि रन टाइम पर ग्राफ़ का आकार तय किया जाता है।

विकल्प 3: ट्री

ट्री HDS है लेकिन परिमित नहीं है क्योंकि ट्री का आकार रन टाइम पर तय किया जाता है।

विकल्प 4: हैश तालिका

हैश तालिका का आदेश दिया गया है और परिमित डेटा संरचना है (आकार संकलन समय पर तय किया गया है)।

इसलिए उत्तर के लिए विकल्प 4 सबसे अच्छा विकल्प है।

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

अवधारणा:

कथन 1: बाइनरी सर्च लीनियर सर्च की तुलना में तेज है।

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

कथन 2: बाइनरी सर्च उन सभी इनपुट लिस्ट्स पर लागू नहीं किया जा सकता है जिन पर लीनियर सर्च लागू की जा सकती है।

सत्य, बाइनरी सर्च केवल सॉर्टेड लिस्ट पर लागू होती है, यह एक सॉर्टेड लिस्ट पर लागू नहीं हो सकती है। जबकि लीनियर सर्च सभी प्रकार की लिस्ट्स के लिए लागू होती है। इसका अर्थ है सॉर्टेड या अनसॉर्टेड प्रकार की लिस्ट्स।

अतः सही उत्तर I और II दोनों है।

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

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

संकल्पना:

खुला एड्रेसिंग या बंद हैशिंग हैश तालिका में टकराव वियोजन की एक विधि है। इस विधि के साथ हैश टकराव को ऐरे में वैकल्पिक स्थानों के माध्यम से जाँच या खोज द्वारा वियोजित किया जाता है।

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

हैश तालिका आकार = 7

हैश फंक्शन = (MOD 7)

हैश तालिका कुंजी, 53, 32, 43, 51, 99 हैं।

53 के हैश तालिका मान = 53 MOD 7 =4

32 के हैश तालिका मान = 32 MOD 7 =4

43 के हैश तालिका मान = 43 MOD 7 =1

51 के हैश तालिका मान = 51 MOD 7 =2

99 के हैश तालिका मान = 99 MOD 7 =1

ऐरे के साथ हैश तालिका A[ 0...6] है।

सूचकांक 0

सूचकांक 1 43

सूचकांक 2 51

सूचकांक 3 99

सूचकांक 4 53

सूचकांक 5 32

सूचकांक 6

अतः सही उत्तर EMPTY, 43, 51, 99, 53, 32, EMPTY है।

संकल्पना:

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

व्याख्या:

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

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

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

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

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

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

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

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