GKPAD.COM

ONLINE HINDI EDUCATION PORTAL

IGNOU MCS-021 Solved Question Paper PDF Download

The IGNOU MCS-021 Solved Question Paper PDF Download page is designed to help students access high-quality exam resources in one place. Here, you can find ignou solved question paper IGNOU Previous Year Question paper solved PDF that covers all important questions with detailed answers. This page provides IGNOU all Previous year Question Papers in one PDF format, making it easier for students to prepare effectively.

Whether you are looking for IGNOU Previous Year Question paper solved in English or ignou previous year question paper solved in hindi, this page offers both options to suit your learning needs. These solved papers help you understand exam patterns, improve answer writing skills, and boost confidence for upcoming exams.

IGNOU MCS-021 Solved Question Paper PDF

IGNOU Previous Year Solved Question Papers

This section provides IGNOU MCS-021 Solved Question Paper PDF in both Hindi and English. These ignou solved question paper IGNOU Previous Year Question paper solved PDF include detailed answers to help you understand exam patterns and improve your preparation. You can also access IGNOU all Previous year Question Papers in one PDF for quick and effective revision before exams.

IGNOU MCS-021 Previous Year Solved Question Paper in Hindi

Q1. (a) इस कथन को सही ठहराएं कि दो फलन f(n) और g(n) के लिए जैसे कि : f(n) = n2 + 38x + y और g(n) = n2 तब f(n) = O(g(n)), जहाँ O : बिग-ओ नोटेशन है। (b) निम्नलिखित के लिए एक एल्गोरिथम लिखें: (i) एक लिंक्ड सूची में यादृच्छिक स्थिति में एक तत्व डालें। (ii) एक लिंक्ड सूची की शुरुआत से एक तत्व हटाएं। (c) स्टैक क्या है? बताएं कि ऐरे का उपयोग करके स्टैक को कैसे लागू किया जा सकता है। (d) न्यूनतम लागत स्पैनिंग ट्री खोजने के लिए प्रिम का एल्गोरिथम लिखें और समझाएं। जटिलता के संदर्भ में एल्गोरिथम की व्याख्या करें।

Ans.

(a) बिग-ओ नोटेशन का औचित्य

बिग-ओ नोटेशन एक एल्गोरिथम की सबसे खराब स्थिति में प्रदर्शन या ऊपरी सीमा का वर्णन करता है। एक फलन f(n) को O(g(n)) कहा जाता है यदि धनात्मक स्थिरांक c और n 0 मौजूद हैं, जैसे कि सभी n ≥ n 0 के लिए 0 ≤ f(n) ≤ c * g(n) होता है।

दिए गए फलन हैं:

f(n) = n² + 38n + y (मान लें कि x, n है और y एक स्थिरांक है)

g(n) = n² हमें यह सिद्ध करना है कि f(n) = O(g(n)) है। इसके लिए, हमें स्थिरांक c और n₀ खोजने की आवश्यकता है ताकि n² + 38n + y ≤ c * n² सभी n ≥ n₀ के लिए सत्य हो। आइए असमानता को सरल करें:

n² + 38n + y ≤ c * n²

पूरी असमानता को n² से विभाजित करने पर (n > 0 के लिए):

1 + 38/n + y/n² ≤ c जैसे-जैसे n बढ़ता है, 38/n और y/n² दोनों पद शून्य के करीब आते हैं।

मान लीजिए हम n₀ = 1 चुनते हैं। तब n ≥ 1 के लिए:

  • 38/n ≤ 38
  • y/n² ≤ y (मान लें y > 0)

इसलिए, 1 + 38/n + y/n² ≤ 1 + 38 + y । अब, हम c = 39 + y चुन सकते हैं।

इस प्रकार, c = 39 + y और n₀ = 1 के लिए, असमानता f(n) ≤ c * g(n) सभी n ≥ n₀ के लिए सत्य है।

अतः, यह सिद्ध होता है कि f(n) = O(g(n)) है। इसका अर्थ है कि f(n) की वृद्धि दर n² से अधिक नहीं है।

(b) लिंक्ड लिस्ट एल्गोरिदम

(i) एक लिंक्ड सूची में यादृच्छिक (दी गई) स्थिति में एक तत्व डालना

यह एल्गोरिथम एक लिंक्ड सूची में दी गई ‘स्थिति’ पर एक नया नोड सम्मिलित करता है। ALGORITHM InsertAtPosition(head, data, position) 1. // एक नया नोड बनाएं 2. newNode = createNode(data) 3. 4. // यदि सूची खाली है या स्थिति 1 है (शुरुआत में डालना) 5. IF position == 1 THEN 6. newNode->next = head 7. head = newNode 8. RETURN head 9. ENDIF 10. 11. // सही स्थिति खोजने के लिए सूची में घूमें 12. temp = head 13. count = 1 14. WHILE temp != NULL AND count < position – 1 15. temp = temp->next 16. count = count + 1 17. ENDWHILE 18. 19. // यदि स्थिति मान्य है 20. IF temp == NULL THEN 21. PRINT “अमान्य स्थिति” 22. ELSE 23. newNode->next = temp->next 24. temp->next = newNode 25. ENDIF 26. 27. RETURN head (ii) एक लिंक्ड सूची की शुरुआत से एक तत्व हटाना

यह एल्गोरिथम सूची के पहले नोड को हटाता है। ALGORITHM DeleteFromBeginning(head) 1. // जांचें कि क्या सूची खाली है 2. IF head == NULL THEN 3. PRINT “सूची खाली है, कुछ भी हटाया नहीं जा सकता” 4. RETURN NULL 5. ENDIF 6. 7. // अगले नोड को नए हेड के रूप में स्टोर करें 8. temp = head->next 9. 10. // पुराने हेड को मुक्त करें 11. FREE(head) 12. 13. // नए हेड को वापस करें 14. RETURN temp

(c) स्टैक और ऐरे का उपयोग करके इसका कार्यान्वयन

एक स्टैक एक रैखिक डेटा संरचना है जो LIFO (लास्ट-इन, फर्स्ट-आउट) सिद्धांत का पालन करती है। इसका मतलब है कि जो तत्व सबसे अंत में डाला गया है, उसे सबसे पहले हटाया जाता है। इसे एक भौतिक स्टैक (जैसे किताबों का ढेर) के रूप में देखा जा सकता है, जहां आप केवल सबसे ऊपर से किताबें जोड़ या हटा सकते हैं। स्टैक के मुख्य संचालन:

  • Push: स्टैक के शीर्ष पर एक तत्व जोड़ता है।
  • Pop: स्टैक के शीर्ष से एक तत्व हटाता है और उसे वापस करता है।
  • Peek (या Top): स्टैक के शीर्ष तत्व को हटाए बिना वापस करता है।
  • isEmpty: जांचता है कि स्टैक खाली है या नहीं।

ऐरे का उपयोग करके स्टैक का कार्यान्वयन:

ऐरे का उपयोग करके स्टैक को लागू करने के लिए, हमें एक ऐरे और एक पूर्णांक चर ‘top’ की आवश्यकता होती है जो स्टैक के सबसे ऊपरी तत्व के सूचकांक को ट्रैक करता है। प्रारंभ में, जब स्टैक खाली होता है, तो ‘top’ को -1 पर सेट किया जाता है। // C-जैसी संरचना DEFINE MAX_SIZE 100 struct Stack { int items[MAX_SIZE]; int top; }; // आरंभीकरण void init(Stack *s) { s->top = -1; } // Push ऑपरेशन void push(Stack *s, int value) { IF s->top == MAX_SIZE – 1 THEN PRINT “स्टैक ओवरफ्लो” RETURN ENDIF s->top = s->top + 1 s->items[s->top] = value } // Pop ऑपरेशन int pop(Stack *s) { IF s->top == -1 THEN PRINT “स्टैक अंडरफ्लो” RETURN -1 // त्रुटि मान ENDIF int item = s->items[s->top] s->top = s->top – 1 RETURN item }

