संकेतों और व्याख्याओं के साथ मुफ़्त डेटा संरचनाएँ बहुविकल्पीय अभ्यास प्रश्न, तीन स्तरों पर: मुख्य शब्द और तथ्य, अवधारणाओं का अनुप्रयोग, केस और विश्लेषण।
डेटा संरचना मेमोरी में डेटा को व्यवस्थित करने का एक तरीका है ताकि कुछ संक्रियाएँ तेज़ हों: कोई वस्तु ढूँढना, जोड़ना, हटाना।
कोई भी संरचना हर चीज़ में तेज़ नहीं है। एक चुनने का अर्थ है यह चुनना कि कौन-सी संक्रियाएँ सस्ती होनी चाहिए। उनकी लागत बिग O में लिखी जाती है, जहाँ n वस्तुओं की संख्या है।
दो मूल निर्माण खंड ऐरे और लिंक्ड लिस्ट हैं।
एक ऐरे अपनी वस्तुओं को मेमोरी के एक खंड में, एक के बाद एक, संग्रहीत करता है। कंप्यूटर गणना कर सकता है कि वस्तु i कहाँ है, इसलिए a[i] पढ़ने में O(1) लगता है। आगे डालने का अर्थ है हर वस्तु को खिसकाना: O(n)।
एक लिंक्ड लिस्ट हर वस्तु को एक नोड में अगले नोड के पॉइंटर के साथ संग्रहीत करती है। अंतिम पॉइंटर null है। शीर्ष (h) पर डालने से केवल एक पॉइंटर बदलता है: O(1)। पर वस्तु i तक पहुँचने के लिए i पॉइंटरों का अनुसरण करना होता है: O(n)।
एक डबली लिंक्ड लिस्ट में पिछले नोड का पॉइंटर भी होता है, इसलिए आप दोनों दिशाओं में चल सकते हैं।
स्व-जाँच कौन-सी संक्रिया ऐरे के लिए O(1) पर सिंगली लिंक्ड लिस्ट के लिए O(n) है?
आगे एक नई वस्तु डालना
वस्तुओं को एक-एक करके गिनना
सूचकांक i पर वस्तु पढ़ना
हर वस्तु पर एक बार जाना
उत्तर: सूचकांक i पर वस्तु पढ़ना. ऐरे वस्तु i का पता सीधे निकालता है। लिंक्ड लिस्ट को शीर्ष से i पॉइंटरों का अनुसरण करना होता है। आगे डालना उलटी स्थिति है: लिस्ट के लिए सस्ता, ऐरे के लिए महँगा।
2स्टैक और क्यू
एक स्टैक प्लेटों के ढेर जैसा है: आप केवल ऊपर जोड़ते और हटाते हैं। अंदर जाने वाली अंतिम वस्तु बाहर आने वाली पहली है: LIFO।
push एक वस्तु ऊपर रखता है, pop ऊपरी वस्तु हटाता है, peek ऊपरी को बिना हटाए पढ़ता है। सभी O(1) हैं।
उपयोग: संपादक का undo फ़ंक्शन, प्रोग्राम का कॉल स्टैक, कोष्ठकों के संतुलन की जाँच, गहराई-प्रथम खोज।
एक क्यू काउंटर पर लाइन जैसी है: आप पीछे जुड़ते और आगे से निकलते हैं। अंदर जाने वाली पहली वस्तु बाहर आने वाली पहली है: FIFO।
enqueue पीछे जोड़ता है, dequeue आगे से हटाता है। दोनों O(1) हैं।
उपयोग: प्रिंट कार्य, संभाले जाने की प्रतीक्षा में संदेश, चौड़ाई-प्रथम खोज।
एक डेक (द्वि-सिरा क्यू) दोनों सिरों पर जोड़ने और हटाने देता है। एक प्राथमिकता क्यू हमेशा सबसे उच्च प्राथमिकता वाली वस्तु पहले हटाती है; यह आमतौर पर हीप के रूप में बनाई जाती है।
स्व-जाँच टेक्स्ट संपादक के “undo” बटन के लिए कौन-सी डेटा संरचना सबसे उपयुक्त है?
क्यू
ग्राफ़
स्टैक
हैश टेबल
उत्तर: स्टैक. Undo को सबसे हाल की क्रिया पहले उलटनी होती है: अंतिम अंदर, पहला बाहर। क्यू सबसे पुरानी क्रिया पहले उलटती।
3ट्री, हीप, हैश टेबल और ग्राफ़
एक ट्री में एक शीर्ष नोड होता है, मूल (रूट)। हर अन्य नोड का ठीक एक जनक होता है। बिना संतानों वाले नोड पत्तियाँ हैं। n नोडों वाले ट्री में n − 1 किनारे होते हैं।
बाइनरी ट्री में हर नोड की अधिकतम दो संतानें होती हैं। बाइनरी सर्च ट्री (BST) एक नियम जोड़ता है: बाएँ उपवृक्ष की कुंजियाँ नोड से छोटी, दाएँ उपवृक्ष की बड़ी होती हैं।
BST में खोज एक पथ पर नीचे जाती है, इसलिए लागत O(ऊँचाई) है। संतुलित ट्री (AVL, red-black) ऊँचाई को log₂ n के निकट रखता है। क्रमबद्ध क्रम में डाली गई कुंजियाँ ऊँचाई n की एक श्रृंखला बनाती हैं।
एक हीप ऐसा बाइनरी ट्री है जिसमें हर जनक अपनी संतानों से छोटा (min-heap) या बड़ा (max-heap) होता है। न्यूनतम या अधिकतम मूल पर होता है, और डालने और हटाने की लागत O(log n) है।
एक हैश टेबल कुंजी–मान युग्म संग्रहीत करती है। एक हैश फ़ंक्शन कुंजी को सूचकांक में बदलता है, इसलिए डालना और खोजना औसतन O(1) लेते हैं। समान सूचकांक वाली दो कुंजियाँ एक टकराव हैं, जिसे चेनिंग (प्रति स्लॉट एक सूची) या ओपन एड्रेसिंग (दूसरा स्लॉट आज़माना) से हल किया जाता है।
एक ग्राफ़ में किनारों से जुड़े शीर्ष होते हैं, जिनकी दिशा या भार हो सकता है। यह आसन्नता मैट्रिक्स, O(V²) मेमोरी, या आसन्नता सूचियों, O(V + E), के रूप में संग्रहीत होता है।
स्व-जाँच कुंजियाँ 50, 30, 70, 20 और 40 इसी क्रम में एक खाली बाइनरी सर्च ट्री में डाली जाती हैं। 30 की बाईं संतान क्या है?
20
40
70
इसकी कोई बाईं संतान नहीं है
उत्तर: 20. 20, 50 से छोटा है, इसलिए यह बाईं ओर 30 पर जाता है। यह 30 से भी छोटा है, इसलिए फिर बाईं ओर जाता है। 40, 30 से बड़ा है और उसकी दाईं संतान बनता है।
4विधि चरण-दर-चरण
प्रश्न अक्सर एक कार्य का वर्णन करते हैं और पूछते हैं कि कौन-सी संरचना उपयुक्त है, या पूछते हैं कि कुछ संक्रियाओं के बाद संरचना कैसी दिखती है।
वह संक्रिया ढूँढें जिसे तेज़ होना चाहिए: स्थिति से पहुँच, कुंजी से, सबसे नई वस्तु, सबसे पुरानी वस्तु, सबसे छोटी वस्तु, या एक परास।
इसे संरचना से मिलाएँ: सूचकांक → ऐरे, कुंजी → हैश टेबल, सबसे नई → स्टैक, सबसे पुरानी → क्यू, सबसे छोटी या बड़ी → हीप, क्रमबद्ध क्रम या परास → संतुलित सर्च ट्री।
कार्य के लिए आवश्यक अन्य संक्रियाओं की लागत बिग O में जाँचें।
ट्रेस प्रश्न के लिए संक्रियाओं को एक-एक करके करें और हर एक के बाद की अवस्था लिखें।
अंतिम अवस्था को संरचना के नियम से जाँचें: LIFO, FIFO, BST क्रम या हीप क्रम।
5एक हल किया गया उदाहरण
हर चरण का अनुसरण करें। अगला चरण खोलने से पहले उसका अनुमान लगाने का प्रयास करें।
हल किया गया उदाहरण
कुंजियाँ 50, 30, 70, 20, 40 और 60 इसी क्रम में एक खाली बाइनरी सर्च ट्री में डाली जाती हैं। इन-ऑर्डर ट्रैवर्सल क्या है, और 60 की खोज को कितनी तुलनाएँ चाहिए?
1
मूल डालें
पहली कुंजी, 50, मूल बनती है।
2
30 और 70 डालें
30, 50 से छोटा है, इसलिए बाईं ओर जाता है। 70, 50 से बड़ा है, इसलिए दाईं ओर जाता है।
3
20, 40 और 60 डालें
20: 50 से छोटा, 30 से छोटा, इसलिए 30 के बाईं ओर। 40: 50 से छोटा, 30 से बड़ा, इसलिए 30 के दाईं ओर। 60: 50 से बड़ा, 70 से छोटा, इसलिए 70 के बाईं ओर।
4
इन-ऑर्डर ट्रैवर्सल करें
इन-ऑर्डर ट्रैवर्सल बाएँ उपवृक्ष, फिर नोड, फिर दाएँ उपवृक्ष पर जाता है।
इससे 20, 30, 40, 50, 60, 70 मिलता है: कुंजियाँ क्रमबद्ध क्रम में, जैसा BST के लिए हमेशा होता है।
5
60 की खोज
50 से तुलना: बड़ा, दाईं ओर जाएँ। 70 से तुलना: छोटा, बाईं ओर जाएँ। 60 से तुलना: मिल गया।
खोज को 3 तुलनाएँ चाहिए, प्रति स्तर एक।
उत्तर
इन-ऑर्डर: 20, 30, 40, 50, 60, 70। 60 की खोज को 3 तुलनाएँ चाहिए।
6सामान्य गलतियाँ
LIFO और FIFO को मिलाना। स्टैक सबसे नई वस्तु लौटाता है, क्यू सबसे पुरानी।
यह सोचना कि लिंक्ड लिस्ट सूचकांक से तेज़ पहुँच देती है। उसे शीर्ष से चलना होता है।
यह मानना कि BST हमेशा O(log n) है। केवल संतुलित ट्री ऐसा है; क्रमबद्ध प्रविष्टियाँ O(n) देती हैं।
हैश टेबल में टकराव भूल जाना। O(1) औसत है, सबसे खराब स्थिति नहीं।
ट्रैवर्सलों को मिलाना। प्रीऑर्डर: नोड पहले। इन-ऑर्डर: नोड बीच में। पोस्टऑर्डर: नोड अंत में।
बड़े विरल ग्राफ़ के लिए आसन्नता मैट्रिक्स का उपयोग करना। यह O(V²) मेमोरी बर्बाद करता है।
स्व-जाँच आप 1, 2 और 3 को इसी क्रम में एक खाली क्यू में enqueue करते हैं। पहला dequeue कौन-सी वस्तु लौटाता है?
1, 2 और 3 एक साथ
1
2
3
उत्तर: 1. क्यू पहला अंदर, पहला बाहर है, इसलिए 1 पहले निकलता है। 3 स्टैक (pop) का उत्तर होता, जो सबसे नई वस्तु लौटाता है।
7परीक्षा प्रश्न कैसे दिखते हैं
आसान: मुख्य शब्द और तथ्य। LIFO और FIFO, नोड, मूल या पत्ती क्या है, BST नियम, हैश फ़ंक्शन क्या करता है।
मध्यम: अवधारणाओं का अनुप्रयोग। कौन-सी संरचना किसी कार्य के लिए उपयुक्त है, push और pop या BST प्रविष्टियों का परिणाम, ट्री ट्रैवर्सल, रैखिक प्रोबिंग वाली हैश टेबल, बिग O में लागतें।
कठिन: मामले और विश्लेषण। संतुलित ट्री, ऐरे में हीप, B-ट्री, ट्राई, यूनियन-फ़ाइंड, ब्लूम फ़िल्टर और LRU कैश जैसे डिज़ाइन।
सूचकांक 0 से ऐरे में संग्रहीत हीप के लिए सूचकांक i की संतानें 2i + 1 और 2i + 2 पर हैं, और उसका जनक ⌊(i − 1) / 2⌋ पर है।
स्टैटिक ऐरे और डायनेमिक ऐरे में मुख्य अंतर क्या है?
Aस्टैटिक ऐरे धीमी इंडेक्स पहुँच देता है
Bडायनेमिक ऐरे मेमोरी के बड़े ब्लॉक में जाकर बढ़ सकता है
Cडायनेमिक ऐरे अपने तत्वों को लिंक्ड नोडों में संग्रहीत करता है ताकि वह एक-एक करके बढ़ सके
Dस्टैटिक ऐरे केवल संख्याएँ संग्रहीत कर सकता है
संकेत दिखाएँ
Python लिस्ट और Java ArrayList इनमें से एक के उदाहरण हैं।
दो गलत उत्तर अब काट दिए गए हैं। बचे हुए दो में से एक सही है।
उत्तर और व्याख्या दिखाएँ
यह उत्तर क्यों है
स्टैटिक ऐरे का आकार निश्चित होता है; डायनेमिक ऐरे भर जाने पर एक बड़ा ऐरे आवंटित करके तत्व कॉपी करता है।
उत्तर
B · डायनेमिक ऐरे मेमोरी के बड़े ब्लॉक में जाकर बढ़ सकता है
उदाहरण 2मध्यम
बाइनरी मिन-हीप में extract-min कैसे काम करता है?
Aऐरे का अंतिम तत्व हटाएँ
Bअंतिम तत्व को रूट पर ले जाकर नीचे sift करें
Cरूट हटाकर सभी तत्वों को एक स्थान बाएँ खिसकाएँ
Dनए न्यूनतम के लिए सभी लीफ़ खोजें
संकेत दिखाएँ
ट्री को पूर्ण रखें, फिर क्रम ठीक करें।
दो गलत उत्तर अब काट दिए गए हैं। बचे हुए दो में से एक सही है।
उत्तर और व्याख्या दिखाएँ
यह उत्तर क्यों है
अंतिम तत्व रूट का रिक्त स्थान भरता है और हीप गुण पूरा होने तक अपने छोटे चाइल्ड से स्वैप होता है, जिसमें O(log n) लगता है।
उत्तर
B · अंतिम तत्व को रूट पर ले जाकर नीचे sift करें
उदाहरण 3कठिन
union by rank या path compression के बिना, n तत्वों वाली union-find संरचना में एक find की वर्स्ट-केस लागत क्या है?
AO(1)
BO(α(n))
CO(log n)
DO(n)
संकेत दिखाएँ
ट्री विकृत (degenerate) हो सकते हैं।
दो गलत उत्तर अब काट दिए गए हैं। बचे हुए दो में से एक सही है।
उत्तर और व्याख्या दिखाएँ
यह उत्तर क्यों है
सरल union ट्री को एक लंबी शृंखला में जोड़ सकते हैं, इसलिए find को n − 1 पैरेंट पॉइंटरों का अनुसरण करना पड़ सकता है; दोनों ह्यूरिस्टिक इसे लगभग स्थिर कर देते हैं।
उत्तर
D · O(n)
प्रश्न और उत्तर
डेटा संरचनाएँ क्या है?
कोई भी संरचना हर चीज़ में तेज़ नहीं है। एक चुनने का अर्थ है यह चुनना कि कौन-सी संक्रियाएँ सस्ती होनी चाहिए। उनकी लागत बिग O में लिखी जाती है, जहाँ n वस्तुओं की संख्या है।
दो मूल निर्माण खंड ऐरे और लिंक्ड लिस्ट हैं।
डेटा संरचनाएँ को चरण-दर-चरण कैसे सीखें?
डेटा संरचना क्या है
स्टैक और क्यू
ट्री, हीप, हैश टेबल और ग्राफ़
विधि चरण-दर-चरण
एक हल किया गया उदाहरण
सामान्य गलतियाँ
परीक्षा प्रश्न कैसे दिखते हैं
डेटा संरचनाएँ के अभ्यास में क्या शामिल है?
आसान: मुख्य शब्द और तथ्य
मध्यम: अवधारणाओं का अनुप्रयोग
कठिन: केस और विश्लेषण
हर प्रश्न में चार विकल्प होते हैं, और केवल एक सही होता है। अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।
अभ्यास कैसे काम करता है
हर प्रश्न में चार विकल्प होते हैं, और केवल एक सही होता है।
अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।
आपकी प्रगति, गलतियाँ और सहेजे गए प्रश्न रखे जाते हैं, ताकि आप परीक्षा से पहले दोहरा सकें।