单选题
| 题号 | 题目 | 答案 |
|---|
| 1 | 堆的形状是一棵： | 完全二叉树 | | 2 | 创建一个初始堆，含有N个记录，其时间复杂度是： | O(N) | | 3 | 已知关键字序列（5，8，12，19，28，20，15，22）是最小堆（小根堆），插入关键字3，调整后得到的最小堆是： | 3，5，12，8，28，20，15，22，19 | | 4 | 哪种树，树中任何结点到根结点路径上的各结点值是有序的？ | 堆 | | 5 | 将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为： | 9 | | 6 | 对最小堆（小顶堆）{1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} 进行三次删除最小元的操作后，结果序列为： | 4,6,5,12,7,10,8,15,14,9,13,11 | | 7 | 在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是： | ⌊n/2⌋+2 | | 8 | 用线性时间复杂度的算法将给定序列{ 28, 12, 5, 8, 19, 20, 15, 22 }调整为最大堆（大根堆），然后插入30。则结果序列为： | { 30, 28, 20, 22, 19, 5, 15, 8, 12 } | | 9 | 在一个有2333个元素的最小堆中，下列哪个下标不可能是最大元的位置？ | 1116 | | 10 | 在将数据序列（ 6, 1, 5, 9, 8, 4, 7 ）建成大根堆时，正确的序列变化过程是： | 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5 |
选择题题解
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;
}
|