(d) प्रिम का एल्गोरिथम

प्रिम का एल्गोरिथम एक लालची (greedy) एल्गोरिथम है जिसका उपयोग एक जुड़े, अविभाजित और भारित ग्राफ के लिए न्यूनतम लागत स्पैनिंग ट्री (Minimum Cost Spanning Tree – MST) खोजने के लिए किया जाता है। MST एक सबग्राफ है जो ग्राफ के सभी वर्टिस को जोड़ता है, जिसमें कोई चक्र नहीं होता है और किनारों के कुल भार का योग न्यूनतम होता है। एल्गोरिथम के चरण: 1. आरंभ करें: एक सेट `mstSet` बनाएं जो MST में शामिल वर्टिस को ट्रैक करता है, प्रारंभ में यह खाली होता है। सभी वर्टिस के लिए ‘की’ (key) मानों को अनंत (infinity) पर सेट करें और पहले वर्टेक्स की ‘की’ को 0 पर सेट करें ताकि इसे पहले चुना जा सके। 2. पुनरावृति (Iterate): जब तक `mstSet` में सभी वर्टिस शामिल न हो जाएं: a. `mstSet` में नहीं मौजूद वर्टिस में से न्यूनतम ‘की’ मान वाले वर्टेक्स `u` को चुनें। b. वर्टेक्स `u` को `mstSet` में जोड़ें। c. `u` के सभी आसन्न वर्टिस `v` के लिए, यदि `v` `mstSet` में नहीं है और किनारे `(u, v)` का भार `v` के वर्तमान ‘की’ मान से कम है, तो `v` के ‘की’ मान को किनारे `(u, v)` के भार से अपडेट करें और `v` के पैरेंट के रूप में `u` को सेट करें। जटिलता (Complexity):

प्रिम के एल्गोरिथम की समय जटिलता इस बात पर निर्भर करती है कि न्यूनतम ‘की’ मान वाले वर्टेक्स को खोजने के लिए किस डेटा संरचना का उपयोग किया जाता है:

  • आसन्न मैट्रिक्स (Adjacency Matrix) और रैखिक खोज: यदि ग्राफ को आसन्न मैट्रिक्स के रूप में दर्शाया जाता है और न्यूनतम ‘की’ खोजने के लिए हम केवल ऐरे को स्कैन करते हैं, तो जटिलता O(V²) होती है, जहाँ V वर्टिस की संख्या है।
  • आसन्न सूची (Adjacency List) और बाइनरी हीप: यदि ग्राफ को आसन्न सूची के रूप में दर्शाया जाता है और न्यूनतम ‘की’ मानों को संग्रहीत करने के लिए बाइनरी हीप (प्राथमिकता कतार) का उपयोग किया जाता है, तो जटिलता O(E log V) होती है, जहाँ E किनारों की संख्या है। यह आमतौर पर विरल (sparse) ग्राफ के लिए अधिक कुशल होता है।

Q2. (a) मर्ज सॉर्ट के लिए एक एल्गोरिथम लिखें। डेटा के निम्नलिखित सेट को सॉर्ट करने के लिए इस एल्गोरिथम की चरण-दर-चरण कार्यप्रणाली लिखें: 7, 8, 25, 6, 4, 28, 2, 35 (b) AA ट्री क्या हैं? बताएं कि AA ट्री रेड-ब्लैक ट्री से कैसे भिन्न हैं।

Ans.

(a) मर्ज सॉर्ट एल्गोरिथम और कार्यप्रणाली

मर्ज सॉर्ट एक ‘डिवाइड एंड कॉन्कर’ (Divide and Conquer) एल्गोरिथम है। यह इनपुट ऐरे को दो हिस्सों में विभाजित करता है, खुद को दो हिस्सों के लिए रिकर्सिव रूप से कॉल करता है और फिर दो सॉर्ट किए गए हिस्सों को मर्ज करता है।

एल्गोरिथम:

ALGORITHM MergeSort(arr, left, right) 1. IF left < right THEN 2. // मध्य बिंदु का पता लगाएं 3. mid = left + (right – left) / 2 4. 5. // पहले और दूसरे आधे हिस्से को सॉर्ट करें 6. MergeSort(arr, left, mid) 7. MergeSort(arr, mid + 1, right) 8. 9. // सॉर्ट किए गए हिस्सों को मिलाएं 10. Merge(arr, left, mid, right) 11. ENDIF ALGORITHM Merge(arr, l, m, r) 1. // दो सब-ऐरे के आकार की गणना करें 2. n1 = m – l + 1 3. n2 = r – m 4. 5. // अस्थायी ऐरे बनाएं 6. CREATE L[n1], R[n2] 7. 8. // डेटा को अस्थायी ऐरे में कॉपी करें 9. FOR i = 0 TO n1-1 : L[i] = arr[l + i] 10. FOR j = 0 TO n2-1 : R[j] = arr[m + 1 + j] 11. 12. // अस्थायी ऐरे को वापस arr[l..r] में मर्ज करें 13. i = 0, j = 0, k = l 14. WHILE i < n1 AND j < n2 15. IF L[i] <= R[j] THEN 16. arr[k] = L[i] 17. i = i + 1 18. ELSE 19. arr[k] = R[j] 20. j = j + 1 21. ENDIF 22. k = k + 1 23. ENDWHILE 24. 25. // L[] और R[] में बचे हुए तत्वों को कॉपी करें 26. WHILE i < n1 : arr[k] = L[i]; i++; k++; ENDWHILE 27. WHILE j < n2 : arr[k] = R[j]; j++; k++; ENDWHILE डेटा सेट पर चरण-दर-चरण कार्यप्रणाली: `7, 8, 25, 6, 4, 28, 2, 35`

1. विभाजन चरण (Divide Phase):

  • `[7, 8, 25, 6, 4, 28, 2, 35]` को `[7, 8, 25, 6]` और `[4, 28, 2, 35]` में विभाजित किया जाता है।
  • `[7, 8, 25, 6]` को `[7, 8]` और `[25, 6]` में विभाजित किया जाता है।
  • `[7, 8]` को `[7]` और `[8]` में विभाजित किया जाता है।
  • `[25, 6]` को `[25]` और `[6]` में विभाजित किया जाता है।
  • `[4, 28, 2, 35]` को `[4, 28]` और `[2, 35]` में विभाजित किया जाता है।
  • `[4, 28]` को `[4]` और `[28]` में विभाजित किया जाता है।
  • `[2, 35]` को `[2]` और `[35]` में विभाजित किया जाता है।

2. विलय चरण (Merge Phase):

  • `[7]` और `[8]` को मर्ज करके `[7, 8]` बनता है।
  • `[25]` और `[6]` को मर्ज करके `[6, 25]` बनता है।
  • `[4]` और `[28]` को मर्ज करके `[4, 28]` बनता है।
  • `[2]` और `[35]` को मर्ज करके `[2, 35]` बनता है।
  • अब, `[7, 8]` और `[6, 25]` को मर्ज करके `[6, 7, 8, 25]` बनता है।
  • `[4, 28]` और `[2, 35]` को मर्ज करके `[2, 4, 28, 35]` बनता है।
  • अंत में, `[6, 7, 8, 25]` और `[2, 4, 28, 35]` को मर्ज करके अंतिम सॉर्टेड ऐरे बनता है:

अंतिम परिणाम: `[2, 4, 6, 7, 8, 25, 28, 35]`

