cpp

1. Podstawowe operacje programu Która z poniższych operacji nie jest wymieniona jako podstawowa operacja realizowana przez program?

wysyłanie danych przez sieć

2. Generacje języków programowania Do której generacji języków programowania zaliczają się języki asemblerowe?

G2. Języki niskiego poziomu

3. Języki wysokiego poziomu Jaka jest główna cecha języków wysokiego poziomu, np. C++ czy Python?

(c) uniezależnienie od sprzętu w znacznym stopniu

Liście drzewa binarnego to węzły, które charakteryzują się tym, że

oba ich wskaźniki są równe NU

5. Binarne drzewa poszukiwań (BTS) Zgodnie z zasadą porządku BTS, lewe poddrzewo dla każdego węzła zawiera tylko węzły z wartościami:

(b) mniejszymi niż wartość węzła główne

6. Wypisywanie elementów drzewa BTS Wyświetlając elementy drzewa BTS w kolejności inorder, uzyskujemy ciąg wartości:

posortowanych rosnąc

7. Drzewa wyważone Drzewa AVL i drzewa czerwono-czarne (RBT) to przykłady:

drzew wyważonych

W drzewie AVL wskaźnik wyważenia węzła (Wsk) to różnica wysokości dla lewego i prawego poddrzewa (Hp−HLcap H sub p minus cap H sub cap L 𝐻𝑝−𝐻𝐿 ). Dla drzewa dokładnie wyważonego wartość bezwzględna tej różnicy może wynosić co najwyżej:

jeden

9. Założenia dotyczące drzew RBT Jednym z kluczowych założeń dotyczących drzew czerwono-czarnych (RBT) jest to, że każdy liść (NULL) jest koloru:

czarnego

10. Operacje na drzewach RBT Operacje wstawiania i usuwania węzła w drzewach RBT wykonują się w czasie proporcjonalnym do:

nlog(n)bold n log open paren bold n close paren 𝐧log(𝐧)

11. Porównanie drzew AVL i RBT Dla dużych zbiorów danych, które drzewa są średnio szybsze w operacjach wyszukiwania?

drzewa AVL

Jaka struktura danych służy do implementacji kolejki priorytetowej, która pozwala usunąć element o największym kluczu?

Kopiec(sterta)

Dodawanie do kopca minimalnego W kopcu minimalnym, jeśli nowy element jest mniejszy od rodzica, należy

zamienić je miejscami (przesiewanie w górę)

Grafy spójne i minimalne drzewa rozpinające Graf, którego dowolne dwa węzły można połączyć ścieżką, to:

graf spójny

Który z algorytmów obliczających najkrótszą ścieżkę działa poprawnie również dla wag o ujemnych wartościach?

Algorytm Bellmana-Forda

Moduły w języku C++ W module C++, plik nagłówkowy (*.h) zawiera przede wszystkim:

deklaracje funkcji i definicje struktur

Struktury a klasy w C++ Technicznie, główna różnica między strukturami a klasami w C++ polega na tym, że domyślnie pola i metody struktur są publiczne, natomiast pola i metody klas są domyślnie

prywatne

Kontenery STL std: vector to szablon klasy ułatwiający pracę z:

jednowymiarowymi tablicami dynamicznymi

Złożoność algorytmów prostego sortowania Wszystkie zaprezentowane algorytmy prostego sortowania (wybieranie, wstawianie, bąbelkowe) mają złożoność obliczeniową rzędu:

O(n2)bold cap O open paren bold n squared close paren 𝐎(𝐧𝟐)

alokacjastata dynamiPrzydział pamięci na zmienne statyczne odbywa się automatycznie w obszarze pamięci zwanym stosem, który ma stały i ograniczony rozmiar. Przydział pamięci na zmienne dynamiczne odbywa się na żądanie programisty w obszarze pamięci zwanym

stertą

Procesor a kod maszynowy Procesor komputera realizuje operacje zapisane w:

kodzie maszynowym

Języki programowania piątej generacji (G5), czyli inteligentne systemy wiedzy, pozwalają na

automatyczne generowanie kodu

Drzewo a drzewo binarne Jaka jest kluczowa różnica między ogólną definicją "drzewa" a "drzewa binarnego" w dokumencie?

Drzewo binarne ma dokładnie dwa wskaźniki na węzeł, a ogólne drzewo ma dwa lub więcej.

Drzewa binarne mają zastosowanie jako:

drzewa wyrażeń (np. w bryłach CSG)

Wypisywanie elementów drzewa BTS w kolejności preorder oznacza następującą sekwencję odwiedzin

węzeł, lewe poddrzewo, prawe poddrzewo

Drzewa wyważone, takie jak AVL czy RBT, utrzymują wysokość drzewa na możliwie najniższym poziomie, co zapewnia optymalną wydajność operacji takich jak:

wyszukiwanie, wstawianie i usuwanie

Rotacje w drzewach pozwalają na:

