建堆时，最坏情况下需要挪动元素次数是等于树中各结点的高度和。问：对于元素个数为12的堆，其各结点的高度之和是多少？
答：一共有 4 层。
1 + 2 + 3 + 4 = 10
- A. 2, 55, 52, 72, 28, 98, 71
- B. 2, 28, 71, 72, 55, 98, 52
- C. 2, 28, 52, 72, 55, 98, 71 (√)
- D. 28, 2, 71, 72, 55, 98, 52
自己按照 1 - (2, 3), 2 - (4, 5) 的树结构捋。
在最大堆 {97,76,65,50,49,13,27}中插入83后，该最大堆为：
- A. {97,76,65,83,49,13,27,50}
- B. {97,83,65,76,49,13,27,50} (√)
- C. {97,83,65,76,50,13,27,49}
- D. {97,83,65,76,49,50,13,27}
把 83 放到队尾，位置是 8 ，然后自己往前捋：4 2 1 ...
对由同样的n个整数构成的二叉搜索树（查找树）和最小堆，下面哪个说法是不正确的:
- A. 二叉搜索树（查找树）高度大于等于最小堆高度
（二叉搜树不一定是完全二叉树，对） - B. 对该二叉搜索树（查找树）进行中序遍历可得到从小到大的序列
- C. 从最小堆根节点到其任何叶结点的路径上的结点值构成从小到大的序列
- D. 对该最小堆进行按层序（level order）遍历可得到从小到大的序列
（1,2,3和1,3,2都是最小堆）
如果哈夫曼树有67个结点，则可知叶结点总数为：34
2n-1=67
- A. 00，100，101，110，111（存在度为1的结点）
- B. 000，001，01，10，11
- C. 0000，0001，001，01，1
- D. 000，001，010，011，1
一段文本中包含对象{a,b,c,d,e}，其出现次数相应为{3,2,4,2,1}，则经过哈夫曼编码后，该文本所占总位数为：27。
先画哈夫曼树，然后得到每个的编码，然后编码长度乘出现次数求和。
已知a、b两个元素均是所在集合的根结点，且分别位于数组分量3和2位置上，其parent值分别为-3,-2。问：将这两个集合按集合大小合并后，a和b的parent值分别是多少？
-5 3
-3 表示是根节点，且本集合有 3 个元素。
我认为，应该是把树画出来，看有没有对象不在叶节点上。
很简单的建堆。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], idx;
void up(int u)
{
while (u / 2 && h[u / 2] > h[u])
{
swap(h[u], h[u / 2]);
u = u / 2;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++ i)
{
int a;
cin >> a;
h[++idx] = a;
up(idx);
}
for (int i = 0; i < m; ++ i)
{
int a;
cin >> a;
cout << h[a];
while (a / 2)
{
cout << " " << h[a / 2];
a = a / 2;
}
cout << endl;
}
}
input 1
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
output 1
no
no
yes
There are 2 components.
input 2
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S
output 2
no
no
yes
yes
The network is connected.
#include <iostream>
using namespace std;
const int N = 10010;
int p[N], st[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
for (int i = 0; i < N; ++ i) p[i] = i;
int n;
scanf("%d", &n);
char op;
scanf("%c", &op);
while (true)
{
if (op == 'S') break;
int a, b;
scanf("%d %d", &a, &b);
if (op == 'I') // 注意这里写 p[a] = find(b) 会不过一个答案
p[find(a)] = find(b);
else if (op == 'C')
{
int pa = find(a);
int pb = find(b);
if (pa == pb) printf("yes\n");
else printf("no\n");
}
scanf("%c", &op);
}
int k = 0;
for (int i = 1; i <= n; ++ i)
{
int px = find(i);
if (!st[px])
{
k ++ ;
st[px] = true;
}
}
if (k == 1) printf("The network is connected.");
else printf("There are %d components.", k);
}2021年11月10日补：
- 注意在合并操作中，要写成
p[find(a)] = find(b);而非p[a] = find(b);
// 建树，建完了检查：
// - WPL 最小
// - 有没有度为1的节点
// - 有没有是编码终点但是不是叶节点的
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 130, M = 65; // n 个字符，合并 n - 1 次，新增 n - 1 个节点
char g[M][M];
int n, l[N], r[N], idx, st[N];
int w[M];
int char2int(char c)
{
if (c >= '0' && c <= '9') return c - 0;
if (c >= 'a' && c <= 'z') return c - 'a' + 10;
if (c >= 'A' && c <= 'Z') return c - 'A' + 'z' - 'a' + 1;
return '9' - '0' + 1 + 'z' - 'a' + 1 + 'Z' - 'A' + 1;
}
int main()
{
cin >> n;
// 先自己建个哈夫曼树求最优 WPL
priority_queue<int> q;
for (int i = 0; i < n; ++ i)
{
char c;
int a, b;
cin >> c >> b;
a = char2int(c);
w[a] = b;
q.push(-b);
}
// 建一下树求 wpl
int best_wpl = 0;
while (q.size())
{
auto t = q.top();
q.pop();
if (q.size())
{
auto t1 = q.top();
q.pop();
int new_node = - t - t1;
best_wpl += new_node;
q.push(- new_node);
}
}
int m;
cin >> m;
while (m --)
{
int wpl = 0;
idx = 0;
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
memset(st, 0, sizeof st);
for (int i = 0; i < n; ++ i)
{
char c;
cin >> c >> g[i];
wpl += w[char2int(c)] * strlen(g[i]);
// 建树
int root = 0, j = 0;
while (g[i][j])
{
if (g[i][j] == '0')
{
if (l[root] == -1)
{
l[root] = ++ idx;
root = idx;
}
else root = l[root];
}
else
{
if (r[root] == -1)
{
r[root] = ++ idx;
root = idx;
}
else root = r[root];
}
j ++ ;
}
st[root] = true; // 标记一下这个是编码终点
}
// 检查 wpl
if (wpl != best_wpl)
{
cout << "No\n";
continue;
}
// 遍历检查树
bool flag = true;
queue<int> nodes;
nodes.push(0);
while (nodes.size())
{
int t = nodes.front();
nodes.pop();
if (l[t] == -1 && r[t] != -1 || l[t] != -1 && r[t] == -1)
{
flag = false;
break;
}
if (l[t] != -1 && r[t] != -1)
{
if (st[t])
{
flag = false;
break;
}
nodes.push(l[t]);
nodes.push(r[t]);
}
else if (l[t] != -1 || r[t] != -1)
{
flag = false;
break;
}
}
if (flag) cout << "Yes\n";
else cout << "No\n";
}
}