Edukacja


M E N U  TESTY2 Zalogowany:   Kurs: Algorytmy i struktury danych (ASD)  POMOCWYLOGUJTwój wynik: 1 punktów na 6 możliwych do uzyskania (16,67 %).NrOpcjaPunktyPoprawnaOdpowiedź1Koszt algorytmu Partition, zastosowanego do ciągu o  elementach jest:, jeżeli operacją dominującą jest porównanie elementów1++, jeżeli operacją dominującą jest przestawienie elementów0+, jeżeli operacją dominującą jest porównanie elementów02Do znalezienia elementu największego w danym elementowym ciągu, gdzie jest potęgą , zastosowano następujący algorytm :jeżeli ciąg składa się z jednego elementu, to jest to element największy,jeżeli
ciąg składa się z więcej niż jednego elementu, to dzielimy go na
połowy, w każdej z nich rekurencyjnie wyszukujemy element największy,
porównujemy uzyskane wartości i ustalamy ostateczny wynik.Które z poniższych zdań jest prawdziwe?Rząd złożoności rozważanego algorytmu jest taki sam, rząd złożoności algorytmu sekwencyjnego1+Koszt
tego algorytmu, mierzony liczbą wykonanych porównań, musi być większy
niż koszt sekwencyjnego algorytmu wyszukiwania maksimum.0Rząd złożoności rozważanego algorytmu jest asymptotycznie większy niż rząd złożoności algorytmu sekwencyjnego0+3Niech będzie problemem wyszukiwania elementu -tego co do wielkości w danym -elementowym zbiorze. Które z poniższych zdań jest prawdziwe?Algorytm naiwny rozwiązywania problemu  ma złożoność 0+Jeśli , to problem można rozwiązać wykonując co najwyżej porównania1+Koszt średni algorytmu Hoare'a dla problemu wynosi 04Rozważmy algorytm Hoare'a wyszukaia elementu -tego co do wielkości w niepuprządkowanym uniwersum rozmiaru , wtedy: w implementacji rekurencyjnej algorytmu z bez uwzględnienia kosztu pamięciowego wywołań rekurencyjnych1++Liczba wywołań procedury podziału (np. Split, Partition) jest rzędu co najwyżej 0+Pesymistyczna złożoność czasowa algorytmu jest rzędu co najwyżej 1++5Jaką pozycję zwróci algorytm Partition (pozycje ciągu numerujemy od , a jako element rozdzielający wybieramy ostatni element rozważanego ciągu)?Jeżeli ciąg jest postaci , to wynikiem jest 0Jeżeli ciąg jest postaci , to wynikiem jest pozycja 1++Zawsze jest to pozycja, gdzie jest długością ciągu06Rozważ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?Argumentem -go wykonania algorytmu Partition jest tablica postaci: , w której szukamy indeksu elementu -go co do wielkości0W
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ści1+W rozważanym przypadku liczba wykonanań algorytmu Partition jest równa dokładnie 1++System edukacyjny. PJWSTK 2001-2007