单选题
选择题题解
1、完全二叉树（深度为 k ，有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称为完全二叉树。）
满二叉树（堆不保证节点的个数正好能构成满二叉树）
二叉排序树（最小堆只保证父节点比孩子节点小，并不是二叉排序树）
平衡二叉树（二叉平衡树肯定是一颗二叉排序树，堆不是二叉排序树）
3、（5，8，12，19，28，20，15，22）
插入3，3换19再换8再换5
10、是建树后调整序列的规则，是从第【n/2】（个节点最后一个有儿子的节点）向前面的【n/2-1】等节点的顺序进行，可以看作是自底向上、同层自右向左的顺序进行，找同级最大的一层层向上移动。
编程题
堆中的路径 — 用数组建立堆
这个题比较简单，就是用数组建立一个堆，这个堆也是个完全二叉树，所以满足性质：
从1开始的数组中父结点的下标是子结点下标的 int ( i / 2 )
主要操作：
代码中最主要的步骤就是在堆中插入一个元素：
为了满足完全二叉树，我们需要把新的结点先放到最后一个位置，
为了满足最小堆的建立，我们把新的结点进行与父结点比较并调整
我们在与父结点比较时，因为数组的有效结点是从1开始的，我们应该避免与数组的0元素比较
我们可以在0这个下标放一个特别特别小的数
使得在Insert这个操作中，我们不需要单独设置一个条件避免与H[0]比较
而是直接不让H[0]满足H[i / 2] > X这个条件
代码
#include<stdio.h> #include<stdlib.h> int H[1001], size; // 构建最小堆 void Insert(int x) { // 先放到最后一个位置（为了满足二叉树要求），之后再调整其位置（为了满足堆要求） int i; for (i=++size;H[i/2]>x ;i/=2) { H[i] = H[i / 2]; // 当父结点比x大时，把x放在父结点位置上 父结点的下到子结点 } H[i] = x; } int main() { int n, m, x, i, j; scanf("%d %d", &n, &m); size = 0; H[0] = -10001; // 设置岗哨，使得每次遍历树的父结点的结束条件变得简单 for (i = 0; i < n; i++) { scanf("%d", &x); Insert(x); } for (i = 0; i < m; i++) { scanf("%d", &j); printf("%d", H[j]); while (j>1) { j /= 2; printf(" %d", H[j]); } printf("\n"); } return 0; }
7-1 关于堆的判断 (25分)
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
x is the root：x是根结点；
x and y are siblings：x和y是兄弟结点；
x is the parent of y：x是y的父结点；
x is a child of y：x是y的一个子结点。
输入格式：
每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式：
对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。
输入样例：
5 4 46 23 26 24 10 24 is the root 26 and 23 are siblings 46 is the parent of 23 23 is a child of 10
输出样例：
F T F T
代码
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstdlib> #define INF 1000000 using namespace std; int a[1010], n, m; // a存堆 // 插入小顶堆 /* 调整序列的规则 : 是从第【n/2】（个节点最后一个有儿子的节点）向前面的【n/2-1】等节点的顺序进行 */ int insert(int i) { int temp; while (a[i / 2] > a[i] && i != 1) { temp = a[i]; a[i] = a[i / 2]; a[i / 2] = temp; i = i / 2; } return 0; } // 找元素的爸爸 int find(int x) { int p, i; for (i = 1; i <= n; i++) { if (a[i] == x) p = i; } return a[p / 2]; } // 判断函数 int panduan() { string str, str1, str2; int x, y; char ch; cin >> x >> str; if (str == "and") { cin >> y >> str1 >> str2; if (find(x) == find(y)) // 兄弟结点就找相同的爸爸就行 cout << "T" << endl; else cout << "F" << endl; return 0; } cin >> str; if (str == "a") { cin >> str1 >> str2 >> y; if (find(x) == y) // x是y的一个子结点。 看x的爸爸是不是y cout << "T" << endl; else cout << "F" << endl; return 0; } cin >> str; if (str == "root") { // x是根结点； 看x是不是第一个 if (a[1] == x) cout << "T" << endl; else cout << "F" << endl; return 0; } cin >> str1 >> y; if (find(y) == x) // x是y的父结点； 看y的爸爸是不是x cout << "T" << endl; else cout << "F" << endl; return 0; } int main() { cin >> n >> m; int i, j; cin >> a[1]; for (i = 2; i <= n; i++) { cin >> a[i]; insert(i);//除了第一个节点不用进行插入排序，余下节点都需要进行插入排序 } while (m--) { panduan();//对字符串进行对错判断 } return 0; }
