ડેટા સ્ટ્રક્ચર અને એપ્લિકેશન (1333203) - વિન્ટર 2024 સોલ્યુશન

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

#

રેખીય ડેટા સ્ટ્રક્ચર્સના નામ લખો.

જવાબ:

યાદ રાખવાની યુક્તિ: “બધા વિદ્યાર્થીઓ લાઈનમાં ઊભા રહે છે”

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

#

ટાઇમ અને સ્પેસ કોમ્પલેક્ષીટી વ્યાખ્યાયીત કરો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “ટાઇમ સ્ટેપ્સ, સ્પેસ સ્ટોર્સ”

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

#

ઉદાહરણ સાથે ક્લાસ અને ઓબ્જેક્ટનો કોન્સેપ્ટ સમજાવો.

જવાબ:

ડાયાગ્રામ:

classDiagram
    class Student {
        -int rollNo
        -string name
        +setData()
        +displayData()
    }

કોડ ઉદાહરણ:

class Student:
    def __init__(self):
        self.rollNo = 0
        self.name = ""
        
    def setData(self, r, n):
        self.rollNo = r
        self.name = n
        
    def displayData(self):
        print(self.rollNo, self.name)

# ઓબ્જેક્ટ બનાવવા
student1 = Student()
student1.setData(101, "રાજ")

યાદ રાખવાની યુક્તિ: “ક્લાસ બનાવે, ઓબ્જેક્ટ વાપરે”

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

#

વિદ્યાર્થીઓના રેકોર્ડ્સ ને સંચાલિત કરવા માટેનો એક ક્લાસ બનાવો જેમા વિદ્યાર્થીને ઉમેરવા તેમજ બાદ કરવા માટેની મેથડ હોય.

જવાબ:

ડાયાગ્રામ:

classDiagram
    class StudentManager {
        -Student[] students
        -int count
        +addStudent()
        +removeStudent()
        +displayAll()
    }

કોડ:

class StudentManager:
    def __init__(self):
        self.students = []
        
    def addStudent(self, roll, name):
        student = Student()
        student.setData(roll, name)
        self.students.append(student)
        
    def removeStudent(self, roll):
        for i in range(len(self.students)):
            if self.students[i].rollNo == roll:
                self.students.pop(i)
                break
    
    def displayAll(self):
        for student in self.students:
            student.displayData()

યાદ રાખવાની યુક્તિ: “ઉમેરો વધારે, કાઢો ઘટાડે”

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

#

ક્લાસમાં કન્સ્ટ્રક્ટરનું મહત્વ સમજાવો.

જવાબ:

યાદ રાખવાની યુક્તિ: “શરૂઆત હંમેશા સારી”

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

#

સ્ટેક પર વિવિધ ઓપરેશન સમજાવો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “નાખો કાઢો જુઓ”

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

#

*પોસ્ટફિક્સ એક્સપ્રેશન ABC+D/ નું મૂલ્યાંકન અલગોરિધમનું વર્ણન કરો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “વાંચો, પુશ કરો, પોપ કરો, ગણતરી કરો”

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

#

સ્ટેક અને ક્યુ વચ્ચેનો તફાવત લખો.

જવાબ:

યાદ રાખવાની યુક્તિ: “સ્ટેક છેલ્લું પહેલું, ક્યુ પહેલું પહેલું”

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

#

સર્ક્યુલર ક્યુ નો કોન્સેપ્ટ સમજાવો.

જવાબ:

ડાયાગ્રામ:

graph TD
    A[Front] --> B[1]
    B --> C[2]
    C --> D[3]
    D --> E[4]
    E --> F[5]
    F --> G[Rear]
    G --> A

યાદ રાખવાની યુક્તિ: “સર્ક્યુલર ફ્રન્ટને રીઅર સાથે જોડે”

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

#

સિંગલી લિંક્ડ લિસ્ટમાં આપેલ નોડ પછી અને પહેલાં નવા નોડ દાખલ કરવાની પ્રક્રિયાનું વર્ણન કરો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “પછી: લિંક બદલો, પહેલા: અગાઉનો શોધો”

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

