Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Tekijän kotisivu: Zhi Guyun tulee ulos Xiusta

1. Monivalinta kysymykset: Tutustu peruskäsitteisiin ja perustoimintoihin
2. Täyttää tyhjät kohdat: vahvistaa ydinkäsitteiden ja yksityiskohtien ymmärtämistä
3. lyhyitä vastauksia kysymyksiin: Testaa teoreettisen tiedon hallintaa
4. Ohjelmointikysymyksiä: Testaa todellista ohjelmointikykyä ja tietorakennesovellusta
5. 

Tietorakenteen simulointimäärä

1. Monivalintakysymykset (kukin 2 pistettä, yhteensä 20 pistettä)

1. Elementin lisäämisen aika monimutkaisuus taulukkoon on ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n^2)

2. Keon lajittelussa maksimikeon rakentamisen aika monimutkaisuus on ().
   A. O(n)
   B. O(n log n)
   C. O(log n)
   D. O(n^2)

3. Punamusta puu on eräänlainen ().
   A. Täydellinen binääripuu
   B. Tasapainotettu binääripuu
   C. Min-kasa
   D. Max kasa

4. Mikä seuraavista hash-taulukoita koskevista väittämistä on virheellinen ().
   A. Hajautustaulukon hakuajan monimutkaisuus on O(1)
   B. Hajautustaulukon lisäysajan monimutkaisuus on O(1)
   C. Hash-taulukot voivat ratkaista ristiriitoja
   D. Hajautustaulukon hakuajan monimutkaisuuden on oltava O(1)

5. Kuvaajan läpikäymisessä syvyys-ensimmäisen haun (DFS) ja leveyshaun (BFS) aikakompleksisuus on () vastaavasti.
   A. O(V + E) ja O(V)
   B. O(V^2) ja O(V)
   C. O(V + E) ja O(V + E)
   D. O(V) ja O(V^2)

6. Yksisuuntaisen linkitetyn luettelon kääntämisen aika monimutkaisuus on ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n^2)

7. Binäärihakupuussa solmun poistamisen pahimmassa tapauksessa aika monimutkaisuus on ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n log n)

8. Millä seuraavista lajittelualgoritmeista on keskimääräinen aikamonimutkaisuus O(n log n)().
   A. Kuplalajittelu
   B. Nopea lajittelu
   C. Lisäyslajittelu
   D. Valinnan lajittelu

9. Binääripuussa solmun aste on ().
   A. Tämän solmun lapsisolmujen lukumäärä
   B. Solmun syvyys
   C. Solmun korkeus
   D. Solmun taso

10. Suurin ero B-puun ja B+-puun välillä on ().
    A. Kaikki B-puun solmut tallentavat tietoja, kun taas vain B+-puun lehtisolmut tallentavat tietoja.
    B. B-puu on tasapainoisempi kuin B+-puu
    C. B-puun lisäys- ja poistotoiminnot ovat yksinkertaisempia
    D. B+-puun hakutehokkuus on alhaisempi

2. Täytä tyhjät kysymykset (kukin 3 pistettä, yhteensä 15 pistettä)

1. Täydellisen binääripuun, joka sisältää n solmua, korkeus on ______.
2. Pikalajittelun keskimääräinen aika monimutkaisuus on ______.
3. Linkitetyssä luettelossa k:nnen elementin löytämisen aika monimutkaisuus on ______.
4. Graafin vierekkäisyysmatriisiesityksen avaruuskompleksisuus on ______.
5. Huffman-puussa painotettu polun pituus lasketaan ______.

3. Lyhytvastauskysymykset (10 pistettä kukin, yhteensä 30 pistettä)

1. Kuvaile lyhyesti punamustien puiden ominaisuuksia ja kerro kuinka punamustat puut säilyttävät tasapainon.
2. Selitä ero dynaamisten taulukoiden ja linkitettyjen luetteloiden välillä ja keskustele niiden eduista, haitoista ja sovellusskenaarioista.
3. Kuvaile hash-taulukoiden periaatteet ja selitä kuinka käsitellä törmäyksiä.

4. Ohjelmointikysymykset (15 pistettä kukin, yhteensä 35 pistettä)

1. Ota käyttöön toiminto, joka määrittää, onko linkitetty luettelo palindromiin linkitetty luettelo.

   def is_palindrome(head):
       # 请在这里编写代码
   1
   2

2. Kirjoita koodi toteuttaaksesi lisäystoiminnon binäärihakupuussa.

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       # 请在这里编写代码
   1
   2
   3
   4
   5
   6
   7
   8

3. Toteuta leveysensimmäinen haku (BFS) käyttämällä vierekkäisyysmatriisin edustamaa kuvaajaa.

   def bfs(graph, start):
       # 请在这里编写代码
   1
   2

