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

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

#

રેખીય ડેટા સ્ટ્રક્ચર વ્યાખ્યાયિત કરો અને તેના ઉદાહરણો આપો.

જવાબ: રેખીય ડેટા સ્ટ્રક્ચર એ એલિમેન્ટ્સનો એવો સંગ્રહ છે કે જેમાં દરેક એલિમેન્ટની પહેલાં અને પછી એક જ એલિમેન્ટ હોય છે (સિવાય કે પ્રથમ અને છેલ્લા એલિમેન્ટ).

કોષ્ટક: રેખીય ડેટા સ્ટ્રક્ચરના ઉદાહરણો

યાદ રાખવાનું સૂત્ર: “ALSQ એ લાઇનમાં છે”

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

#

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

જવાબ: ટાઇમ અને સ્પેસ કોમ્પ્લેક્સિટી એલ્ગોરિધમની કાર્યક્ષમતાને એક્ઝિક્યુશન ટાઇમ અને મેમરી વપરાશના સંદર્ભમાં માપે છે, જેમ ઇનપુટ સાઇઝ વધે છે.

કોષ્ટક: કોમ્પ્લેક્સિટી કમ્પેરિઝન

યાદ રાખવાનું સૂત્ર: “TS: ટાઇમ-સ્પીડ અને સ્પેસ-સ્ટોરેજ”

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

#

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

જવાબ: ક્લાસ અને ઓબ્જેક્ટ એ OOP ના મૂળભૂત કોન્સેપ્ટ છે જ્યાં ક્લાસ એ એટ્રિબ્યુટ્સ અને બિહેવિયર્સ ધરાવતા ઓબ્જેક્ટ બનાવવા માટેના બ્લુપ્રિન્ટ છે.

ડાયાગ્રામ: ક્લાસ અને ઓબ્જેક્ટ રિલેશનશિપ

classDiagram
    class Student {
        +name: string
        +rollNo: int
        +marks: float
        +displayInfo()
    }
    Student <|-- StudentObject: Creates

કોડ ઉદાહરણ:

class Student:
    def __init__(self, name, rollNo, marks):
        self.name = name
        self.rollNo = rollNo
        self.marks = marks
    
    def displayInfo(self):
        print(f"Name: {self.name}, Roll No: {self.rollNo}, Marks: {self.marks}")

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

• ક્લાસ: એટ્રિબ્યુટ્સ (name, rollNo, marks) અને મેથડ્સ (displayInfo) વ્યાખ્યાયિત કરતા બ્લુપ્રિન્ટ
• ઓબ્જેક્ટ: ક્લાસથી બનાવેલ ઇન્સ્ટન્સ (student1) જેમાં ચોક્કસ વેલ્યુઝ હોય છે

યાદ રાખવાનું સૂત્ર: “CAR - ક્લાસ એટ્રિબ્યુટ્સ અને રુટિન્સ વ્યાખ્યાયિત કરે છે”

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

#

ઇંસ્ટટંસ મેથડ, ક્લાસ મેથડ અને સ્ટેટિક મેથડ ઉદાહરણ સાથે સમજાવો.

જવાબ: Python ત્રણ પ્રકારની મેથડ્સને સપોર્ટ કરે છે: ઇન્સ્ટન્સ, ક્લાસ અને સ્ટેટિક મેથડ, દરેક અલગ હેતુ માટે વપરાય છે.

કોષ્ટક: મેથડ પ્રકારોની તુલના

કોડ ઉદાહરણ:

class Student:
    school = "ABC School"  # ક્લાસ વેરિએબલ
    
    def __init__(self, name):
        self.name = name  # ઇન્સ્ટન્સ વેરિએબલ
    
    def instance_method(self):  # ઇન્સ્ટન્સ મેથડ
        return f"Hi {self.name} from {self.school}"
    
    @classmethod
    def class_method(cls):  # ક્લાસ મેથડ
        return f"School is {cls.school}"
    
    @staticmethod
    def static_method():  # સ્ટેટિક મેથડ
        return "This is a utility function"

