Edukacja


M E N U  TESTY2 Zalogowany:   Kurs: Algorytmy i struktury danych (ASD)  POMOCWYLOGUJTwój wynik: 3 punktów na 6 możliwych do uzyskania (50 %).NrOpcjaPunktyPoprawnaOdpowiedź1Dany jest elementowy ciąg parami różnych elementów. Jaki jest koszt (mierzony liczba wykonanych porównań elementów) następującego algorytmu  wyszukiwania mediany tego ciągu.int i:=1;while (i < n+1) do    znajdz_i_usun_minimum_ciagu(E);    znajdz_i_usun_maksimum_ciagu(E);    i:=i+1;odZakładamy, że usuwanie elementów zmniejsza liczbę elementów ciągu i nie wymaga dodatkowych porównań. 01++1+2Niech będzie liczbą porównań, jaką wykona w najgorszym przypadku algorytm poszukiwań binarnych BinSearch zastosowany do ciągu o elementach. Która odpowiedź jest poprawna?Wartość parametru jest równa co najwyżej rozmiarowi danych wejściowych 1++Jeśli , to 0Wartość parametru jest niezależna od rozmiaru danych wejściowych 03W ciągu uporządkowanym rosnąco szukamy metodą binarnych poszukiwań takiego , by , dla pewnego ustalonego . Jakiej długości jest przeszukiwany ciąg, jeśli wykonaliśmy dokładnie porównań?Długość ciągu jest mniejsza 0Nieograniczonej0Co najwyżej  razy tyle ile w przypadku -ciu porównań i tej samej metody postępowania1++4Oszacuj koszt algorytmu skoki co  zastosowanego do uporządkowanego ciągu elementowego. porównań1+Co najwyżej  porównań, jeśli , 1++Nie więcej niż porównań1++5Niech będzie dana tablica  liczb rzeczywistych i pewna liczba . Co jest wynikiem następującego algorytmu .int i:=0, j:=0;while (i < n) do    if (A[i+1]=x) then j:=j+1; fi    i:=i+1;odreturn j;1++Po wykonaniu pętli zachodzi warunek 1+Wartość zmienna jest równa -krotności ilości wstąpień liczby w rozważanej tablicy wejściowej06Dany jest dowolny ciąg -elementowy. Zadanie polega na zbadaniu, czy dany element
występuje w tym ciągu czy nie. Rozważmy następującą modyfikację
algorytmu wyszukiwania sekwencyjnego: rzucamy sprawiedliwą monetą:jeśli wypadnie orzeł, to przeszukujemy ciąg sekwencyjnie w kierunku od lewej do prawej,jeśli wypadnie reszka, to przeszukujemy ciąg sekwencyjnie od prawej do lewej.Ile porównań trzeba średnio wykonać, jeżeli element szukany znajduje się na -tej pozycji w danym ciągu?Dokładnie , niezależnie do długości ciągu wejściowego 01++Dokładnie 0System edukacyjny. PJWSTK 2001-2007