#

લિંક્ડ લિસ્ટ મા એક છેડાથી બીજા છેડા સુધી પસાર થવાની પ્રક્રિયા સમજાવો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “શરૂ કરો, જુઓ, આગળ વધો, દોહરાવો”

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

#

ઇનફિક્સથી પોસ્ટફિક્સમાં એક્સપ્રેસનનું રૂપાંતર સમજાવો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “ઓપરેટર પુશ-પોપ, ઓપરેન્ડ સીધા આઉટપુટમાં”

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

#

સિંગલી લિંક્ડ લિસ્ટની શરૂઆતનો અને અંતનો નોડ ડીલીટ કરવા માટેનો પ્રોગ્રામ લખો.

જવાબ:

ડાયાગ્રામ:

કોડ:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def deleteFirst(self):
        if self.head is None:
            return
        self.head = self.head.next
    
    def deleteLast(self):
        if self.head is None:
            return
        
        # જો માત્ર એક જ નોડ હોય
        if self.head.next is None:
            self.head = None
            return
            
        temp = self.head
        while temp.next.next:
            temp = temp.next
        
        temp.next = None

યાદ રાખવાની યુક્તિ: “પહેલો: હેડ શિફ્ટ કરો, છેલ્લો: પાછલો શોધો”

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

#

લિંક્ડ લિસ્ટમાં કોઇ એલિમેન્ટ શોધવાની પ્રક્રિયા સમજાવો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “શરૂ કરો, ચેક કરો, આગળ વધો, દોહરાવો”

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

#

સર્ક્યુલર લિંક્ડ લિસ્ટ નો કોન્સેપ્ટ સમજાવો.

જવાબ:

ડાયાગ્રામ:

graph LR
    A[10] --> B[20]
    B --> C[30]
    C --> A

યાદ રાખવાની યુક્તિ: “છેલ્લો પહેલાને જોડે”

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

#

લિસ્ટમાંથી બાઇનરી સર્ચનો ઉપયોગ કરીને કોઇ એક એલિમેન્ટ શોધવાનું અલગોરીધમ સમજાવો.

જવાબ:

ડાયાગ્રામ:

graph TD
    A[Start] --> B[Set Low=0, High=n-1]
    B --> C{Low <= High?}
    C -->|Yes| D[Mid = (Low+High)/2]
    D --> E{A[Mid] == Key?}
    E -->|Yes| F[Return Mid]
    E -->|No| G{A[Mid] < Key?}
    G -->|Yes| H[Low = Mid+1]
    G -->|No| I[High = Mid-1]
    H --> C
    I --> C
    C -->|No| J[Return -1]

કોડ:

def binarySearch(arr, key):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

યાદ રાખવાની યુક્તિ: “મધ્ય, તુલના, અડધું કાઢો”

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

#

લિંક્ડ લિસ્ટના ઉપયોગ લખો.

જવાબ:

યાદ રાખવાની યુક્તિ: “ડેટા ડાયનેમિક સ્ટોર કરો”

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

#

સિંગલી અને ડબલી લિંક્ડ લિસ્ટ વચ્ચેનો તફાવત લખો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “એક દિશા, બે દિશા”

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

#

સિલેક્શન સોર્ટ અલગોરીધમનો ઉપયોગ કરીને આંકડાઓને ચઢતા ક્રમમાં ગોઠવવાનો પ્રોગ્રામ લખો.

જવાબ:

ડાયાગ્રામ:

કોડ:

def selectionSort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # મિનિમમ એલિમેન્ટને પહેલા એલિમેન્ટ સાથે સ્વેપ કરો
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# ઉદાહરણ
arr = [5, 3, 8, 1, 2]
sorted_arr = selectionSort(arr)
print(sorted_arr)  # આઉટપુટ: [1, 2, 3, 5, 8]

યાદ રાખવાની યુક્તિ: “મિનિમમ શોધો, પોઝિશન બદલો”

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

#

બબલ સોર્ટ અલગોરીધમ સમજાવો.

જવાબ:

ડાયાગ્રામ:

