37 11


Nr

Opcja

Punkty

Poprawna

Odpowiedź

1

Rozważmy funkcje zmiennej 0x01 graphic
. Które z poniższych zdań jest prawdziwe?

Ciąg funkcji 0x01 graphic
jest ciągiem ściśle malejącym względem ich rzędów

1

+

0x01 graphic

0

0x01 graphic

0

2

Rozważmy drzewo 0x01 graphic
typu AVL powstałe na skutek kolejnego wstawiania elementów ciągu 0x01 graphic
do początkowo pustej struktury (przy użyciu operacji INSERT). Które z poniższych zdań jest prawdziwe?

Łączna liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

0

Etykiety wierzchołków drzewa 0x01 graphic
wypisane w kolejności PostOrder tworzą ciąg: 0x01 graphic

1

+

Łączna liczba rotacji podwójnych w lewo-prawo wykonanych w trakcie budowy drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

0

3

Rozważmy drzewo 0x01 graphic
typu BST powstałe na skutek kolejnego wstawiania elementów ciągu 0x01 graphic
do początkowo pustej struktury (przy użyciu operacji INSERT). Które z poniższych zdań jest prawdziwe?

Etykiety wierzchołków drzewa 0x01 graphic
wypisane w kolejności PostOrder tworzą ciąg: 0x01 graphic

0

Etykiety wierzchołków drzewa 0x01 graphic
wypisane w kolejności PreOrder tworzą ciąg: 0x01 graphic

0

Liczba wierzchołków zewnętrznych drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

1

+

4

Rozważmy pełne drzewo binarne 0x01 graphic
wysokości 0x01 graphic
. Które z poniższych zdań jest prawdziwe?

Jeżeli wierzchołki drzewa 0x01 graphic
w kolejności InOrder tworzą ciąg 0x01 graphic
, to w kolejności PostOrder tworzą ciąg: 0x01 graphic

0

Jeżeli wierzchołki drzewa 0x01 graphic
w kolejności PreOrder tworzą ciąg 0x01 graphic
, to w kolejności InOrder tworzą ciąg: 0x01 graphic

1

+

Jeżeli wierzchołki drzewa 0x01 graphic
w kolejności PostOrder tworzą ciąg 0x01 graphic
, to w kolejności PreOrder tworzą ciąg: 0x01 graphic

0

5

Rozważmy nieskierowany graf prosty 0x01 graphic
, którego wierzchołki etykietowane są liczbami naturalnymi od 0x01 graphic
do 0x01 graphic
włącznie, zadany tabicą list sąsiedztwa postaci: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
i przedstawiony na poniższym rysunku. Dla grafu 0x01 graphic
stosujemy algorytm kolorowania LF (largest first). Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą. Kolory indeksujemy od 0x01 graphic
.

0x01 graphic

Po zastosowaniu algorytm LF wierzchołek 0x01 graphic
ma przypisany kolor 0x01 graphic

0

Po zastosowaniu algorytm LF wierzchołek 0x01 graphic
ma przypisany kolor 0x01 graphic

1

+

Po zastosowaniu algorytm LF wierzchołek 0x01 graphic
ma przypisany taki sam kolor jak wierzchołek 0x01 graphic

0

6

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg liczb naturalnych: 0x01 graphic
. Do posortowania owej tablicy stosujemy algorytm CountingSort. Które z poniższych zdań jest prawdziwe?

