Data Structures Previous Year Questions

Explanation

In the worst case the element is at the last position or absent, so linear search compares with all n elements. That makes it O(n).सबसे खराब स्थिति में तत्व आखिरी स्थान पर होता है या होता ही नहीं, इसलिए linear search सभी n तत्वों से तुलना करता है। इससे यह O(n) होता है।

Explanation

In an extended binary tree used to represent an expression, the internal nodes hold operators and the external (leaf) nodes hold operands. For example, in a + b, '+' is internal and a, b are leaves.व्यंजक दर्शाने वाले extended binary tree में आंतरिक नोड operators रखते हैं और बाहरी (पत्ता) नोड operands रखते हैं। उदाहरण के लिए, a + b में '+' आंतरिक है और a, b पत्ते हैं।

Explanation

An adjacency list stores only the edges that exist, using O(V + E) space. An adjacency matrix always uses O(V²) space, which is wasteful when a sparse graph has few edges.Adjacency list केवल मौजूद किनारे संग्रहीत करती है और O(V + E) स्थान लेती है। Adjacency matrix हमेशा O(V²) स्थान लेती है, जो तब बर्बादी है जब विरल (sparse) ग्राफ में कम किनारे हों।

Explanation

Sudoku is solved by backtracking. You place a digit, check the constraints, and undo the choice (backtrack) when no valid digit fits later. Factorial, finding the maximum and quicksort do not need trial and undo.Sudoku backtracking से हल होता है। आप एक अंक रखते हैं, constraints जाँचते हैं, और जब बाद में कोई वैध अंक न बैठे तो चुनाव को पलट देते हैं (backtrack)। Factorial, अधिकतम निकालना और quicksort में आज़माने और पलटने की ज़रूरत नहीं होती।

Explanation

The question is loosely worded. Going by its own definition (at least 3 biconnected components), a tree with n-1 edges has every edge as a separate biconnected component, so n-1 edges give at least 3 when n ≥ 4.प्रश्न की भाषा ढीली है। इसकी अपनी परिभाषा (कम से कम 3 biconnected components) के अनुसार, n-1 किनारों वाले tree में हर किनारा अलग biconnected component होता है, इसलिए n ≥ 4 होने पर n-1 किनारों से कम से कम 3 बनते हैं।

Explanation

In a threaded binary tree, null right/left pointers are replaced by threads to the inorder successor/predecessor. This allows inorder traversal without a stack or recursion.Threaded binary tree में खाली दाएँ/बाएँ pointers की जगह inorder successor/predecessor तक जाने वाले threads होते हैं। इससे stack या recursion के बिना inorder traversal संभव होता है।

Explanation

Of the options, B is the intended one. Strictly, a complete binary tree fills every level except possibly the last, which is filled from the left, so all leaves lie on the last one or two levels.विकल्पों में B ही अभीष्ट है। सख्ती से, complete binary tree में आखिरी स्तर को छोड़कर हर स्तर पूरा भरा होता है और आखिरी स्तर बाईं ओर से भरा जाता है, इसलिए सभी पत्ते आखिरी एक या दो स्तरों पर होते हैं।

Explanation

A singly linked list with front and rear pointers gives O(1) enqueue at the rear and O(1) dequeue at the front, so no backward links are needed.आगे और पीछे के pointers वाली singly linked list पीछे से O(1) में enqueue और आगे से O(1) में dequeue देती है, इसलिए पीछे की ओर जाने वाले लिंक की ज़रूरत नहीं है।

Explanation

Official answer key: (a) DFS Correct answer should be: (c) Both DFS and BFS Connected components can be found with either DFS or BFS. Scoring follows the official key.आधिकारिक उत्तर कुंजी: (a) DFS सही उत्तर होना चाहिए: (c) DFS और BFS दोनों Connected components को DFS या BFS किसी से भी निकाला जा सकता है। स्कोरिंग आधिकारिक कुंजी के अनुसार है।

Explanation

An array-based stack allocates a fixed block of memory for a maximum number of elements in advance. A linked stack grows node by node.Array-आधारित stack पहले से ही अधिकतम तत्वों के लिए मेमोरी का एक निश्चित ब्लॉक आवंटित कर लेता है। Linked stack नोड-दर-नोड बढ़ता है।

Explanation

MQTT stands for Message Queuing Telemetry Transport, a lightweight publish-subscribe messaging protocol for IoT.MQTT का पूरा नाम Message Queuing Telemetry Transport है, जो IoT के लिए एक हल्का publish-subscribe मैसेजिंग प्रोटोकॉल है।

Explanation

Binary search halves the search range on every comparison, so at most about log₂n + 1 comparisons are needed: O(log n).

Explanation

A spanning tree on n vertices is a tree, and every tree with n vertices has exactly n - 1 edges, so the minimum (and only) count is n - 1.

Explanation

