Prova di ammissione A.A. 2005/2006

Prima parte – Informatica

Esercizio 1

Scrivere una piccola libreria di funzioni (in un qualsiasi linguaggio procedurale, e.g. C, C++, C#, Pascal, Fortran, Java) in grado di gestire uno stack (pila, ordinamento LIFO) di numeri interi. Le funzioni realizzate devono essere: Sintassi C:

  • typedef int boolean;
  • void push(int v);
  • int pop(void);
  • int top(void);
  • boolean empty(void);

Sintassi Pascal:

  • procedure push(v:integer);
  • function pop():integer;
  • function top():integer;
  • function empty():boolean;

Push inserisce un elemento nello stack, pop lo estrae, top restituisce l’elemento in cima allo stack senza estrarlo, empty restituisce vero se lo stack è vuoto, falso altrimenti.

Esercizio 2

Cosa fa la funzione bar che segue?

Versione C:

int bar(int x,int v[],int base,int len)
{
printf("BAR %d %d\n",base,len);
if (len <= 0)
 return -1;
else {
 int i=len/2;
 if (x == v[base+i])
  return base+i;
 else if (x < v[base+i])
  return bar(x,v,base,i);
 else
  return bar(x,v,base+i+1,len-(i+1));
}
}

Versione Pascal:

type
vettofint=array[0..99]of integer;

function bar(x:integer;v:vettofint;base:integer;len:integer):integer;
var
i:integer;
begin
writeln('BAR ',base,' ',len);
if (len <= 0) then
 bar:= -1
else
begin
 i:=len div 2;
 if (x = v[base+i]) then
  bar:=base+i
 else if (x < v[base+i]) then
  bar:=bar(x,v,base,i)
 else
  bar:=bar(x,v,base+i+1,len-(i+1));
end;
end;

Esercizio 3

Descrivere brevemente cosa è un albero binario di ricerca. Quale è la complessità computazionale per cercare un dato in un albero binario di ricerca?

Seconda parte - Inglese

Spiegare (in Italiano) il significato di questo passo del libro di “TCP/IP Illustrated, Volume 1, The Protocols, W. Richard Stevens

Dynamic routing occurs when routers talk to adjacent routers, informing each other of what networks each router is currently connected to. The routers must communicate using a routing protocol, of which there are many to choose from. The process on the router that is running the routing protocol, communicating with its neighbor routers, is usually called a routing daemon. As shown in Figure 9.1, the routing daemon updates the kernel’s routing table with information it receives from neighbor routers. The use of dynamic routing does not change the way the kernel performs routing at the IP layer, as we described in Section 9.2. We called this the routing mechanism. “The kernel still searches its routing table in the same way, looking for host routes, network routes, and default routes. What changes is the information placed into the routing table-instead of coming from route commands in bootstrap files, the routes are added and deleted dynamically by a routing daemon, as routes change over time. As we mentioned earlier, the routing daemon adds a routing policy to the system, choosing which routes to place into the kernel’s routing table. If the daemon finds multiple routes to a destination, the daemon chooses (somehow) which route is best, and which one to insert into the kernel’s table. If the daemon finds that a link has gone down (perhaps a router crashed or a phone line is out of order), it can delete the affected routes or add alternate routes that bypass the problem.

 
prova_2005.txt · Ultima modifica: 2009/07/24 09:21 da kendra
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki