40 Questions
Š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
False
Binarno stablo ima
čvorove 2. stepena
Realizacija binarnog stabla statičkim nizom je najefikasnija od svih realizacija
False
Kod prikaza binarnog stabla statičkim nizom nisu potrebni podaci o vezama elemenata.
True
Koji je najgori oblik binarnog stabla prikazanog statičkim nizom?
Struktura koja se koristi za binarno stablo sadrži polja
vrijednost, lijevo i desno dijete, roditelj.
Sortirano binarno stablo ima osobine:
ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena
Tri standardna načina obilaska binarnog stabla su:
inorder, preorder i postorder
Koje 2 osnovne operacije treba podržati prioritetni red?
Dodavanje novog i brisanje najvećeg elementa
Najprirodniji i najučinkovitiji način predstavljanja prioritetnog reda je kao:
gomile
Gomila je ______________________ , gdje se čvorovi mogu porediti ____________________.
Šta je potrebno uraditi nakon promjene prioriteta nekog čvora gomile?
Dodavanje novog elementa u gomilu vrši se:
na dnu gomile
Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu?
Složenost heap sort algoritma je bolja od O(nlog2n)
False
Eulerov graf je
Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je:
stepen svakog vrha paran
Korijeni podstabla čvora x su ______, a čvor x im je _________.
Šta je stepen stabla?
Dubina stabla je najmanja razina svih čvorova stabla
True
Binarno stablo ima
čvorove 2. stepena
Šta je puno binarno stablo?
Realizacija binarnog stabla statičkim nizom je najefikasnija od svih realizacija
True
Kod prikaza binarnog stabla statičkim nizom nisu potrebni podaci o vezama elemenata.
True
Koji je najgori oblik binarnog stabla prikazanog statičkim nizom?
Struktura koja se koristi za binarno stablo sadrži polja
vrijednost, lijevo i desno dijete, roditelj.
Sortirano binarno stablo ima osobine:
ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena
Tri standardna načina obilaska binarnog stabla su:
inorder, preorder i postorder
Koje 2 osnovne operacije treba podržati prioritetni red?
Dodavanje novog i brisanje najvećeg elementa
Najprirodniji i najučinkovitiji način predstavljanja prioritetnog reda je kao:
gomile
Gomila je ______________________ , gdje se čvorovi mogu porediti ____________________.
Šta je potrebno uraditi nakon promjene prioriteta nekog čvora gomile?
Dodavanje novog elementa u gomilu vrši se:
na dnu gomile
Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu?
Složenost heap sort algoritma je bolja od O(nlog2n)
True
Eulerov graf je
Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je:
stepen svakog vrha paran
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.
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.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
