एल्गोरिद्म, ग्राफ, गतिशील प्रोग्रामिंग और संबंधपरक डेटाबेस

क्रमण, ग्राफ एल्गोरिद्म, गतिशील प्रोग्रामिंग, SQL, इंडेक्स और लेनदेन पर स्नातक-स्तरीय पुनरावलोकन के 32 कार्ड। बुनियादी प्रोग्रामिंग, डेटा संरचनाओं और SQL का पूर्वज्ञान अपेक्षित है।

Category
Computer Science
Level
basic
Languages
hi → hi
Cards
32
Markdown
एल्गोरिद्म, ग्राफ, गतिशील प्रोग्रामिंग और संबंधपरक डेटाबेस (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1दो-चरणीय लॉकिंग (2PL) के दो चरण क्या हैं?वृद्धि चरण: लॉक छोड़े बिना हासिल करना। संकुचन चरण: नए लॉक लिए बिना छोड़ना। उपयुक्त टकराने वाले पठन/लेखन लॉक के साथ 2PL टकराव-क्रमिककरणीय अनुसूचियाँ सुनिश्चित करता है, लेकिन गतिरोध फिर भी संभव है।
2प्रथम, द्वितीय और तृतीय सामान्य रूप की शर्तें क्या हैं?1NF: गुणों के मान अविभाज्य हों। 2NF: 1NF हो और कोई गैर-प्रमुख गुण किसी भी प्रत्याशी कुंजी के ऐसे उपसमुच्चय पर निर्भर न हो जो पूरी कुंजी न हो। 3NF: 1NF हो और हर गैर-तुच्छ निर्भरता X→A में X सुपरकी हो या A प्रमुख गुण हो। प्रमुख गुण कम से कम एक प्रत्याशी कुंजी का सदस्य है।
3टोपोलॉजिकल क्रम क्या है और कान का एल्गोरिद्म उसे कैसे ढूँढ़ता है?निर्देशित अचक्रीय ग्राफ में हर किनारा u→v, u को v से पहले रखता है। बार-बार शून्य अंतःकोटि वाला शीर्ष निकालें, उसके बाहर जाने वाले किनारे हटाएँ और नए शून्य अंतःकोटि शीर्ष कतार में डालें। V से कम शीर्ष निकलें तो निर्देशित ग्राफ में चक्र है।
4लोभी एल्गोरिद्म और गतिशील प्रोग्रामिंग में क्या अंतर है?लोभी विधि स्थानीय चुनाव पर टिक जाती है और यह प्रमाण चाहिए कि ऐसे चुनाव इष्टतम हल को बनाए रखते हैं। DP पुनरावृत्ति से विकल्पों की तुलना करके उपसमस्या परिणाम फिर उपयोग करती है। वैश्विक इष्टतम के लिए सही मॉडल और पुनरावृत्ति चाहिए, केवल 'DP' नाम पर्याप्त नहीं।
5चौड़ाई-प्रथम खोज अभारित ग्राफ में न्यूनतम पथ कैसे ढूँढ़ती है?BFS पहले-आया-पहले-निकला कतार से शीर्षों को किनारों की संख्या के अनुसार दूरी-क्रम में खोजती है। कतार में डालते समय चिह्नित करने से दोबारा जाना बचता है। पहुँच योग्य शीर्ष तक पहली मिली राह में किनारों की संख्या न्यूनतम होती है।
6आसन्नता आव्यूह और सामान्य आसन्नता सूचियों की तुलना कैसे होती है?V शीर्षों और E किनारों के लिए आव्यूह O(V²) स्थान लेता है और किनारे की मौजूदगी O(1) में जाँचता है। सूचियाँ O(V+E) स्थान लेती हैं; बिना क्रम वाली सूची में किनारा (u,v) खोजने में O(deg(u)) लगता है, जहाँ deg(u) उस सूची की लंबाई है।
7क्रुस्कल और प्रिम एल्गोरिद्म न्यूनतम विस्तार वृक्ष कैसे बनाते हैं?संबद्ध अनिर्देशित भारित ग्राफ में क्रुस्कल बढ़ते भार-क्रम में किनारे देखता है और Union–Find से चक्र बनाने वाले किनारे अस्वीकार करता है। प्रिम वृक्ष के भीतर से बाहर के शीर्ष तक जाने वाला न्यूनतम भार का किनारा बार-बार चुनकर एक वृक्ष बढ़ाता है।
8इन-प्लेस हीप सॉर्ट की सबसे खराब समय और अतिरिक्त स्थान सीमाएँ क्या हैं?हीप बनाने में O(n), फिर सभी निष्कर्षणों में कुल O(n log n) काम लगता है। इनपुट ऐरे में पुनरावृत्त नीचे-खिसकाने की प्रक्रिया से हीप सॉर्ट का सबसे खराब समय O(n log n) और अतिरिक्त स्थान O(1) होता है।
9काउंटिंग सॉर्ट या रेडिक्स सॉर्ट कब रैखिक समय में चल सकते हैं?k संभव मानों की सीमा में n कुंजियों के लिए काउंटिंग सॉर्ट O(n+k) लेता है। आधार b और d स्थिर अंक-क्रमण चरणों वाला रेडिक्स सॉर्ट O(d(n+b)) लेता है। ये तभी रैखिक हैं जब ये प्राचल इसकी अनुमति दें; ये तुलना के अलावा कुंजी की संरचना का भी उपयोग करते हैं।
10किसी क्रमण एल्गोरिद्म का स्थिर होना क्या है?समान कुंजी वाले तत्व अपना मूल सापेक्ष क्रम बनाए रखते हैं। बराबरी पर बाएँ तत्व को पहले लेकर मर्ज सॉर्ट स्थिर बनाया जा सकता है; मानक इन-प्लेस क्विक सॉर्ट सामान्यतः अस्थिर है। स्थिरता कार्यान्वयन पर निर्भर करती है।
11SQL Server में क्लस्टर्ड और नॉनक्लस्टर्ड रो-स्टोर इंडेक्स में क्या अंतर है?क्लस्टर्ड इंडेक्स तालिका की पंक्तियाँ कुंजी-क्रम में रखता है, इसलिए प्रति तालिका अधिकतम एक होता है। नॉनक्लस्टर्ड इंडेक्स की अपनी कुंजियाँ और पंक्ति-स्थानसूचक होते हैं और उसमें अन्य स्तंभ भी हो सकते हैं। ये शब्द और भंडारण विवरण डेटाबेस प्रणालियों में बदलते हैं।
12मेमोइज़ेशन और नीचे से ऊपर की गतिशील प्रोग्रामिंग में क्या अंतर है?मेमोइज़ेशन आवश्यकता पड़ने पर उपसमस्याएँ हल करता है, सामान्यतः पुनरावर्ती ढंग से, और परिणाम सहेजता है। नीचे से ऊपर की DP अवस्थाएँ ऐसे क्रम में निकालती है कि निर्भर अवस्थाओं के परिणाम पहले से उपलब्ध हों; सामान्यतः सारणी भरी जाती है।
13समूहित क्वेरी में WHERE और HAVING में क्या अंतर है?WHERE समूह बनाने से पहले इनपुट पंक्तियाँ छाँटता है। HAVING बने समूह छाँटता है और COUNT(*)>1 जैसी समुच्चयन शर्तें लगा सकता है।
14पूर्णांक क्षमता W के मानक 0/1 नैपसैक की पुनरावृत्ति क्या है?D[i,w] पहले i सामानों से क्षमता w में मिलने वाला सर्वोत्तम मूल्य हो और भार wᵢ धनात्मक पूर्णांक हों। D[0,w]=0 रखें। wᵢ>w हो तो D[i−1,w] लें; अन्यथा max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]) लें। O(NW) समय छद्म-बहुपद समय है।
15गहराई-प्रथम खोज निर्देशित ग्राफ में चक्र कैसे पहचान सकती है?DFS पुनरावर्तन या स्पष्ट स्टैक से गहराई में जाती है। वर्तमान DFS पथ पर अभी सक्रिय शीर्ष तक जाने वाला किनारा पीछे जाने वाला किनारा है और निर्देशित चक्र सिद्ध करता है। किसी भी पहले देखे शीर्ष तक किनारा होना मात्र पर्याप्त नहीं।
16प्रविष्टि क्रमण कैसे काम करता है और लगभग क्रमबद्ध इनपुट पर उसका समय किससे तय होता है?यह हर तत्व को क्रमबद्ध आरंभिक भाग में डालता है। आसन्न स्थानांतरण या अदला-बदली वाला सामान्य संस्करण Θ(n+I) समय लेता है, जहाँ I उलटे क्रम वाले युग्मों की संख्या है। I=O(n) हो तो समय रैखिक है; केवल छोटा इनपुट सबसे खराब स्थिति की Θ(n²) सीमा नहीं बदलता।
17लेनदेन के ACID गुणों का क्या अर्थ है?परमाण्विकता: प्रभाव पूरे लागू हों या बिल्कुल न हों। संगति: सही लेनदेन प्रतिबंध और अनुप्रयोग के अपरिवर्तनीय नियम बनाए रखते हैं। पृथक्करण: समवर्ती व्यवहार चुने गए पृथक्करण स्तर का पालन करता है। स्थायित्व: कॉन्फ़िगर की गई डेटाबेस गारंटियों में आने वाली विफलताओं के बाद भी कमिट किए प्रभाव बने रहते हैं।
18क्विक सॉर्ट Θ(n²) समय क्यों ले सकता है और यादृच्छिकीकरण कैसे मदद करता है?बार-बार बहुत असंतुलित विभाजन, जैसे हर बार अलग कुंजियों में सबसे छोटी को पिवट चुनना, द्विघात काम कराते हैं। कुंजियाँ अलग हों या दोहराई कुंजियों का उपयुक्त प्रबंधन हो, तो यादृच्छिक पिवट से अपेक्षित समय O(n log n) होता है। तीन मानों की माध्यिका उपयोगी व्यावहारिक युक्ति है, सबसे खराब स्थिति की गारंटी नहीं।
19INNER JOIN और LEFT JOIN में क्या अंतर है?INNER JOIN जोड़ की शर्त पूरी करने वाले पंक्ति-संयोजन लौटाता है। LEFT JOIN बिना मेल वाली प्रत्येक बाईं पंक्ति भी रखता है और दाईं ओर के स्तंभों में NULL भरता है। कई दाईं पंक्तियों का मेल होने पर एक बाईं पंक्ति से कई आउटपुट पंक्तियाँ मिल सकती हैं।
20गैर-पुनरावर्तनीय पठन क्या है और कौन-सा मानक पृथक्करण स्तर उसे रोकता है?दूसरा लेनदेन अद्यतन या विलोपन कमिट कर दे, फिर वही पंक्ति दोबारा पढ़ने पर डेटा बदला मिले या पंक्ति गायब हो। REPEATABLE READ और SERIALIZABLE इस विसंगति को रोकते हैं।
21सामान्य समकालिक कमिट में PostgreSQL WAL स्थायित्व कैसे देता है?संबंधित लॉग रिकॉर्ड कमिट की पुष्टि से पहले और बदले डेटा पृष्ठ लिखे जाने से पहले टिकाऊ भंडारण तक पहुँचते हैं। क्रैश के बाद WAL उन परिवर्तनों को फिर लागू कर सकता है जो डेटा पृष्ठों में नहीं पहुँचे। अतुल्यकालिक कमिट में हाल में पुष्टि किए गए लेनदेन खो सकते हैं।
22B+ वृक्ष डेटाबेस इंडेक्स और परास क्वेरी के लिए उपयोगी क्यों हैं?अधिक शाखाएँ वृक्ष को कम गहरा रखकर पृष्ठ-अभिगम घटाती हैं। क्रमबद्ध कुंजियाँ और जुड़े पर्ण परास स्कैन में मदद करते हैं। हैश इंडेक्स समानता-आधारित खोज के लिए हैं; वे स्वभावतः वही क्रमबद्ध परास-अभिगम नहीं देते।
23डर्टी रीड क्या है और उसे रोकने वाला पहला मानक पृथक्करण स्तर कौन-सा है?दूसरे लेनदेन के अभी कमिट न हुए डेटा को पढ़ना, चाहे वह लेनदेन बाद में रोलबैक हो या न हो। READ COMMITTED और उससे मजबूत मानक पृथक्करण स्तर डर्टी रीड रोकते हैं।
24सबसे लंबे उभयनिष्ठ उपानुक्रम (LCS) की लंबाई के लिए गतिशील प्रोग्रामिंग पुनरावृत्ति क्या है?L[i,j], i और j लंबाई के आरंभिक भागों की LCS लंबाई हो। L[0,j]=L[i,0]=0 रखें। अंतिम अक्षर समान हों तो L[i,j]=1+L[i−1,j−1]; अन्यथा L[i,j]=max(L[i−1,j],L[i,j−1])। पूरी सारणी O(mn) समय और स्थान लेती है।
25फैंटम रीड क्या है और उसे कैसे रोका जाता है?दूसरे लेनदेन के परिवर्तन कमिट होने के बाद वही शर्त-आधारित क्वेरी दोहराने पर मेल खाने वाली पंक्तियों का समुच्चय बदल जाता है। मानक मॉडल में SERIALIZABLE इसे रोकता है; PostgreSQL REPEATABLE READ सहित कुछ कार्यान्वयन निचले स्तर पर भी रोकते हैं।
26बेलमैन–फोर्ड ऋणात्मक किनारों को कैसे संभालता है और पहुँच योग्य ऋणात्मक चक्र कैसे पहचानता है?सभी किनारों पर दूरी-सुधार अधिकतम V−1 बार करें। किसी पहुँच योग्य शीर्ष से एक और सुधार संभव हो तो स्रोत से पहुँच योग्य ऋणात्मक चक्र है। सबसे खराब समय O(VE) है; उस चक्र से पहुँच योग्य शीर्षों की कोई परिमित न्यूनतम-पथ लागत नहीं होती।
27गतिशील प्रोग्रामिंग कई अनुकूलन समस्याओं में उपयोगी क्यों है?इष्टतम उपसंरचना होने पर पूर्ण समस्या का इष्टतम हल उपसमस्याओं के इष्टतम हलों से व्यक्त किया जा सकता है। उपसमस्याएँ दोहरती हों तो उत्तर सहेजने से बार-बार का काम बचता है। अवस्थाएँ और पुनरावृत्ति संबंध मूल समस्या का सही निरूपण करें।
28द्विआधारी खोज के लिए क्या आवश्यक है और वह कब O(log n) समय लेती है?यह तुलना-क्रम में सजे डेटा के खोज-अंतराल को बार-बार आधा करती है। जिस ऐरे में सूचकांक से पहुँच O(1) और तुलना स्थिर समय की हो, उसके n तत्वों में खोज O(log n) समय लेती है।
29मानक ऐरे मर्ज सॉर्ट कैसे काम करता है और उसकी समय व स्थान सीमाएँ क्या हैं?यह दोनों आधों को पुनरावर्ती ढंग से क्रमबद्ध करके रैखिक समय में मिलाता है। स्थिर समय की तुलनाएँ मानने पर मानक संस्करण Θ(n log n) समय और O(n) सहायक स्थान लेता है।
30SQL SELECT क्वेरी का सरलीकृत तार्किक प्रक्रिया-क्रम क्या है?CTE, विंडो फलनों या समुच्चय संक्रियाओं के बिना: FROM/JOIN → WHERE → GROUP BY और समुच्चयन → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET। यह तार्किक मॉडल है, अनुकूलक का वास्तविक भौतिक निष्पादन-क्रम होना जरूरी नहीं।
31PostgreSQL में प्राथमिक कुंजी और बाह्य कुंजी में क्या अंतर है?प्राथमिक कुंजी अद्वितीय, गैर-NULL मानों से पंक्तियाँ पहचानती है। बाह्य कुंजी अपने NULL नियमों के अधीन संदर्भित कुंजी मानों से मेल माँगती है। वह उसी या दूसरी तालिका की उपयुक्त UNIQUE कुंजी या प्राथमिक कुंजी को संदर्भित कर सकती है।
32डाइकस्ट्रा का एल्गोरिद्म कब वैध है और सामान्य हीप-आधारित समय सीमा क्या है?किनारों के भार ऋणात्मक न हों तो यह न्यूनतम अस्थायी दूरी वाले शीर्ष को बार-बार अंतिम रूप देता है। आसन्नता सूची और द्विआधारी न्यूनतम हीप का कार्यान्वयन O((V+E) log V) लेता है। ऋणात्मक किनारे अंतिम दूरी के तर्क को अमान्य कर सकते हैं।