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

सही उत्तर हैश टेबल है। 

Key Points

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

Additional Information

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

सही उत्तर रैखिक जांच है। 

Key Points

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

Additional Information

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

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

संकल्पना:

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

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

 

उदाहरण के लिए, लंबाई 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) प्रक्रिया शेड्यूलिंग

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

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

इन्सर्ट 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) प्रक्रिया शेड्यूलिंग

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