ડેટા સ્ટ્રક્ચર વિથ પાયથન (4331601) - સમર 2024 સોલ્યુશન

પ્રશ્ન 1(a) [3 ગુણ]

Array અને list નો તફાવત જણાવો.

જવાબ:

મેમરી ટ્રીક: "Arrays નિશ્ચિત મિત્રો, Lists લવચીક નેતાઓ"

પ્રશ્ન 1(b) [4 ગુણ]

Class અને object ના concept python program ની મદદથી સમજાવો.

જવાબ:

Class એ એક blueprint છે જે objects ના structure અને behavior વ્યાખ્યાયિત કરે છે. Object એ class નો instance છે.

Python

• Class: Template બનાવે છે
• Object: વાસ્તવિક instance બનાવે છે
• Constructor: Object initialize કરે છે

મેમરી ટ્રીક: "Class Blueprint બનાવે Object Instances"

પ્રશ્ન 1(c) [7 ગુણ]

Constructor ની વ્યાખ્યા આપો. વિવિધ પ્રકાર ના constructor python program સાથે સમજાવો.

જવાબ:

Constructor એ special method છે જે object creation time પર automatically call થાય છે. Python માં __init__() method constructor છે.

Python

Constructor ના પ્રકારો:

મેમરી ટ્રીક: "Default Parameters Copy Objects"

પ્રશ્ન 1(c) OR [7 ગુણ]

Polymorphism ની વ્યાખ્યા આપો. Inheritance વડે Polymorphism નો python program લખો.

જવાબ:

Polymorphism એ સમાન interface વાપરીને અલગ અલગ objects પર અલગ અલગ operations કરવાની ક્ષમતા છે.

Python

• Method Overriding: Child class માં સમાન method name
• Dynamic Binding: Runtime પર method selection
• Code Reusability: સમાન interface, અલગ implementation

મેમરી ટ્રીક: "ઘણા Objects, એક Interface"

પ્રશ્ન 2(a) [3 ગુણ]

Python અંતર્ગત data structure List, Tuple અને Dictionary સમજાવો.

જવાબ:

મેમરી ટ્રીક: "Lists બદલાય, Tuples રહે, Dictionaries નકશો"

પ્રશ્ન 2(b) [4 ગુણ]

Stack ની એપ્લિકેશન જણાવો.

જવાબ:

Stack Applications:

• Function Calls: Call stack management
• Expression Evaluation: Infix to postfix conversion
• Undo Operations: Text editors, browsers
• Parentheses Matching: Syntax checking

goat

મેમરી ટ્રીક: "Functions Evaluate કરે Undo Parentheses"

પ્રશ્ન 2(c) [7 ગુણ]

Stack ની વ્યાખ્યા આપો. PUSH અને POP operation ઉદાહરણ સાથે સમજાવો. Stack ના PUSH અને POP operation ના algorithm લખો.

જવાબ:

Stack એ LIFO (Last In First Out) સિદ્ધાંત અનુસરતું linear data structure છે.

PUSH Algorithm:

1. Check કરો કે stack ભરેલો છે કે નહીં
2. જો ભરેલો હોય, print "Stack Overflow"
3. અન્યથા, top increment કરો
4. Top position પર element add કરો

POP Algorithm:

1. Check કરો કે stack ખાલી છે કે નહીં
2. જો ખાલી હોય, print "Stack Underflow"
3. અન્યથા, top થી element remove કરો
4. Top decrement કરો

ઉદાહરણ:

Python

મેમરી ટ્રીક: "છેલ્લો અંદર, પહેલો બહાર - થાળીઓ જેવું"

પ્રશ્ન 2(a) OR [3 ગુણ]

નીચેની વ્યાખ્યા આપો: I. Time Complexity II. Space Complexity III. Best case

જવાબ:

મેમરી ટ્રીક: "Time Space Best Performance"

પ્રશ્ન 2(b) OR [4 ગુણ]

નીચે આપેલા infix expression ને postfix માં ફેરવો. A – (B / C + (D % E * F) / G) H*

જવાબ:

Step-by-step conversion:

Infix: A – (B / C + (D % E * F) / G) * H

1. A B C / D E % F * G / + - H *

Stack operations:
- Operators: -, (, /, +, (, %, *, ), /, ), *
- Final: A B C / D E % F * G / + - H *

Postfix પરિણામ: A B C / D E % F * G / + - H *

મેમરી ટ્રીક: "Operands પહેલા, Operators પછી"

પ્રશ્ન 2(c) OR [7 ગુણ]

Circular queue ની વ્યાખ્યા આપો. Circular queue ના INSERT અને DELETE operations આકૃતિ સાથે સમજાવો.

જવાબ:

Circular Queue એ queue નું સુધારેલું સ્વરૂપ છે જ્યાં છેલ્લી સ્થિતિ પ્રથમ સ્થિતિ સાથે જોડાયેલી હોય છે.

goat

INSERT Algorithm:

1. Check કરો કે queue ભરેલો છે કે નહીં
2. rear = (rear + 1) % size
3. queue[rear] = element
4. જો પ્રથમ element હોય, તો front = 0 સેટ કરો