યાદ રાખવાનું સૂત્ર: “ICS: ઇન્સ્ટન્સ-Self, ક્લાસ-Cls, સ્ટેટિક-Solo”

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

#

રીકર્ઝીવ ફંકશન નો કોંસેપ્ટ સમજાવો.

જવાબ: રિકર્સિવ ફંક્શન એ એવું ફંક્શન છે જે પોતાની એક્ઝિક્યુશન દરમિયાન સમાન સમસ્યાના નાના ઉદાહરણોને હલ કરવા માટે પોતાને જ કૉલ કરે છે.

ડાયાગ્રામ: રિકર્સિવ ફંક્શન એક્ઝિક્યુશન

graph TD
    A[factorial(3)] --> B[factorial(2)]
    B --> C[factorial(1)]
    C --> D[Return 1]
    D --> E[Return 1*2=2]
    E --> F[Return 2*3=6]

યાદ રાખવાનું સૂત્ર: “BASE અને RECURSE - બેઝ કેસ સ્ટોપ્સ, રિકર્ઝન રિપીટ્સ”

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

#

સ્ટેક અને ક્યુ વ્યાખ્યાયિત કરો.

જવાબ: સ્ટેક અને ક્યુ એ લીનિયર ડેટા સ્ટ્રક્ચર છે જેમાં ડેટા ઇન્સર્શન અને રિમૂવલ માટે અલગ એક્સેસ પેટર્ન છે.

કોષ્ટક: સ્ટેક વિ. ક્યુ

યાદ રાખવાનું સૂત્ર: “SLIFF vs QFIFF - સ્ટેક-LIFO vs ક્યુ-FIFO”

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

#

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

જવાબ: સ્ટેક ઓપરેશન્સ LIFO (લાસ્ટ ઇન ફર્સ્ટ આઉટ) સિદ્ધાંતને અનુસરે છે અને નીચેના મૂળભૂત ઓપરેશન્સ ધરાવે છે:

કોષ્ટક: સ્ટેક ઓપરેશન્સ

ડાયાગ્રામ: સ્ટેક ઓપરેશન્સ

કોડ ઉદાહરણ:

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
    
    def peek(self):
        if not self.isEmpty():
            return self.items[-1]
    
    def isEmpty(self):
        return len(self.items) == 0

યાદ રાખવાનું સૂત્ર: “PIPES - Push In, Pop Exit, See top”

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

#

સિંગલી લિંક્ડ લિસ્ટ વ્યાખ્યાયિત કરો.

જવાબ: સિંગલી લિંક્ડ લિસ્ટ એ એક લીનિયર ડેટા સ્ટ્રક્ચર છે જેમાં નોડ્સનો કલેક્શન હોય છે જ્યાં દરેક નોડમાં ડેટા અને આગળના નોડનો રેફરન્સ હોય છે.

ડાયાગ્રામ: સિંગલી લિંક્ડ લિસ્ટ

યાદ રાખવાનું સૂત્ર: “DNL - ડેટા અને નેક્સ્ટ લિંક”

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

#

ક્યુ ઉપર એનક્યુ ડીક્યુ ઓપરેશન સમજાવો.

જવાબ: એનક્યુ અને ડિક્યુ ક્યુ ડેટા સ્ટ્રક્ચરમાં એલિમેન્ટ્સ ઉમેરવા અને કાઢવા માટેના મુખ્ય ઓપરેશન્સ છે.

કોષ્ટક: ક્યુ ઓપરેશન્સ

ડાયાગ્રામ: ક્યુ ઓપરેશન્સ

યાદ રાખવાનું સૂત્ર: “ERfDFr - Enqueue at Rear, Dequeue from Front”

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

#

