Questions bank for Final exam on SSD5
Binary search trees
1. Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.
Реализуйте бинарное дерево поиска (для maxheap и minheap задачи аналогичны) для целых чисел. Программа получает на вход последовательность целых чисел и строит из них дерево. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.
Формат входных данных
На вход программа получает последовательность натуральных чисел. Последовательность завершается числом 0, которое означает конец ввода, и добавлять его в дерево не надо.
Формат выходных данных
Выведите единственное число – высоту получившегося дерева.
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 |
Пример соответствует следующему дереву:
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int h,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- h=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x;
- int h(pnode t)
- {
- return t? t->h: 0;
- }
- void update(pnode &t)
- {
- t->h=max(h(t->l),h(t->r))+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- printf("%d",h(t));
- return 0;
- }
2) Подсчитайте количество элементов в получившемся дереве и выведите это количество.
|
|
Пример
Входные данные | Выходные данные |
1 2 3 1 0 |
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- printf("%d",size(t));
- return 0;
- }
3) Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 | |
1 1 1 2 2 2 0 |
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- void del_max(pnode &t)
- {
- if(t->r)
- del_max(t->r);
- else
- t=t->l;
- }
- int max(pnode t)
- {
- return (t->r)? max(t->r): t->x;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- int k=2;
- for (int i=1;i<=k;i++)
- ans=max(t), del_max(t);
- printf("%d",ans);
- return 0;
- }
4) Выведите все элементы полученного дерева в порядке возрастания.
|
|
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 | 1 2 3 4 5 6 7 8 9 |
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
5) Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 | 1 4 6 8 |
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if (t->r) dfs(t->r);
- if ((!(t->r)&&!(t->l)))
- printf("%d ",t->x);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
6) Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 | 3 5 7 |
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if ((t->r)&&(t->l))
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
7) Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.
Пример
Входные данные | Выходные данные |
7 3 2 1 9 5 4 6 8 0 | 2 9 |
//Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
- int size(pnode t)
- {
- return t? t->size: 0;
- }
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if ((t->r!=0)^(t->l!=0))
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
Стеки, очереди, деки, списки, кольца
|
|