Optimal BST uses dynamic programming because an optimal tree's left and right subtrees must themselves be optimal (optimal substructure), with overlapping subproblems reused from a table.

Explanation

Floyd-Warshall runs three nested loops over k, i and j, each from 1 to n, so it takes O(n³) time.

Explanation

The divide-and-conquer MaxMin algorithm makes about 3n/2 - 2 comparisons; T(n) = 2T(n/2) + 2 solves to O(n).

Explanation

Integer is a primitive (built-in) data type, while stack, queue and list are abstract data types defined by their operations, independent of implementation.

Explanation

Inserting at the beginning needs only to set newnode->next = head and head = newnode, which is O(1); inserting at the end or at a position requires traversal.

Explanation

Compressed sparse formats store only non-zero values with their indices; CSC compresses the data column by column, so it suits sparse matrices and column-wise access. CSR is the row-wise counterpart.

Explanation

CSR stores the non-zeros row by row with a row-pointer array, so all elements of a row are contiguous and can be traversed efficiently.

Explanation

An image is a grid of pixels addressed by row and column, so a 2-D array (one value per pixel, e.g. grayscale) is the natural structure.

Explanation

Floyd-Warshall uses three nested loops over the n vertices (intermediate k, source i, destination j), so it does n × n × n updates, giving O(n³) time.Floyd-Warshall n शीर्षों पर तीन नेस्टेड लूप (मध्यवर्ती k, स्रोत i, गंतव्य j) चलाता है, इसलिए n × n × n अद्यतन करता है, यानी O(n³) समय।

Explanation

In a B-tree of order m, each internal node can have at most m children and therefore at most m − 1 keys.ऑर्डर m के B-tree में हर आंतरिक नोड के अधिकतम m बच्चे हो सकते हैं और इसलिए अधिकतम m − 1 कुंजियाँ।

Explanation

A microphone is an analog sensor, since it produces a continuously varying voltage from sound. A keyboard and a push button give discrete on/off signals, so they are digital.माइक्रोफोन analog सेंसर है, क्योंकि वह ध्वनि से लगातार बदलता वोल्टेज बनाता है। कीबोर्ड और पुश बटन असतत on/off संकेत देते हैं, इसलिए वे digital हैं।

Explanation

A threaded binary tree reuses the otherwise-null child pointers to store threads to inorder predecessors and successors. Only a small flag bit per link is added, so the extra space is minimal.Threaded binary tree अन्यथा null रहने वाले चाइल्ड पॉइंटर को inorder predecessor और successor की threads रखने में उपयोग करता है। हर लिंक पर केवल एक छोटा फ्लैग बिट जुड़ता है, इसलिए अतिरिक्त स्थान न्यूनतम है।

Explanation

A grammar is ambiguous if some string has more than one parse tree, or more than one leftmost derivation.कोई व्याकरण ambiguous है यदि किसी स्ट्रिंग के एक से अधिक parse tree हों, या एक से अधिक leftmost derivation।

Explanation

A linked list is a linear structure, so it is traversed linearly from the head node along the next pointers until NULL. Preorder, inorder and postorder are tree traversals.लिंक्ड लिस्ट रैखिक संरचना है, इसलिए उसे head नोड से next पॉइंटर के साथ NULL तक रैखिक रूप से traverse किया जाता है। Preorder, inorder और postorder वृक्ष के traversal हैं।

Explanation

Pushdown automata accept exactly the context-free languages (Type 2). Linear bounded automata accept context-sensitive languages, and Turing machines accept recursive and RE languages.Pushdown automata ठीक context-free भाषाएँ (Type 2) स्वीकार करते हैं। Linear bounded automata context-sensitive भाषाएँ स्वीकार करते हैं, और Turing मशीनें recursive और RE भाषाएँ।

Explanation

Merge sort splits the array in half each time (log n levels) and merges in linear time at each level, so T(n) = 2T(n/2) + n = O(n log n) in every case.Merge sort हर बार ऐरे को आधा बाँटती है (log n स्तर) और हर स्तर पर रैखिक समय में मिलाती है, इसलिए हर स्थिति में T(n) = 2T(n/2) + n = O(n log n)।

Explanation

An image is a grid of pixels in rows and columns, so a 2-D array (pixel[row][column]) maps onto it naturally.इमेज पंक्तियों और स्तंभों में पिक्सेल का ग्रिड है, इसलिए 2-D array (pixel[row][column]) उस पर स्वाभाविक रूप से बैठता है।

Explanation

MQTT stands for Message Queuing Telemetry Transport. It is a lightweight publish-subscribe messaging protocol widely used in IoT.

Explanation

Greedy best-first search expands the node that looks closest to the goal according to the heuristic h(n). It ignores the cost already paid to reach that node.Greedy best-first search heuristic h(n) के अनुसार लक्ष्य के सबसे नज़दीक दिखने वाले नोड को विस्तारित करती है। वह उस नोड तक पहुँचने में लग चुकी लागत को अनदेखा करती है।

