Fondamenti di informatica (SSE e Statistica)

Prova scritta del 4 giugno 2001

Domanda 1

Scrivere un programma C che legge da tastiera 20 interi, e li stampa ordinati in senso non decrescente usando l’algoritmo insertion-sort. Calcolare la complessità asintotica del programma proposto, nel caso peggiore. Spiegare il significato delle notazioni usate per esprimere la complessità asintotica.

Domanda 2

Scrivere un funzione C di nome max_subseq che, dati come parametri un array di interi V e il numero di elementi in esso contenuti, restituisce la lunghezza massima di una sottosequenza di elementi adiacenti tutti strettamente maggiori della media degli elementi in V.

Esempio:

se alla funzione venissero passati i seguenti parametri

vettore 4 5 6 5 7 9 8 4 3 2 6 7 e lunghezza 12

essendo la media degli elementi uguale a 5.5, la funzione dovrebbe restituire il valore 3 (infatti, tra le sottosequenze sotto evidenziate, la più lunga contiene tre elementi)

4 5 6 5 7 9 8 4 3 2 6 7

Domanda 3

Descrivere l’utilità e il funzionamento dello strato del sistema operativo che si occupa della gestione dei processi.