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 12 mo磧iwych do uzyskania (0 %).

Bie鎥owski Miko豉j
NrOpcjaPunktyPoprawnaOdpowied
1

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 .

Kolejno嗆 kolorowania wierzcho趾闚 grafu w trakcie wykonania algorytmu LF jest nast瘼uj帷a: 0
Po zastosowaniu algorytm LF wierzcho貫k ma przypisany taki sam kolor jak wierzcho貫k 1+
Kolejno嗆 kolorowania wierzcho趾闚 grafu w trakcie wykonania algorytmu LF jest nast瘼uj帷a: 0
2Rozwa禦y kopiec binarny typu min zaimplementowany w drzewie binarnym i 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?
Je瞠li zamiast drzewa binarnego do implementacji kopca binarnego u篡jemy tablicy, to jej finalna posta b璠zie nast瘼uj帷a: 0
Etykiety wierzcho趾闚 drzewa-kopca wypisane w kolejno軼i PostOrder tworz ci庵: 0
Etykiety wierzcho趾闚 drzewa-kopca wypisane w kolejno軼i PostOrder tworz ci庵: 1+
3Rozwa禦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?
Liczba wierzcho趾闚 wewn皻rznych drzewa-kopca jest r闚na dok豉dnie 0
Etykiety wierzcho趾闚 drzewa-kopca wypisane w kolejno軼i InOrder tworz ci庵: 1+
Je瞠li zamiast drzewa binarnego do implementacji kopca binarnego u篡jemy tablicy, to jej finalna posta b璠zie nast瘼uj帷a: 1+
4Rozwa禦y kopiec binarny typu min zaimplementowany w drzewie binarnym. Kopiec konstruujemy z element闚 ci庵u stosuj帷 szybki algorytm budowy kopca HeapConstruct. Nast瘼nie w kopcu wykonujem -krotnie operaj DELMIN. Kt鏎e z poni窺zych zda jest prawdziwe?
Liczba wierzcho趾闚 wewn皻rznych drzewa-kopca jest r闚na dok豉dnie 0
Wysoko嗆 drzewa-kopca jest r闚na dok豉dnie 1+
Etykiety wierzcho趾闚 drzewa-kopca wypisane w kolejno軼i InOrder tworz ci庵: 0
5Rozwa禦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.
Kod litery odczytany z drzewa jest nast瘼uj帷y: 1+
Kod litery odczytany z drzewa jest nast瘼uj帷y: 0
Kod litery odczytany z drzewa jest nast瘼uj帷y: 1+
6

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
Wysoko嗆 minimalego drzewa rozpinaj帷ego b璠帷ego rezultatem dzia豉nia algorytmu Prima jest r闚na dok豉dnie 1+
Liczba wierzcho趾闚 zewn皻rznych w minimalym drzewie rozpinaj帷ym b璠帷ym rezultatem dzia豉nia algorytmu Prima jest r闚na dok豉dnie 0
7Rozwa禦y zach豉nny algorytm PrimTSP rozwi您uj帷y problem komiwoja瞠ra w -wierzcho趾owym grafie , kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie i rozmieszczone s w odpowiednio nast瘼uj帷ych punktach p豉szczyzny euklidesowej: . Kt鏎e z poni窺zych zda jest prawdziwe je瞠li wierzcho趾iem startowym jest ? Uwaga! W przypadku niejednoznacznej mo磧iwo軼i wyboru wierzcho趾闚, jako pierwszy wybieramy wierzcho貫k z mniejsz etykiet.
Kraw璠 nale篡 do wyznaczonego cyklu Hamiltona w grafie 1+
Kolejno嗆 przy陰czania wierzcho趾闚 do konstruowanego cyklu Hamiltona w trakcie wykonania algorytmu PrimTSP jest nast瘼uj帷a: 0
Maksymalna wysoko嗆 stosu pomocniczego u篡tego do realizacji przej軼ia grafu metod DFS w celu wyznaczenia cyklu Hamiltona jest r闚na dok豉dnie 0
8Jaka b璠zie kolejno嗆 element闚 tablicy po wykonaniu algorytmu Construct, konstrukcji kopca w tablicy, je郵i na pocz徠ku tablica zawiera豉 liczby (w podanym porz康ku)?

Kolejno嗆 element闚 nie ulegnie zmianie

0
Taka sama jak w przypadku tablicy postaci pocz徠kowej 1+
0
9

Co robi nast瘼uj帷y algorytm , gdzie

  1. int i; 
  2. for i:=1 to k do
  3.     K:=delmin(K);
  4. od;
  5. return min(K);

je郵i jest kopcem o elementach i ?

Znajduje -szy co do wielkosci element kopca

1+
Znajduje -ty co do wielko軼i element kopca 0
Z kosztem ze wzgl璠u na liczb operacji por闚na element闚 kopca , znajduje -szy najwi瘯szy element struktury1+
10

Rozwa禦y tekst sk豉daj帷y si z symboli b璠帷ych cyframi dziesi皻nymi ze zbioru , gdzie cyfra wyst瘼uje:

  • razy, je瞠li jest liczb parzyst,
  • razy, je瞠li jest liczb nieparzyst.

Na podstawie rozwa瘸nego tekstu zbudowano drzewo kodowe Huffmana. Kt鏎y z poni窺zych kod闚 binarnych reprezentuje zadan liczb naturaln ?

, je瞠li 1+
, je瞠li 0
, je瞠li 1+
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.

Liczba kraw璠zi grafu odrzuconych (ze wzgl璠u na mo磧iwo嗆 utworzenia cyklu) w trakcie konstrukcji drzewa rozpinaj帷ego, tu po ustaleniu jego finalnej postaci, jest r闚na dok豉dnie 1+
Liczba kraw璠zi grafu odrzuconych (ze wzgl璠u na mo磧iwo嗆 utworzenia cyklu) w trakcie konstrukcji drzewa rozpinaj帷ego, tu po ustaleniu jego finalnej postaci, jest r闚na dok豉dnie 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 zach豉nny algorytm KruskalTSP rozwi您uj帷y problem komiwoja瞠ra w -wierzcho趾owym grafie , kt鏎ego wierzcho趾i etykietowane s liczbami naturalnymi od do w陰cznie i rozmieszczone s w odpowiednio nast瘼uj帷ych punktach p豉szczyzny euklidesowej: . 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 konstruowanego cyklu Hamiltona w trakcie wykonania rozwa瘸nego algorytmu jest nast瘼uj帷a: 0
Kolejno嗆 akceptowania kraw璠zi grafu do konstruowanego cyklu Hamiltona w trakcie wykonania rozwa瘸nego algorytmu jest nast瘼uj帷a: 1+
Kraw璠 nale篡 do wyznaczonego cyklu Hamiltona w grafie 0
System edukacyjny. PJWSTK 2001-2007