單選題
| 題號 | 題目 | 答案 |
|---|
| 1 | 堆的形狀是一棵： | 完全二叉樹 | | 2 | 創(chuàng)建一個初始堆，含有N個記錄，其時間復雜度是： | O(N) | | 3 | 已知關鍵字序列（5，8，12，19，28，20，15，22）是最小堆（小根堆），插入關鍵字3，調(diào)整后得到的最小堆是： | 3，5，12，8，28，20，15，22，19 | | 4 | 哪種樹，樹中任何結(jié)點到根結(jié)點路徑上的各結(jié)點值是有序的？ | 堆 | | 5 | 將6,、4,、3、5,、8,、9順序插入初始為空的最大堆（大根堆）中，那么插入完成后堆頂?shù)脑貫?#xff1a; | 9 | | 6 | 對最小堆（小頂堆）{1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} 進行三次刪除最小元的操作后，結(jié)果序列為： | 4,6,5,12,7,10,8,15,14,9,13,11 | | 7 | 在有n（>1）個元素的最大堆（大根堆）中，最小元的數(shù)組下標可以是： | ?n/2?+2 | | 8 | 用線性時間復雜度的算法將給定序列{ 28, 12, 5, 8, 19, 20, 15, 22 }調(diào)整為最大堆（大根堆），然后插入30,。則結(jié)果序列為： | { 30, 28, 20, 22, 19, 5, 15, 8, 12 } | | 9 | 在一個有2333個元素的最小堆中，下列哪個下標不可能是最大元的位置？ | 1116 | | 10 | 在將數(shù)據(jù)序列（ 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 個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點一一對應時，稱為完全二叉樹,。）
 -
滿二叉樹（堆不保證節(jié)點的個數(shù)正好能構(gòu)成滿二叉樹） -
二叉排序樹（最小堆只保證父節(jié)點比孩子節(jié)點小，并不是二叉排序樹） -
平衡二叉樹（二叉平衡樹肯定是一顆二叉排序樹，堆不是二叉排序樹）
3、（5，8，12，19，28，20，15，22）
插入3，3換19再換8再換5
10,、是建樹后調(diào)整序列的規(guī)則，是從第【n/2】（個節(jié)點最后一個有兒子的節(jié)點）向前面的【n/2-1】等節(jié)點的順序進行，可以看作是自底向上,、同層自右向左的順序進行，找同級最大的一層層向上移動。
編程題
堆中的路徑 — 用數(shù)組建立堆
這個題比較簡單，就是用數(shù)組建立一個堆，這個堆也是個完全二叉樹，所以滿足性質(zhì)：
從1開始的數(shù)組中父結(jié)點的下標是子結(jié)點下標的 int ( i / 2 )
主要操作：
-
代碼中最主要的步驟就是在堆中插入一個元素：
為了滿足完全二叉樹，我們需要把新的結(jié)點先放到最后一個位置，
為了滿足最小堆的建立，我們把新的結(jié)點進行與父結(jié)點比較并調(diào)整 -
我們在與父結(jié)點比較時，因為數(shù)組的有效結(jié)點是從1開始的，我們應該避免與數(shù)組的0元素比較
我們可以在0這個下標放一個特別特別小的數(shù)
使得在Insert這個操作中，我們不需要單獨設置一個條件避免與H[0]比較
而是直接不讓H[0]滿足H[i / 2] > X這個條件
代碼
#include<stdio.h>
#include<stdlib.h>
int H[1001], size;
// 構(gòu)建最小堆
void Insert(int x)
{
// 先放到最后一個位置（為了滿足二叉樹要求），之后再調(diào)整其位置（為了滿足堆要求）
int i;
for (i=++size;H[i/2]>x ;i/=2)
{
H[i] = H[i / 2];// 當父結(jié)點比x大時，把x放在父結(jié)點位置上 父結(jié)點的下到子結(jié)點
}
H[i] = x;
}
int main()
{
int n, m, x, i, j;
scanf("%d %d", &n, &m);
size = 0;
H[0] = -10001;// 設置崗哨，使得每次遍歷樹的父結(jié)點的結(jié)束條件變得簡單
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分)
將一系列給定數(shù)字順序插入一個初始為空的小頂堆H[],。隨后判斷一系列相關命題是否為真,。命題分下列幾種：
- x is the root：x是根結(jié)點；
- x and y are siblings：x和y是兄弟結(jié)點；
- x is the parent of y：x是y的父結(jié)點；
- x is a child of y：x是y的一個子結(jié)點。
輸入格式：
每組測試第1行包含2個正整數(shù)N（≤ 1000）和M（≤ 20），分別是插入元素的個數(shù),、以及需要判斷的命題數(shù),。下一行給出區(qū)間[?10000,10000]內(nèi)的N個要被插入一個初始為空的小頂堆的整數(shù)。之后M行，每行給出一個命題,。題目保證命題中的結(jié)點鍵值都是存在的,。
輸出格式：
對輸入的每個命題，如果其為真，則在一行中輸出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存堆
// 插入小頂堆
/*
調(diào)整序列的規(guī)則 : 是從第【n/2】（個節(jié)點最后一個有兒子的節(jié)點）向前面的【n/2-1】等節(jié)點的順序進行
*/
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];
}
// 判斷函數(shù)
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))// 兄弟結(jié)點就找相同的爸爸就行
cout << "T" << endl;
else
cout << "F" << endl;
return 0;
}
cin >> str;
if (str == "a") {
cin >> str1 >> str2 >> y;
if (find(x) == y)// x是y的一個子結(jié)點,。 看x的爸爸是不是y
cout << "T" << endl;
else
cout << "F" << endl;
return 0;
}
cin >> str;
if (str == "root") {// x是根結(jié)點； 看x是不是第一個
if (a[1] == x)
cout << "T" << endl;
else
cout << "F" << endl;
return 0;
}
cin >> str1 >> y;
if (find(y) == x)// x是y的父結(jié)點； 看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);//除了第一個節(jié)點不用進行插入排序，余下節(jié)點都需要進行插入排序
}
while (m--)
{
panduan();//對字符串進行對錯判斷
}
return 0;
}
|
