M E N U  TESTY2 Zalogowany: Miko豉j Bie鎥owski  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJ
Kurs
Oceny
Materia造
Og這szenia
Testy2
Inny kurs
Wyloguj
Administrator

Tw鎩 wynik: 0 punkt闚 na 20 mo磧iwych do uzyskania (0 %).

Bie鎥owski Miko豉j
NrOpcjaPunktyPoprawnaOdpowied
1Rozwa禦y funkcje zmiennej . Kt鏎e z poni窺zych zda jest prawdziwe?
0
0
Ci庵 funkcji jest ci庵iem 軼i郵e malej帷ym wzgl璠em ich rz璠闚1+
2Rozwa禦y drzewo typu AVL powsta貫 na skutek kolejnego wstawiania element闚 ci庵u do pocz徠kowo pustej struktury (przy u篡ciu operacji INSERT). Kt鏎e z poni窺zych zda jest prawdziwe?
Wysoko嗆 drzewa jest r闚na dok豉dnie 0
ㄠczna liczba rotacji pojedynczych w lewo wykonanych w trakcie budowy drzewa jest r闚na dok豉dnie 1+
Liczba wierzcho趾闚 wewn皻rznych drzewa jest r闚na dok豉dnie 0
3

Rozwa禦y nieskierowany graf prosty , kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie, zadany tabic list s御iedztwa postaci: , , , , , , i przedstawiony na poni窺zym rysunku. Wierzcho趾i grafu odwiedzamy w kolejno軼i BFS z wierzcho趾a startowego . Kt鏎e z poni窺zych zda jest prawdziwe? Uwaga! W algorytmie BFS wierzcho趾i grafu umieszczamy w kolejce pomocniczej w kolejno軼i rosn帷ych warto軼i etykiet.

Kolejno嗆 odwiedzenia wierzcho趾闚 jest nast瘼uj帷a: 1+
Liczba operacji OUT w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest r闚na dok豉dnie 1+
Maksymalna d逝go嗆 kolejki pomocniczej w trakcie wykonania algorytmu BFS jest r闚na dok豉dnie 1+
4Rozwa禦y drzewo typu BST powsta貫 na skutek kolejnego wstawiania element闚 ci庵u do pocz徠kowo pustej struktury (przy u篡ciu operacji INSERT). Nast瘼nie z drzewa usuwamy wierzcho趾i z etykietami . Kt鏎e z poni窺zych zda jest prawdziwe?. Uwaga! W razie konieczno軼i w operacji DELETE w miejsce usuwanego wierzcho趾a wstawiamy wierzcho貫k bezpo鈔ednio poprzedni (drzewo ) albo nast瘼ny (drzewo ) wzgl璠em porz康ku etykiet.
Wysoko嗆 drzewa jest r闚na dok豉dnie 1+
Liczba wierzcho趾闚 zewn皻rznych drzewa jest r闚na dok豉dnie 0
Etykiety wierzcho趾闚 drzewa wypisane w kolejno軼i PostOrder tworz ci庵: 1+
5Rozwa禦y pe軟e drzewo binarne wysoko軼i . Kt鏎e z poni窺zych zda jest prawdziwe?
Je瞠li wierzcho趾i drzewa w kolejno軼i InOrder tworz ci庵 , to w kolejno軼i PreOrder tworz ci庵: 1+
Je瞠li wierzcho趾i drzewa w kolejno軼i PreOrder tworz ci庵 , to w kolejno軼i InOrder tworz ci庵: 0
Je瞠li wierzcho趾i drzewa w kolejno軼i PostOrder tworz ci庵 , to w kolejno軼i InOrder tworz ci庵: 1+
6

Rozwa禦y nieskierowany graf prosty , kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie, zadany tabic list s御iedztwa postaci: , , , , , , , , , i przedstawiony na poni窺zym rysunku. Dla grafu stosujemy algorytm kolorowania LF (largest first). Kt鏎e z poni窺zych zda jest prawdziwe? Uwaga! W przypadku niejednoznacznej mo磧iwo軼i wyboru wierzcho趾闚, jako pierwszy wybieramy wierzcho貫k z mniejsz etykiet. Kolory indeksujemy od .