DELETE Algorithm:

1. Check કરો કે queue ખાલી છે કે નહીં
2. element = queue[front]
3. front = (front + 1) % size
4. Element return કરો

• ફાયદો: Memory efficiency
• ઉપયોગ: CPU scheduling, buffering

મેમરી ટ્રીક: "ભરાઈ જાય તો પાછા ફરો"

પ્રશ્ન 3(a) [3 ગુણ]

List નો ઉપયોગ કરી Stack નું Implementation સમજાવો.

જવાબ:

Stack operations Python List વડે:

Python

• PUSH: append() method
• POP: pop() method
• TOP: stack[-1] for peek

મેમરી ટ્રીક: "Append ધકેલે, Pop ખેંચે"

પ્રશ્ન 3(b) [4 ગુણ]

Linked list ની વિવિધ એપ્લિકેશન વિશે ચર્ચા કરો.

જવાબ:

Linked List Applications:

• Dynamic Memory: Runtime પર size બદલાય
• Insertion/Deletion: કોઈપણ સ્થાને કાર્યક્ષમ
• Implementation: Stacks, queues, graphs
• Undo Functionality: Browser history, text editors

મેમરી ટ્રીક: "ગતિશીલ Implementation Undo Memory"

પ્રશ્ન 3(c) [7 ગુણ]

Doubly linked list સમજાવો. Doubly linked list માં શરૂઆત ની node ને delete કરવા માટેનો algorithm લખો.

જવાબ:

Doubly Linked List માં દરેક node માં data, next pointer અને previous pointer હોય છે.

goat

શરૂઆતથી Delete કરવાનો Algorithm:

1. જો list ખાલી હોય, તો return
2. જો માત્ર એક node હોય:
   - head = NULL
3. અન્યથા:
   - temp = head
   - head = head.next
   - head.prev = NULL
   - temp ને delete કરો

Python

મેમરી ટ્રીક: "બે દિશા નેવિગેશન"

પ્રશ્ન 3(a) OR [3 ગુણ]

નીચે આપેલા infix expression ને postfix માં ફેરવો: A+B/C*D-E/F-G

જવાબ:

Step-by-step conversion:

Infix: A+B/C*D-E/F-G

Postfix: A B C / D * + E F / - G -

Operator precedence: *, / > +, -
ડાબેથી જમણે associativity

મેમરી ટ્રીક: "ગુણા ભાગ પહેલા, સરવાળો બાદબાકી પછી"

પ્રશ્ન 3(b) OR [4 ગુણ]

Circular Linked List તેના ગેરફાયદા સાથે સમજાવો.

જવાબ:

Circular Linked List માં છેલ્લી node નો next pointer પ્રથમ node ને point કરે છે.

goat

ગેરફાયદાઓ:

• અનંત લૂપ જોખમ: ખોટા traversal
• જટિલ Implementation: વધારે સાવધાની જરૂરી
• Memory Overhead: વધારે pointer management
• Debugging મુશ્કેલી: Circular references

મેમરી ટ્રીક: "વર્તુળો મૂંઝવણ લાવી શકે"

પ્રશ્ન 3(c) OR [7 ગુણ]

Doubly Linked List માં Insert operation ને perform કરવા માટેનો Python Program લખો. સ્વચ્છ આકૃતિ સાથે સમજાવો.

જવાબ:

Python

goat

Insert Operations:

• શરૂઆત: Head pointer update કરો
• અંત: છેલ્લા node સુધી traverse કરો
• મધ્ય: prev/next pointers update કરો

મેમરી ટ્રીક: "શરૂઆત અંત મધ્ય Insertions"

પ્રશ્ન 4(a) [3 ગુણ]

Merge sort નો algorithm લખો.

જવાબ:

Merge Sort Algorithm:

1. જો array size <= 1 હોય, તો return
2. Array ને બે ભાગમાં વહેંચો
3. બંને ભાગોને recursively sort કરો
4. Sorted ભાગોને merge કરો

Time Complexity: O(n log n) Space Complexity: O(n)

મેમરી ટ્રીક: "વહેંચો જીતો મેળવો"

પ્રશ્ન 4(b) [4 ગુણ]

Singly Linked List અને Doubly Linked List નો તફાવત જણાવો.

જવાબ:

goat

મેમરી ટ્રીક: "સિંગલ આગળ, ડબલ બંને દિશા"

પ્રશ્ન 4(c) [7 ગુણ]

Selection sort નો algorithm લખો. આપેલા ડેટા ને selection sort ની મદદથી ચડતા ક્રમમાં ગોઠવી બતાવો. ડેટા: 13, 2, 6, 54, 18, 42, 11

જવાબ:

Selection Sort Algorithm:

1. i = 0 થી n-2 સુધી:
   2. array[i...n-1] માં minimum શોધો
   3. Minimum ને array[i] સાથે swap કરો

[13, 2, 6, 54, 18, 42, 11] માટે Trace:

અંતિમ પરિણામ: [2, 6, 11, 13, 18, 42, 54]

મેમરી ટ્રીક: "ન્યૂનતમ પસંદ કરો, સ્થાન બદલો"