A+B/C+D પદ ને પોસ્ટફિક્સ મા ફેરવો અને STACK નો ઉપયોગ કરીને A,B,C અને D ની કોઇ યકમત ધારીને એનુ મુલ્ય શોધો.

જવાબ: “A+B/C+D” એક્સપ્રેશનને પોસ્ટફિક્સમાં કન્વર્ટ કરીને સ્ટેકનો ઉપયોગ કરીને તેનું મૂલ્યાંકન કરવું:

સ્ટેપ 1: પોસ્ટફિક્સમાં કન્વર્ટ કરવું

કોષ્ટક: ઇનફિક્સથી પોસ્ટફિક્સ કન્વર્ઝન

ફાઇનલ પોસ્ટફિક્સ: A B C / + D +

સ્ટેપ 2: વેલ્યુઝ A=5, B=10, C=2, D=3 સાથે મૂલ્યાંકન કરવું

કોષ્ટક: પોસ્ટફિક્સ ઇવેલ્યુએશન

રિઝલ્ટ: 13

યાદ રાખવાનું સૂત્ર: “PC-SE - પુશ ઓપરેન્ડ્સ, કેલ્ક્યુલેટ ઓપરેટર્સ પર, સ્ટેક બધું સ્ટોર કરે”

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

#

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

જવાબ: લિંક્ડ લિસ્ટ એ વર્સેટાઇલ ડેટા સ્ટ્રક્ચર છે જેના ઘણા વ્યવહારિક ઉપયોગો છે.

કોષ્ટક: લિંક્ડ લિસ્ટના ઉપયોગો

યાદ રાખવાનું સૂત્ર: “DSUHM - ડાયનેમિક એલોકેશન, સ્ટેક & ક્યુ, અનડુ, હેશ ટેબલ્સ, મ્યુઝિક પ્લેયર”

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

#

પાયથનમા સિંગલી લિંક્ડ લિસ્ટ કેવી રીતે બનાવી શકાય એ સમજાવો.

જવાબ: પાયથનમાં સિંગલી લિંક્ડ લિસ્ટ બનાવવા માટે નોડ ક્લાસ ડિફાઇન કરવી અને બેઝિક ઓપરેશન્સ ઇમ્પ્લિમેન્ટ કરવા પડે છે.

કોડ ઉદાહરણ:

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        # જો લિસ્ટ ખાલી હોય, તો નવા નોડને હેડ તરીકે સેટ કરો
        if self.head is None:
            self.head = new_node
            return
        # છેલ્લે સુધી ટ્રેવર્સ કરીને નોડ ઉમેરો
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

ડાયાગ્રામ: લિંક્ડ લિસ્ટ બનાવવી

flowchart LR
    A["નોડ બનાવો"] --> B["ખાલી હોય તો હેડ સેટ કરો"]
    A --> C["નહીંતર છેડા સુધી જાઓ"]
    C --> D["છેડે નવો નોડ જોડો"]

યાદ રાખવાનું સૂત્ર: “CHEN - Create nodes, Head first, End attachment, Next pointers”

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

#

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

જવાબ: સિંગલી લિંક્ડ લિસ્ટની શરૂઆત અને અંતમાં નોડ ઉમેરવા માટે અલગ અલગ અભિગમની જરૂર પડે છે.

કોડ ઉદાહરણ:

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    # શરૂઆતમાં ઉમેરવું (prepend)
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    # અંતમાં ઉમેરવું (append)
    def insert_at_end(self, data):
        new_node = Node(data)
        # જો ખાલી લિસ્ટ હોય
        if self.head is None:
            self.head = new_node
            return
        
        # છેલ્લા નોડ સુધી ટ્રેવર્સ કરો
        current = self.head
        while current.next:
            current = current.next
        
        # નવો નોડ જોડો
        current.next = new_node

ડાયાગ્રામ: ઇન્સર્શન ઓપરેશન્સ

યાદ રાખવાનું સૂત્ર: “BEN - Beginning is Easy and Next-based, End Needs traversal”

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

#