graph LR
    A[Pass 1] --> B[Pass 2]
    B --> C[Pass 3]
    C --> D[Pass 4]
    D --> E[Sorted]

યાદ રાખવાની યુક્તિ: “મોટા બબલ ઉપર જાય”

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

#

લિનિયર અને બાઇનરી સર્ચ વચ્ચેનો તફાવત લખો.

જવાબ:

યાદ રાખવાની યુક્તિ: “લિનિયર બધાને જુએ, બાઇનરી અડધું કાપે”

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

#

ક્વીક સોર્ટ અને મર્જ સોર્ટ સમજાવો.

જવાબ:

ક્વીક સોર્ટ:

graph TD
    A[Quick Sort] --> B[Select Pivot]
    B --> C[Partition Around Pivot]
    C --> D[Quick Sort Left Partition]
    C --> E[Quick Sort Right Partition]

મર્જ સોર્ટ:

graph TD
    A[Merge Sort] --> B[Divide Array in Half]
    B --> C[Sort Left Half]
    B --> D[Sort Right Half]
    C --> E[Merge Sorted Halves]
    D --> E

યાદ રાખવાની યુક્તિ: “ક્વીક વિભાજે, મર્જ જોડે”

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

#

પૂર્ણ બાઇનરી ટ્રી ની વ્યાખ્યા આપો.

જવાબ:

ડાયાગ્રામ:

યાદ રાખવાની યુક્તિ: “ડાબેથી જમણે, લેવલ દર લેવલ ભરો”

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

#

બાઇનરી ટ્રી મા ઇનઓર્ડર ટ્રાવર્સલ સમજાવો.

જવાબ:

ડાયાગ્રામ:

કોડ:

def inorderTraversal(root):
    if root:
        inorderTraversal(root.left)
        print(root.data, end=" → ")
        inorderTraversal(root.right)

યાદ રાખવાની યુક્તિ: “ડાબું, રૂટ, જમણું”

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

#

બાઇનરી સર્ચ ટ્રી મા નોડ દાખલ કરવા માટેનો પ્રોગ્રામ લખો.

જવાબ:

ડાયાગ્રામ:

graph TD
    A[50] --> B[30]
    A --> C[70]
    B --> D[20]
    B --> E[40]

    F[Insert 35] --> G[Compare with 50]
    G --> H[Go Left to 30]
    H --> I[Go Right to 40]
    I --> J[Go Left]
    J --> K[Insert 35]

કોડ:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
        
    return root

યાદ રાખવાની યુક્તિ: “તુલના કરો, મૂવ કરો, દાખલ કરો”

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

#

બાઇનરી સર્ચ ટ્રીની મૂળભૂત ખાસિયતો જણાવો.

જવાબ:

યાદ રાખવાની યુક્તિ: “ડાબે ઓછું, જમણે વધુ”

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

#

બાઇનરી ટ્રી મા પોસ્ટ ઓર્ડર ટ્રાવર્સલ સમજાવો.

જવાબ:

ડાયાગ્રામ:

કોડ:

def postorderTraversal(root):
    if root:
        postorderTraversal(root.left)
        postorderTraversal(root.right)
        print(root.data, end=" → ")

યાદ રાખવાની યુક્તિ: “ડાબું, જમણું, રૂટ”

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

#

બાઇનરી સર્ચ ટ્રી માંથી નોડ ડીલીટ કરવા માટેનો પ્રોગ્રામ લખો.

જવાબ:

ડાયાગ્રામ:

graph TD
    A[Find Node]
    A --> B{Node has 0 children?}
    B -->|Yes| C[Simply remove node]
    B -->|No| D{Node has 1 child?}
    D -->|Yes| E[Replace with child]
    D -->|No| F[Replace with inorder successor]

કોડ:

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
        
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        # એક અથવા કોઈ ચાઈલ્ડ નથી
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
            
        # બે ચાઈલ્ડ
        successor = minValueNode(root.right)
        root.key = successor.key
        root.right = deleteNode(root.right, successor.key)
        
    return root

યાદ રાખવાની યુક્તિ: “શોધો, બદલો, ફરી જોડો”