डेटा संरचनाएँ, जटिलता विश्लेषण (Big-O) और मुख्य एल्गोरिदम
प्रोग्रामिंग की बुनियादी जानकारी आवश्यक: स्नातक स्तर की पुनरावृत्ति के लिए ऐरे, लिस्ट, हैशिंग, ट्री, हीप, ट्राई, Union–Find, ब्लूम फ़िल्टर और जटिलता पर 32 कार्ड।
- Category
- Computer Science
- Level
- basic
- Languages
- hi → hi
- Cards
- 32
- Markdown
- डेटा संरचनाएँ, जटिलता विश्लेषण (Big-O) और मुख्य एल्गोरिदम (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | डिसजॉइंट-सेट संरचना में find और union क्या करते हैं? | find(x), x के समुच्चय का प्रतिनिधि देता है। union(x,y) अलग होने पर उनके समुच्चय जोड़ता है; पहले से एक ही होने पर विभाजन नहीं बदलता। | ||
| 2 | क्षमता दोगुनी करने पर डायनेमिक ऐरे के अंत में जोड़ने की अमॉर्टाइज़्ड लागत क्या है? | प्रति जोड़ O(1)। आकार बदलने की लागत O(n) हो सकती है, लेकिन खाली ऐरे से शुरू करके n बार अंत में जोड़ने की कुल लागत O(n) है। | ||
| 3 | AVL संतुलन की शर्त क्या है? | हर नोड पर ऊँचाई(बायाँ) − ऊँचाई(दायाँ) ∈ {−1, 0, 1}। ट्री BST का क्रम-संबंधी इनवेरिएंट भी पूरा करता है। | ||
| 4 | O, Ω और Θ में क्या अंतर है? | ये क्रमशः आसिम्प्टोटिक ऊपरी, निचली और सटीक क्रम की सीमाएँ देते हैं। ये किसी निर्दिष्ट लागत-फलन का वर्णन करते हैं; O अपने आप सबसे खराब स्थिति नहीं दर्शाता। | ||
| 5 | लेवल-ऑर्डर ट्रैवर्सल बाइनरी ट्री को कैसे देखता है? | FIFO क्यू से एक बार में गहराई का एक स्तर देखा जाता है। बाएँ से दाएँ क्रम पाने के लिए बाएँ बच्चे को दाएँ से पहले क्यू में जोड़ते हैं। | ||
| 6 | ट्राई क्या है और L अक्षरों की कुंजी खोजना कब O(L) होता है? | प्रीफ़िक्स ट्री कुंजियों को अक्षरों वाले रास्तों में रखता है और पूरी कुंजी के लिए निशान लगाता है। यदि अगले अक्षर की हर ट्रांज़िशन O(1) है, तो खोज O(L) है। | ||
| 7 | सिंगली लिंक्ड लिस्ट और डायनेमिक ऐरे में शुरू में जोड़ने तथा इंडेक्स से पहुँच की तुलना करें। | लिस्ट: शुरू में जोड़ना O(1), इंडेक्स से पहुँच O(n)। ऐरे: शुरू में जोड़ना O(n), इंडेक्स से पहुँच O(1); शुरू में जोड़ने पर तत्व खिसकते हैं। | ||
| 8 | टेबल में खोज के लिए हैश फ़ंक्शन में कौन-से गुण होने चाहिए? | वह नियतात्मक हो और अपेक्षित कुंजियों को अच्छी तरह बाँटे। निश्चित आकार की कुंजी का हैश O(1) हो सकता है; L अक्षरों की नई स्ट्रिंग का हैश सामान्यतः O(L) होता है। | ||
| 9 | बाइनरी मिन-हीप की दो परिभाषात्मक विशेषताएँ क्या हैं? | यह एक कम्प्लीट बाइनरी ट्री है और हर माता-पिता नोड की कुंजी बच्चों की कुंजियों से बड़ी नहीं होती। इसलिए रूट में एक न्यूनतम मान होता है। | ||
| 10 | पाथ कम्प्रेशन और रैंक से यूनियन के साथ union/find की अमॉर्टाइज़्ड लागत क्या है? | प्रति क्रिया O(α(n)), जहाँ α प्रतिलोम Ackermann फलन और n तत्वों की संख्या है। आरंभीकरण O(n) है; सीमा क्रियाओं के अनुक्रम पर लागू है, हर कॉल की सबसे खराब लागत स्थिर होने का दावा नहीं है। | ||
| 11 | शून्य से इंडेक्स वाली, लंबाई n की हीप ऐरे में नोड i के माता-पिता और बच्चे कहाँ हैं? | माता-पिता: i>0 के लिए ⌊(i−1)/2⌋। बच्चे: 2i+1 और 2i+2, केवल जब वे इंडेक्स n से छोटे हों। इंडेक्स 0 का कोई माता-पिता नोड नहीं है। | ||
| 12 | अलग कुंजियों वाले बाइनरी सर्च ट्री (BST) का क्रम-संबंधी इनवेरिएंट क्या है? | हर नोड पर बाएँ उपवृक्ष की सभी कुंजियाँ छोटी और दाएँ की सभी बड़ी होती हैं। नियम पुनरावर्ती रूप से लागू होता है। | ||
| 13 | क्यू में पहुँच का क्रम और सामान्य क्रिया-लागत क्या है? | FIFO: पीछे जोड़ें, आगे से निकालें। हेड/टेल लिंक या निश्चित क्षमता के सर्कुलर बफ़र में दोनों O(1) हैं; ऐरे के तत्व खिसकाने पर निकालना O(n) होता है। | ||
| 14 | n तत्वों से नीचे से ऊपर हीप बनाने की लागत क्या है? | O(n)। अधिकतर नोड पत्तियों के पास हैं और उन्हें कम नीचे सरकाना पड़ता है; नोड की ऊँचाई के अनुसार काम जोड़ने पर कुल लागत रैखिक होती है। | ||
| 15 | ओपन एड्रेसिंग में लीनियर और क्वाड्रेटिक प्रोबिंग कैसे अलग हैं? | प्रविष्टियाँ ऐरे में रहती हैं। टेबल आकार m और शुरुआती इंडेक्स h के लिए क्रमशः (h+i) mod m और (h+c₁i+c₂i²) mod m आज़माए जाते हैं। क्वाड्रेटिक प्रोबिंग के लिए उपयुक्त पैरामीटर चाहिए। | ||
| 16 | सेपरेट चेनिंग वाली हैश टेबल में अपेक्षित और सबसे खराब क्रिया-लागत क्या है? | सीमित लोड, अच्छी हैश-वितरण और स्थिर लागत वाली कुंजी-क्रियाओं के साथ खोज/हटाने की अपेक्षित लागत O(1) है। गुणोत्तरी क्षमता-वृद्धि में जोड़ने की अपेक्षित अमॉर्टाइज़्ड लागत O(1) है। n टकराती कुंजियों की चेन क्रिया को O(n) बना सकती है। | ||
| 17 | स्टैक कैसे काम करता है और उसकी क्रियाएँ कब O(1) होती हैं? | LIFO: सबसे अंत में जोड़ा गया तत्व पहले निकलता है। लिंक्ड लिस्ट के हेड पर जोड़ना, निकालना और शीर्ष देखना O(1) हैं; ऐरे का आकार बदलने से एक जोड़ O(n) हो सकता है। | ||
| 18 | रेड-ब्लैक BST को कौन-से रंग-नियम संतुलित रखते हैं? | नोड लाल या काले होते हैं; रूट और NIL पत्तियाँ काली होती हैं। लाल नोड के लाल बच्चे नहीं होते। किसी नोड से उसकी वंशज NIL पत्तियों तक हर रास्ते में बराबर संख्या में काले नोड होते हैं। इससे ऊँचाई O(log n) रहती है। | ||
| 19 | पाथ कम्प्रेशन, रैंक से यूनियन और आकार से यूनियन में क्या अंतर है? | कम्प्रेशन देखे गए नोड को रूट की ओर मोड़ता है। रैंक से यूनियन में कम रैंक वाला रूट अधिक रैंक वाले के नीचे, आकार से यूनियन में छोटा समुच्चय बड़े के नीचे जुड़ता है। रैंक वर्तमान ऊँचाई के बराबर होना ज़रूरी नहीं। | ||
| 20 | अलग कुंजियों वाले BST का इनऑर्डर ट्रैवर्सल क्या देता है? | सभी कुंजियाँ सख्ती से बढ़ते क्रम में; n नोड की यात्रा O(n) में होती है। | ||
| 21 | BST में खोजना, जोड़ना और हटाना ऊँचाई h पर कैसे निर्भर करते हैं? | लागत O(h) है। संतुलित ट्री में h = O(log n), चेन में h = O(n)। अपेक्षित O(log n) के लिए यादृच्छिक जोड़-क्रम जैसी धारणाएँ चाहिए। | ||
| 22 | डबली लिंक्ड लिस्ट दिए गए नोड को O(1) में क्यों हटा सकती है? | पिछले और अगले नोड के लिंक पड़ोसियों को सीधे फिर जोड़ने देते हैं। आवश्यकता पर हेड/टेल बदले जाते हैं; पिछले नोड को खोजना नहीं पड़ता। | ||
| 23 | सेपरेट चेनिंग हैश टकराव कैसे सुलझाती है? | हर बकेट में उस इंडेक्स वाली प्रविष्टियों का संग्रह होता है, अक्सर लिंक्ड लिस्ट। एक बकेट में आने वाली अलग कुंजियाँ अलग प्रविष्टियाँ रहती हैं। | ||
| 24 | सर्कुलर ऐरे क्यू किसी तत्व को निकालने के बाद खिसकाने से कैसे बचती है? | आगे और पीछे के इंडेक्स क्षमता के मॉड्यूलो में घूमते हैं। निकालने पर आगे का इंडेक्स बढ़ता है, इसलिए खाली खाने बाकी तत्वों को हिलाए बिना दोबारा उपयोग होते हैं। | ||
| 25 | n → ∞ होने पर इन वृद्धि दरों को धीमी से तेज़ क्रम में रखें: n!, n, 1, n², log n, 2ⁿ, n log n। | आसिम्प्टोटिक क्रम: 1 < log n < n < n log n < n² < 2ⁿ < n!। | ||
| 26 | AVL में जोड़ने से हुआ बायाँ-दायाँ असंतुलन कैसे सुधारा जाता है? | पहले बाएँ बच्चे को बाएँ घुमाएँ; फिर असंतुलित नोड को दाएँ घुमाएँ। | ||
| 27 | बाइनरी हीप में जोड़ने, रूट हटाने और रूट देखने की लागत क्या है? | ऐरे का आकार बदले बिना क्रमशः O(log n), O(log n) और O(1)। आकार बदलने की लागत O(n) हो सकती है। | ||
| 28 | बाइनरी ट्री के प्रीऑर्डर, इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल के क्रम क्या हैं? | प्रीऑर्डर: नोड → बायाँ → दायाँ। इनऑर्डर: बायाँ → नोड → दायाँ। पोस्टऑर्डर: बायाँ → दायाँ → नोड। | ||
| 29 | निश्चित आकार की ऐरे में इंडेक्स से पहुँच O(1) क्यों है? | बराबर आकार के खाने लगातार रखे होते हैं: पता(i) = आधार + i·खाने_का_आकार। माना जाता है कि पते की गणना स्थिर समय लेती है। | ||
| 30 | केवल जोड़ने की अनुमति वाला ब्लूम फ़िल्टर क्या उत्तर दे सकता है? | नकारात्मक परिणाम बताता है कि तत्व जोड़ा नहीं गया; सकारात्मक बताता है कि शायद जोड़ा गया हो। हैश बिट ऐरे में बिट सेट करते हैं; झूठे सकारात्मक संभव हैं, पर स्थिति अक्षुण्ण रहने पर झूठे नकारात्मक नहीं। | ||
| 31 | गैर-ऋणात्मक फलनों f और g के लिए f(n) ∈ O(g(n)) का क्या अर्थ है? | ऐसे स्थिरांक c > 0 और n₀ ≥ 0 मौजूद हैं कि हर n ≥ n₀ के लिए f(n) ≤ c·g(n) हो। | ||
| 32 | हैश टेबल का लोड फ़ैक्टर क्या है और उसका आकार क्यों बदल सकता है? | α = n/m: n प्रविष्टियाँ और m बकेट या खाने। कार्यान्वयन की सीमा पार होने पर टेबल बढ़ाकर दोबारा हैशिंग हो सकती है; 0.75 सार्वभौमिक सीमा नहीं है। |