સિંગલી લિંક્ડ મા રહેલ નોડ ની સંખ્યા ગણવા માટેનો કોડ લખો.

જવાબ: નોડની સંખ્યા ગણવા માટે હેડથી ટેઇલ સુધી આખી લિંક્ડ લિસ્ટ ટ્રેવર્સ કરવી પડે છે.

કોડ ઉદાહરણ:

def count_nodes(self):
    count = 0
    current = self.head
    
    # લિસ્ટને ટ્રેવર્સ કરો અને નોડ્સ ગણો
    while current:
        count += 1
        current = current.next
    
    return count

ડાયાગ્રામ: નોડ્સ ગણવા

flowchart LR
    A[count=0 ઇનિશિયલાઇઝ કરો] --> B[હેડથી શરૂ કરો]
    B --> C[દરેક નોડ ટ્રેવર્સ કરો]
    C --> D[count વધારો]
    D --> E[આગળના નોડ પર જાઓ]
    E --> C
    C -- બધા નોડ્સ ટ્રેવર્સ થયા --> F[count રિટર્ન કરો]

યાદ રાખવાનું સૂત્ર: “CIT - Count Incrementally while Traversing”

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

#

કોલમ એ અને કોલમ બી ના યોગ્ય વિકલ્પ જોડો.

જવાબ: વિવિધ લિંક્ડ લિસ્ટ પ્રકારો અને તેમના લક્ષણો વચ્ચેનું મેચિંગ:

કોષ્ટક: લિંક્ડ લિસ્ટ પ્રકારો અને લક્ષણોનું મેચિંગ

ડાયાગ્રામ: વિવિધ લિંક્ડ લિસ્ટ પ્રકારો

યાદ રાખવાનું સૂત્ર: “SDCN - Single-Direction, Double-Direction, Circular-Connection, Node-Component”

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

#

સિંગલી લિંક્ડ લિસ્ટ મા પ્રથમ અને છેલ્લો નોડ ને કાઢી નાખવાનુ સમજાવો.

જવાબ: સિંગલી લિંક્ડ લિસ્ટમાંથી નોડ કાઢવાની જટિલતા પોઝિશન (પ્રથમ વિ. છેલ્લો) પર આધારિત હોય છે.

કોષ્ટક: ડિલીશન કંપેરિઝન

કોડ ઉદાહરણ:

def delete_first(self):
    # ચેક કરો કે લિસ્ટ ખાલી છે કે નહીં
    if self.head is None:
        return
    
    # હેડને બીજા નોડ પર અપડેટ કરો
    self.head = self.head.next

def delete_last(self):
    # ચેક કરો કે લિસ્ટ ખાલી છે કે નહીં
    if self.head is None:
        return
    
    # જો માત્ર એક જ નોડ હોય
    if self.head.next is None:
        self.head = None
        return
    
    # બીજા છેલ્લા નોડ સુધી ટ્રેવર્સ કરો
    current = self.head
    while current.next.next:
        current = current.next
    
    # છેલ્લો નોડ દૂર કરો
    current.next = None

ડાયાગ્રામ: ડિલીશન ઓપરેશન્સ

યાદ રાખવાનું સૂત્ર: “FELO - First is Easy, Last needs One-before-last”

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

#

ડબ્લી લિંક્ડ લિસ્ટ નો કોન્સૈપ્ટ સમજાવો.

જવાબ: ડબલી લિંક્ડ લિસ્ટ એ બાયડાયરેક્શનલ લીનિયર ડેટા સ્ટ્રક્ચર છે જેમાં નોડ્સમાં ડેટા, અગાઉના, અને આગળના રેફરન્સ હોય છે.

ડાયાગ્રામ: ડબલી લિંક્ડ લિસ્ટ

યાદ રાખવાનું સૂત્ર: “PDN - Previous, Data, Next”

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

#

લિનિયર સર્ચ નો કોન્સૈપ્ટ સમજાવો.