પ્રશ્ન 4(a) OR [3 ગુણ]

Insertion sort નો algorithm લખો.

જવાબ:

Insertion Sort Algorithm:

1. i = 1 થી n-1 સુધી:
   2. key = array[i]
   3. j = i-1
   4. જ્યાં સુધી j >= 0 અને array[j] > key:
      5. array[j+1] = array[j]
      6. j = j-1
   7. array[j+1] = key

Time Complexity: O(n²) Best Case: O(n) sorted array માટે

મેમરી ટ્રીક: "યોગ્ય સ્થાને દાખલ કરો"

પ્રશ્ન 4(b) OR [4 ગુણ]

Circular linked list માં અંત માં નવી node insert કરવા માટેનો algorithm લખો.

જવાબ:

Algorithm:

1. Data સાથે new_node બનાવો
2. જો list ખાલી હોય:
   - head = new_node
   - new_node.next = new_node
3. અન્યથા:
   - temp = head
   - જ્યાં સુધી temp.next != head:
     - temp = temp.next
   - temp.next = new_node
   - new_node.next = head

Python

મેમરી ટ્રીક: "Head પર પાછા વર્તુળ"

પ્રશ્ન 4(c) OR [7 ગુણ]

Bubble sort નો algorithm લખો. આપેલા ડેટા ને bubble sort ની મદદથી ચડતા ક્રમમાં ગોઠવી બતાવો. ડેટા: 37, 22, 64, 84, 58, 52, 11

જવાબ:

Bubble Sort Algorithm:

1. i = 0 થી n-2 સુધી:
   2. j = 0 થી n-2-i સુધી:
      3. જો array[j] > array[j+1]:
         4. array[j] અને array[j+1] ને swap કરો

[37, 22, 64, 84, 58, 52, 11] માટે Trace:

અંતિમ પરિણામ: [11, 22, 37, 52, 58, 64, 84]

મેમરી ટ્રીક: "સૌથી મોટા બબલ ઉપર"

પ્રશ્ન 5(a) [3 ગુણ]

Binary search tree અને તેની application સમજાવો.

જવાબ:

Binary Search Tree (BST) એ binary tree છે જ્યાં left subtree માં નાની values અને right subtree માં મોટી values હોય છે.

ગુણધર્મો:

• Left child < Parent < Right child
• Inorder traversal sorted sequence આપે છે
• Search time: O(log n) average case

Applications:

મેમરી ટ્રીક: "Binary Search Trees ડેટા ગોઠવે"

પ્રશ્ન 5(b) [4 ગુણ]

Linear Search માટે Python Program લખો તથા ઉદાહરણ સાથે સમજાવો.

જવાબ:

Python

કામગીરી:

• ક્રમિક તપાસ: Element દર element
• Time Complexity: O(n)
• Space Complexity: O(1)
• કામ કરે છે: Unsorted arrays પર

મેમરી ટ્રીક: "લીનિયર લાઇન દર લાઇન"

પ્રશ્ન 5(c) [7 ગુણ]

આપેલી સાંખ્યઓ માટે Binary Search Tree બનાવો તથા તેના Preorder, Inorder અને Postorder traversals લખો: 45, 35, 12, 58, 5, 55, 58, 80, 35, 42

જવાબ:

BST બાંધકામ (duplicates અવગણવામાં આવેલ):

goat

Insertion ક્રમ: 45(root), 35(left), 12(35 ની left), 58(right), 5(12 ની left), 55(58 ની left), 80(58 ની right), 42(12 ની right)

Traversals:

મેમરી ટ્રીક: "Pre-Root પહેલા, In-Sorted, Post-Root છેલ્લે"

પ્રશ્ન 5(a) OR [3 ગુણ]

નીચેની વ્યાખ્યા આપો: I. Binary tree II. level number III. Leaf-node

જવાબ:

goat

મેમરી ટ્રીક: "Binary Levels લીડ કરે Leaves તરફ"

પ્રશ્ન 5(b) OR [4 ગુણ]

Linear Search અને Binary search વચ્ચેનો તફાવત જણાવો.

જવાબ:

goat

મેમરી ટ્રીક: "Linear લાઇન, Binary વિભાજન"

પ્રશ્ન 5(c) OR [7 ગુણ]

Binary search tree માં node ને insertion અને deletion માટેનો algorithm લખો.

જવાબ:

Insertion Algorithm:

1. જો root NULL છે, તો નવી node ને root બનાવો
2. જો data < root.data, તો left subtree માં insert કરો
3. જો data > root.data, તો right subtree માં insert કરો
4. જો data == root.data, તો insertion નહીં (duplicate)

Deletion Algorithm:

1. જો node leaf છે: સીધું delete કરો
2. જો node માં એક child છે: child સાથે બદલો
3. જો node માં બે children છે:
   - Inorder successor શોધો
   - Data ને successor ના data સાથે બદલો
   - Successor ને delete કરો

Python

કેસો:

• Leaf deletion: સીધું removal
• એક child: Child સાથે replace
• બે children: Successor સાથે replace

મેમરી ટ્રીક: "Insert સરખાવો, Delete બદલો"