Liczba chromatyczna grafu jest r闚na dok豉dnie 0
Liczba chromatyczna grafu jest r闚na dok豉dnie 0
Po zastosowaniu algorytm LF wierzcho貫k ma przypisany taki sam kolor jak wierzcho貫k 1+
7Rozwa禦y wykonanie algorytmu obliczania warto軼i poprawnie i w pe軟i nawiasowanego wyra瞠nia arytmetycznego, przy u篡ciu dw鏂h stos闚: stosu argument闚 i stosu operator闚. Wyra瞠nie wej軼iowe ma posta . Kt鏎e z poni窺zych zda jest prawdziwe?
Liczba operacji POP na stosie argument闚 w trakcie wykonania algorytmu jest r闚na dok豉dnie 1+
Liczba operacji PUSH na stosie argument闚 w trakcie wykonania algorytmu jest r闚na dok豉dnie 0
Liczba operacji POP na stosie argument闚 w trakcie wykonania algorytmu jest r闚na dok豉dnie 0
8Rozwa禦y kopiec binarny typu min zaimplementowany w drzewie binarnym. Kopiec konstruujemy z element闚 ci庵u stosuj帷 szybki algorytm budowy kopca HeapConstruct. Kt鏎e z poni窺zych zda jest prawdziwe?
Wysoko嗆 drzewa-kopca jest r闚na dok豉dnie 0
Liczba operacji przestawie element闚 kopca wykonanych w trakcie jego budowy jest r闚na co najwy瞠j 1+
Etykiety wierzcho趾闚 drzewa-kopca wypisane w kolejno軼i PostOrder tworz ci庵: 0
9Rozwa禦y drzewo kodowe Huffmana powsta貫 na skutek zastosowania algorytmu budowy drzewa kodu Huffmana dla ci庵u znak闚 zawieraj帷ego odpowiednio (znak - krotno嗆 wyst徙ie): , , , , , , , . Kt鏎e z poni窺zych zda jest prawdziwe? Uwaga! W przypadku niejednoznacznego wyboru poddrzew, za mniejsze uznajemy to, kt鏎ego etykiet li軼i czytane od lewej do prawej strony tworz s這wo mniejsze w sensie porz康ku leksykograficznego.
Wysoko嗆 drzewa jest r闚na dok豉dnie 0
Wysoko嗆 drzewa jest r闚na dok豉dnie 0
Kod litery odczytany z drzewa jest nast瘼uj帷y: 1+
10Rozwa禦y tablic reprezentuj帷 -elementowy ci庵 r騜nych liczb naturalnych: . W owej tablicy wyszukujemy indeksu elementu -go co do wielko軼i za pomoc algorytmu Hoare'a z procedur podzia逝 zgodn z metod Partition. Kt鏎e z poni窺zych zda jest prawdziwe?
W rozwa瘸nym przypadku liczba wykonana algorytmu Partition jest r闚na dok豉dnie 1+
W rozwa瘸nym przypadku liczba wykonana algorytmu Partition jest wi瘯sza od liczby wykona tego algorytmu, gdy zamiast indeksu elementu -go co do wielko軼i b璠ziemy wyszukiwali indeksu elementu -go co do wielko軼i1+
Argumentem -go wykonania algorytmu Partition jest tablica postaci: , w kt鏎ej szukamy indeksu elementu -go co do wielko軼i0
11

Rozwa禦y nieskierowany graf prosty z wagami, kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie, zadany tabic list s御iedztwa postaci: , , , , , , , i przedstawiony na poni窺zym rysunku. Dla grafu stosujemy algorytm Kruskala wyznaczenia minimalnego drzewa rozpinaj帷ego. Kt鏎e z poni窺zych zda jest prawdziwe? Uwaga! W przypadku niejednoznacznej mo磧iwo軼i wyboru kraw璠zi, jako pierwsz wybieramy kraw璠, kt鏎ej etykiety wierzcho趾闚 kra鎍owych w kolejno軼i niemalej帷ej tworz mniejsz liczb naturaln.

Kolejno嗆 akceptowania kraw璠zi grafu do drzewa rozpinaj帷ego w trakcie wykonania rozwa瘸nego algorytmu jest nast瘼uj帷a: 0
Maksymalna waga kraw璠zi tworz帷ej otrzymane drzewo rozpinaj帷e grafu jest r闚na co najmniej 0
Liczba kraw璠zi grafu odrzuconych (ze wzgl璠u na mo磧iwo嗆 utworzenia cyklu) w trakcie konstrukcji drzewa rozpinaj帷ego, jeszcze przed ustaleniem jego finalnej postaci, jest r闚na dok豉dnie 1+
12Rozwa禦y tablic indeksowan od reprezentuj帷 -elementowy cz窷ciowo uporz康kowany ci庵 liczb naturalnych: . Do ca趾owitego uporz康kowania element闚 owej tablicy stosujemy algorytm Merge. Kt鏎e z poni窺zych zda jest prawdziwe?
Elementy tablicy , kt鏎e w algorytmie Merge s argumentami ostatniej operacji por闚nania elment闚, to kolejno oraz 0
Elementy tablicy , kt鏎e w algorytmie Merge s argumentami ostatniej operacji por闚nania elment闚, to kolejno oraz 1+
Elementy tablicy , kt鏎e w algorytmie Merge nie s argumentami ostatniej operacji por闚nania elment闚, to kolejno oraz 0
13

Rozwa禦y nieskierowany graf prosty z wagami, kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie, zadany tabic list s御iedztwa postaci: , , , , , , , i przedstawiony na poni窺zym rysunku. Dla grafu i wierzcho趾a startowego stosujemy stosujemy algorytm Prima wyznaczenia minimalnego drzewa rozpinaj帷ego. Kt鏎e z poni窺zych zda jest prawdziwe? Uwaga! W przypadku niejednoznacznej mo磧iwo軼i wyboru wierzcho趾闚, jako pierwszy wybieramy wierzcho貫k z mniejsz etykiet.