જવાબ: લિનિયર સર્ચ એ સરળ સિક્વેન્શિયલ સર્ચ અલ્ગોરિધમ છે જે ટાર્ગેટ શોધવા માટે એક પછી એક દરેક એલિમેન્ટ ચેક કરે છે.

કોષ્ટક: લિનિયર સર્ચ લક્ષણો

ડાયાગ્રામ: લિનિયર સર્ચ પ્રોસેસ

flowchart LR
    A[પ્રારંભ] --> B[પ્રથમ એલિમેન્ટ ચેક કરો]
    B -- મેચ થયું --> C[પોઝિશન રિટર્ન કરો]
    B -- મેચ નથી થયું --> D[આગળના એલિમેન્ટ પર જાઓ]
    D --> E{અંત સુધી પહોંચ્યા?}
    E -- ના --> B
    E -- હા --> F[નથી મળ્યું]

યાદ રાખવાનું સૂત્ર: “SCENT - Search Consecutively Each element until Target”

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

#

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

જવાબ: બાયનરી સર્ચ એક કાર્યક્ષમ અલ્ગોરિધમ છે જે સર્ચ ઇન્ટરવલને વારંવાર અડધા ભાગમાં વિભાજિત કરીને સોર્ટેડ એરેમાં એલિમેન્ટ્સ શોધે છે.

કોડ ઉદાહરણ:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # ચેક કરો કે ટાર્ગેટ મિડ પર છે કે નહીં
        if arr[mid] == target:
            return mid
        
        # જો ટાર્ગેટ મોટો હોય, તો ડાબા ભાગને અવગણો
        elif arr[mid] < target:
            left = mid + 1
        
        # જો ટાર્ગેટ નાનો હોય, તો જમણા ભાગને અવગણો
        else:
            right = mid - 1
    
    # ટાર્ગેટ નથી મળ્યો
    return -1

ડાયાગ્રામ: બાયનરી સર્ચ પ્રોસેસ

યાદ રાખવાનું સૂત્ર: “MCLR - Middle Compare, Left or Right adjust”

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

#

સિલેક્શન સોર્ટ અલ્ગોરીધમ નો કોન્સૈપ્ટ સમજાવો.

જવાબ: સિલેક્શન સોર્ટ એ સરળ કમ્પેરિઝન-બેઝ્ડ સોર્ટિંગ અલ્ગોરિધમ છે જે એરેને સોર્ટેડ અને અનસોર્ટેડ રીજનમાં વિભાજિત કરે છે.

કોષ્ટક: સિલેક્શન સોર્ટ લક્ષણો

યાદ રાખવાનું સૂત્ર: “FSMR - Find Smallest, Move to Right position, Repeat”

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

#

બબલ સોર્ટ મેથડ સમજાવો.

જવાબ: બબલ સોર્ટ એ સરળ સોર્ટિંગ અલ્ગોરિધમ છે જે વારંવાર લિસ્ટમાં આગળ વધે છે, આસપાસના એલિમેન્ટ્સની તુલના કરે છે, અને જો તેઓ ખોટા ક્રમમાં હોય તો તેમને સ્વેપ કરે છે.

કોષ્ટક: બબલ સોર્ટ લક્ષણો

ડાયાગ્રામ: બબલ સોર્ટ પ્રોસેસ

યાદ રાખવાનું સૂત્ર: “CABS - Compare Adjacent, Bubble-up Swapping”

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

#

ઉદાહરણ સાથે ક્વીક સોર્ટ મેથડનુ વર્કિંગ સમજાવો.

જવાબ: ક્વિક સોર્ટ એ કાર્યક્ષમ ડિવાઇડ-એન્ડ-કોન્કર સોર્ટિંગ અલ્ગોરિધમ છે જે પિવોટ એલિમેન્ટ પસંદ કરીને અને એરેને પાર્ટિશન કરીને કામ કરે છે.

