Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Стеки, очереди, деки, списки, кольца




Читайте также:
  1. ВПЕРЕДИ РАЗДАЛИСЬ АВТОМАТНЫЕ ОЧЕРЕДИ, И АБДУЛЛА РЕЗКО НАЖАЛ НА ТОРМОЗА.
  2. Контактные кольца, контрольные кольца
  3. Лабораторная работа 2. Табуляция, списки, многоколончатая верстка
  4. МЕТОД ОТРЫВА КОЛЬЦА
  5. Определение коэффициента поверхностного натяжения методом отрыва кольца.
  6. ПОРШНИ И ПОРШНЕВЫЕ КОЛЬЦА
  7. Списки, табуляция, таблицы, многоколончатая верстка
  8. Текущие регистры (списки, картотеки) населения
  9. УПРАЖНЕНИЯ НА КОЛЬЦАХ

Questions bank for Final exam on SSD5

Binarysearchtrees

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Реализуйте бинарное дерево поиска (для maxheap и minheap задачи аналогичны) для целых чисел. Программа получает на вход последовательность целых чисел и строит из них дерево. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.

Формат входных данных

На вход программа получает последовательность натуральных чисел. Последовательность завершается числом 0, которое означает конец ввода, и добавлять его в дерево не надо.

Формат выходных данных

Выведите единственное число – высоту получившегося дерева.

Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0

Пример соответствует следующему дереву:

  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int h,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. h=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x;
  24. int h(pnode t)
  25. {
  26. return t ? t->h : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->h=max(h(t->l),h(t->r))+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0)
  42. t=new node(x);
  43. else
  44. if (t->x > x) add(t->l, x);
  45. else
  46. add(t->r, x);
  47. update(t);
  48. }
  49. int main()
  50. {
  51. freopen( "input.txt","r",stdin );
  52. freopen( "output.txt","w",stdout );
  53. pnode t=0;
  54. while (1)
  55. {
  56. scanf("%d",&x);
  57. if (!x) break;
  58. if (! find(t, x))
  59. add(t, x);
  60. }
  61. printf("%d",h(t));
  62. return 0;
  63. }

 

2) Подсчитайте количество элементов в получившемся дереве и выведите это количество.

Пример

Входные данные Выходные данные
1 2 3 1 0

 



  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int size,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. size=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x;
  24. int size(pnode t)
  25. {
  26. return t ? t->size : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->size=size(t->l)+size(t->r)+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0) t=new node(x);
  42. else
  43. if (t->x > x) add(t->l, x);
  44. else
  45. add(t->r, x);
  46. update(t);
  47. }
  48. int main()
  49. {
  50. freopen( "input.txt","r",stdin );
  51. freopen( "output.txt","w",stdout );
  52. pnode t=0;
  53. while (1)
  54. {
  55. scanf("%d",&x);
  56. if (!x) break;
  57. if (! find(t, x))
  58. add(t, x);
  59. }
  60. printf("%d",size(t));
  61. return 0;
  62. }

 

3) Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.



Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0
1 1 1 2 2 2 0

 

  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int size,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. size=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x,ans;
  24. int size(pnode t)
  25. {
  26. return t ? t->size : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->size=size(t->l)+size(t->r)+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0) t=new node(x);
  42. else
  43. if (t->x > x) add(t->l, x);
  44. else
  45. add(t->r, x);
  46. update(t);
  47. }
  48. void del_max(pnode &t)
  49. {
  50. if(t->r)
  51. del_max(t->r);
  52. else
  53. t=t->l;
  54. }
  55. int max(pnode t)
  56. {
  57. return (t->r) ? max(t->r) : t->x;
  58. }
  59. int main()
  60. {
  61. freopen( "input.txt","r",stdin );
  62. freopen( "output.txt","w",stdout );
  63. pnode t=0;
  64. while (1)
  65. {
  66. scanf("%d",&x);
  67. if (!x) break;
  68. if (! find(t, x))
  69. add(t, x);
  70. }
  71. int k=2;
  72. for (int i=1;i<=k;i++)
  73. ans=max(t), del_max(t);
  74. printf("%d",ans);
  75. return 0;
  76. }

 

4) Выведите все элементы полученного дерева в порядке возрастания.

Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0 1 2 3 4 5 6 7 8 9

 

  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int size,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. size=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x,ans;
  24. int size(pnode t)
  25. {
  26. return t ? t->size : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->size=size(t->l)+size(t->r)+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0) t=new node(x);
  42. else
  43. if (t->x > x) add(t->l, x);
  44. else
  45. add(t->r, x);
  46. update(t);
  47. }
  48. void dfs(pnode t)
  49. {
  50. if (t->l) dfs(t->l);
  51. printf("%d ",t->x);
  52. if (t->r) dfs(t->r);
  53. }
  54. int main()
  55. {
  56. freopen( "input.txt","r",stdin );
  57. freopen( "output.txt","w",stdout );
  58. pnode t=0;
  59. while (1)
  60. {
  61. scanf("%d",&x);
  62. if (!x) break;
  63. if (! find(t, x))
  64. add(t, x);
  65. }
  66. dfs(t);
  67. return 0;
  68. }

 



5) Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.

Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0 1 4 6 8
  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int size,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. size=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x,ans;
  24. int size(pnode t)
  25. {
  26. return t ? t->size : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->size=size(t->l)+size(t->r)+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0) t=new node(x);
  42. else
  43. if (t->x > x) add(t->l, x);
  44. else
  45. add(t->r, x);
  46. update(t);
  47. }
  48. void dfs(pnode t)
  49. {
  50. if (t->l) dfs(t->l);
  51. if (t->r) dfs(t->r);
  52. if ((!(t->r)&&!(t->l)))
  53. printf("%d ",t->x);
  54. }
  55. int main()
  56. {
  57. freopen( "input.txt","r",stdin );
  58. freopen( "output.txt","w",stdout );
  59. pnode t=0;
  60. while (1)
  61. {
  62. scanf("%d",&x);
  63. if (!x) break;
  64. if (! find(t, x))
  65. add(t, x);
  66. }
  67. dfs(t);
  68. return 0;
  69. }

 

6) Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.

Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0 3 5 7

 

  1. // Solution
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. using namespace std;
  11. struct node
  12. {
  13. int size,x;
  14. node *l, *r;
  15. node (int key)
  16. {
  17. x=key;
  18. size=1;
  19. l=r=0;
  20. }
  21. };
  22. typedef node* pnode;
  23. int x,ans;
  24. int size(pnode t)
  25. {
  26. return t ? t->size : 0;
  27. }
  28. void update(pnode &t)
  29. {
  30. t->size=size(t->l)+size(t->r)+1;
  31. }
  32. int find(pnode t, int x)
  33. {
  34. if (t==0) return 0;
  35. if (t->x == x) return 1;
  36. if (t->x > x) return find(t->l, x);
  37. return find(t->r, x);
  38. }
  39. void add(pnode &t,int x)
  40. {
  41. if (t==0) t=new node(x);
  42. else
  43. if (t->x > x) add(t->l, x);
  44. else
  45. add(t->r, x);
  46. update(t);
  47. }
  48. void dfs(pnode t)
  49. {
  50. if (t->l) dfs(t->l);
  51. if ((t->r)&&(t->l))
  52. printf("%d ",t->x);
  53. if (t->r) dfs(t->r);
  54. }
  55. int main()
  56. {
  57. freopen( "input.txt","r",stdin );
  58. freopen( "output.txt","w",stdout );
  59. pnode t=0;
  60. while (1)
  61. {
  62. scanf("%d",&x);
  63. if (!x) break;
  64. if (! find(t, x))
  65. add(t, x);
  66. }
  67. dfs(t);
  68. return 0;
  69. }

 

7) Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.

Пример

Входные данные Выходные данные
7 3 2 1 9 5 4 6 8 0 2 9

//Solution

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <cmath>
  7. #include <set>
  8. #include <map>
  9. using namespace std;
  10. struct node
  11. {
  12. int size,x;
  13. node *l, *r;
  14. node (int key)
  15. {
  16. x=key;
  17. size=1;
  18. l=r=0;
  19. }
  20. };
  21. typedef node* pnode;
  22. int x,ans;
  23. int size(pnode t)
  24. {
  25. return t ? t->size : 0;
  26. }
  27. void update(pnode &t)
  28. {
  29. t->size=size(t->l)+size(t->r)+1;
  30. }
  31. int find(pnode t, int x)
  32. {
  33. if (t==0) return 0;
  34. if (t->x == x) return 1;
  35. if (t->x > x) return find(t->l, x);
  36. return find(t->r, x);
  37. }
  38. void add(pnode &t,int x)
  39. {
  40. if (t==0) t=new node(x);
  41. else
  42. if (t->x > x) add(t->l, x);
  43. else
  44. add(t->r, x);
  45. update(t);
  46. }
  47. void dfs(pnode t)
  48. {
  49. if (t->l) dfs(t->l);
  50. if ((t->r!=0)^(t->l!=0))
  51. printf("%d ",t->x);
  52. if (t->r) dfs(t->r);
  53. }
  54. int main()
  55. {
  56. freopen( "input.txt","r",stdin );
  57. freopen( "output.txt","w",stdout );
  58. pnode t=0;
  59. while (1)
  60. {
  61. scanf("%d",&x);
  62. if (!x) break;
  63. if (! find(t, x))
  64. add(t, x);
  65. }
  66. dfs(t);
  67. return 0;
  68. }

 

Стеки, очереди, деки, списки, кольца


Дата добавления: 2015-09-15; просмотров: 13; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.014 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты