UC3M

Telematic/Audiovisual Syst./Communication Syst. Engineering

Systems Architecture

September 2017 - January 2018

7.8. Self-assessment questions

Check with these questions if you understood this document

  1. The incomplete piece of code defining a hash table data structure, with collisions managed as linked list is as follows:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct datos {
     char *name;
     int nia; 
    };
    struct elemento_t {
     struct datos valor;
     struct elemento_t *next;
    };
    struct tabla_type {
     int tamanho;
     int num_elementos;
     double densidad_deseada;
     ???????????????????????
    };

    Choose the missing piece of code

    • struct elemento_t *tabla;

    • struct elemento_t **tabla;

    • struct elemento_t tabla;

  2. The incomplete piece of code defining a variable table of the type tabla_type:

    1
    2
    3
    4
    5
    6
    7
    tabla_type tabla;
    int i;
    tabla.tamanho=20;
    tabla.num_elementos=0;
    tabla.densidad_deseada=0.25;
    tabla.tabla = (elemento_type **) malloc (sizeof(elemento_type *)*tabla.tamanho);
    ?????????????????

    Choose the missing piece of code

    • for (i=0;i<tabla.tamanho;i++)
      {
       tabla.tabla[i]=NULL;
      }

    • for (i=0;i<tabla.tamanho;i++)
      {
       tabla.tabla=NULL;
      }

    • There is nothing missing in the code.

  3. The incomplete piece of code of the hash function and the needed functions to insert a new element

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int hash(int clave,tabla_type *tabla)
    {
    /*fmod returns the module of the division*/
    return (int ) fmod((float)clave,(float)tabla->tamanho); 
    }
    
    elemento_type *new_element(int clave, datos valor, elemento_type *next){
     elemento_type *new_el = (elemento_type *)malloc(sizeof (elemento_type));
     new_el->datos=valor;
     new_el->clave=clave;
     new_el->next=next;
     return new_el;
    }
    
    void insert_element(int clave, datos valor, tabla_type *table){
     int index;
     index = hash(clave,tabla);
    ?????????????????????????????????
    }

    Choose the missing piece of code

    • new_element(clave,valor,tabla);

    • tabla=new_element(clave,valor,tabla[index]);

    • tabla->tabla[index]=new_element(clave,valor,tabla->tabla[index]);