Explanation

An FPGA can be fully reprogrammed by the user to implement almost any logic circuit, so it offers the most customisation. ROM and PLA designs have fixed structures, and gate arrays are configured at the factory.FPGA को उपयोगकर्ता पूरी तरह पुनः प्रोग्राम कर सकता है ताकि लगभग कोई भी लॉजिक सर्किट बने, इसलिए वह सबसे अधिक अनुकूलन देता है। ROM और PLA की संरचनाएँ स्थिर हैं, और gate array फैक्टरी में कॉन्फ़िगर होते हैं।

Explanation

A stack follows LIFO (Last In, First Out). Push and pop happen only at the top, so the last element pushed is the first one popped. A queue is FIFO.स्टैक LIFO (Last In, First Out) का पालन करता है। Push और pop केवल शीर्ष पर होते हैं, इसलिए सबसे बाद में push हुआ तत्व सबसे पहले pop होता है। Queue FIFO है।

Explanation

A double-ended queue comes from the deque class in the collections module: from collections import deque.Double-ended queue collections मॉड्यूल की deque क्लास से आती है: from collections import deque।

Explanation

A spanning tree of a connected graph with n vertices contains all n vertices and no cycle, so it always has exactly n - 1 edges.n शीर्षों वाले जुड़े ग्राफ़ के spanning tree में सभी n शीर्ष होते हैं और कोई चक्र नहीं होता, इसलिए उसमें हमेशा ठीक n - 1 एज होते हैं।

Explanation

Each recursive call pushes an activation record (local variables, parameters and return address) onto the call stack, which is popped when the call returns, allowing the program to backtrack to the caller.हर रिकर्सिव कॉल एक activation record (लोकल वेरिएबल, पैरामीटर और return address) call stack पर डालती है, जो कॉल लौटने पर हटता है, जिससे प्रोग्राम कॉलर तक वापस जा पाता है।

Explanation

A deque (double-ended queue) allows insertion and deletion at both the front and the rear ends.Deque (double-ended queue) आगे और पीछे दोनों सिरों पर डालने और हटाने की अनुमति देती है।

Explanation

A smart card contains an embedded microchip (processor and/or memory) that stores and processes data; this chip is what makes the card "smart".Smart card में एम्बेडेड माइक्रोचिप (प्रोसेसर और/या मेमोरी) होती है जो डेटा रखती और प्रोसेस करती है; यही चिप कार्ड को "स्मार्ट" बनाती है।

Explanation

Tower of Hanoi needs 2^n - 1 minimum moves. For n = 3, 2³ - 1 = 7.Tower of Hanoi को न्यूनतम 2^n - 1 चालें चाहिए। n = 3 के लिए 2³ - 1 = 7।

Explanation

Balance factor = height of left subtree - height of right subtree. In an AVL tree it must be -1, 0 or +1 for every node.Balance factor = बाएँ उप-वृक्ष की ऊँचाई - दाएँ उप-वृक्ष की ऊँचाई। AVL वृक्ष में हर नोड के लिए यह -1, 0 या +1 होना चाहिए।

Explanation

Inserting at the beginning of a linked list only needs a new node pointing to the old head and an updated head pointer, so it takes O(1) time. The others need traversal.लिंक्ड लिस्ट के आरंभ में डालने के लिए केवल पुराने head की ओर इशारा करता नया नोड और अद्यतन head पॉइंटर चाहिए, इसलिए O(1) समय लगता है। अन्य में traversal चाहिए।

Explanation

The divide-and-conquer max-min algorithm makes about 3n/2 - 2 comparisons (T(n) = 2T(n/2) + 2), which is O(n).Divide-and-conquer max-min एल्गोरिदम लगभग 3n/2 - 2 तुलनाएँ करता है (T(n) = 2T(n/2) + 2), जो O(n) है।

Explanation

Optimal BST is solved by dynamic programming because it has optimal substructure: the best tree contains optimal subtrees for its left and right key ranges (and the subproblems overlap).

Explanation

Memoization stores the results of overlapping subproblems (for example the best cost from each vertex to the sink) so they are reused, not recomputed, in multistage graph DP.Memoization ओवरलैपिंग उप-समस्याओं के परिणाम (जैसे हर वर्टेक्स से sink तक की सर्वोत्तम लागत) संग्रहीत करती है ताकि multistage graph DP में उन्हें दोबारा गणना करने के बजाय दोबारा उपयोग किया जाए।

Explanation

An array-based stack reserves a fixed block of memory for a set maximum number of elements, so it can overflow. A linked-list stack grows dynamically.Array-आधारित स्टैक अधिकतम तत्वों की तय संख्या के लिए मेमोरी का निश्चित ब्लॉक आरक्षित करता है, इसलिए वह overflow हो सकता है। Linked-list स्टैक गतिशील रूप से बढ़ता है।