uzyskanie drzewa wyważonego

Dla każdego węzła w drzewie AVL ilość węzłów (waga) jego lewego i prawego poddrzewa może różnić się tylko o

jeden

W drzewach czerwono-czarnych (RBT), jeśli węzeł jest czerwony, to obaj jego potomkowie muszą być koloru:

czarnego

Wysokość drzewa RBT o nn 𝑛 węzłach wewnętrznych wynosi co najwyżej:

2⋅log(n+1)2 center dot log open paren bold n plus 1 close paren

Jaka struktura danych jest używana do implementacji priority_queue w bibliotece STL?

kopiec(head)

Listę węzłów i listę krawędzi w grafie najprościej przechowywać w:

tablicach jednowymiarowych

Algorytm Dijkstry służy do wyznaczania najkrótszych ścieżek, ale tylko dla grafów z:

dodatnimi wagami krawędzi

Algorytm A* jest podobny do algorytmu Dijkstry, ale jest szybszy, ponieważ wykorzystuje:

metody heurystyczne (H[i]) do szacowania odległości

Plik implementacji modułu C++ o rozszerzeniu *. cpp zawiera

definicje (implementacje) funkcji z pliku nagłówkowego

Konstruktor to specjalna funkcja, która:

jest wywoływana w chwili alokacji pamięci na obiekt

Szablon klasy std: set (posortowany zbiór unikalnych elementów) jest implementacją

drzew czerwono-czarnych(RBT)

Tablice statyczne przekazywane do funkcji w C++ są przekazywane przez:

referencję (nie są kopiowane)

Notacja "duże O" opisuje

asymptotyczne zachowanie funkcji (dla odpowiednio dużego n)

Obszar pamięci zwany stosem programu ma:

stały rozmiar (rzędu 1-2 MB) i łatwo może ulec przepełnieniu

Procesor realizuje operacje zapisane w:

kodzie maszynowym

Języki pierwszej generacji (G1) to języki poziomu maszynowego, w których programowanie odbywa się na poziomie:

pojedynczych bitów

Węzły, które mają oba wskaźniki równe NULL, to:

liście drzewa

Dla każdego węzła w binarnym drzewie poszukiwań (BTS), prawe poddrzewo zawiera tylko węzły z wartościami:

większymi niż wartość węzła głównego

Wypisywanie elementów drzewa BTS w kolejności postorder oznacza odwiedzanie:

lewego poddrzewa, prawego poddrzewa, węzła

Drzewa AVL to specjalny typ drzew BST, w których wysokość jest utrzymywana na możliwie:

najniższym poziomie

Drzewo RBT gwarantuje, że jest w przybliżeniu wyważone, a przywrócenie jego własności wymaga co najwyżej

dwóch operacji rotacji

Każda gałąź w drzewie RBT jest co najwyżej:

dwa razy dłuższa niz dowolna inna

W kopcu maksymalnym, największy element jest zawsze na pozycji:

korzenia

Sortowanie przez kopcowanie (malejąco) polega na wielokrotnym pobieraniu

największego elementu

Graf, którego dowolne dwa węzły można połączyć ścieżką, to graf

spójny

Algorytm Kruskala służy do szukania:

minimalnego drzewa rozpinającego

Algorytm Bellmana-Forda (w przeciwieństwie do Dijkstry) nie używa:

kolejki priorytetowej

Plik nagłówkowy o rozszerzeniu *. h zawiera między innymi:

definicje struktur

Destruktor jest wywoływany w chwili:

zwalniania pamięci po zmiennej

Metoda push_back() wstawia nową wartość na

koniec tablicy

Stos (std: stack) działa w trybie

last-in fisrt-out (LIFO

W sortowaniu przez wybieranie, w pierwszym kroku, najmniejszy element w tablicy zamieniamy z:

pierwszym elementem

Przydział pamięci na zmienne dynamiczne odbywa się w obszarze pamięci zwanym:

stertą

Rekurencję ogonową bardzo łatwo jest zastąpić:

pętlą

Jedną z podstawowych operacji realizowanych przez program jest

ustawianie sygnałów wyjściowych

Języki symboliczne i języki asemblerowe należą do generacji:

G2

Języki G4 są specyficzne dla pewnego zastosowania, na przykład

programowanue baz danych

Drzewo to regularna struktura pamięciowa, gdzie każdy element (węzeł) zawiera:

dwa lub więcej wskaźników

Bryły CSG są reprezentowane przez drzewa wyrażeń, gdzie bryły podstawowe znajdują się w:

liściach

Dla danego węzła w BTS, lewe poddrzewo zawiera tylko węzły z wartościami:

mniejszymi niż wartość węzła

Wyświetlając drzewo BTS w kolejności inorder uzyskujemy:

c) ciąg wartości posortowanych rosnąco

Przykłady drzew wyważonych to:

