Programy mają być napisane tak, by można było wpisać swoje dane



Rozwišzania zadań z kolokwium I, AiSD, 11.XII.2017

1) Usuwanie liczb z zakresu a<=y<=b z uporzšdkowanej listy wartownikiem *p->x=MAXINT > b.

void usun(wsk *p, int a, int b){
  wsk q;
  while (*p->x < a) { p=&((*p)->nast); }
  while (*p->x <= b) {
      q=*p;
      *p=q->nast;
      free(q);
  }
}


2) Wykrywanie powtórzeń w li?cie cyklicznej

int powt(wsk p){
   wsk q=p,r;
   if (p!=NULL){
      do {
         r=q->nast;
         while (r!=p) {
            if (r->x==q->x) { return 1; }
            r=r->nast;
         }
         q=q->nast;
      } while (q!=p);
   }
   return 0;
}


3) Tworzenie "lustrzanej" kopii drzewa

wsk lusrto (wsk T){
   if (T==NULL) {return NULL;}
   wsk q=malloc(sizeof(eldrzewa));
   q->x=T->x;
   q->l=lustro(T->p);
   q->p=lustro(T->l);
   return q;
}


4) Odpowiedz: 1 - drzewo zdegenerowane, 0 - w przeciwnym razie

int degen(wsk T){
   if (T==NULL){return 1;}
   if ((T->l!=NULL)&&(T->p!=NULL)) {return 0;}
   return (T->l!=NULL) ? degen(T->l) : degen(T->p);
}


----------------------------------------------------------------------------------------
Kolokwium II  (25.I.2018)


1) Funkcja obliczajšca wyważenie drzewa

int liczebnosc(wsk T){
   if (T==NULL) { return 0; }
   else {
      return liczebnosc(T->l) + liczebnosc(T->p) + 1;
   }
}

int wywazenie(wsk T){
   if (T==NULL) { return 0; }
   else {
     return max(abs(liczebnosc(T->l)-liczebnosc(T->p)), wywazenie(T->l), wywazenie(T->p));
   }
}


2) Porównanie metod sortowania - wstawianie w tablicy i wstawianie do listy dynamicznej

W obydwu przypadkach liczba porównań jest w pesymistycznym przypadku rzędu O(n^2),
natomiast liczba podstawień - O(n^2) w tablicy oraz O(n) w li?cie.


3) Tworzenie macierzy sšsiedztwa dla drzewa (globalna macierz M[n][n] jest pierwotnie wyzerowana)

void tworz(wsk T){
   if (T!=NULL){
      if (T->l!=NULL){
          M[T->x][T->l->x]=1;
          tworz(T->l);
      }
      if (T->p!=NULL){
          M[T->x][T->p->x]=1;
          tworz(T->p);
      }
}


4) Dzialanie procedury DFS i BFS

DFS: kolejnosc odwiedzenia wierzcholkow - 1, 3, 2, 5, 4, 6, 7, 8

      1
      |
      3
      |
      2
      |
      5
     / \
    4   7
   /     \
  6       8


BFS: kolejnosc - 1, 3, 2, 6, 7, 4, 5, 8

          1 ___
        / | \  \
       3  2  6  7
      /   |      \
     4    5       8