Студопедия

КАТЕГОРИИ:

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


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

Стр 1 из 6Следующая ⇒



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>
  11. using namespace std;
  12. struct node
  13. {
  14. int h,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. h=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x;
  26. int h(pnode t)
  27. {
  28. return t ? t->h : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->h=max(h(t->l),h(t->r))+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0)
  47. t=new node(x);
  48. else
  49. if (t->x > x) add(t->l, x);
  50. else
  51. add(t->r, x);
  52. update(t);
  53. }
  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. printf("%d",h(t));
  68. return 0;
  69. }

 

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>
  11. using namespace std;
  12. struct node
  13. {
  14. int size,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. size=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x;
  26. int size(pnode t)
  27. {
  28. return t ? t->size : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->size=size(t->l)+size(t->r)+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0) t=new node(x);
  47. else
  48. if (t->x > x) add(t->l, x);
  49. else
  50. add(t->r, x);
  51. update(t);
  52. }
  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. printf("%d",size(t));
  67. return 0;
  68. }

 

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>
  11. using namespace std;
  12. struct node
  13. {
  14. int size,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. size=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x,ans;
  26. int size(pnode t)
  27. {
  28. return t ? t->size : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->size=size(t->l)+size(t->r)+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0) t=new node(x);
  47. else
  48. if (t->x > x) add(t->l, x);
  49. else
  50. add(t->r, x);
  51. update(t);
  52. }
  54. void del_max(pnode &t)
  55. {
  56. if(t->r)
  57. del_max(t->r);
  58. else
  59. t=t->l;
  60. }
  62. int max(pnode t)
  63. {
  64. return (t->r) ? max(t->r) : t->x;
  65. }
  67. int main()
  68. {
  69. freopen( "input.txt","r",stdin );
  70. freopen( "output.txt","w",stdout );
  71. pnode t=0;
  72. while (1)
  73. {
  74. scanf("%d",&x);
  75. if (!x) break;
  76. if (! find(t, x))
  77. add(t, x);
  78. }
  79. int k=2;
  80. for (int i=1;i<=k;i++)
  81. ans=max(t), del_max(t);
  82. printf("%d",ans);
  83. return 0;
  84. }

 

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>
  11. using namespace std;
  12. struct node
  13. {
  14. int size,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. size=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x,ans;
  26. int size(pnode t)
  27. {
  28. return t ? t->size : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->size=size(t->l)+size(t->r)+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0) t=new node(x);
  47. else
  48. if (t->x > x) add(t->l, x);
  49. else
  50. add(t->r, x);
  51. update(t);
  52. }
  54. void dfs(pnode t)
  55. {
  56. if (t->l) dfs(t->l);
  57. printf("%d ",t->x);
  58. if (t->r) dfs(t->r);
  59. }
  61. int main()
  62. {
  63. freopen( "input.txt","r",stdin );
  64. freopen( "output.txt","w",stdout );
  65. pnode t=0;
  66. while (1)
  67. {
  68. scanf("%d",&x);
  69. if (!x) break;
  70. if (! find(t, x))
  71. add(t, x);
  72. }
  73. dfs(t);
  74. return 0;
  75. }

 

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>
  11. using namespace std;
  12. struct node
  13. {
  14. int size,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. size=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x,ans;
  26. int size(pnode t)
  27. {
  28. return t ? t->size : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->size=size(t->l)+size(t->r)+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0) t=new node(x);
  47. else
  48. if (t->x > x) add(t->l, x);
  49. else
  50. add(t->r, x);
  51. update(t);
  52. }
  54. void dfs(pnode t)
  55. {
  56. if (t->l) dfs(t->l);
  57. if (t->r) dfs(t->r);
  58. if ((!(t->r)&&!(t->l)))
  59. printf("%d ",t->x);
  60. }
  62. int main()
  63. {
  64. freopen( "input.txt","r",stdin );
  65. freopen( "output.txt","w",stdout );
  66. pnode t=0;
  67. while (1)
  68. {
  69. scanf("%d",&x);
  70. if (!x) break;
  71. if (! find(t, x))
  72. add(t, x);
  73. }
  74. dfs(t);
  75. return 0;
  76. }

 

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>
  11. using namespace std;
  12. struct node
  13. {
  14. int size,x;
  15. node *l, *r;
  16. node (int key)
  17. {
  18. x=key;
  19. size=1;
  20. l=r=0;
  21. }
  22. };
  23. typedef node* pnode;
  24. int x,ans;
  26. int size(pnode t)
  27. {
  28. return t ? t->size : 0;
  29. }
  31. void update(pnode &t)
  32. {
  33. t->size=size(t->l)+size(t->r)+1;
  34. }
  36. int find(pnode t, int x)
  37. {
  38. if (t==0) return 0;
  39. if (t->x == x) return 1;
  40. if (t->x > x) return find(t->l, x);
  41. return find(t->r, x);
  42. }
  44. void add(pnode &t,int x)
  45. {
  46. if (t==0) t=new node(x);
  47. else
  48. if (t->x > x) add(t->l, x);
  49. else
  50. add(t->r, x);
  51. update(t);
  52. }
  54. void dfs(pnode t)
  55. {
  56. if (t->l) dfs(t->l);
  57. if ((t->r)&&(t->l))
  58. printf("%d ",t->x);
  59. if (t->r) dfs(t->r);
  60. }
  62. int main()
  63. {
  64. freopen( "input.txt","r",stdin );
  65. freopen( "output.txt","w",stdout );
  66. pnode t=0;
  67. while (1)
  68. {
  69. scanf("%d",&x);
  70. if (!x) break;
  71. if (! find(t, x))
  72. add(t, x);
  73. }
  74. dfs(t);
  75. return 0;
  76. }

 

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>
  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;
  25. int size(pnode t)
  26. {
  27. return t ? t->size : 0;
  28. }
  30. void update(pnode &t)
  31. {
  32. t->size=size(t->l)+size(t->r)+1;
  33. }
  35. int find(pnode t, int x)
  36. {
  37. if (t==0) return 0;
  38. if (t->x == x) return 1;
  39. if (t->x > x) return find(t->l, x);
  40. return find(t->r, x);
  41. }
  43. void add(pnode &t,int x)
  44. {
  45. if (t==0) t=new node(x);
  46. else
  47. if (t->x > x) add(t->l, x);
  48. else
  49. add(t->r, x);
  50. update(t);
  51. }
  53. void dfs(pnode t)
  54. {
  55. if (t->l) dfs(t->l);
  56. if ((t->r!=0)^(t->l!=0))
  57. printf("%d ",t->x);
  58. if (t->r) dfs(t->r);
  59. }
  61. int main()
  62. {
  63. freopen( "input.txt","r",stdin );
  64. freopen( "output.txt","w",stdout );
  65. pnode t=0;
  66. while (1)
  67. {
  68. scanf("%d",&x);
  69. if (!x) break;
  70. if (! find(t, x))
  71. add(t, x);
  72. }
  73. dfs(t);
  74. return 0;
  75. }

 

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

Поделиться:

Дата добавления: 2015-09-15; просмотров: 194; Мы поможем в написании вашей работы!; Нарушение авторских прав

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