drzewa AVL i drzewa czerwono-czarne (RBT

Maksymalna liczba koniecznych rotacji dla drzewa o n węzłach w celu uzyskania drzewa wyważonego jest rzędu:

log(n)log open paren bold n close paren log(𝐧)

Wskaźnik wyważenia węzła to różnica wysokości poddrzewa prawego i lewego (Hp−HLcap H sub p minus cap H sub cap L 𝐻𝑝−𝐻𝐿). W drzewie AVL różnica ta może wynosić:

-1,0,1

Zgodnie z założeniami drzew RBT, korzeń musi być koloru:

czarnego

Każda prosta ścieżka z ustalonego węzła do dowolnego liścia w RBT ma tyle samo:

czarnych węzłów

W drzewie czerwono-czarnym pochylonym w lewo (LLRBT) prawy potomek jest czerwony tylko i wyłącznie wtedy, gdy:

czerwony jest również lewy potomek

Operacje wstawiania i usuwania w RBT wykonują się w czasie proporcjonalnym do

nbold n 𝐧

Drzewa AVL są lepiej wyważone (od RBT), a więc lepiej się sprawdzają w operacjach

wyszukiwania

W kopcu minimalnym, jeśli nowy element jest mniejszy od rodzica, zamieniamy je miejscami. Proces ten nazywa się:

przesiewaniem w górę (heapify up)

Krawędzie w grafach mogą mieć przypisane zwroty, tworząc:

grafy skierowane

MST to spójny podgraf grafu spójnego, w którym suma wag krawędzi jest:

najmniejsza

Algorytm Bellmana-Forda ma złożoność obliczeniową rzędu:

O(|E|⋅|V|) bold cap O open paren the absolute value of bold cap E end-absolute-value center dot the absolute value of bold cap V end-absolute-value close paren 𝐎(|𝐄|⋅|𝐕|)

Algorytm A* jest algorytmem heurystycznym, który sortuje elementy w kolejce Q wg wartości F[i]=G[i]+H[i]cap F open bracket i close bracket equals cap G open bracket i close bracket plus cap H open bracket i close bracket 𝐹[𝑖]=𝐺[𝑖]+𝐻[𝑖] to

szacunkowa pozostała długość ścieżki do celu

W pliku implementacji *. cpp mogą znajdować się ewentualne definicje i deklaracje lokalne, dostępne tylko w

tym module

Pola i metody klas w C++ są domyślnie

prywatne

Szablon klasy std: forward_list implementuje listę dynamiczną

jednokierunkową

std: map to posortowany zbiór unikalnych

par <klucz, wartość>

Gdy tablica statyczna jest przekazywana do funkcji przez referencję, operacje na niej wewnątrz funkcji:

zmieniają zawartość tablicy oryginalnej

Z zaprezentowanych algorytmów prostego sortowania, najlepsze (najszybsze średnio) jest sortowanie przez

wybieranie

Wszystkie zaprezentowane algorytmy sortowania prostego mają złożoność obliczeniową rzędu O(n2)bold cap O open paren bold n squared close paren 𝐎(𝐧𝟐)

pętli w pętli

Stos ma stały rozmiar (rzędu 1-2 MB) i łatwo może ulec przepełnieniu, np. w przypadku

zbyt dużych tablic statycznych lub źle napisanej rekurencji

Przydział pamięci dynamicznej odbywa się w trakcie pracy programu na żądanie programisty za pomocą instrukcji:

new

Funkcje rekurencyjne muszą charakteryzować się warunkiem końca, ponieważ:

bez niego funkcja wywoływałaby się w nieskończoność

Po co stosujemy drzewa czerwono czarne?

żeby hierarchiczna struktura drzewa była bardziej widziana

Ktöre z poniższych stwierdzen o drzewach binarnego wyszukiwania jest falszywe:

wszystkie elementy w wezle SA wieksze niz elementy lewego i prawego poddrzewa

Ktore z poniższych stwierdzen o rekurencji jest prawdziwe:

rekurencja posrednia to wzajemne wywolywanie przez siebie dwu lub wiecej podprogramow

Czy lista przechowujaca ciag liczb musi skladać się z rekordow(struktur)?

musi bo kazdy element listy oprocz liczby musi zawierac wskaźnik, wiec pola SA roznych typow

Jeśli chcemy jak najtańszym kosztem polączyć ze sobą wszystkie stacje metra musimy:

znależć minimalne drzewo rozpinające grafu reprezentującego sieć metra

Ktöre z poniższych stwierdzeń nie dotyczy rekurencyjnego wyświetlania drzewa binarnego:

zeby móc wyświetlić drzewa binarne, musi istnieć jego lewe i prawe podrzewo

Jaka przewagę mają drzewa binarne nad listami?

pozwalają na znacznie szybsze wyszukiwanie elementów w duzych zbiorach

Pętla sterowana warunkiem umożliwia:

wvkonanie pewnych czynności cyklicznie dopóki pewien warunek jest prawdziwy