કોષ્ટક: ક્વિક સોર્ટ સ્ટેપ્સ

એરે [7, 2, 1, 6, 8, 5, 3, 4] સાથે ઉદાહરણ:

પિવોટ: 4
પાર્ટિશન પછી: [2, 1, 3] 4 [7, 6, 8, 5]
                 ડાબી    P  જમણી

ડાબા ભાગને રિકર્સિવલી સોર્ટ: [1] 2 [3] → [1, 2, 3]
જમણા ભાગને રિકર્સિવલી સોર્ટ: [5] 7 [6, 8] → [5, 6, 7, 8]

ફાઇનલ સોર્ટેડ એરે: [1, 2, 3, 4, 5, 6, 7, 8]

ડાયાગ્રામ: ક્વિક સોર્ટ પાર્ટિશનિંગ

flowchart TD
    A[એરે: 7,2,1,6,8,5,3,4] --> B[પિવોટ પસંદ કરો: 4]
    B --> C[પાર્ટિશન]
    C --> D[ડાબી: 2,1,3]
    C --> E[પિવોટ: 4]
    C --> F[જમણી: 7,6,8,5]
    D --> G[ડાબા ભાગને રિકર્સિવલી સોર્ટ કરો]
    F --> H[જમણા ભાગને રિકર્સિવલી સોર્ટ કરો]
    G --> I[સોર્ટેડ ડાબો: 1,2,3]
    H --> J[સોર્ટેડ જમણો: 5,6,7,8]
    I --> K[ફાઇનલ: 1,2,3,4,5,6,7,8]
    E --> K
    J --> K

યાદ રાખવાનું સૂત્ર: “PPR - Pivot, Partition, Recursive divide”

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

#

બાયનરી ટ્રી સમજાવો.

જવાબ: બાયનરી ટ્રી એ એક હાયરાર્કિકલ ડેટા સ્ટ્રક્ચર છે જેમાં દરેક નોડને વધુમાં વધુ બે ચિલ્ડ્રન હોય છે જેને લેફ્ટ અને રાઇટ ચાઇલ્ડ તરીકે ઓળખવામાં આવે છે.

ડાયાગ્રામ: બાયનરી ટ્રી

કોષ્ટક: બાયનરી ટ્રી પ્રોપર્ટીઝ

યાદ રાખવાનું સૂત્ર: “RLTM - Root, Left, Two, Maximum”

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

#

ટ્રી ના સંદભભ મા રૂટ, પાથ, પેરંટ અને ચિલ્ડ્રન પદો વ્યાખ્યાયિત કરો.

જવાબ: ટ્રીમાં હાયરાર્કીમાં નોડ્સ વચ્ચેના સંબંધોને વર્ણવવા માટે ચોક્કસ શબ્દાવલી છે.

કોષ્ટક: ટ્રી શબ્દાવલી

ડાયાગ્રામ: ટ્રી શબ્દાવલી

યાદ રાખવાનું સૂત્ર: “RPPC - Root at Top, Path connects, Parent above, Children below”

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

#

નીચે આપેલા ટ્રી માટે પ્રીઓર્ડર અને પોસ્ટઓર્ડર ટ્રાવર્સલ લાગુ કરો.

જવાબ: પ્રીઓર્ડર અને પોસ્ટઓર્ડર એ ડેપ્થ-ફર્સ્ટ ટ્રી ટ્રાવર્સલ મેથડ્સ છે જેમાં અલગ અલગ નોડ વિઝિટિંગ સિક્વન્સ હોય છે.

આપેલ ટ્રી:

કોષ્ટક: ટ્રી ટ્રાવર્સલ કંપેરિઝન

કોડ ઉદાહરણ:

def preorder(root):
    if root:
        print(root.data, end=", ")  # રૂટ વિઝિટ
        preorder(root.left)         # લેફ્ટ સબટ્રી વિઝિટ
        preorder(root.right)        # રાઇટ સબટ્રી વિઝિટ

