SPIA 161-180
40 Questions
5 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Šta je puno binarno stablo?

Korijeni podstabla čvora x su ______, a čvor x im je _________.

Šta je stepen stabla?

Dubina stabla je najmanja razina svih čvorova stabla

<p>False</p> Signup and view all the answers

Binarno stablo ima

<p>čvorove 2. stepena</p> Signup and view all the answers

Realizacija binarnog stabla statičkim nizom je najefikasnija od svih realizacija

<p>False</p> Signup and view all the answers

Kod prikaza binarnog stabla statičkim nizom nisu potrebni podaci o vezama elemenata.

<p>True</p> Signup and view all the answers

Koji je najgori oblik binarnog stabla prikazanog statičkim nizom?

Signup and view all the answers

Struktura koja se koristi za binarno stablo sadrži polja

<p>vrijednost, lijevo i desno dijete, roditelj.</p> Signup and view all the answers

Sortirano binarno stablo ima osobine:

<p>ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena</p> Signup and view all the answers

Tri standardna načina obilaska binarnog stabla su:

<p>inorder, preorder i postorder</p> Signup and view all the answers

Koje 2 osnovne operacije treba podržati prioritetni red?

<p>Dodavanje novog i brisanje najvećeg elementa</p> Signup and view all the answers

Najprirodniji i najučinkovitiji način predstavljanja prioritetnog reda je kao:

<p>gomile</p> Signup and view all the answers

Gomila je ______________________ , gdje se čvorovi mogu porediti ____________________.

Signup and view all the answers

Šta je potrebno uraditi nakon promjene prioriteta nekog čvora gomile?

Signup and view all the answers

Dodavanje novog elementa u gomilu vrši se:

<p>na dnu gomile</p> Signup and view all the answers

Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu?

Signup and view all the answers

Složenost heap sort algoritma je bolja od O(nlog2n)

<p>False</p> Signup and view all the answers

Eulerov graf je

Signup and view all the answers

Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je:

<p>stepen svakog vrha paran</p> Signup and view all the answers

Korijeni podstabla čvora x su ______, a čvor x im je _________.

Signup and view all the answers

Šta je stepen stabla?

Signup and view all the answers

Dubina stabla je najmanja razina svih čvorova stabla

<p>True</p> Signup and view all the answers

Binarno stablo ima

<p>čvorove 2. stepena</p> Signup and view all the answers

Šta je puno binarno stablo?

Signup and view all the answers

Realizacija binarnog stabla statičkim nizom je najefikasnija od svih realizacija

<p>True</p> Signup and view all the answers

Kod prikaza binarnog stabla statičkim nizom nisu potrebni podaci o vezama elemenata.

<p>True</p> Signup and view all the answers

Koji je najgori oblik binarnog stabla prikazanog statičkim nizom?

Signup and view all the answers

Struktura koja se koristi za binarno stablo sadrži polja

<p>vrijednost, lijevo i desno dijete, roditelj.</p> Signup and view all the answers

Sortirano binarno stablo ima osobine:

<p>ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena</p> Signup and view all the answers

Tri standardna načina obilaska binarnog stabla su:

<p>inorder, preorder i postorder</p> Signup and view all the answers

Koje 2 osnovne operacije treba podržati prioritetni red?

<p>Dodavanje novog i brisanje najvećeg elementa</p> Signup and view all the answers

Najprirodniji i najučinkovitiji način predstavljanja prioritetnog reda je kao:

<p>gomile</p> Signup and view all the answers

Gomila je ______________________ , gdje se čvorovi mogu porediti ____________________.

Signup and view all the answers

Šta je potrebno uraditi nakon promjene prioriteta nekog čvora gomile?

Signup and view all the answers

Dodavanje novog elementa u gomilu vrši se:

<p>na dnu gomile</p> Signup and view all the answers

Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu?

Signup and view all the answers

Složenost heap sort algoritma je bolja od O(nlog2n)

<p>True</p> Signup and view all the answers

Eulerov graf je

Signup and view all the answers

Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je:

<p>stepen svakog vrha paran</p> Signup and view all the answers

Study Notes

Binary Trees

  • A full binary tree is a tree in which every node has exactly two children.
  • The roots of the subtree of node x are the left and right subtrees, and node x is their parent.
  • The degree of a tree is the maximum degree of its nodes.
  • The depth of a tree is the minimum level of all its nodes.

Binary Tree Representation

  • Binary tree representation using a static array is the most efficient of all representations.
  • When representing a binary tree using a static array, no data about element connections is needed.
  • The worst form of a binary tree represented using a static array is a skewed tree.
  • The structure used for a binary tree contains fields for the left and right child nodes and the parent node.

Sorted Binary Trees

  • A sorted binary tree has the property that for every node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.
  • There are three standard ways to traverse a binary tree: inorder, preorder, and postorder.

Priority Queues

  • A priority queue must support two basic operations: enqueue and dequeue.
  • The most natural and efficient way to represent a priority queue is as a heap.
  • A heap is a special type of binary tree in which each node is smaller than or equal to its children, and nodes can be compared using a priority function.
  • After changing the priority of a node in a heap, the heap must be updated to maintain the heap property.
  • Adding a new element to a heap is done by inserting it at the end of the array and then bubbling it up to its correct position.
  • The worst-case time complexity for adding a new element to a heap is O(log n).
  • The time complexity of the heap sort algorithm is better than O(n log n).

Euler Graphs

  • An Euler graph is a graph that has an Euler path, which is a path that visits every edge exactly once.
  • A unique closed Euler path exists in an Euler graph if and only if the graph is connected and has exactly two nodes of odd degree.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Description

Test your knowledge about the implementation of binary trees using static arrays, sorted binary trees, and their worst-case scenarios. Explore the properties and characteristics of binary trees represented by static arrays.

Use Quizgecko on...
Browser
Browser