(b) AA ट्री और रेड-ब्लैक ट्री

AA ट्री (AA Tree) एक प्रकार का संतुलित बाइनरी सर्च ट्री है, जिसे रेड-ब्लैक ट्री के एक सरल विकल्प के रूप में डिजाइन किया गया है। इसका नाम इसके आविष्कारक, Arne Andersson के नाम पर रखा गया है। AA ट्री रेड-ब्लैक ट्री की तुलना में लागू करने में आसान होते हैं क्योंकि उनमें पुनर्संतुलन (rebalancing) के मामले कम होते हैं। AA ट्री और रेड-ब्लैक ट्री में अंतर:

  1. संरचनात्मक नियम (Structural Rules):
    • AA ट्री: AA ट्री में, नोड्स में ‘रंग’ के बजाय एक ‘स्तर’ (level) होता है। रेड-ब्लैक ट्री में ‘रेड’ नोड के समान, AA ट्री में एक ‘हॉरिजॉन्टल लिंक’ होता है (जब एक चाइल्ड नोड का स्तर उसके पैरेंट के समान होता है)। AA ट्री में नियम अधिक सख्त हैं:
      • हॉरिजॉन्टल लिंक केवल दाएं हो सकते हैं; कोई बाएं हॉरिजॉन्टल लिंक नहीं हो सकता।
      • लगातार दो दाएं हॉरिजॉन्टल लिंक नहीं हो सकते।
    • रेड-ब्लैक ट्री: इसमें नियमों का एक जटिल सेट होता है, जिसमें शामिल है कि प्रत्येक नोड या तो लाल या काला होता है, रूट काला होता है, सभी पत्तियां (NIL) काली होती हैं, यदि कोई नोड लाल है तो उसके दोनों बच्चे काले होने चाहिए, और प्रत्येक नोड से उसकी किसी भी वंशज पत्तियों तक सभी रास्तों में समान संख्या में काले नोड होते हैं।
  2. पुनर्संतुलन संचालन (Rebalancing Operations):
    • AA ट्री: केवल दो पुनर्संतुलन संचालन का उपयोग करता है: `skew` (बाएं हॉरिजॉन्टल लिंक को ठीक करने के लिए) और `split` (दो लगातार दाएं हॉरिजॉन्टल लिंक को ठीक करने के लिए)। यह कार्यान्वयन को बहुत सरल बनाता है।
    • रेड-ब्लैक ट्री: पुनर्संतुलन के लिए अधिक जटिल संचालन की आवश्यकता होती है, जिसमें कई रोटेशन और री-कलरिंग मामले शामिल होते हैं।
  3. नोड डेटा (Node Data):
    • AA ट्री: प्रत्येक नोड अपने `स्तर` (एक पूर्णांक) को संग्रहीत करता है।
    • रेड-ब्लैक ट्री: प्रत्येक नोड अपना `रंग` (एक बिट, लाल/काला) संग्रहीत करता है।
  4. कार्यान्वयन जटिलता (Implementation Complexity):
    • AA ट्री: सरल नियमों और कम मामलों के कारण लागू करना आसान है।
    • रेड-ब्लैक ट्री: अधिक जटिल होने के कारण लागू करना अधिक कठिन है।

संक्षेप में, AA ट्री रेड-ब्लैक ट्री की जटिलता का एक सरलीकरण है, जो प्रदर्शन में थोड़ी कमी के बदले में कार्यान्वयन में आसानी प्रदान करता है।

Q3. (a) निम्नलिखित बहुपद फलन को संग्रहीत करने के लिए ‘C’ भाषा में एक प्रोग्राम लिखें: f(x) = ax² + bx + c, जहाँ a, b और c स्थिरांक हैं। (b) रैखिक खोज क्या है? बताएं कि क्या रैखिक खोज बाइनरी खोज से अधिक कुशल है। एक उपयुक्त उदाहरण के साथ अपने उत्तर का औचित्य सिद्ध करें।

Ans.

(a) बहुपद फलन को संग्रहीत करने के लिए ‘C’ प्रोग्राम

एक द्विघात बहुपद `f(x) = ax² + bx + c` को संग्रहीत करने का सबसे सीधा तरीका एक संरचना (structure) का उपयोग करना है जो तीन गुणांक (coefficients) `a`, `b`, और `c` को रखती है।

यहाँ ‘C’ भाषा में एक प्रोग्राम है जो इसे प्रदर्शित करता है: #include

// a के लिए पद if (p.a != 0) { printf(“%.2fx^2 “, p.a); } // b के लिए पद if (p.b != 0) { if (p.b > 0 && p.a != 0) printf(“+ “); printf(“%.2fx “, p.b); } // c के लिए पद if (p.c != 0) { if (p.c > 0 && (p.a != 0 || p.b != 0)) printf(“+ “); printf(“%.2f”, p.c); } printf(“\n”); } int main() { // एक बहुपद चर घोषित करें struct QuadraticPolynomial my_poly; // मान लीजिए हम बहुपद f(x) = 3x^2 – 5x + 2 को संग्रहीत करना चाहते हैं // यहाँ a=3.0, b=-5.0, c=2.0 float a_val = 3.0; float b_val = -5.0; float c_val = 2.0; // बहुपद बनाएं createPolynomial(&my_poly, a_val, b_val, c_val); // संग्रहीत बहुपद प्रदर्शित करें printf(“संग्रहीत बहुपद है:\n”); displayPolynomial(my_poly); return 0; } यह प्रोग्राम `struct QuadraticPolynomial` का उपयोग करके बहुपद के गुणांकों को कुशलतापूर्वक संग्रहीत करता है और इसे पठनीय प्रारूप में प्रदर्शित करता है।

(b) रैखिक खोज बनाम बाइनरी खोज

रैखिक खोज (Linear Search) , जिसे अनुक्रमिक खोज भी कहा जाता है, एक सूची में एक लक्ष्य मान खोजने की एक विधि है। यह सूची के प्रत्येक तत्व को क्रम में तब तक जांचता है जब तक कि लक्ष्य तत्व नहीं मिल जाता या पूरी सूची की खोज नहीं हो जाती। दक्षता की तुलना:

सामान्य तौर पर, रैखिक खोज बाइनरी खोज से कम कुशल है ।

  • बाइनरी खोज (Binary Search): इसकी समय जटिलता O(log n) है। यह बहुत तेज़ है क्योंकि यह प्रत्येक चरण में खोज स्थान को आधा कर देता है। हालाँकि, इसकी एक महत्वपूर्ण शर्त है: सूची को सॉर्ट किया जाना चाहिए ।
  • रैखिक खोज (Linear Search): इसकी सबसे खराब और औसत समय जटिलता O(n) है। यह बाइनरी खोज की तुलना में बहुत धीमी है, खासकर बड़ी सूचियों के लिए।

तो, क्या रैखिक खोज कभी भी अधिक कुशल हो सकती है? हाँ, कुछ विशिष्ट परिदृश्यों में:

  1. अव्यवस्थित डेटा (Unsorted Data): यदि डेटा सॉर्ट नहीं किया गया है, तो बाइनरी खोज लागू नहीं की जा सकती है। डेटा को पहले सॉर्ट करने (उदा. O(n log n) समय में) और फिर बाइनरी खोज (O(log n)) करने में कुल समय O(n log n) लगेगा, जो केवल रैखिक खोज (O(n)) करने से बहुत अधिक है। इस मामले में, रैखिक खोज अधिक कुशल विकल्प है।
  2. बहुत छोटी सूचियाँ (Very Small Lists): बहुत छोटी सूचियों के लिए (उदाहरण के लिए, 10 से कम तत्व), रैखिक खोज का सरल लूप बाइनरी खोज के अधिक जटिल तर्क (मध्य बिंदु की गणना, आदि) की तुलना में ओवरहेड के कारण वास्तव में तेज़ हो सकता है।
  3. डेटा संरचना (Data Structure): रैखिक खोज केवल अनुक्रमिक पहुंच (sequential access) की मांग करती है, इसलिए यह लिंक्ड लिस्ट जैसी डेटा संरचनाओं पर अच्छी तरह से काम करती है। बाइनरी खोज के लिए रैंडम एक्सेस (O(1) समय में किसी भी तत्व तक पहुंच) की आवश्यकता होती है, जो ऐरे के लिए तो संभव है लेकिन लिंक्ड लिस्ट के लिए नहीं।