Vastaus

1. Monivalintakysymykset

1. B
2. A
3. B
4. D
5. C
6. B
7. B
8. B
9. A
10. A

2. Täytä tyhjät kohdat

1. log(n+1) pyöristys alaspäin
2. O(n log n)
3. Päällä)
4. O(V^2)
5. Kaikkien lehtien solmujen painotetun polun pituuksien summa

3. Lyhyt vastaus kysymyksiin

1. punaisen mustan puun ominaisuuksia：

   • Ominaisuus 1: Jokainen solmu on punainen tai musta.
   • Ominaisuus 2: Pääsolmu on musta.
   • Ominaisuus 3: Jokainen lehtisolmu (NIL-solmu) on musta.
   • Ominaisuus 4: Jos solmu on punainen, niin sen molemmat alisolmut ovat mustia (eli ei voi olla kahta peräkkäistä punaista solmua kaikilla poluilla kustakin lehdestä juureen).
   • Ominaisuus 5: Kaikki yksinkertaiset polut mistä tahansa solmusta jokaiseen sen lehteen sisältävät saman määrän mustia solmuja.

   Kuinka punamustat puut ylläpitävät tasapainoa：

   • Lisäys- ja poistotoimenpiteiden jälkeen punamustan puun ominaisuuksia ylläpidetään pyörittämällä ja värittämällä uudelleen, jolloin varmistetaan, että puun korkeus pysyy aina O(log n) -alueen sisällä.

2. Ero dynaamisen taulukon ja linkitetyn luettelon välillä：

   • Dynaamiset taulukot (kuten luettelot Pythonissa): Muisti on jatkuvaa, elementteihin pääsee nopeasti käsiksi indeksien kautta, lisäys- ja poistotoiminnot vaativat elementtien siirtämistä ja ajallinen monimutkaisuus on O(n).
   • Linkitetty lista: Muisti ei ole jatkuva ja yhdistetty osoittimien (viitteiden) kautta. Lisäys- ja poistooperaatioiden aikamonimutkaisuus on O(1), mutta elementtien aikamonimutkaisuus on O(n).
   • Hyödyt ja haitat：
     • Dynaaminen taulukko: Etuna on, että satunnaiskäyttö on nopeaa, mutta haittana on, että lisääminen ja poistaminen ovat hitaita ja saattavat vaatia laajentamista.
     • Linkitetty luettelo: Etuna on, että lisääminen ja poistaminen ovat nopeita, mutta haittana on, että satunnaiskäyttö on hidasta ja vie enemmän muistia (koska osoittimet on tallennettava).
   • Sovellusskenaariot：
     • Dynaamiset taulukot sopivat skenaarioihin, joissa elementtejä on käytettävä usein ja kokoa ei muuteta usein, kuten välimuistiin.
     • Linkitetyt listat soveltuvat skenaarioihin, jotka vaativat usein elementtien lisäämistä ja poistamista, kuten jonojen ja pinojen toteuttamiseen.

3. Hash-taulukon periaate：

   • Hash-taulukot yhdistävät avaimet taulukon hakemiston paikkoihin hash-funktion avulla, mikä mahdollistaa nopeat haku-, lisäys- ja poistotoiminnot.
   • Miten käsitellä konflikteja：
     • Avoin osoitemenetelmä: Ristiriitatilanteessa seuraavan vapaan sijainnin etsimiseen käytetään lineaarista ilmaisua, toissijaista ilmaisua ja muita menetelmiä.
     • Ketjuosoitemenetelmä: Kun on ristiriita, elementit, joilla on sama hash-arvo, tallennetaan linkitettyyn luetteloon.

4. Ohjelmointikysymykset

1. Selvitä, onko linkitetty luettelo palindromiin linkitetty luettelo:

   class ListNode:
       def __init__(self, x):
           self.val = x
           self.next = None
   
   def is_palindrome(head):
       # 使用快慢指针找到链表中点
       slow = fast = head
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
       
       # 反转后半部分链表
       prev = None
       while slow:
           temp = slow.next
           slow.next = prev
           prev = slow
           slow = temp
       
       # 比较前半部分和后半部分
       left, right = head, prev
       while right:
           if left.val != right.val:
               return False
           left = left.next
           right = right.next
       return True
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28

2. Lisäystoiminto binäärihakupuussa:

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       if root is None:
           return TreeNode(key)
       if key < root.val:
           root.left = insert(root.left, key)
       else:
           root.right = insert(root.right, key)
       return root
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

3. Leveys ensin haku (BFS):

   from collections import deque
   
   def bfs(graph, start):
       visited = [False] * len(graph)
       queue = deque([start])
       visited[start] = True
       result = []
   
       while queue:
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10