Strona główna

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


Pobieranie 108.96 Kb.
Data18.06.2016
Rozmiar108.96 Kb.







Nr

Opcja

Punkty

Poprawna

Odpowiedź

1

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






1

+









1

+









1

+

+

2

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




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

0










Wysokość drzewa jest równa dokładnie

1

+

+




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

0







3

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






Liczba operacji OUT w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest równa dokładnie

0










Maksymalna długość kolejki pomocniczej w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej długości kolejki pomocniczej, w trakacie wykonania rozważnego algorytmu dla grafu i wierzchołka startowego

1

+

+




Maksymalna długość kolejki pomocniczej w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej długości kolejki pomocniczej, w trakacie wykonania rozważnego algorytmu dla grafu i wierzchołka startowego

0







4

Rozważmy drzewo typu BST powstałe na skutek kolejnego wstawiania elementów ciągu do początkowo pustej struktury (przy użyciu operacji INSERT). Następnie z drzewa usuwamy wierzchołki z etykietami . 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 ) albo następny (drzewo ) względem porządku etykiet.




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

0










Liczba wierzchołków wewnętrznych drzewa jest równa dokładnie

0










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

1

+

+

5

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




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

0










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

0










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

1

+

+

6

Rozważmy drzewo binarne zgodne z poniższym rysunkiem. Które z następujacych zdań jest prawdziwe?






Wysokość rozważanego drzewa jest równa dokładnie

0










Do poziomu włącznie rozważane drzewo jest drzewem regularnym (lokalnie pełnym)

0










Wysokość rozważanego drzewa jest równa dokładnie

1

+

+

7

Rozważmy nieskierowany graf prosty , którego wierzchołki etykietowane są liczbami naturalnymi od do włącznie, zadany tabicą list sąsiedztwa postaci: , , , , , , , , , i przedstawiony na poniższym rysunku. Dla grafu 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 .






Liczba chromatyczna grafu jest równa dokładnie

0










Po zastosowaniu algorytm LF wierzchołek ma przypisany kolor

1

+

+




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

0







8

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




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

1

+

+




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

0










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

0







9

Rozważmy nieskierowany graf prosty z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do włącznie, zadany tabicą list sąsiedztwa postaci: , , , , , , , i przedstawiony na poniższym rysunku. Dla grafu i wierzchołka startowego 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ą.






Kolejność przyłączania wierzchołków do drzewa najkrótszych ścieżek grafu w trakcie wykonania algorytmu Dijkstry jest następująca:

0










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

0










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

1

+

+

10

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




Liczba wierzchołków wewnętrznych drzewa-kopca jest równa dokładnie

0










Liczba wierzchołków wewnętrznych drzewa-kopca jest równa dokładnie

1

+

+




Liczba wierzchołków wewnętrznych drzewa-kopca jest równa dokładnie

0







11

Rozważmy tablicę reprezentującą -elementowy ciąg różnych liczb naturalnych: . W owej tablicy wyszukujemy indeksu elementu -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 -go co do wielkości będziemy wyszukiwali indeksu elementu -go co do wielkości

1

+

+




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

0










W rozważanym przypadku liczba wykonanań algorytmu Partition jest równa dokładnie

0







12

Rozważmy drzewo kodowe Huffmana powstałe na skutek zastosowania algorytmu budowy drzewa kodu Huffmana dla ciągu znaków zawierającego odpowiednio (znak - krotność wystąpień): , , , , , , , . 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.




Etykiety liści drzewa czytane od lewej do prawej strony tworzą ciąg

0










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

1

+

+




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

0







13

Rozważmy tablicę reprezentującą -elementowy ciąg różnych liczb naturalnych: . Do posortowania owej tablicy stosujemy algorytm InsertionSort. 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 .




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

1

+

+




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

1

+

+




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

1

+

+

14

Rozważmy nieskierowany graf prosty z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do włącznie, zadany tabicą list sąsiedztwa postaci: , , , , , , , i przedstawiony na poniższym rysunku. Dla grafu 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ą.






Kolejność akceptowania krawędzi grafu do drzewa rozpinającego w trakcie wykonania rozważanego algorytmu jest następująca:

0










Suma wag krawędzi tworzących drzewo rozpinające grafu będące rezultatem działania algorytmu Kruskala jest równa dokładnie

0










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

1

+

+

15

Rozważmy tablicę reprezentującą -elementowy ciąg różnych liczb naturalnych: . 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?




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

1

+

+




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

1

+

+




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

0







16

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




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

0










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

1

+

+




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

1

+

+

17

Rozważmy tablicę reprezentującą -elementowy ciąg różnych liczb naturalnych: . 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 wyskokść drzewa wywołań rekurencyjnych algorytmu QuickSort jest równa dokładnie

1

+

+




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

0










W rozważanym przypadku liczba wykonanań rekurencyjnych algorytmu QuickSort jest równa dokładnie

0







18

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




Łączna liczba operacji FIRST we wszystkich kolejkach w trakcie wykonania rozważanego algorytmu jest równa dokładnie

0










Maksymalna długość dowolnej kolejki (tj. maksymalna liczba jednocześnie przechowywanych elementów) w trakcie wykonania rozważanego algorytmu jest równa dokładnie

0










Łączna liczba operacji IN we wszystkich kolejkach w trakcie wykonania rozważanego algorytmu jest równa dokładnie

1

+

+

19

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




Ostateczna wysokość stosu tuż po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku wykonania następującego ciągu operacji: , , , , , , ,

1

+

+




Ostateczna wysokość stosu tuż po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku wykonania następującego ciągu operacji: , , , , , , ,

0










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

1

+

+

20

Rozważmy nieskierowany graf prosty z wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do włącznie, zadany tabicą list sąsiedztwa postaci: , , , , , , , i przedstawiony na poniższym rysunku. Dla grafu i wierzchołka startowego 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ą.






Kolejność przyłączania wierzchołków do minimalnego drzewa rozpinającego grafu w trakcie wykonania algorytmu Prima jest następująca:

0










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

1

+

+




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

1

+

+


System edukacyjny. PJWSTK 2001-2007


©snauka.pl 2016
wyślij wiadomość