उदाहरण के साथ औचित्य:

मान लीजिए हमें एक ऐरे में तत्व `60` खोजना है। केस 1: अव्यवस्थित ऐरे

ऐरे: `[20, 50, 10, 80, 60, 30]`

  • रैखिक खोज: 20, 50, 10, 80 की जाँच करेगा, और फिर 5वें प्रयास में `60` मिलेगा। (5 तुलनाएँ)
  • बाइनरी खोज: सीधे लागू नहीं किया जा सकता। यदि हम इसे सॉर्ट करते हैं: `[10, 20, 30, 50, 60, 80]` (जिसमें समय लगता है), तो बाइनरी खोज काम करेगी। लेकिन केवल एक खोज के लिए, सॉर्टिंग का ओवरहेड रैखिक खोज को बेहतर विकल्प बनाता है।

केस 2: सॉर्टेड ऐरे

ऐरे: `[10, 20, 30, 50, 60, 80, 90, 100]` (n=8)

  • रैखिक खोज: 10, 20, 30, 50 की जाँच करेगा, और 5वें प्रयास में `60` मिलेगा। (5 तुलनाएँ)
  • बाइनरी खोज: 1. मध्य की जाँच करें: `50`। (60 > 50, तो दाईं ओर खोजें) 2. नए मध्य की जाँच करें: `80`। (60 < 80, तो बाईं ओर खोजें) 3. `60` की जाँच करें। मिल गया। (3 तुलनाएँ)

इस उदाहरण में, बाइनरी खोज सॉर्टेड ऐरे पर स्पष्ट रूप से तेज है। निष्कर्ष: बाइनरी खोज सामान्य रूप से बहुत अधिक कुशल है, लेकिन रैखिक खोज अव्यवस्थित डेटा या बहुत छोटे डेटा सेट के लिए एक बेहतर और “अधिक कुशल” विकल्प है।

Q4. (a) निम्नलिखित बाइनरी ट्री को प्री-ऑर्डर और पोस्ट-ऑर्डर में ट्रैवर्स करें: [Image of a binary tree] (b) एक AVL ट्री क्या है? एक उपयुक्त उदाहरण की सहायता से AVL में नोड्स के सम्मिलन की व्याख्या करें।

Ans.

(a) बाइनरी ट्री ट्रैवर्सल

दिया गया बाइनरी ट्री:

A / \ B C / \ / \ D E F G / / \ H I J

1. प्री-ऑर्डर ट्रैवर्सल (Pre-order Traversal): नियम: (रूट) -> (बायां सबट्री) -> (दायां सबट्री) इस नियम का पालन करते हुए, ट्रैवर्सल इस प्रकार होगा:

  1. A (रूट) पर जाएँ।
  2. A के बाएं सबट्री (B) पर जाएँ।
  3. B (रूट) पर जाएँ।
  4. B के बाएं सबट्री (D) पर जाएँ।
  5. D (रूट) पर जाएँ।
  6. D के बाएं सबट्री (H) पर जाएँ। H पर जाएँ।
  7. D के दाएं सबट्री पर जाएँ (कोई नहीं)।
  8. B के दाएं सबट्री (E) पर जाएँ।
  9. E (रूट) पर जाएँ।
  10. E के बाएं सबट्री (I) पर जाएँ। I पर जाएँ।
  11. E के दाएं सबट्री पर जाएँ (कोई नहीं)।
  12. A के दाएं सबट्री (C) पर जाएँ।
  13. C (रूट) पर जाएँ।
  14. C के बाएं सबट्री (F) पर जाएँ। F पर जाएँ।
  15. C के दाएं सबट्री (G) पर जाएँ।
  16. G (रूट) पर जाएँ।
  17. G के बाएं सबट्री पर जाएँ (कोई नहीं)।
  18. G के दाएं सबट्री (J) पर जाएँ। J पर जाएँ।

प्री-ऑर्डर ट्रैवर्सल परिणाम: A, B, D, H, E, I, C, F, G, J

2. पोस्ट-ऑर्डर ट्रैवर्सल (Post-order Traversal): नियम: (बायां सबट्री) -> (दायां सबट्री) -> (रूट) इस नियम का पालन करते हुए, ट्रैवर्सल इस प्रकार होगा:

  1. A के बाएं सबट्री (B) में गहराई तक जाएँ।
  2. B के बाएं सबट्री (D) में गहराई तक जाएँ।
  3. D के बाएं सबट्री (H) में जाएँ। H पर जाएँ।
  4. D के दाएं सबट्री पर जाएँ (कोई नहीं), फिर D पर जाएँ।
  5. B के दाएं सबट्री (E) में जाएँ।
  6. E के बाएं सबट्री (I) में जाएँ। I पर जाएँ।
  7. E के दाएं सबट्री पर जाएँ (कोई नहीं), फिर E पर जाएँ।
  8. अब B के दोनों बच्चे हो गए, तो B पर जाएँ।
  9. A के दाएं सबट्री (C) में जाएँ।
  10. C के बाएं सबट्री (F) में जाएँ। F पर जाएँ।
  11. C के दाएं सबट्री (G) में जाएँ।
  12. G के बाएं सबट्री पर जाएँ (कोई नहीं)।
  13. G के दाएं सबट्री (J) में जाएँ। J पर जाएँ।
  14. अब G पर जाएँ।
  15. अब C के दोनों बच्चे हो गए, तो C पर जाएँ।
  16. अंत में, रूट A पर जाएँ।

पोस्ट-ऑर्डर ट्रैवर्सल परिणाम: H, D, I, E, B, F, J, G, C, A

(b) AVL ट्री और नोड सम्मिलन

AVL ट्री (AVL Tree) एक स्व-संतुलित बाइनरी सर्च ट्री (self-balancing binary search tree) है, जिसका नाम इसके आविष्कारकों, Adelson-Velsky और Landis के नाम पर रखा गया है। AVL ट्री में, किसी भी नोड के लिए, उसके बाएं और दाएं सबट्री की ऊंचाई में अधिकतम 1 का अंतर हो सकता है। इस अंतर को संतुलन कारक (Balance Factor – BF) कहा जाता है। BF = height(बायां सबट्री) – height(दायां सबट्री) एक AVL ट्री में प्रत्येक नोड का BF -1, 0, या 1 होना चाहिए। AVL ट्री में नोड्स का सम्मिलन: AVL ट्री में एक नोड डालने में दो चरण होते हैं: 1. मानक BST सम्मिलन: नोड को उसी तरह डाला जाता है जैसे एक मानक बाइनरी सर्च ट्री में, यह सुनिश्चित करते हुए कि BST संपत्ति बनी रहे। 2. पुनर्संतुलन (Rebalancing): सम्मिलन के बाद, हम नए डाले गए नोड से रूट तक पथ पर वापस जाते हैं। हम प्रत्येक नोड के संतुलन कारक की जांच करते हैं। यदि कोई नोड असंतुलित हो जाता है (BF = -2 या 2), तो ट्री को संतुलित करने के लिए रोटेशन (rotations) का उपयोग किया जाता है। चार प्रकार के रोटेशन मामले हैं:

  • LL (Left-Left) केस: एक राइट रोटेशन की आवश्यकता है।
  • RR (Right-Right) केस: एक लेफ्ट रोटेशन की आवश्यकता है।
  • LR (Left-Right) केस: पहले एक लेफ्ट रोटेशन और फिर एक राइट रोटेशन की आवश्यकता है।
  • RL (Right-Left) केस: पहले एक राइट रोटेशन और फिर एक लेफ्ट रोटेशन की आवश्यकता है।

