डेटा संरचनाएँ, जटिलता विश्लेषण (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)ExampleMultiple-Choice Options
1डिसजॉइंट-सेट संरचना में find और union क्या करते हैं?find(x), x के समुच्चय का प्रतिनिधि देता है। union(x,y) अलग होने पर उनके समुच्चय जोड़ता है; पहले से एक ही होने पर विभाजन नहीं बदलता।
2क्षमता दोगुनी करने पर डायनेमिक ऐरे के अंत में जोड़ने की अमॉर्टाइज़्ड लागत क्या है?प्रति जोड़ O(1)। आकार बदलने की लागत O(n) हो सकती है, लेकिन खाली ऐरे से शुरू करके n बार अंत में जोड़ने की कुल लागत O(n) है।
3AVL संतुलन की शर्त क्या है?हर नोड पर ऊँचाई(बायाँ) − ऊँचाई(दायाँ) ∈ {−1, 0, 1}। ट्री BST का क्रम-संबंधी इनवेरिएंट भी पूरा करता है।
4O, Ω और Θ में क्या अंतर है?ये क्रमशः आसिम्प्टोटिक ऊपरी, निचली और सटीक क्रम की सीमाएँ देते हैं। ये किसी निर्दिष्ट लागत-फलन का वर्णन करते हैं; 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) होता है।
14n तत्वों से नीचे से ऊपर हीप बनाने की लागत क्या है?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) में होती है।
21BST में खोजना, जोड़ना और हटाना ऊँचाई h पर कैसे निर्भर करते हैं?लागत O(h) है। संतुलित ट्री में h = O(log n), चेन में h = O(n)। अपेक्षित O(log n) के लिए यादृच्छिक जोड़-क्रम जैसी धारणाएँ चाहिए।
22डबली लिंक्ड लिस्ट दिए गए नोड को O(1) में क्यों हटा सकती है?पिछले और अगले नोड के लिंक पड़ोसियों को सीधे फिर जोड़ने देते हैं। आवश्यकता पर हेड/टेल बदले जाते हैं; पिछले नोड को खोजना नहीं पड़ता।
23सेपरेट चेनिंग हैश टकराव कैसे सुलझाती है?हर बकेट में उस इंडेक्स वाली प्रविष्टियों का संग्रह होता है, अक्सर लिंक्ड लिस्ट। एक बकेट में आने वाली अलग कुंजियाँ अलग प्रविष्टियाँ रहती हैं।
24सर्कुलर ऐरे क्यू किसी तत्व को निकालने के बाद खिसकाने से कैसे बचती है?आगे और पीछे के इंडेक्स क्षमता के मॉड्यूलो में घूमते हैं। निकालने पर आगे का इंडेक्स बढ़ता है, इसलिए खाली खाने बाकी तत्वों को हिलाए बिना दोबारा उपयोग होते हैं।
25n → ∞ होने पर इन वृद्धि दरों को धीमी से तेज़ क्रम में रखें: n!, n, 1, n², log n, 2ⁿ, n log n।आसिम्प्टोटिक क्रम: 1 < log n < n < n log n < n² < 2ⁿ < n!।
26AVL में जोड़ने से हुआ बायाँ-दायाँ असंतुलन कैसे सुधारा जाता है?पहले बाएँ बच्चे को बाएँ घुमाएँ; फिर असंतुलित नोड को दाएँ घुमाएँ।
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 सार्वभौमिक सीमा नहीं है।