पायथन में प्रोग्रामन, तथा आँकड़ा संरचनाएँ: स्टैक, कतार, लिंक्ड सूची, BST, हीप व ग्राफ

खंड A.2 के अंतिम दो उप-शीर्षक प्रोग्रामन हैं — प्रवाह-चित्र व छद्म कूट, फिर पायथन: आँकड़ा प्रकार, संकारक, व्यंजक, सप्रतिबंध कथन (if, elif, else, case), लूप (while, for), लूप नियंत्रण (break, continue), फलन, सरणी, शब्दकोश, स्ट्रिंग व पुनरावर्तन — और आँकड़ा संरचनाएँ: स्टैक, कतार, लिंक्ड सूची, द्विआधारी खोज वृक्ष, द्विआधारी हीप व ग्राफ। ये एक अध्याय साझा करते हैं क्योंकि GATE इन्हें एक ही ढंग से पूछता है: छोटा प्रोग्राम अनुरेखित कर बताएँ कि वह क्या छापता है, या किसी संरचना पर संक्रियाओं का अनुक्रम अनुरेखित कर बताएँ कि उसमें क्या है। नीचे का प्रत्येक अंश हाथ से अनुरेखित किया गया है, और जाल वही हैं जो पायथन स्वयं बिछाता है।

1. प्रवाह-चित्र व छद्म कूट

प्रवाह-चित्र मानक प्रतीकों से कलन-विधि खींचता है: आरंभ व अंत हेतु अंडाकार टर्मिनल, प्रक्रम हेतु आयत, निवेश/निर्गम हेतु समांतर चतुर्भुज, प्रति परिणाम एक तीर सहित निर्णय हेतु हीरा, और नियंत्रण प्रवाह हेतु तीर। छद्म कूट वही कलन-विधि संरचित सरल भाषा में लिखता है — IF … THEN … ELSE, WHILE … DO, FOR … TO — किसी भाषा के वाक्यविन्यास के बिना। दोनों केवल तीन नियंत्रण संरचनाओं से बनते हैं: अनुक्रम, चयन व पुनरावृत्ति; कोई भी कलन-विधि इन तीनों से व्यक्त हो सकती है।

2. पायथन: प्रकार, संकारक व नियंत्रण प्रवाह

पायथन के अंतर्निर्मित प्रकार int (असीमित), float, bool, str, तथा पात्र list (परिवर्तनीय, क्रमित), tuple (अपरिवर्तनीय), dict (कुंजी → मान, कुंजियाँ हैश-योग्य होनी चाहिए) व set हैं। स्ट्रिंग व टपल अपरिवर्तनीय हैं: s[0] = "x" त्रुटि देता है। नियतन नाम को वस्तु से बाँधता है, अतः सूची पर b = a के बाद दोनों नाम उसी सूची को इंगित करते हैं, और b.append(4), a को भी बदल देता है; प्रतिलिपि हेतु a[:] या list(a) चाहिए।