उदाहरण: एक खाली AVL ट्री में 10, 20, और 30 डालें।

1. 10 डालें:

10 (BF=0)

2. 20 डालें: (20 > 10, इसलिए 10 के दाईं ओर जाता है)

10 (BF=-1) \ 20 (BF=0) ट्री अभी भी संतुलित है।

3. 30 डालें: (30 > 20, इसलिए 20 के दाईं ओर जाता है)

10 (BF=-2) <– असंतुलित! \ 20 (BF=-1) \ 30 (BF=0) अब, नोड 10 का संतुलन कारक -2 है (`height(L)-height(R) = -1 – 1 = -2`)। यह एक असंतुलन है।

यह एक RR (Right-Right) केस है क्योंकि नया नोड (30) असंतुलित नोड (10) के दाएं बच्चे (20) के दाएं सबट्री में डाला गया है।

इसे ठीक करने के लिए, हम असंतुलित नोड (10) पर एक एकल लेफ्ट रोटेशन (single left rotation) करते हैं। लेफ्ट रोटेशन (10 पर):

  • 20 नया रूट बन जाता है।
  • 10, 20 का बायां बच्चा बन जाता है।

परिणामी संतुलित AVL ट्री:

20 (BF=0) / \ 10(BF=0) 30(BF=0) अब ट्री फिर से AVL संपत्ति का पालन करता है।

Q5. (a) उदाहरण का उपयोग करके एक ग्राफ के लिए ब्रेड्थ फर्स्ट सर्च (BFS) की व्याख्या करें। (b) एक सर्कुलर लिंक्ड लिस्ट क्या है? एक सर्कुलर लिंक्ड लिस्ट बनाने और उसमें से एक तत्व को हटाने के लिए एक एल्गोरिथम लिखें।

Ans.

(a) ब्रेड्थ फर्स्ट सर्च (BFS)

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

BFS एल्गोरिथम: 1. एक खाली क्यू `Q` और एक खाली `visited` सेट बनाएं। 2. शुरूआती वर्टेक्स `s` को `Q` में डालें और इसे `visited` के रूप में चिह्नित करें। 3. जब तक `Q` खाली न हो जाए: a. `Q` से एक वर्टेक्स `u` को डीक्यू (dequeue) करें। b. `u` को प्रोसेस करें (जैसे, इसे प्रिंट करें)। c. `u` के प्रत्येक पड़ोसी `v` के लिए: i. यदि `v` को `visited` नहीं किया गया है:

  • `v` को `visited` के रूप में चिह्नित करें।
  • `v` को `Q` में एनक्यू (enqueue) करें।

उदाहरण:

निम्नलिखित ग्राफ पर विचार करें: A — B | \ | | \ | C — D — E मान लीजिए हम वर्टेक्स A से BFS शुरू करते हैं।

  • चरण 1: A से शुरू करें। A को क्यू में डालें और इसे विज़िटेड के रूप में चिह्नित करें। क्यू: `[A]` विज़िटेड: `{A}` आउटपुट: `A`
  • चरण 2: A को डीक्यू करें। A के सभी अविज़िटेड पड़ोसियों (B, C, D) को क्यू में डालें और उन्हें विज़िटेड के रूप में चिह्नित करें। क्यू: `[B, C, D]` विज़िटेड: `{A, B, C, D}` आउटपुट: `A, B`
  • चरण 3: B को डीक्यू करें। B के अविज़िटेड पड़ोसियों (E) को क्यू में डालें और विज़िटेड के रूप में चिह्नित करें। (A और D पहले से ही विज़िटेड हैं)। क्यू: `[C, D, E]` विज़िटेड: `{A, B, C, D, E}` आउटपुट: `A, B, C`
  • चरण 4: C को डीक्यू करें। C के सभी पड़ोसी (A, D) पहले से ही विज़िटेड हैं। क्यू: `[D, E]` विज़िटेड: `{A, B, C, D, E}` आउटपुट: `A, B, C, D`
  • चरण 5: D को डीक्यू करें। D के सभी पड़ोसी (A, C, E) पहले से ही विज़िटेड हैं। क्यू: `[E]` विज़िटेड: `{A, B, C, D, E}` आउटपुट: `A, B, C, D, E`
  • चरण 6: E को डीक्यू करें। E के सभी पड़ोसी (B, D) पहले से ही विज़िटेड हैं। क्यू: `[]` (खाली)

क्यू अब खाली है, इसलिए एल्गोरिथम समाप्त हो जाता है। BFS ट्रैवर्सल क्रम है: A, B, C, D, E ।

(b) सर्कुलर लिंक्ड लिस्ट

एक सर्कुलर लिंक्ड लिस्ट एक लिंक्ड लिस्ट का एक प्रकार है जहां अंतिम नोड का `next` पॉइंटर NULL की ओर इंगित नहीं करता है, बल्कि यह सूची के पहले नोड (हेड) की ओर वापस इंगित करता है, जिससे एक वृत्ताकार लूप बनता है। एक सर्कुलर लिंक्ड लिस्ट बनाने के लिए एल्गोरिथम:

यह एल्गोरिथम सूची के अंत में नोड्स जोड़कर एक सर्कुलर लिंक्ड लिस्ट बनाता है। हम एक `last` पॉइंटर का उपयोग करेंगे जो सूची के अंतिम नोड को इंगित करता है। `last->next` हमेशा पहले नोड को इंगित करेगा। ALGORITHM AddToEnd(last, data) 1. newNode = createNode(data) 2. 3. // यदि सूची खाली है 4. IF last == NULL THEN 5. last = newNode 6. newNode->next = last // खुद को इंगित करें 7. ELSE 8. newNode->next = last->next // नया नोड पुराने पहले नोड को इंगित करता है 9. last->next = newNode // पुराना अंतिम नोड नए नोड को इंगित करता है 10. last = newNode // ‘last’ को नए नोड में अपडेट करें 11. ENDIF 12. RETURN last एक सर्कुलर लिंक्ड लिस्ट से एक तत्व हटाने के लिए एल्गोरिथम:

यह एल्गोरिथम एक दिए गए `key` वाले नोड को हटाता है। ALGORITHM DeleteNode(last, key) 1. // यदि सूची खाली है 2. IF last == NULL THEN RETURN NULL 3. 4. current = last->next // पहला नोड 5. prev = last 6. 7. // नोड को खोजें 8. REPEAT 9. IF current->data == key THEN 10. // नोड मिल गया, अब इसे हटाएं 11. IF current == last AND current->next == last THEN // केवल एक नोड 12. last = NULL 13. FREE(current) 14. RETURN last 15. ENDIF 16. 17. // यदि नोड अंतिम नोड है 18. IF current == last THEN 19. last = prev 20. ENDIF 21. 22. prev->next = current->next 23. FREE(current) 24. RETURN last 25. 26. ENDIF 27. prev = current 28. current = current->next 29. UNTIL current != last->next 30. 31. PRINT “तत्व नहीं मिला” 32. RETURN last

IGNOU MCS-021 Previous Year Solved Question Paper in English

