Klasówka 1 z ASD
8.11.2012

Zadanie 1 [6 punktów]

Udowodnij, że do scalania dwóch ciągów uporządkowanych długości 2 i 5 potrzeba i wystarcza 5 porównań.

Zadanie 4 [7 punktów]

Powiemy, że dwa napisy są podobne wtedy i tylko wtedy, gdy zawierają jednakowe liczby wystąpień tych samych znaków. Danych jest n napisów nad alfabetem m-znakowym {1, 2, …, m}. Zaproponuj algorytm, który stwierdza, ile jest wśród nich różnych klas napisów podobnych. Twój algorytm powinien działać w czasie O(R + m), gdzie R jest sumą długości wszystkich napisów.

Zadanie 5 [7 punktów]

Dana jest 2n-elementowa tablica zawierająca n zer i n jedynek. Chcemy ją uporządkować tak, żeby zera i jedynki były ułożone na przemian, począwszy od zera, tj. 010101... Zaproponuj efektywny algorytm, który wykona to w miejscu i stabilnie (tj. kolejność zer i kolejność jedynek z wejścia muszą być zachowane).