Data Structures - RGPV 2024 Question Paper

Save as PDF

Opens your browser print dialog — select "Save as PDF" to download.

B.Tech./B.Tech. (Working Professional) III Semester

Examination, December 2024

Grading System (GS) / Working Professional

Data Structures

Time : Three Hours

Maximum Marks : 70

Note: i) Attempt any five questions.

किन्हीं पाँच प्रश्नों को हल कीजिए।

ii) All questions carry equal marks.

सभी प्रश्नों के समान अंक हैं।

iii) In case of any doubt or dispute the English version question should be treated as final.

किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।

a) What is the key difference between static and dynamic memory allocation in data structures? Discuss the time complexity of accessing an element in an array and justify your answer.

डाटा संरचनाओं में स्थिर और गतिशील मेमोरी आवंटन के बीच मुख्य अंतर क्या है? सरणी में किसी तत्व तक पहुँचने की समय जटिलता पर चर्चा करें और अपने उत्तर को उचित ठहराएँ।

b) Write a program/ algorithm of polynomial addition using linked list.

लिंक्ड सूची का उपयोग करके बहुपद जोड़ का एक प्रोग्राम/एल्गोरिदम लिखें।

a) Explain how a stack can be used to evaluate a postfix expression.

कम्पीज अभिव्यक्ति (एक्स्प्रेशन) का मूल्यांकन करने के लिए स्टैक का उपयोग कैसे किया जा सकता है?

b) How would you handle a queue overflow in a circular queue implementation? Write the function to insert and delete from circular queue.

आप सर्कुलर क्यू कार्यान्वयन में क्यू ओवरफ्लो को कैसे संभालेंगे? सर्कुलर क्यू से सम्मिलित करने और हटाने के लिए फंक्शन लिखें।

a) Define the terms degree, depth, and height in the context of trees and provide examples.

ट्री के संदर्भ में डिग्री, गहराई और ऊँचाई शब्दों को परिभाषित करें और उदाहरण दें।

b) Why is AVL tree rebalancing required, and how does it maintain its balance?

AVL ट्री रीबेलेंसिंग की आवश्यकता क्यों है और यह अपना संतुलन कैसे बनाए रखता है?

a) Explain the difference between BFS and DFS traversal with an example graph.

एक उदाहरण ग्राफ के साथ BFS और DFS ट्रैवर्सल के बीच अंतर की व्याख्या करें।

b) Why is Kruskal's algorithm considered a greedy algorithm? Justify your answer.

क्रुस्कल के एल्गोरिथम को लालची एल्गोरिथम क्यों माना जाता है? अपने उत्तर का औचित्य सिद्ध करें।

c) Define the following terms with respect to a graph:

Degree of vertex
Incident edge
Directed edge
Path

एक ग्राफ के संबंध में निम्नलिखित शब्दों को परिभाषित करें।

शीर्ष की डिग्री
घटना किनारा
निर्देशित किनारा
पथ

[3]

a) Differentiate between directed and undirected graphs with real-world examples.

वास्तविक दुनिया के उदाहरणों के साथ निर्देशित और अनिर्देशित ग्राफ के बीच अंतर करें।

b) Trace the steps of recursive merge sort algorithm to sort the following elements:
12, 25, 5, 9, 1, 84, 63, 7, 15, 4, 3

निम्नलिखित तत्वों को सॉर्ट करने के लिए पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम के चरणों का पता लगाएं।
12, 25, 5, 9, 1, 84, 63, 7, 15, 4, 3

a) Rearrange following numbers using quick sort:
13, 7, 4, 8, 19, 25, 66, 32, 75

क्विक सॉर्ट का उपयोग करके निम्नलिखित संख्याओं को पुनर्व्यवस्थित करें।
13, 7, 4, 8, 19, 25, 66, 32, 75

b) Write a program to sort the elements using radix sort. Explain giving an example.

रेडिक्स सॉर्ट का उपयोग करके तत्वों को सॉर्ट करने के लिए एक प्रोग्राम लिखें। एक उदाहरण देकर समझाएं।

[4]

a) Develop a binary search tree resulting tree after inserting the following integer keys
29, 13, 11, 35, 77, 26, 59, 21, 9.
i) Check whether the tree is almost complete or not?
ii) Determine the height of the tree
iii) Write postorder and preorder traversals.

निम्नलिखित पूर्णांक कुंजियाँ
29, 13, 11, 35, 77, 26, 59, 21, 9
डालने के बाद प्राप्त बाइनरी सर्च ट्री विकसित करें।
i) जाँच करें कि क्या पेड़ लगभग पूरा हो गया है या नहीं?
ii) पेड़ की ऊँचाई निर्धारित करें
iii) पोस्टऑर्डर और प्रीऑर्डर ट्रैवर्सल लिखें।

b) Explain how Prim's algorithm is used for finding the minimum spanning tree of a graph.

समझाएं कि ग्राफ के न्यूनतम स्पैनिंग ट्री को खोजने के लिए प्राइम एल��गोरिथम का उपयोग कैसे किया जाता है?

a) Discuss the advantages and disadvantages of using Shell sort over Insertion Sort.

इन्सर्शन सॉर्ट की तुलना में शेल सॉर्ट का उपयोग करने के फायदे और नुकसान पर चर्चा करें।

b) Write an algorithm to insert and delete a key from circular queue.

सर्कुलर कतार से कुंजी डालने और हटाने के लिए एक एल्गोरिथम लिखें।

c) Sort the following numbers using Insertion sort. For the Given Numbers:
34, 8, 14, 61, 4, 53, 81, 47

इन्सर्शन सॉर्ट का उपयोग करके निम्नलिखित संख्याओं को सॉर्ट करें। दी गई संख्याओं के लिए:
34, 8, 14, 61, 4, 53, 81, 47

******