Q1. (a) Justify the statement that for two functions f(n) and g(n) such that : f(n) = n² + 38x + y and g(n) = n² Then f(n) = O(g(n)), where O : Big-O notation. (b) Write an algorithm for the following : (i) Insert an element at random position in a linked list. (ii) Delete an element from the beginning of a linked list. (c) What is stack ? Explain how the stack can be implemented using arrays. (d) Write and explain Prim’s algorithm for finding minimum cost spanning tree. Explain the algorithm in terms of complexity.

Ans. (a) Justification of Big-O Notation Big-O notation describes the upper bound or worst-case performance of an algorithm. A function f(n) is said to be O(g(n)) if there exist positive constants c and n 0 such that 0 ≤ f(n) ≤ c * g(n) for all n ≥ n 0 .

Given the functions: f(n) = n² + 38n + y (assuming x is n and y is a constant) g(n) = n²

We need to prove that f(n) = O(g(n)) . To do this, we need to find constants c and n₀ such that n² + 38n + y ≤ c * n² holds for all n ≥ n₀ .

Let’s simplify the inequality: n² + 38n + y ≤ c * n² Dividing the entire inequality by n² (for n > 0): 1 + 38/n + y/n² ≤ c

As n increases, both the terms 38/n and y/n² approach zero. Let’s choose n₀ = 1 . For n ≥ 1, we have:

  • 38/n ≤ 38
  • y/n² ≤ y (assuming y > 0)

Therefore,

1 + 38/n + y/n² ≤ 1 + 38 + y

.

Now, we can choose c = 39 + y . Thus, for c = 39 + y and n₀ = 1, the inequality f(n) ≤ c * g(n) is true for all n ≥ n₀ . Hence, it is justified that f(n) = O(g(n)) . This means the growth rate of f(n) is no more than the growth rate of n².

(b) Linked List Algorithms (i) Insert an element at a random (given) position in a linked list This algorithm inserts a new node at a given ‘position’ in the linked list. 

ALGORITHM InsertAtPosition(head, data, position)1. // Create a new node2. newNode = createNode(data)3. 4. // If list is empty or insertion is at the beginning (position 1)5. IF position == 1 THEN6. newNode->next = head7. head = newNode8. RETURN head9. ENDIF10. 11. // Traverse the list to find the correct position12. temp = head13. count = 114. WHILE temp != NULL AND count < position - 115. temp = temp->next16. count = count + 117. ENDWHILE18. 19. // If the position is valid20. IF temp == NULL THEN21. PRINT "Invalid position"22. ELSE23. newNode->next = temp->next24. temp->next = newNode25. ENDIF26. 27. RETURN head

(ii) Delete an element from the beginning of a linked list This algorithm removes the first node of the list. 

ALGORITHM DeleteFromBeginning(head)1. // Check if the list is empty2. IF head == NULL THEN3. PRINT "List is empty, cannot delete"4. RETURN NULL5. ENDIF6. 7. // Store the next node as the new head8. temp = head->next9. 10. // Free the old head11. FREE(head)12. 13. // Return the new head14. RETURN temp

(c) Stack and Its Implementation Using an Array A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means the element that is inserted last is the first one to be removed. It can be visualized as a physical stack (like a stack of plates), where you can only add or remove plates from the top.

Main Operations of a Stack:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the element from the top of the stack.
  • Peek (or Top): Returns the top element of the stack without removing it.
  • isEmpty: Checks if the stack is empty.

Implementation of Stack using Array: To implement a stack using an array, we need an array and an integer variable ‘top’ that tracks the index of the topmost element of the stack. Initially, when the stack is empty, ‘top’ is set to -1. 

// C-like structureDEFINE MAX_SIZE 100struct Stack { int items[MAX_SIZE]; int top;};
// Initializationvoid init(Stack *s) { s->top = -1;}
// Push operationvoid push(Stack *s, int value) { IF s->top == MAX_SIZE - 1 THEN PRINT "Stack Overflow" RETURN ENDIF s->top = s->top + 1 s->items[s->top] = value}
// Pop operationint pop(Stack *s) { IF s->top == -1 THEN PRINT "Stack Underflow" RETURN -1 // Error value ENDIF int item = s->items[s->top] s->top = s->top - 1 RETURN item}

(d) Prim’s Algorithm Prim’s algorithm is a greedy algorithm used to find a Minimum Cost Spanning Tree (MST) for a connected, undirected, and weighted graph. An MST is a subgraph that connects all the vertices of the graph, with no cycles and the minimum possible total edge weight.

Steps of the Algorithm: 1. Initialize: Create a set `mstSet` to track vertices included in the MST, initially empty. Set ‘key’ values for all vertices to infinity and the ‘key’ of the first vertex to 0 so it’s picked first. 2. Iterate: While `mstSet` doesn’t include all vertices: a. Pick a vertex `u` not in `mstSet` that has the minimum ‘key’ value. b. Add vertex `u` to `mstSet`. c. For all adjacent vertices `v` of `u`, if `v` is not in `mstSet` and the weight of edge `(u, v)` is less than the current ‘key’ value of `v`, then update the ‘key’ value of `v` to the weight of edge `(u, v)` and set the parent of `v` as `u`.

Complexity: The time complexity of Prim’s algorithm depends on the data structure used to find the vertex with the minimum ‘key’ value:

  • Adjacency Matrix and Linear Search: If the graph is represented as an adjacency matrix and we simply scan the array to find the minimum ‘key’, the complexity is O(V²) , where V is the number of vertices.
  • Adjacency List and Binary Heap: If the graph is represented as an adjacency list and a binary heap (priority queue) is used to store the minimum ‘key’ values, the complexity is O(E log V) , where E is the number of edges. This is generally more efficient for sparse graphs.

Q2. (a) Write an algorithm for merge sort. Write step-by-step working of this algorithm for sorting the following set of data : 7, 8, 25, 6, 4, 28, 2, 35 (b) What is AA trees ? Explain how AA trees differs from Red-Black tree.

Ans. (a) Merge Sort Algorithm and Working Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Algorithm: 

ALGORITHM MergeSort(arr, left, right)1. IF left < right THEN2. // Find the middle point3. mid = left + (right - left) / 24. 5. // Sort first and second halves6. MergeSort(arr, left, mid)7. MergeSort(arr, mid + 1, right)8. 9. // Merge the sorted halves10. Merge(arr, left, mid, right)11. ENDIF
ALGORITHM Merge(arr, l, m, r)1. // Calculate sizes of two sub-arrays2. n1 = m - l + 13. n2 = r - m4. 5. // Create temp arrays6. CREATE L[n1], R[n2]7. 8. // Copy data to temp arrays9. FOR i = 0 TO n1-1 : L[i] = arr[l + i]10. FOR j = 0 TO n2-1 : R[j] = arr[m + 1 + j]11. 12. // Merge the temp arrays back into arr[l..r]13. i = 0, j = 0, k = l14. WHILE i < n1 AND j < n215. IF L[i] <= R[j] THEN16. arr[k] = L[i]17. i = i + 118. ELSE19. arr[k] = R[j]20. j = j + 121. ENDIF22. k = k + 123. ENDWHILE24. 25. // Copy remaining elements of L[] and R[]26. WHILE i < n1 : arr[k] = L[i]; i++; k++; ENDWHILE27. WHILE j < n2 : arr[k] = R[j]; j++; k++; ENDWHILE

Step-by-step working on data set: `7, 8, 25, 6, 4, 28, 2, 35` 1. Divide Phase:

  • `[7, 8, 25, 6, 4, 28, 2, 35]` is divided into `[7, 8, 25, 6]` and `[4, 28, 2, 35]`.
  • `[7, 8, 25, 6]` is divided into `[7, 8]` and `[25, 6]`.
  • `[7, 8]` is divided into `[7]` and `[8]`.
  • `[25, 6]` is divided into `[25]` and `[6]`.
  • `[4, 28, 2, 35]` is divided into `[4, 28]` and `[2, 35]`.
  • `[4, 28]` is divided into `[4]` and `[28]`.
  • `[2, 35]` is divided into `[2]` and `[35]`.