Kolejno嗆 przy陰czania wierzcho趾闚 do minimalnego drzewa rozpinaj帷ego grafu w trakcie wykonania algorytmu Prima jest nast瘼uj帷a: 0
Suma wag kraw璠zi tworz帷ych minimalne drzewo rozpinaj帷e b璠帷e rezultatem dzia豉nia algorytmu Prima jest r闚na dok豉dnie 0
Suma wag kraw璠zi tworz帷ych minimalne drzewo rozpinaj帷e b璠帷e rezultatem dzia豉nia algorytmu Prima jest r闚na dok豉dnie 1+
14Rozwa禦y tablic reprezentuj帷 -elementowy ci庵 -cyfrowych liczb naturalnych: . Do posortowania owej tablicy stosujemy algorytm RadixSort zaimplementowany przy u篡ciu kolejek. Kt鏎e z poni窺zych zda jest prawdziwe?
ㄠczna liczba operacji IN we wszystkich kolejkach w trakcie wykonania rozwa瘸nego algorytmu jest r闚na dok豉dnie 0
Tu po sortowaniu liczb wzgl璠em cyfr na -ej pozycji dziesi皻nej (liczonej od prawej do lewej strony), zawarto嗆 tablicy jest nast瘼uj帷a: 0
Tu po sortowaniu liczb wzgl璠em cyfr na -ej pozycji dziesi皻nej (liczonej od prawej do lewej strony), zawarto嗆 tablicy jest nast瘼uj帷a: 1+
15Rozwa禦y pocz徠kowo pust struktur stosu , do kt鏎ej wstawiono elementy: . Nast瘼nie na strukturze wykonano kolejno ci庵 operacji: , , , , , , , . Kt鏎e z poni窺zych zda jest prawdziwe?
Maksymalna wysoko嗆 stosu w trakcie wykonania przedstawionego ci庵u operacji jest taka sama jak w przypadku wykonania nast瘼uj帷ego ci庵u operacji: , , , , , , , 1+
Ostateczna wysoko嗆 stosu tu po wykonaniu przedstawionego ci庵u operacji jest taka sama jak w przypadku wykonania nast瘼uj帷ego ci庵u operacji: , , , , , , , 0
Ostateczna wysoko嗆 stosu tu po wykonaniu przedstawionego ci庵u operacji jest r闚na dok豉dnie 0
16

Rozwa禦y algorytm , gdzie jest typem danych reprezentuj帷ym podzbiory zbioru

  1. set A:=;
  2. int i:=0;
  3. while (i < n) do
  4.     A:=A{i};
  5.     i:=i+1;
  6. od
  7. return A;

Kt鏎e z nast瘼uj帷ych zda jest prawdziwe?

Je瞠li jest liczb naturaln wi瘯sz od zera, to po wykonaniu algorymu spe軟ione s warunki oraz 0
Niezmiennikiem p皻li w algorytmie jest formu豉 0
Niezmiennikiem p皻li w algorytmie  jest formu豉 1+
17Koszt algorytmu Partition, zastosowanego do ci庵u o  elementach jest:
, je瞠li operacj dominuj帷 jest por闚nanie element闚1+
, je瞠li operacj dominuj帷 jest por闚nanie element闚1+

Rz璠u , je瞠li operacj dominuj帷 jest przestawienie element闚

0
18Kt鏎e z wymienionych zda jest prawdziwe?
D逝go嗆 dowolnej drogi od korzenia do li軼ia w drzewie decyzyjnym dla algorytmu sortowania przez wyb鏎 zastosowanego do ci庵u elementowego wynosi co najwy瞠j 0
Algorytm InsertionSort, zastosowany do ci庵u uporz康kowanego o elementach, wykonuje tylko przestawie1+
Algorytm InsertionSort wykonuje dla ci庵u odwrotnie uporz康kowanego asymptotycznie mniej por闚na ni algorytm SelectionSort0
19

Niech b璠zie drzewem BST powsta造m przez kolejne wstawianie wierzcho趾闚 o etykietach do pocz徠kowo pustej struktury. Kt鏎e z ponizszych zda jest prawdziwe?

Usuni璚ie wierzcho趾a z etykiet w drzewie prowadzi do drzewa, w kt鏎ym w miejscu wierzcho趾a z etykiet znajdzie si wierzcho貫k z etykiet albo

1+

Usuni璚ie wierzcho趾a z etykiet w drzewie prowadzi do drzewa, kt鏎ego korzeniem b璠zie wierzcho貫k z etykiet

1+

Wysoko嗆 drzewa jest niezale積a od kolejno軼i wstawiania rozwa瘸nych wierzcho趾闚

0
20Niech b璠zie kopcem-drzewem o wierzcho趾ach i niech b璠zie liczb jego li軼i na ostatnim poziomie. Zaznacz zdania prawdziwe.
Je郵i , dla pewnego , to 0
Je郵i , to 0
Je郵i , to 1+
System edukacyjny. PJWSTK 2001-2007