def postorder(root):
    if root:
        postorder(root.left)        # લેફ્ટ સબટ્રી વિઝિટ
        postorder(root.right)       # રાઇટ સબટ્રી વિઝિટ
        print(root.data, end=", ")  # રૂટ વિઝિટ

યાદ રાખવાનું સૂત્ર: “PRE-NLR, POST-LRN - પ્રીઓર્ડર (Node-Left-Right), પોસ્ટઓર્ડર (Left-Right-Node)”

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

#

બાયનરી ટ્રી ની એપ્લિકેશન્સ લખો.

જવાબ: બાયનરી ટ્રીના કમ્પ્યુટર સાયન્સના વિવિધ ક્ષેત્રોમાં અનેક વ્યવહારિક ઉપયોગો છે.

કોષ્ટક: બાયનરી ટ્રી એપ્લિકેશન્સ

યાદ રાખવાનું સૂત્ર: “BEHPD - BST, Expression, Huffman, Priority queue, Decision tree”

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

#

બાયનરી સર્ચ ટ્રી મા નોડ કેવી રીતે ઉમેરી શકાય તે સમજાવો.

જવાબ: બાયનરી સર્ચ ટ્રી (BST)માં ઇન્સર્શન BST પ્રોપર્ટી અનુસરે છે: લેફ્ટ ચાઇલ્ડ < પેરેન્ટ < રાઇટ ચાઇલ્ડ.

કોષ્ટક: BST માં ઇન્સર્શન સ્ટેપ્સ

ડાયાગ્રામ: BST ઇન્સર્શન

flowchart TD
    A[રૂટથી શરૂ કરો] --> B{નવી વેલ્યુ < કરંટ?}
    B -- હા --> C[લેફ્ટ ચાઇલ્ડ પર જાઓ]
    B -- ના --> D[રાઇટ ચાઇલ્ડ પર જાઓ]
    C --> E{લેફ્ટ ચાઇલ્ડ છે?}
    D --> F{રાઇટ ચાઇલ્ડ છે?}
    E -- હા --> B
    E -- ના --> G[લેફ્ટ ચાઇલ્ડ તરીકે ઇન્સર્ટ કરો]
    F -- હા --> B
    F -- ના --> H[રાઇટ ચાઇલ્ડ તરીકે ઇન્સર્ટ કરો]

યાદ રાખવાનું સૂત્ર: “LSRG - Less-go-left, Same-or-greater-go-right”

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

#

8, 4, 12, 2, 6, 10, 14, 1, 3, 5 નમ્બર માટે બાયનરી સર્ચ ટ્રી દોરો અને ટ્રી માટે ઇન ઓર્ડર ટ્રાવર્સલ લખો.

જવાબ: બાયનરી સર્ચ ટ્રી (BST) BST પ્રોપર્ટી જાળવીને નોડ્સ ઇન્સર્ટ કરીને બનાવવામાં આવે છે.

આપેલ એલિમેન્ટ્સ માટે બાયનરી સર્ચ ટ્રી:

કોષ્ટક: BST કન્સ્ટ્રક્શન પ્રોસેસ

ઇન-ઓર્ડર ટ્રાવર્સલ:

ઇન-ઓર્ડર ટ્રાવર્સલ નોડ્સને આ ક્રમમાં વિઝિટ કરે છે: લેફ્ટ સબટ્રી, કરંટ નોડ, રાઇટ સબટ્રી.

આપેલ BST માટે, ઇન-ઓર્ડર ટ્રાવર્સલ આ છે: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14

કોડ ઉદાહરણ:

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)    # લેફ્ટ સબટ્રી વિઝિટ
        print(root.data, end=", ")      # કરંટ નોડ વિઝિટ
        inorder_traversal(root.right)   # રાઇટ સબટ્રી વિઝિટ

યાદ રાખવાનું સૂત્ર: “LNR - Left, Node, Right makes sorted order in BST”