2. Merge Phase:

  • Merge `[7]` and `[8]` to get `[7, 8]`.
  • Merge `[25]` and `[6]` to get `[6, 25]`.
  • Merge `[4]` and `[28]` to get `[4, 28]`.
  • Merge `[2]` and `[35]` to get `[2, 35]`.
  • Now, merge `[7, 8]` and `[6, 25]` to get `[6, 7, 8, 25]`.
  • Merge `[4, 28]` and `[2, 35]` to get `[2, 4, 28, 35]`.
  • Finally, merge `[6, 7, 8, 25]` and `[2, 4, 28, 35]` to get the final sorted array:


Final result: `[2, 4, 6, 7, 8, 25, 28, 35]`

(b) AA Trees and Red-Black Trees An AA tree is a type of balanced binary search tree designed to be a simpler alternative to Red-Black trees. It was named after its inventor, Arne Andersson. AA trees are easier to implement than Red-Black trees because they have fewer rebalancing cases.

Differences between AA Trees and Red-Black Trees:

  1. Structural Rules:
    • AA Tree: In an AA tree, nodes have a ‘level’ instead of a ‘color’. A ‘horizontal link’ in an AA tree (when a child node is at the same level as its parent) is analogous to a ‘red’ node in a Red-Black tree. The rules in an AA tree are stricter:
      • Horizontal links can only be to the right; there can be no left horizontal links.
      • There cannot be two consecutive right horizontal links.
    • Red-Black Tree: It has a more complex set of rules, including that every node is either red or black, the root is black, all leaves (NIL) are black, if a node is red, then both its children must be black, and every path from a given node to any of its descendant leaves contains the same number of black nodes.
  2. Rebalancing Operations:
    • AA Tree: Uses only two rebalancing operations: `skew` (to fix left horizontal links) and `split` (to fix two consecutive right horizontal links). This greatly simplifies implementation.
    • Red-Black Tree: Requires more complex operations for rebalancing, involving numerous rotation and re-coloring cases.
  3. Node Data:
    • AA Tree: Each node stores its `level` (an integer).
    • Red-Black Tree: Each node stores its `color` (a single bit, red/black).
  4. Implementation Complexity:
    • AA Tree: Easier to implement due to simpler rules and fewer cases.
    • Red-Black Tree: More difficult to implement due to its complexity.

In essence, the AA tree is a simplification of the complexity of the Red-Black tree, trading a small amount of performance for ease of implementation.

Q3. (a) Write a program in ‘C’ language to store the following polynomial function : f(x) = ax² + bx + c, where a, b and c are constants. (b) What is a linear search ? Explain whether linear search is more efficient than binary search. Justify your answer with an suitable example.

Ans. (a) ‘C’ Program to Store a Polynomial Function The most straightforward way to store a quadratic polynomial `f(x) = ax² + bx + c` is to use a structure that holds the three coefficients `a`, `b`, and `c`.

Here is a ‘C’ program demonstrating this: 

#include <stdio.h>
// A structure to represent the quadratic polynomial ax^2 + bx + cstruct QuadraticPolynomial { float a; // coefficient for x^2 float b; // coefficient for x float c; // constant term};
// Function to create and initialize a polynomialvoid createPolynomial(struct QuadraticPolynomial *p, float coeff_a, float coeff_b, float coeff_c) { p->a = coeff_a; p->b = coeff_b; p->c = coeff_c;}
// Function to display the polynomialvoid displayPolynomial(struct QuadraticPolynomial p) { // Handling conditions for pretty printing printf("f(x) = "); // Term for a if (p.a != 0) { printf("%.2fx^2 ", p.a); }
 // Term for b if (p.b != 0) { if (p.b > 0 && p.a != 0) printf("+ "); printf("%.2fx ", p.b); }
 // Term for c if (p.c != 0) { if (p.c > 0 && (p.a != 0 || p.b != 0)) printf("+ "); printf("%.2f", p.c); } printf("\n");}
int main() { // Declare a polynomial variable struct QuadraticPolynomial my_poly;
 // Let's store the polynomial f(x) = 3x^2 - 5x + 2 // Here a=3.0, b=-5.0, c=2.0 float a_val = 3.0; float b_val = -5.0; float c_val = 2.0;
 // Create the polynomial createPolynomial(&my_poly, a_val, b_val, c_val);
 // Display the stored polynomial printf("The stored polynomial is:\n"); displayPolynomial(my_poly);
 return 0;}

This program efficiently stores the coefficients of the polynomial using `struct QuadraticPolynomial` and displays it in a readable format.

(b) Linear Search vs. Binary Search Linear search , also known as sequential search, is a method for finding a target value within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

Efficiency Comparison: In general, linear search is less efficient than binary search .

  • Binary Search: Has a time complexity of O(log n) . It is very fast as it halves the search space with each step. However, it has a crucial prerequisite: the list must be sorted .
  • Linear Search: Has a worst-case and average time complexity of O(n) . This is much slower than binary search, especially for large lists.

So, can linear search ever be more efficient? Yes, in a few specific scenarios:

  1. Unsorted Data: If the data is not sorted, binary search cannot be applied. The total time to first sort the data (e.g., in O(n log n) time) and then perform a binary search (O(log n)) would be O(n log n), which is much more than just performing a linear search (O(n)). In this case, linear search is the more efficient choice.
  2. Very Small Lists: For extremely small lists (e.g., fewer than 10 elements), the simple loop of a linear search might actually be faster than the more complex logic of binary search (calculating mid-point, etc.) due to overhead.
  3. Data Structure: Linear search only requires sequential access, so it works well on data structures like linked lists. Binary search requires random access (access to any element in O(1) time), which is possible for arrays but not for linked lists.

Justification with an Example: Suppose we need to find the element `60` in an array.

Case 1: Unsorted Array Array: `[20, 50, 10, 80, 60, 30]`

  • Linear Search: Will check 20, 50, 10, 80, and then find `60` on the 5th attempt. (5 comparisons)
  • Binary Search: Cannot be applied directly. If we sort it: `[10, 20, 30, 50, 60, 80]` (which takes time), then binary search would work. But for a single search, the overhead of sorting makes linear search the better option.

Case 2: Sorted Array Array: `[10, 20, 30, 50, 60, 80, 90, 100]` (n=8)

  • Linear Search: Will check 10, 20, 30, 50, and find `60` on the 5th attempt. (5 comparisons)
  • Binary Search: 1. Check middle: `50`. (60 > 50, so search right) 2. Check new middle: `80`. (60 < 80, so search left) 3. Check `60`. Found. (3 comparisons)

In this example, binary search is clearly faster on a sorted array.

Conclusion: Binary search is vastly more efficient in general, but linear search is a better and “more efficient” choice for unsorted data or very small datasets.

Q4. (a) Traverse the following Binary tree pre-order and post-order : [Image of a binary tree] (b) What is an AVL tree ? Explain insertion of nodes into AVL with the help of a suitable example.

Ans. (a) Binary Tree Traversal Given the binary tree: 

 A / \ B C / \ / \ D E F G / / \H I J

