Ctrl+K

2. Klasówka 2014/15 (08.01.2015)

2. Klasówka 2014/15 (08.01.2015)#

Zadanie 1 [9 punktów]#

Słowa kluczowe: grafy

Dane jest drzewo z korzeniem T, które jest DFS-drzewem rozpinającym pewnego n-wierzchołkowego grafu G. Wierzchołki drzewa są identyfikowane z ich numerami DFS wyznaczających kolejność ich pierwszych odwiedzin. Dla każdego wierzchołka i różnego od korzenia, t[i] jest numerem ojca i w drzewie T. Wartość t[.] dla korzenia jest równa 0. Zaproponuj efektywny algorytm, który

  1. [2 punkty] sprawdzi, czy graf G może być grafem dwuspójnym wierzchołkowo, a jeśli odpowiedź jest pozytywna, to poda

  2. [3 punkty] minimalną liczbę krawędzi w grafie G,

  3. [4 punkty] maksymalną liczbę krawędzi w grafie G.

Zadanie 2 [11 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie

Zaproponuj efektywną strukturę danych umożliwiającą wykonywanie na dynamicznym, skończonym ciągu liczb całkowitych alpha następujących operacji:

  • Init(\(\alpha\)):: zainicjuj ciąg jako pusty (operacja wykonywana tylko raz na samy początku);

  • Insert(\(\alpha, a, k\)):: wstaw liczbę a na k-tą pozycję w ciągu \(\alpha\), \(1 \le k \le | \alpha|+1\);

  • Delete(\(\alpha, k\)):: usuń k-ty element z ciągu \(\alpha\), \(1 \le k \le | \alpha|\);

  • Value(\(\alpha, k\)):: podaj wartość \(\alpha[k]\), \(1 \le k \le | \alpha|\);

za pierwsze cztery operacje [2 punkty]

  • BestSum(alpha)::[5 punktów] podaj wartość równą \(\max(\{0\} \cup \{ \alpha[i]+\alpha[i+1]+\ldots+\alpha[j]: 1 \le i \le j \le | \alpha|\})\);

  • LargeNeighbour(alpha, k, e):: [4 punkty] podaj takie najmniejsze, dodatnie r, że \(\alpha[k-r] > \alpha[k] + e\) lub \(\alpha[k+r] > \alpha[k] + e\); jeżeli takie r nie istnieje, to wynikiem jest 0.

Zawartość