Chapter 1 डाटा स्ट्रक्चर का परिचय
पाठ्यपुस्तक के प्रश्न
वस्तुनिष्ठ प्रश्न
प्रश्न 1.
जब एल्गोरिथ्म की दक्षता का निर्धारण करते हैं तो स्पेस पहलू मापा जाता है
(अ) एल्गोरिथ्म द्वारा आवश्यक अधिकतम मैमोरी की
(ब) एल्गोरिथ्म द्वारा आवश्यक न्यूनतम मैमोरी की
(स) एल्गोरिथ्म द्वारा आवश्यक औसत मैमोरी की
(द) एल्गोरिथ्म द्वारा आवश्यक अधिकतम डिस्क मैमोरी की
उत्तर:
(अ) एल्गोरिथ्म द्वारा आवश्यक अधिकतम मैमोरी की
प्रश्न 2.
एक एल्गोरिथ्म के लिए औसत मामले की जटिलता है
(अ) एल्गोरिथ्म के औसत मामले का विश्लेषण बहुत अधिक जटिल है।
(ब) एल्गोरिथ्म के औसत मामले का विश्लेषण बहुत सरल है।
(स) कभी-कभी अधिक जटिल और कभी-कभी अधिक सरल होता है।
(द) उपरोक्त में से कोई नहीं
उत्तर:
(स) कभी-कभी अधिक जटिल और कभी-कभी अधिक सरल होता है।
प्रश्न 3.
एल्गोरिथ्म की दक्षता का निर्धारण करने के लिए समय का पहलू मापा जाता है
(अ) माइक्रोसेकण्ड की गिनती
(ब) प्रमुख ऑपरेशनों की संख्या की गणना
(स) बयानों की संख्या की गणना
(द) एल्गोरिथ्म के किलोबाइट की गिनती
उत्तर:
(ब) प्रमुख ऑपरेशनों की संख्या की गणना
प्रश्न 4.
निम्नलिखित में से रैखिक डेटा स्ट्रक्चर है
(अ) ट्री
(ब) ग्राफ
(स) ऐरे
(द) इनमें से कोई नहीं
उत्तर:
(स) ऐरे
प्रश्न 5.
निम्नलिखित में से रैखिक डेटा स्ट्रक्चर नहीं है
(अ) ऐरे
(ब) लिंक लिस्ट
(स) ऊपर के दोनों
(द) इनमें से कोई नहीं
उत्तर:
(द) इनमें से कोई नहीं
लघु उत्तरीय प्रश्न
प्रश्न 1.
डेटा स्ट्रक्चर क्या है?
उत्तर-
डेटा स्ट्रक्चर डेटा को एकत्रित (कलेक्ट) और आयोजित (ऑर्गेनाइज) करने का एक तरीका है जिससे हम प्रभावी तरीके से इन डेटा पर कार्यवाही (ऑपरेशन) कर सकें। डाटा स्ट्रक्चर डेटा के बेहतर व्यवस्था और भण्डारण के लिए होते हैं। डेटा स्ट्रक्चर किसी भी संगठन के डेटा का एक तार्किक और गणितीय दृश्य है। उदाहरण के लिए, डेटा के रूप में खिलाड़ी को नाम विराट और उम्र 26 है। यहाँ विराट स्ट्रिंग प्रकार का डेटा है और 26 पूर्णांक प्रकार का डेटा है। हम इस डेटा को एक रिकॉर्ड के रूप में जैसे एक खिलाड़ी रिकॉर्ड की तरह व्यवस्थित कर सकते हैं। अब हम खिलाड़ी रिकॉर्ड को एक फाइल या डेटाबेस में एक डाटा स्ट्रक्चर के रूप में संचित (स्टोर) कर सकते हैं उदाहरण के लिए धोनी 30, गंभीर 31, सहवाग 33।।
प्रश्न 2.
एक एल्गोरिथ्म की कुशलता के लिए दो मुख्य उपाय क्या हैं?
उत्तर-
एक एल्गोरिथ्म की कुशलता के लिए दो मुख्य उपाय निम्नलिखित हैं
(i) स्पेस जटिलता (Space Complexity) : एल्गोरिथ्म के निष्पादन के दौरान आवश्यक ‘मैमोरी को स्पेस जटिलता कहते हैं। बहु उपयोगकर्ता सिस्टम के लिए और जब सीमित रूप से मैमोरी उपलब्ध हो तब इसे गंभीरता से लिया जाना चाहिए। आमतौर पर एक एल्गोरिथ्म को निम्नलिखित घटकों के लिए मैमोरी की आवश्यकता होती है
इन्सट्रक्शन स्पेसः यह प्रोग्राम के निष्पादन योग्य संस्करण को संचय करने के लिए आवश्यक मैमोरी स्पेस है। यह स्पेस निश्चित या स्थायी होती है जो कि प्रोग्राम में कोड की लाइनों की संख्या पर निर्भर करती है।
डेटा स्पेसः यह सभी कॉन्सटेन्ट और वैरिएबल मानों को संचित करने के लिए आवश्यक स्पेस है।
(ii) समय जटिलता (Time Complexity) : एक प्रोग्राम के पूर्ण निष्पादन के लिए आवश्यक समय प्रतिनिधित्व करने के लिए एक तरीका है। एल्गोरिथम की समय जटिलता को सबसे अधिक Big O संकेतन का उपयोग करके व्यक्त किया जाता है। एल्गोरिथ्म द्वारा किये जाने वाले प्राथमिक फंक्शनों की संख्या को गिनकर समय जटिलता की गणना की जाती है। और क्योंकि एल्गोरिथ्म की कार्य क्षमता अलग-अलग इनपुट डेटा के साथ अलग-अलग हो सकती है। इसलिए एल्गोरिथ्म की वर्स्ट केस (बुरी-से-बुरी) समय जटिलता का उपयोग करते हैं। यह किसी भी इनपुट आकार के लिए एल्गोरिथ्म द्वारा लिया जाने वाला अधिकतम समय होता है।
प्रश्न 3.
समय जटिलता क्यों महत्त्वपूर्ण है?
उत्तर-
एक प्रोग्राम के पूर्ण निष्पादन के लिए आवश्यक समय प्रतिनिधित्व करने के लिए एक तरीका है। एल्गोरिथ्म की समय जटिलता को सबसे अधिक Big O संकेतन का उपयोग करके व्यक्त किया जाता है। एल्गोरिथ्म द्वारा किये जाने वाले प्राथमिक फंक्शनों की संख्या को गिनकर समय जटिलता की गणना की जाती है। और क्योंकि एल्गोरिथ्म की कार्य क्षमता अलग-अलग इनपुट डेटा के साथ अलग-अलग हो सकती है इसलिए एल्गोरिथ्म की वर्स्ट केस (बुरी-से-बुरी) समय जटिलता का उपयोग करते हैं। यह किसी भी इनपुट आकार के लिए एल्गोरिथ्म द्वारा लिया जाने वाला अधिकतम समय होता है।
प्रश्न 4.
रेखीय डेटा स्ट्रक्चर के उदाहरण दीजिए।
उत्तर-
रेखीय डेटा स्ट्रक्चर (Linear Data Structure)
ये एकल स्तर के डाटा स्ट्रक्चर होते हैं। इनके तत्त्व एक अनुक्रम (सीक्वेंस) बनाते हैं, इसलिए इन्हें रेखीय डाटा स्ट्रक्चर कहते हैं।
उदाहरण – स्टैक (Stack); क्यू (Queue), लिंक लिस्ट (Link List)
निबंधात्मक प्रश्न
प्रश्न 1.
स्पेस जटिलता की गणना कैसे की जा सकती है?
उत्तर-
एक एल्गोरिथ्म या डेटा संरचना की स्पेस जटिलता, किसी समय उपयोग की जाने वाली अधिकतम राशि है, यह एल्गोरिथ्म द्वारा इनपुट के लिए उपयोग की जाने वाली जगह (Space) को इग्नोर (Ignore) करता है।
उदाहरण –
- बाइनरी सर्च (Binary Search) (1) स्पेस (Space) का उपयोग करती है।
- क्विक सोर्ट (Quick Sort) (1) स्पेस * (Space*) का उपयोग करती है।
प्रश्न 2.
डेटा स्ट्रक्चर का क्या उपयोग है?
उत्तर-
डेटा स्ट्रक्चर किसी कम्प्यूटर सिस्टम में डेटा को स्टोर तथा व्यवस्थित (Organise) करने का एक तरीका होता है जिससे कि हम डेटा का आसानी से इस्तेमाल कर सकें अर्थात् डेटा को इस प्रकार स्टोर तथा व्यवस्थित किया जाता है। कि उसके बाद में किसी भी समय आसानी से Access किया जा सके।
डेटा स्ट्रक्चर लगभग सभी प्रोग्राम और सॉफ्टवेयर सिस्टम में उपयोग किये जाते हैं। कुछ प्रोग्रामिंग भाषाएँ भी एल्गोरिथ्म के स्थान पर डेटा स्ट्रक्चर को प्राथमिकता देती हैं। डेटा स्ट्रक्चर किसी भी प्रोग्रामिंग भाषा के Root में होते हैं, क्योंकि इन्हीं के आधार पर एप्लीकेशन प्रोग्राम्स (Application Programs) के Data Handle होते हैं।
वास्तव में डेटा स्ट्रक्चर किसी भी समस्या को Solve करने के Abstract तरीके होते हैं, ये किसी भी Programming Language पर निर्भर नहीं होते और इन्हें किसी भी Programming Language में Implement किया जा सकता है।
डाटा स्ट्रक्चर डेटा के बेहतर व्यवस्था और भण्डारण के लिए होते हैं। डेटा स्ट्रक्चर किसी भी संगठन के डेटा का एक तार्किक और गणितीय दृश्य है। उदाहरण के लिए, डेटा के रूप में खिलाड़ी का नाम सुरेश और उम्र 28 है। यह सुरेश स्ट्रिंग प्रकार का डेटा है और 28 पूर्णांक प्रकार का डेटा है। हम इस डेटा को एक रिकार्ड के रूप में जैसे एक खिलाडी रिकॉर्ड की तरह व्यवस्थित कर सकते हैं। अब हम खिलाड़ी रिकॉर्ड को एक फाइल या डेटाबेस में एक डाटा स्ट्रक्चर के रूप में संचित (स्टोर) कर सकते हैं। उदाहरण के लिए धोनी 30, सचिन 31, सहवाग 33।
प्रश्न 3.
यौगिक डेटा स्ट्रक्चर को समझाइए।
उत्तर-
यौगिक डाटा स्ट्रक्चर Compound Data Structure
सरल डेटा स्ट्रक्चर को विभिन्न तरीकों में संयोजित करके जटिल डाटा स्ट्रक्चर बनाये जा सकते हैं। ये अग्रलिखित दो प्रकार के होते हैं।
1. रेखीय डाटा स्ट्रक्चर (Linear Data Structure)
ये एकल स्तर के डाटा स्ट्रक्चर होते हैं। इनके तत्त्व एक अनुक्रम (सीक्वेंस) बनाते हैं इसलिए इन्हें रेखीय डाटा स्ट्रक्चर कहते हैं। ये निम्न प्रकार के होते हैं
- स्टैक
- क्यू
- लिंक लिस्ट
2. गैर-रेखीय डाटा स्ट्रक्चर (Non-linear Data Structure)
ये बहुस्तरीय डाटा स्ट्रक्चर होते हैं। गैर-रेखीय डाटा स्ट्रक्चर के उदाहरण ट्री और ग्राफ हैं।
डाटा स्ट्रक्चर पर ऑपरेशनः डाटा स्ट्रक्चर पर किये जाने वाले बुनियादी ऑपरेशन निम्न प्रकार हैं:
इनसर्शन (Insertion): इनसर्श का अर्थ एक डाटा स्ट्रक्चर में एक नये डेटा तत्त्व को जोड़ना।।
डिलिशन (Deletion): डिलिशन का अर्थ एक डाटा स्ट्रक्चर में एक डेटा तत्त्व को हटाना यदि वह मौजूद है।
सर्च (Search): एक डाटा स्ट्रक्चर में निर्दिष्ट डेटा तत्त्व खोजने को सर्च कहते हैं।
टूवर्सिग (Traversing): एक डाटा स्ट्रक्चर में मौजूद सभी डेटा तत्त्वों के प्रसंस्करण (प्रोसेसिंग) को टूवर्सिग कहते हैं।
सोर्टिग (Sorting): डाटा स्ट्रक्चर के तत्त्वों को एक निर्दिष्ट क्रम में व्यस्थित करने को सोर्टिग कहते हैं।
मर्जिग (Merging); दो एक ही प्रकार के डाटा स्ट्रक्चर के तत्त्वों का संयोजन कर उसी प्रकार के एक नये डाटा स्ट्रक्चर बनाने को मर्जिग कहते हैं।
अन्य महत्त्वपूर्ण प्रश्न
अतिलघु उत्तरीय प्रश्न
प्रश्न 1.
सरल डाटा स्ट्रक्चर में कौन से डेटा टाइप्स लिए जाते हैं?
उत्तर-
सरल डाटा स्ट्रक्चर में प्रिमिटिव डेटा टाइप्स; जैसे-इंटिन्जर्स, रियल, करैक्टर, बूलियन से बनाया जाता है।
प्रश्न 2.
सरल डेटा स्ट्रक्चर कितने प्रकार के होते हैं?
उत्तर-
सरल डेटा स्ट्रक्चर निम्न दो प्रकार के होते हैं
- ऐरे
- स्ट्रक्चर
प्रश्न 3.
यौगिक डेटा स्ट्रक्चर कितने प्रकार के होते हैं?
उत्तर-
यौगिक डेटा स्ट्रक्चर निम्न दो प्रकार के होते हैं
- रेखीय डाटा स्ट्रक्चर (Linear data structure)
- गैर-रेखीय डाटा स्ट्रक्चर (Non-linear data structure)
प्रश्न 4.
गैर-रेखीय डाटा स्ट्रक्चर क्या है? उदाहरण दीजिए।
उत्तर-
ये बहुस्तरीय डाटा स्ट्रक्चर होते हैं। इसके उदाहरण ट्री और ग्राफ हैं।
प्रश्न 5.
एल्गोरिथ्म से आप क्या समझते हैं?
उत्तर-
एल्गोरिथ्म तर्क या निर्देशों का एक परिमित सेट है जो एक निश्चित पूर्व निर्धारित कार्य को पूरा करने के लिए। लिखी जाती है।
प्रश्न 6.
कुशल और तेज एल्गोरिथ्म क्या होता है?
उत्तर-
यदि एल्गोरिथ्म को निष्पादित करने में कम समय एवम् मैमोरी की आवश्यकता होती है तो उसे कुशल और तेज एल्गोरिथ्म कहते हैं।
प्रश्न 7.
डेटा स्पेस से आप क्या समझते हो?
उत्तर-
डेटा स्पेस (Data Space)-यह सभी कॉन्टेन्ट और वैरिएबल मानों को संचित करने के लिए आवश्यक स्पेस है।।
लघु उत्तरीय प्रश्न
प्रश्न 1.
एल्गोरिथ्म पर संक्षिप्त टिप्पणी लिखिए।
उत्तर-
एल्गोरिथ्म (Algorithm): एल्गोरिथ्म तर्क या निर्देशों का एक परिमित सेट है जो एक निश्चित पूर्वनिर्धारित कार्य को पूरा करने के लिए लिखी जाती है। एल्गोरिथ्म पूरा कोड या प्रोग्राम नहीं होता, यह सिर्फ मूल समस्या का समाधान है, और इसे एक अनौपचारिक उच्च स्तरीय विवरण के रूप में जैसे शुडोकोड़ (pseudo code) या फ्लोचार्ट से व्यक्त किया जा सकता है। यदि एल्गोरिथ्म को निष्पादित करने में कम समय एवं मैमोरी की आवश्यकता होती है तो कुशल और तेज एल्गोरिथ्म कहते हैं। एक एल्गोरिथ्म का प्रदर्शन निम्नलिखित गुण के आधार पर मापा जाता है
- स्पेस जटिलता (Space complexity)
- समय जटिलता (Time complexity)
प्रश्न 2.
स्पेस जटिलता क्या होती है?
उत्तर-
एल्गोरिथ्म के निष्पादन के दौरान आवश्यक मैमोरी को स्पेस जटिलता कहते हैं। बह-उपयोगकर्ता सिस्टम के लिए और जब सीमित रूप से मैमोरी उपलब्ध हो तब इसे गंभीरता से लिया जाना चाहिए। आमतौर पर एक एल्गोरिथ्म को इन्सट्रक्शन स्पेस और डेटा स्पेस के लिए मैमोरी की आवश्यकता होती है।
प्रश्न 3.
समय जटिलता पर संक्षिप्त टिप्पणी लिखिए।
उत्तर-
समय जटिलता (Time Complexity)
एक प्रोग्राम के पूर्ण निष्पादन के लिए आवश्यक समय का प्रतिनिधित्व करने के लिए एक तरीका है। एल्गोरिथ्म की समय जटिलता को सबसे अधिक Big O संकेतन का उपयोग करके व्यक्त किया है। एल्गोरिथ्म द्वारा किये जाने वाले प्राथमिक फंक्शनों की संख्या को गिनकर समय जटिलता की गणना की जाती है। और क्योंकि एल्गोरिथ्म की कार्यक्षमता अलग-अलग इनपुट डेटा के साथ अलग-अलग हो सकती है इसलिए एल्गोरिथ्म की वर्स्ट केस (बुरी-से-बुरी) समय जटिलता का उपयोग करते हैं। यह किसी भी इनपुट आकार के लिए एल्गोरिथ्म द्वारा लिया जाने वाला अधिकतम समय होता है।
निबंधात्मक प्रश्न
प्रश्न 1.
डाटा स्ट्रक्चर का वर्गीकरण चित्र सहित समझाइए।
उत्तर-
सरल डाटा स्ट्रक्चर
ये आमतौर पर प्रिमिटिव डाटा टाइप्स: जैसे-इंटिजर्स, रियल, करैक्टर, बूलियन से बनाया जाता है। सरल डाटा स्ट्रक्चर अग्रलिखित दो प्रकार के होते हैं
- ऐरे
- स्ट्रक्चर
यौगिक डाटा स्ट्रक्चर
सरल डेटा स्ट्रक्चर को विभिन्न तरीकों में संयोजित करके जटिल डाटा स्ट्रक्चर बनाये जा सकते हैं। ये निम्नलिखित दो प्रकार के होते हैं।
1. रेखीय डाटा स्ट्रक्चर (Linear Data Structure)
ये एकल स्तर के डाटा स्ट्रक्चर होते हैं। इनके तत्त्व एक अनुक्रम (सीक्वेंस) बनाते हैं इसलिए इन्हें रेखीय डाटा स्ट्रक्चर कहते हैं।
ये निम्नलिखित प्रकार के होते हैं
- स्टैक
- क्यू
- लिंक्ड लिस्ट
2. गैर-रेखीय डाटा स्ट्रक्चर (Non-linear Data Structure)
ये बहुस्तरीय डाटा स्ट्रक्चर होते हैं। गैर-रेखीय डाटा स्ट्रक्चर के उदाहरण ट्री और ग्राफ हैं।
डाटा स्ट्रक्चर पर ऑपरेशनः डाटा स्ट्रक्चर पर किये जाने वाले बुनियादी ऑपरेशन निम्न प्रकार है:
इनसर्शन (Insertion): इनसर्शन का अर्थ एक डाटा स्ट्रक्चर में एक नये डेटा तत्त्व को जोड़ना।।
डिलिशन (Deletion): डिलिशन का अर्थ एक डाटा स्ट्रक्चर में एक डेटा तत्त्व को हटाना, यदि वह मौजूद है।
सर्च (Search): एक डाटा स्ट्रक्चर में निर्दिष्ट डेटा तत्त्व खोजने को सर्च कहते हैं।
टूवसिंग (Traversing): एक डाटा स्ट्रक्चर में मौजूद सभी डेटा तत्त्वों के प्रसंस्करण (प्रोसेसिंग) को ट्वर्सिग कहते हैं।
सोर्टिग (Sorting): डाटा स्ट्रक्चर के तत्त्वों को एक निर्दिष्ट क्रम में व्यवस्थित करने को सोर्टिग कहते हैं।
मजिंग (Merging): दो एक ही प्रकार के डाटा स्ट्रक्चर के तत्त्वों का संयोजन कर उसी प्रकार के एक नये डाटा स्ट्रक्चर बनाने को मजिंग कहते हैं।