1. Pre-order Traversal: The rule is: (Root) -> (Left Subtree) -> (Right Subtree) Following this rule, the traversal would be:

  1. Visit A (Root).
  2. Go to A’s left subtree (B).
  3. Visit B (Root).
  4. Go to B’s left subtree (D).
  5. Visit D (Root).
  6. Go to D’s left subtree (H). Visit H.
  7. Go to D’s right subtree (none).
  8. Go to B’s right subtree (E).
  9. Visit E (Root).
  10. Go to E’s left subtree (I). Visit I.
  11. Go to E’s right subtree (none).
  12. Go to A’s right subtree (C).
  13. Visit C (Root).
  14. Go to C’s left subtree (F). Visit F.
  15. Go to C’s right subtree (G).
  16. Visit G (Root).
  17. Go to G’s left subtree (none).
  18. Go to G’s right subtree (J). Visit J.


Pre-order traversal result: A, B, D, H, E, I, C, F, G, J

2. Post-order Traversal: The rule is: (Left Subtree) -> (Right Subtree) -> (Root) Following this rule, the traversal would be:

  1. Go deep into A’s left subtree (B).
  2. Go deep into B’s left subtree (D).
  3. Go to D’s left subtree (H). Visit H.
  4. Go to D’s right subtree (none), then visit D.
  5. Go to B’s right subtree (E).
  6. Go to E’s left subtree (I). Visit I.
  7. Go to E’s right subtree (none), then visit E.
  8. Now both children of B are done, visit B.
  9. Go to A’s right subtree (C).
  10. Go to C’s left subtree (F). Visit F.
  11. Go to C’s right subtree (G).
  12. Go to G’s left subtree (none).
  13. Go to G’s right subtree (J). Visit J.
  14. Now visit G.
  15. Now both children of C are done, visit C.
  16. Finally, visit the root A.


Post-order traversal result: H, D, I, E, B, F, J, G, C, A

(b) AVL Tree and Node Insertion An AVL Tree is a self-balancing binary search tree, named after its inventors, Adelson-Velsky and Landis. In an AVL tree, for any node, the heights of its left and right subtrees can differ by at most 1. This difference is called the Balance Factor (BF) . BF = height(left subtree) – height(right subtree) The BF of every node in an AVL tree must be -1, 0, or 1.

Insertion of Nodes into an AVL Tree: Inserting a node into an AVL tree involves two steps: 1. Standard BST Insertion: The node is inserted as it would be in a standard binary search tree, ensuring the BST property is maintained. 2. Rebalancing: After insertion, we trace back up the path from the newly inserted node to the root. We check the balance factor of each node along this path. If any node becomes unbalanced (BF = -2 or 2), rotations are used to rebalance the tree.

There are four types of rotation cases:

  • LL (Left-Left) Case: Requires a single Right rotation.
  • RR (Right-Right) Case: Requires a single Left rotation.
  • LR (Left-Right) Case: Requires a Left rotation followed by a Right rotation.
  • RL (Right-Left) Case: Requires a Right rotation followed by a Left rotation.

Example: Insert 10, 20, and 30 into an empty AVL tree.

1. Insert 10: 

 10 (BF=0)

2. Insert 20: (20 > 10, so it goes to the right of 10) 

 10 (BF=-1) \ 20 (BF=0)

The tree is still balanced.

3. Insert 30: (30 > 20, so it goes to the right of 20) 

 10 (BF=-2) <-- Unbalanced! \ 20 (BF=-1) \ 30 (BF=0)

Now, the balance factor of node 10 is -2 (`height(L)-height(R) = -1 – 1 = -2`). This is an imbalance. This is an RR (Right-Right) case because the new node (30) was inserted into the right subtree of the right child (20) of the unbalanced node (10). To fix this, we perform a single left rotation on the unbalanced node (10).

Left Rotation (on 10):

  • 20 becomes the new root.
  • 10 becomes the left child of 20.

Resulting balanced AVL Tree: 

 20 (BF=0) / \ 10(BF=0) 30(BF=0)

The tree now adheres to the AVL property again.

Q5. (a) Explain Breadth First Search (BFS) for a graph using example. (b) What is a circular linked list ? Write a algorithm to create a circular linked list and delete an element from it.

Ans. (a) Breadth First Search (BFS) Breadth First Search (BFS) is a graph traversal algorithm that starts at a source vertex and explores the graph layer by layer. It explores all neighbors at the present depth before moving on to the vertices at the next depth level. BFS uses a Queue data structure to keep track of which vertices to visit next.

BFS Algorithm: 1. Create an empty queue `Q` and an empty `visited` set. 2. Enqueue the starting vertex `s` into `Q` and mark it as `visited`. 3. While `Q` is not empty: a. Dequeue a vertex `u` from `Q`. b. Process `u` (e.g., print it). c. For each neighbor `v` of `u`: i. If `v` has not been `visited`:

  • Mark `v` as `visited`.
  • Enqueue `v` into `Q`.

Example: Consider the following graph: 

 A --- B | \ | | \ | C -- D -- E

Let’s start BFS from vertex A .

  • Step 1: Start at A. Enqueue A and mark it as visited. Queue: `[A]` Visited: `{A}` Output: `A`
  • Step 2: Dequeue A. Enqueue all unvisited neighbors of A (B, C, D) and mark them as visited. Queue: `[B, C, D]` Visited: `{A, B, C, D}` Output: `A, B`
  • Step 3: Dequeue B. Enqueue unvisited neighbors of B (E) and mark as visited. (A and D are already visited). Queue: `[C, D, E]` Visited: `{A, B, C, D, E}` Output: `A, B, C`
  • Step 4: Dequeue C. All neighbors of C (A, D) are already visited. Queue: `[D, E]` Visited: `{A, B, C, D, E}` Output: `A, B, C, D`
  • Step 5: Dequeue D. All neighbors of D (A, C, E) are already visited. Queue: `[E]` Visited: `{A, B, C, D, E}` Output: `A, B, C, D, E`
  • Step 6: Dequeue E. All neighbors of E (B, D) are already visited. Queue: `[]` (Empty)

The queue is now empty, so the algorithm terminates. The BFS traversal order is: A, B, C, D, E .

(b) Circular Linked List A circular linked list is a type of linked list where the last node’s `next` pointer does not point to NULL, but instead points back to the first node (head) of the list, forming a circular loop.

Algorithm to Create a Circular Linked List: This algorithm creates a circular linked list by adding nodes at the end. We use a `last` pointer which points to the last node in the list. `last->next` will always point to the first node. 

ALGORITHM AddToEnd(last, data)1. newNode = createNode(data)2. 3. // If the list is empty4. IF last == NULL THEN5. last = newNode6. newNode->next = last // Point to itself7. ELSE8. newNode->next = last->next // New node points to the old first node9. last->next = newNode // Old last node points to the new node10. last = newNode // Update 'last' to be the new node11. ENDIF12. RETURN last

Algorithm to Delete an Element from a Circular Linked List: This algorithm deletes a node with a given `key`. 

ALGORITHM DeleteNode(last, key)1. // If the list is empty2. IF last == NULL THEN RETURN NULL3. 4. current = last->next // First node5. prev = last6. 7. // Find the node8. REPEAT9. IF current->data == key THEN10. // Node found, now delete it11. IF current == last AND current->next == last THEN // Only one node12. last = NULL13. FREE(current)14. RETURN last15. ENDIF16. 17. // If the node is the last node18. IF current == last THEN19. last = prev20. ENDIF21. 22. prev->next = current->next23. FREE(current)24. RETURN last25. 26. ENDIF27. prev = current28. current = current->next29. UNTIL current != last->next30. 31. PRINT "Element not found"32. RETURN last

Download IGNOU previous Year Question paper download PDFs for MCS-021 to improve your preparation. These ignou solved question paper IGNOU Previous Year Question paper solved PDF in Hindi and English help you understand the exam pattern and score better.

Thanks!

Reader Interactions

Leave a Reply

Your email address will not be published. Required fields are marked *