संकारक जिनके परिणाम चौंकाते हैं
व्यंजकमानक्यों
7 / 23.5/ सदा वास्तविक भाग है।
7 // 2, -7 // 23, −4// −∞ की ओर फ़्लोर करता है, शून्य की ओर नहीं।
7 % 3, -7 % 21, 1% भाजक का चिह्न लेता है, अतः a == (a // b) * b + a % b।
घात संकारक की क्रमशः 2, 3, 2 पर शृंखला512घात संकारक दाएँ-साहचर्य है: 2 का (3 का वर्ग) = 2⁹ = 512, (2³)² = 64 नहीं।
1 < 3 < 2Falseशृंखलित: 1 < 3 and 3 < 2।
0 or "x", 0 and 5"x", 0and/or लघु-पथित होते हैं और एक संकार्य लौटाते हैं, True/False नहीं।

चयन if / elif / else है; पायथन 3.10 ने किसी मान को प्रतिरूपों से मिलाने हेतु match / case जोड़ा, case _ डिफ़ॉल्ट के रूप में। while शर्त सत्य रहने तक दोहराता है; for किसी भी अनुक्रम पर पुनरावृत्ति करता है, और range(a, b) से a, a + 1, …, b − 1 मिलते हैं। break सबसे भीतरी लूप छोड़ता है; continue उसकी अगली पुनरावृत्ति पर कूदता है; लूप का else खंड केवल तब चलता है जब लूप break के बिना समाप्त हो।

🧠 अनुरेखण करें, अनुमान नहीं
लूप चर व प्रत्येक बदलते नाम को स्तंभों में लिखें और प्रति पंक्ति एक पुनरावृत्ति चलें। नीचे के तीसरे प्रश्नोत्तरी प्रश्न के लूप हेतु — 3 के गुणज छोड़ें, 8 पर रुकें, शेष जोड़ें — पंक्तियाँ s = 1, 3, 7, 12, 19 देती हैं और लूप i = 8 पर रुकता है, अतः यह 19 छापता है।

3. फलन, स्ट्रिंग, सरणी, शब्दकोश व पुनरावर्तन

फलन def से परिभाषित होता है, return के बिना अंत तक पहुँचने पर None लौटाता है, और डिफ़ॉल्ट तर्क ले सकता है — फलन परिभाषित होते समय एक बार मूल्यांकित, अतः def f(x, acc=[]) जैसा परिवर्तनीय डिफ़ॉल्ट पुकारों के बीच अपनी सामग्री बनाए रखता है। स्ट्रिंग 0 से और अंत से −1 से अनुक्रमित होती हैं, और s[start:stop:step] से कटती हैं: "robot"[::-1] = "tobor", "robot"[1:3] = "ob"। पायथन की list गतिशील सरणी का काम करती है (array मॉड्यूल व NumPy प्रकारित सरणियाँ देते हैं)। dict कुंजी से खोजता है; अनुपस्थित कुंजी पर d[k], KeyError देता है जबकि d.get(k, 0), 0 लौटाता है।

पुनरावर्ती फलन छोटे निवेश पर स्वयं को पुकारता है और उसे आधार स्थिति तक पहुँचना चाहिए। उसकी लागत उसकी पुकारों से गिनी जाती है: f(n) = f(n − 1) + f(n − 2) हेतु, f(0) व f(1) सीधे लौटते हुए, पुकारों की संख्या C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1 सहित, C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15 देती है — घातीय वृद्धि, जिसे स्मरणीकरण (memoisation) हटाता है। प्रत्येक पुकार एक स्टैक फ़्रेम घेरती है, अतः गहरा पुनरावर्तन पायथन की पुनरावर्तन सीमा पार कर सकता है जहाँ लूप नहीं करेगा।

4. स्टैक, कतार व लिंक्ड सूची

स्टैक अंतिम-आगत, प्रथम-निर्गत है: शीर्ष पर push व pop, दोनों O(1) — फलन पुकारों, पूर्ववत्, व्यंजक मूल्यांकन व गहराई-प्रथम खोज के पीछे की संरचना। push 5, push 8, pop, push 2, push 7, pop के बाद स्टैक में 5, 2 हैं, 2 शीर्ष पर। कतार प्रथम-आगत, प्रथम-निर्गत है: पीछे enqueue, आगे dequeue, चौड़ाई-प्रथम खोज व कार्य बफ़रों द्वारा प्रयुक्त; पायथन में collections.deque दोनों सिरों पर O(1) देता है, जबकि list.pop(0), O(n) है। एकल लिंक्ड सूची प्रत्येक अवयव को अगले के संकेतक सहित संचित करती है: शीर्ष पर जोड़ना या हटाना O(1) है, पर k-वें अवयव तक पहुँचना O(k), यादृच्छिक पहुँच नहीं।

5. द्विआधारी खोज वृक्ष, द्विआधारी हीप व ग्राफ

द्विआधारी खोज वृक्ष में किसी नोड के बाएँ उपवृक्ष की प्रत्येक कुंजी छोटी और दाएँ उपवृक्ष की प्रत्येक कुंजी बड़ी होती है, अतः मध्य-क्रम अनुप्रस्थन कुंजियों को क्रमबद्ध क्रम में देखता है। खोज, प्रविष्टि व विलोपन ऊँचाई h हेतु O(h) लेते हैं — संतुलित होने पर O(log n), सबसे खराब स्थिति में O(n), जब क्रमबद्ध निवेश शृंखला बनाता है। 50, 30, 70, 20, 40, 60, 80 जोड़ने से पूर्ण वृक्ष बनता है जिसका पूर्व-क्रम 50 30 20 40 70 60 80 व पश्च-क्रम 20 40 30 60 80 70 50 है।

द्विआधारी हीप सरणी में संचित पूर्ण द्विआधारी वृक्ष है: 0-आधारित अनुक्रमण में अनुक्रमांक i के बच्चे 2i + 1 व 2i + 2 पर और उसका जनक ⌊(i − 1)/2⌋ पर। अधिकतम-हीप में प्रत्येक जनक अपने बच्चों से कम नहीं, अतः अधिकतम अनुक्रमांक 0 पर है। प्रविष्टि अंत में जोड़कर ऊपर छानती है, O(log n); अधिकतम निकालना अंतिम अवयव को मूल पर लाकर नीचे छानता है, O(log n); n वस्तुओं से नीचे-से-ऊपर हीप बनाना O(n) है। रिक्त अधिकतम-हीप में 10, 20, 15, 30, 40 जोड़ने से सरणी [40, 30, 15, 10, 20] मिलती है।

V शीर्षों व E कोरों वाला ग्राफ आसन्नता आव्यूह के रूप में संचित होता है, V × V प्रविष्टियाँ, O(1) कोर खोज सहित O(V²) स्थान, या आसन्नता सूचियों के रूप में, O(V + E) स्थान, विरल ग्राफों हेतु बेहतर। चौड़ाई-प्रथम खोज कतार प्रयोग करती है और स्रोत से कोरों में लघुतम पथ पाती है; गहराई-प्रथम खोज स्टैक, या पुनरावर्तन, प्रयोग करती है और चक्र पहचान व सांस्थितिक क्रमण का आधार है। आसन्नता सूचियों सहित दोनों O(V + E) लेती हैं।

मुख्य बिंदु

  • प्रवाह-चित्र व छद्म कूट केवल अनुक्रम, चयन व पुनरावृत्ति प्रयोग करते हैं।
  • // −∞ की ओर फ़्लोर करता है और % भाजक का चिह्न लेता है; दाएँ-साहचर्य है; and/or एक संकार्य लौटाते हैं।
  • सूचियाँ परिवर्तनीय हैं और नियतन से साझा होती हैं; स्ट्रिंग व टपल अपरिवर्तनीय हैं; लूप का else केवल break के बिना चलता है।
  • स्टैक LIFO, कतार FIFO, लिंक्ड-सूची शीर्ष प्रविष्टि O(1); BST मध्य-क्रम क्रमबद्ध है और उसकी सबसे खराब स्थिति O(n) है।
  • हीप के बच्चे 2i + 1, 2i + 2 पर; निर्माण O(n), प्रविष्टि व निष्कर्षण O(log n); BFS कतार, DFS स्टैक प्रयोग करता है।

अभ्यास प्रश्न (14)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. पायथन कथन print(7 // 2, 7 % 3) क्या निर्गत करता है?

    1. 3 1
    2. 3.5 1
    3. 3 2
    4. 4 1
    उत्तर देखें

    उत्तर: A — 3 1

    // फ़्लोर भाग है, 7 // 2 = 3; % शेषफल है, 7 % 3 = 1। 3.5, 7 / 2 है, वास्तविक भाग।

  2. पायथन में -7 // 2 व -7 % 2 के मान क्रमशः हैं:

    1. −4 व 1
    2. −3 व −1
    3. −4 व −1
    4. −3 व 1
    उत्तर देखें

    उत्तर: A — −4 व 1

    // ऋण अनंत की ओर फ़्लोर करता है: −3.5 का फ़्लोर −4। शेषफल फिर a = (a // b) × b + a % b से आता है: −7 = (−4)(2) + 1, अतः 1, भाजक का चिह्न लेते हुए। −3 व −1, C का खंडन करने वाला भाग देता है।

  3. यह पायथन कूट क्या छापता है?
    s = 0
    for i in range(1, 10):
        if i % 3 == 0:
            continue
        if i == 8:
            break
        s += i
    print(s)

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 19

    i = 1, 2 जोड़कर 3; 3 छोड़ा गया; 4, 5 इसे 12 पर लाते हैं; 6 छोड़ा गया; 7 इसे 19 पर लाता है; i = 8 पर लूप जोड़ने से पहले टूटता है। break को continue जैसा मानना 8 जोड़ेगा और फिर 9 पर, जो 3 का गुणज है, रुककर 27 छापेगा।

  4. def f(n):
        if n <= 1:
            return n
        return f(n - 1) + f(n - 2)
    आरंभिक पुकार सहित, f(5) का मूल्यांकन करते समय f को की गई कुल पुकारों की संख्या ____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 15

    C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1 सहित: C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 1 + 9 + 5 = 15। लौटाया गया मान, f(5) = 5, भिन्न संख्या है।

  5. a = [1, 2, 3]
    b = a
    b.append(4)
    print(len(a))
    निर्गम है:

    1. 4
    2. 3
    3. त्रुटि, क्योंकि a बदला नहीं गया
    4. 7
    उत्तर देखें

    उत्तर: A — 4

    b = a, b को उसी सूची वस्तु का दूसरा नाम बनाता है, अतः b के माध्यम से जोड़ना उस सूची को बदलता है जिसे a नामित करता है: उसकी लंबाई 4 है। पृथक् प्रतिलिपि हेतु b = a[:] या list(a) चाहिए।

  6. d = {"x": 1, "y": 2}
    d["x"] += 5
    print(d.get("z", 0) + d["x"])
    निर्गम है:

    1. 6
    2. KeyError
    3. 8
    4. 1
    उत्तर देखें

    उत्तर: A — 6

    d["x"] 6 बन जाता है; d.get("z", 0) अनुपस्थित कुंजी हेतु KeyError के स्थान पर डिफ़ॉल्ट 0 लौटाता है, जैसा d["z"] करता; 0 + 6 = 6।

  7. पायथन में "robot"[::-1] का मान क्या है?

    1. "tobor"
    2. "robot"
    3. "t"
    4. "obor"
    उत्तर देखें

    उत्तर: A — "tobor"

    आरंभ व अंत छोड़कर −1 का चरण पूरी स्ट्रिंग को उल्टा चलता है। "t", s[-1] होगा, केवल अंतिम वर्ण।

  8. for n in [3, 5, 7]:
        if n % 2 == 0:
            break
    else:
        print("none even")
    यह कूट:

    1. none even छापता है
    2. कुछ नहीं छापता
    3. वाक्यविन्यास त्रुटि है, क्योंकि else को if के बाद आना चाहिए
    4. none even तीन बार छापता है
    उत्तर देखें

    उत्तर: A — none even छापता है

    for लूप का else खंड एक बार चलता है जब लूप break के बिना समाप्त हो। कोई अवयव सम नहीं, अतः break कभी नहीं चलता और else एक बार छापता है। सूची में सम संख्या होती तो यह कुछ नहीं छापता।

  9. रिक्त स्टैक से आरंभ कर push(5), push(8), pop(), push(2), push(7), pop() संक्रियाएँ की जाती हैं। अब स्टैक के शीर्ष पर अवयव ____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 2

    push 5, 8 के बाद स्टैक [5, 8] है; pop, 8 हटाता है; push 2, 7 से [5, 2, 7]; pop, 7 हटाता है, [5, 2] शेष, 2 शीर्ष पर। कतार इसके स्थान पर 5 व 8 हटाती।

  10. एक द्विआधारी हीप 0-आधारित अनुक्रमण वाली सरणी में संचित है। अनुक्रमांक 4 वाले नोड के दाएँ बच्चे का अनुक्रमांक ____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 10

    i के बच्चे 2i + 1 (बायाँ) व 2i + 2 (दायाँ) पर हैं: 9 व 10। 1-आधारित अनुक्रमण में नियम 2i व 2i + 1 है, जो नोड 4 के दाएँ बच्चे हेतु 9 देगा।

  11. कुंजियाँ 50, 30, 70, 20, 40, 60, 80 उसी क्रम में रिक्त द्विआधारी खोज वृक्ष में जोड़ी जाती हैं। इसका पश्च-क्रम अनुप्रस्थन है:

    1. 20 40 30 60 80 70 50
    2. 20 30 40 50 60 70 80
    3. 50 30 20 40 70 60 80
    4. 80 70 60 50 40 30 20
    उत्तर देखें

    उत्तर: A — 20 40 30 60 80 70 50

    वृक्ष के मूल पर 50, बाईं ओर 30 (20, 40 सहित) व दाईं ओर 70 (60, 80 सहित) है। पश्च-क्रम प्रत्येक नोड पर बायाँ, दायाँ, फिर मूल देखता है: 20 40 30, 60 80 70, 50। क्रमबद्ध सूची मध्य-क्रम अनुप्रस्थन है और 50 30 20 40 70 60 80 पूर्व-क्रम।

  12. कुंजियाँ 10, 20, 15, 30, 40 उसी क्रम में 0-आधारित अनुक्रमण वाली सरणी में संचित आरंभतः रिक्त अधिकतम-हीप में जोड़ी जाती हैं, प्रत्येक प्रविष्टि ऊपर छनती है। पाँचों प्रविष्टियों के बाद अनुक्रमांक 4 पर अवयव ____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 20

    10 → [10]; 20, 10 से बदलता है → [20, 10]; 15 → [20, 10, 15]; अनुक्रमांक 3 पर 30, 10 से फिर 20 से बदलता है → [30, 20, 15, 10]; अनुक्रमांक 4 पर 40, 20 (अनुक्रमांक 1) से फिर 30 से बदलता है → [40, 30, 15, 10, 20]। अनुक्रमांक 4 पर 20 है।

  13. कौन-से कथन सत्य हैं?

    1. चौड़ाई-प्रथम खोज कतार से कार्यान्वित होती है
    2. V शीर्षों वाले ग्राफ के आसन्नता आव्यूह को O(V²) संग्रहण चाहिए
    3. n कुंजियों वाले असंतुलित द्विआधारी खोज वृक्ष में खोज सबसे खराब स्थिति में O(log n) समय लेती है
    4. एकल लिंक्ड सूची के शीर्ष पर प्रविष्टि O(1) समय लेती है
    उत्तर देखें

    उत्तर: A — चौड़ाई-प्रथम खोज कतार से कार्यान्वित होती है; B — V शीर्षों वाले ग्राफ के आसन्नता आव्यूह को O(V²) संग्रहण चाहिए; D — एकल लिंक्ड सूची के शीर्ष पर प्रविष्टि O(1) समय लेती है

    (A) BFS शीर्षों को दूरी के क्रम में देखता है, जो FIFO कतार देती है। (B) शीर्षों के प्रति क्रमित युग्म एक प्रविष्टि। (C) असत्य: असंतुलित वृक्ष ऊँचाई n की शृंखला हो सकता है, अतः सबसे खराब स्थिति O(n) है। (D) नया नोड पुराने शीर्ष की ओर इंगित करता है और शीर्ष बन जाता है — अचर कार्य।

  14. पायथन के विषय में कौन-से कथन सत्य हैं?

    1. टपल अपरिवर्तनीय हैं
    2. स्ट्रिंग परिवर्तनीय हैं, अतः s[0] = "x" स्ट्रिंग को यथास्थान बदलता है
    3. शब्दकोश कुंजियाँ हैश-योग्य होनी चाहिए, अतः सूची कुंजी नहीं हो सकती
    4. x and y में x असत्य होने पर y मूल्यांकित नहीं होता
    उत्तर देखें

    उत्तर: A — टपल अपरिवर्तनीय हैं; C — शब्दकोश कुंजियाँ हैश-योग्य होनी चाहिए, अतः सूची कुंजी नहीं हो सकती; D — x and y में x असत्य होने पर y मूल्यांकित नहीं होता

    (A) टपल के अवयव पुनः नियत नहीं हो सकते। (B) असत्य: स्ट्रिंग अपरिवर्तनीय हैं, और अवयव नियतन TypeError देता है; नई स्ट्रिंग बनानी पड़ती है। (C) कुंजियाँ हैश से खोजी जाती हैं, और परिवर्तनीय सूची का कोई हैश नहीं। (D) and लघु-पथित होता है, स्वयं x लौटाते हुए।