Po trzeciej pętli iteracyjnej (wypisanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 0x01 graphic

0

Po pierwszej pętli iteracyjnej (zliczanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 0x01 graphic

0

Po drugiej pętli iteracyjnej (sumowanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 0x01 graphic

1

+

7

Rozważmy nieskierowany graf prosty 0x01 graphic
z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od 0x01 graphic
do 0x01 graphic
włącznie, zadany tabicą list sąsiedztwa postaci: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
i przedstawiony na poniższym rysunku. Dla grafu 0x01 graphic
i wierzchołka startowego 0x01 graphic
stosujemy algorytm Dijkstry. Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą.

0x01 graphic

Najkrótsza ścieżka z wierzchołka 0x01 graphic
do wierzchołka 0x01 graphic
w rozważanym grafie jest długości dokładnie 0x01 graphic

0

Liczba wierzchołków wewnętrznych w drzewie najkrótszych ścieżek będącym rezultatem działania algorytmu Dijkstry jest równa dokładnie 0x01 graphic

1

+

Najkrótsza ścieżka z wierzchołka 0x01 graphic
do wierzchołka 0x01 graphic
w rozważanym grafie jest długości dokładnie 0x01 graphic

0

8

Rozważmy nieskierowany graf prosty 0x01 graphic
, którego wierzchołki etykietowane są liczbami naturalnymi od 0x01 graphic
do 0x01 graphic
włącznie, zadany tabicą list sąsiedztwa postaci: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
i przedstawiony na poniższym rysunku. Wierzchołki grafu 0x01 graphic
odwiedzamy w kolejności DFS z wierzchołka startowego 0x01 graphic
. Które z poniższych zdań jest prawdziwe? Uwaga! W algorytmie DFS wierzchołki grafu umieszczamy na stosie pomocniczym w kolejności malejących wartości etykiet.

0x01 graphic

Maksymalna wysokość stosu pomocniczego w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej wysokości stosu pomocniczego, w trakacie wykonania rozważnego algorytmu dla grafu 0x01 graphic
i wierzchołka startowego 0x01 graphic

1

+

Maksymalna wysokość stosu pomocniczego w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej wysokości stosu pomocniczego, w trakacie wykonania rozważnego algorytmu dla grafu 0x01 graphic
i wierzchołka startowego 0x01 graphic

1

+

Liczba operacji PUSH na stosie pomocniczym w trakcie wykonania algorytmu DFS jest równa dokładnie 0x01 graphic

0

9

Rozważmy kopiec binarny 0x01 graphic
typu min zaimplementowany w drzewie binarnym i powstały na skutek kolejnego wstawiania elementów ciągu 0x01 graphic
do początkowo pustej struktury (przy użyciu operacji INSERT). Które z poniższych zdań jest prawdziwe?

Wysokość drzewa-kopca 0x01 graphic
jest równa dokładnie 0x01 graphic

1

+

Wysokość drzewa-kopca 0x01 graphic
jest równa dokładnie 0x01 graphic

0

Liczba operacji porównań elementów kopca wykonanych w trakcie jego budowy jest równa co najwyżej 0x01 graphic

0

10

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg różnych liczb naturalnych: 0x01 graphic
. W owej tablicy wyszukujemy indeksu elementu 0x01 graphic
-go co do wielkości za pomocą algorytmu Hoare'a z procedurą podziału zgodną z metodą Partition. Które z poniższych zdań jest prawdziwe?

W rozważanym przypadku liczba wykonanań algorytmu Partition jest większa od liczby wykonań tego algorytmu, gdy zamiast indeksu elementu 0x01 graphic
-go co do wielkości będziemy wyszukiwali indeksu elementu 0x01 graphic
-go co do wielkości

1

+

Argumentem 0x01 graphic
-go wykonania algorytmu Partition jest tablica postaci: 0x01 graphic
, w której szukamy indeksu elementu 0x01 graphic
-go co do wielkości

0

W rozważanym przypadku liczba wykonanań algorytmu Partition jest większa od liczby wykonań tego algorytmu, gdy zamiast indeksu elementu 0x01 graphic
-go co do wielkości będziemy wyszukiwali indeksu elementu 0x01 graphic
-go co do wielkości

1

+

11

Rozważmy drzewo kodowe Huffmana 0x01 graphic
powstałe na skutek zastosowania algorytmu budowy drzewa kodu Huffmana dla ciągu znaków zawierającego odpowiednio (znak - krotność wystąpień): 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
. Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznego wyboru poddrzew, za mniejsze uznajemy to, którego etykiet liści czytane od lewej do prawej strony tworzą słowo mniejsze w sensie porządku leksykograficznego.

Wysokość drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

1

+

Kod litery 0x01 graphic
odczytany z drzewa 0x01 graphic
jest następujący: 0x01 graphic

0

Wysokość drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

0

12

Rozważmy nieskierowany graf prosty 0x01 graphic
z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od 0x01 graphic
do 0x01 graphic
włącznie, zadany tabicą list sąsiedztwa postaci: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
i przedstawiony na poniższym rysunku. Dla grafu 0x01 graphic
stosujemy algorytm Kruskala wyznaczenia minimalnego drzewa rozpinającego. Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru krawędzi, jako pierwszą wybieramy krawędź, której etykiety wierzchołków krańcowych w kolejności niemalejącej tworzą mniejszą liczbę naturalną.

0x01 graphic

Liczba krawędzi grafu odrzuconych (ze względu na możliwość utworzenia cyklu) w trakcie konstrukcji drzewa rozpinającego, jeszcze przed ustaleniem jego finalnej postaci, jest równa dokładnie 0x01 graphic

0

Maksymalna waga krawędzi tworzącej otrzymane drzewo rozpinające grafu 0x01 graphic
jest równa co najmniej 0x01 graphic

1

+

Maksymalna waga krawędzi tworzącej otrzymane drzewo rozpinające grafu 0x01 graphic
jest równa co najwyżej 0x01 graphic

0

13

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg różnych liczb naturalnych: 0x01 graphic
. Do posortowania owej tablicy stosujemy algorytm MergeSort w implementacji rekurencyjnej, z procedurą scalania zgodną z metodą Merge. Które z poniższych zdań jest prawdziwe?

Rezultatem 0x01 graphic
-go wykonania algorytmu MergeSort jest tablica postaci: 0x01 graphic

0

W rozważanym przypadku liczba wykonanań rekurencyjnych algorytmu MergeSort jest równa dokładnie liczbie wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych 0x01 graphic

0

W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu MergeSort jest równa dokładnie wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych 0x01 graphic

1

+

14

Rozważmy początkowo pustą strukturę kolejki 0x01 graphic
, do której wstawiono elementy: 0x01 graphic
. Następnie na strukturze 0x01 graphic
wykonano kolejno ciąg operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
. Które z poniższych zdań jest prawdziwe?

Ostateczna długość kolejki 0x01 graphic
tuż po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku wykonania następującego ciągu operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic

0

0x01 graphic
, gdzie 0x01 graphic
jest kolejką, której proces konstrukcji przebiegł analogicznie jak dla kolejki 0x01 graphic
tyle, że dla innego ciągu operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic

1

+

Ostateczna długość kolejki 0x01 graphic
tuż po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku wykonania następującego ciągu operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic

1

+

15

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg różnych liczb naturalnych: 0x01 graphic
. Do posortowania owej tablicy stosujemy algorytm QuickSort w implementacji rekurencyjnej, z procedurą podziału zgodną z metodą Partition. Które z poniższych zdań jest prawdziwe?

W rozważanym przypadku liczba wykonanań algorytmu Partition jest równa dokładnie liczbie wykonań rozważanego algorytmu dla danych wejściowych 0x01 graphic

0

W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu QuickSort jest równa dokładnie 0x01 graphic

0

W rozważanym przypadku liczba wykonanań rekurencyjnych algorytmu QuickSort jest równa dokładnie liczbie wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych 0x01 graphic

1

+

16

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg 0x01 graphic
-cyfrowych liczb naturalnych: 0x01 graphic
. Do posortowania owej tablicy stosujemy algorytm RadixSort zaimplementowany przy użyciu kolejek. Które z poniższych zdań jest prawdziwe?

Tuż po sortowaniu liczb względem cyfr na 0x01 graphic
-ej pozycji dziesiętnej (liczonej od prawej do lewej strony), zawartość tablicy 0x01 graphic
jest następująca: 0x01 graphic

0

Tuż po sortowaniu liczb względem cyfr na 0x01 graphic
-ej pozycji dziesiętnej (liczonej od prawej do lewej strony), zawartość tablicy 0x01 graphic
jest następująca: 0x01 graphic

1

+

Tuż po sortowaniu liczb względem cyfr na 0x01 graphic
-ej pozycji dziesiętnej (liczonej od prawej do lewej strony), zawartość tablicy 0x01 graphic
jest następująca: 0x01 graphic

0

17

Rozważmy początkowo pustą strukturę stosu 0x01 graphic
, do której wstawiono elementy: 0x01 graphic
. Następnie na strukturze 0x01 graphic
wykonano kolejno ciąg operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
. Które z poniższych zdań jest prawdziwe?

Ostateczna wysokość stosu 0x01 graphic
tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie 0x01 graphic

1

+

0x01 graphic
, gdzie 0x01 graphic
jest stosem, którego proces konstrukcji przebiegł analogicznie jak dla stosu 0x01 graphic
tyle, że dla innego ciągu operacji: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic

0

Ostateczna wysokość stosu 0x01 graphic
tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie 0x01 graphic

0

18

Rozważmy nieskierowany graf prosty 0x01 graphic
z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od 0x01 graphic
do 0x01 graphic
włącznie, zadany tabicą list sąsiedztwa postaci: 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
i przedstawiony na poniższym rysunku. Dla grafu 0x01 graphic
i wierzchołka startowego 0x01 graphic
stosujemy stosujemy algorytm Prima wyznaczenia minimalnego drzewa rozpinającego. Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą.

0x01 graphic

Wysokość minimalego drzewa rozpinającego będącego rezultatem działania algorytmu Prima jest równa dokładnie 0x01 graphic

1

+

Wysokość minimalego drzewa rozpinającego będącego rezultatem działania algorytmu Prima jest równa dokładnie 0x01 graphic

0

Liczba wierzchołków wewnętrznych w minimalym drzewie rozpinającym będącym rezultatem działania algorytmu Prima jest równa dokładnie 0x01 graphic

0

19

Rozważmy tablicę 0x01 graphic
reprezentującą 0x01 graphic
-elementowy ciąg różnych liczb naturalnych: 0x01 graphic
. Do posortowania owej tablicy stosujemy algorytm SelectionSort. Które z poniższych zdań jest prawdziwe? Uwaga! Przy zliczaniu przestawień elementów bierzemy pod uwagę jedynie transpozycje między różnymi indeksami tablicy 0x01 graphic
.

Wykonanie pierwszych 0x01 graphic
iteracji pętli zewnętrznej algorytmu wymaga wykonania dokładnie 0x01 graphic
przestawień elementów tablicy 0x01 graphic

0

Wykonanie pierwszych 0x01 graphic
iteracji pętli zewnętrznej algorytmu wymaga wykonania dokładnie 0x01 graphic
porównań elementów tablicy 0x01 graphic

1

+

Wykonanie pierwszych 0x01 graphic
iteracji pętli zewnętrznej algorytmu wymaga wykonania o co najwyżej 0x01 graphic
porównań elementów tablicy 0x01 graphic
mniej niż w przypadku wykonania pierwszych 0x01 graphic
iteracji rozważanego algorytmu

0

20

Rozważmy drzewo 0x01 graphic
typu AVL powstałe na skutek kolejnego wstawiania elementów ciągu 0x01 graphic
do początkowo pustej struktury (przy użyciu operacji INSERT). Następnie z drzewa 0x01 graphic
usuwamy wierzchołki z etykietami 0x01 graphic
. Które z poniższych zdań jest prawdziwe?. Uwaga! W razie konieczności w operacji DELETE w miejsce usuwanego wierzchołka wstawiamy wierzchołek bezpośrednio poprzedni (drzewo 0x01 graphic
) albo następny (drzewo 0x01 graphic
) względem porządku etykiet.

Liczba wierzchołków zewnętrznych drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

0

Łączna liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy i usuwania elementów drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

1

+

Liczba wierzchołków zewnętrznych drzewa 0x01 graphic
jest równa dokładnie 0x01 graphic

0



Wyszukiwarka

Podobne podstrony:
PATOMORFOLOGIA wykład 37 11, PATOMORFOLOGIA wykład 11 (37) (4 I 02)
2011 03 21 22;37;11
PATOMORFOLOGIA wykład 37 11, Patomorfologia
37 11
2011 03 21 22;37;11
2010 08 11 16 29 37
05-01-11 01 01 37 kol2
02 01 11 12 01 37 2010 12 31 13 22 32
[Papermodels@emule] [Maly Modelarz 1969 10 11] PZL 37 Los
2014 03 02 11 39 37 01id 28525 Nieznany
2005 11 37
37) TSiP 2010 11 ćw14
2010 08 11 16 29 37
37 Co tam u Janielskich Pan Bóg wie lepiej luty ,11
11 Rozdzial 34 37

więcej podobnych podstron