daily pastebin goal
42%
SHARE
TWEET

Untitled

a guest Nov 14th, 2018 88 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. Programy mają być napisane tak, by można było wpisać swoje dane
  2.  
  3.  
  4.  
  5. Rozwišzania zadań z kolokwium I, AiSD, 11.XII.2017
  6.  
  7. 1) Usuwanie liczb z zakresu a<=y<=b z uporzšdkowanej listy wartownikiem *p->x=MAXINT > b.
  8.  
  9. void usun(wsk *p, int a, int b){
  10.   wsk q;
  11.   while (*p->x < a) { p=&((*p)->nast); }
  12.   while (*p->x <= b) {
  13.       q=*p;
  14.       *p=q->nast;
  15.       free(q);
  16.   }
  17. }
  18.  
  19.  
  20. 2) Wykrywanie powtórzeń w li?cie cyklicznej
  21.  
  22. int powt(wsk p){
  23.    wsk q=p,r;
  24.    if (p!=NULL){
  25.       do {
  26.          r=q->nast;
  27.          while (r!=p) {
  28.             if (r->x==q->x) { return 1; }
  29.             r=r->nast;
  30.          }
  31.          q=q->nast;
  32.       } while (q!=p);
  33.    }
  34.    return 0;
  35. }
  36.  
  37.  
  38. 3) Tworzenie "lustrzanej" kopii drzewa
  39.  
  40. wsk lusrto (wsk T){
  41.    if (T==NULL) {return NULL;}
  42.    wsk q=malloc(sizeof(eldrzewa));
  43.    q->x=T->x;
  44.    q->l=lustro(T->p);
  45.    q->p=lustro(T->l);
  46.    return q;
  47. }
  48.  
  49.  
  50. 4) Odpowiedz: 1 - drzewo zdegenerowane, 0 - w przeciwnym razie
  51.  
  52. int degen(wsk T){
  53.    if (T==NULL){return 1;}
  54.    if ((T->l!=NULL)&&(T->p!=NULL)) {return 0;}
  55.    return (T->l!=NULL) ? degen(T->l) : degen(T->p);
  56. }
  57.    
  58.  
  59. ----------------------------------------------------------------------------------------
  60. Kolokwium II  (25.I.2018)
  61.  
  62.  
  63. 1) Funkcja obliczajšca wyważenie drzewa
  64.  
  65. int liczebnosc(wsk T){
  66.    if (T==NULL) { return 0; }
  67.    else {
  68.       return liczebnosc(T->l) + liczebnosc(T->p) + 1;
  69.    }
  70. }
  71.  
  72. int wywazenie(wsk T){
  73.    if (T==NULL) { return 0; }
  74.    else {
  75.      return max(abs(liczebnosc(T->l)-liczebnosc(T->p)), wywazenie(T->l), wywazenie(T->p));
  76.    }
  77. }
  78.  
  79.  
  80. 2) Porównanie metod sortowania - wstawianie w tablicy i wstawianie do listy dynamicznej
  81.    
  82. W obydwu przypadkach liczba porównań jest w pesymistycznym przypadku rzędu O(n^2),
  83. natomiast liczba podstawień - O(n^2) w tablicy oraz O(n) w li?cie.
  84.  
  85.  
  86. 3) Tworzenie macierzy sšsiedztwa dla drzewa (globalna macierz M[n][n] jest pierwotnie wyzerowana)
  87.  
  88. void tworz(wsk T){
  89.    if (T!=NULL){
  90.       if (T->l!=NULL){
  91.           M[T->x][T->l->x]=1;
  92.           tworz(T->l);
  93.       }
  94.       if (T->p!=NULL){
  95.           M[T->x][T->p->x]=1;
  96.           tworz(T->p);
  97.       }
  98. }
  99.  
  100.  
  101. 4) Dzialanie procedury DFS i BFS
  102.  
  103. DFS: kolejnosc odwiedzenia wierzcholkow - 1, 3, 2, 5, 4, 6, 7, 8
  104.  
  105.       1
  106.       |
  107.       3
  108.       |
  109.       2
  110.       |
  111.       5
  112.      / \
  113.     4   7
  114.    /     \
  115.   6       8  
  116.                                    
  117.  
  118. BFS: kolejnosc - 1, 3, 2, 6, 7, 4, 5, 8
  119.  
  120.           1 ___
  121.         / | \  \
  122.        3  2  6  7
  123.       /   |      \
  124.      4    5       8
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top