1-1存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。
(1分)作者何钦铭单位浙江大学1-1答案正确(1 分)
1-2具有10个叶结点的二叉树中，有9个度为2的结点。
(1分)作者李廷元单位民用航空飞行学院1-2答案正确(1 分)
1-3某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。
(2分)作者DS课程组单位浙江大学1-3答案正确(2 分)
1-5某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。
(2分)作者DS课程组单位浙江大学1-5答案正确(2 分)
1-7二叉树可以用二叉链表存储，树无法用二叉链表存储。
(1分)作者DS课程组单位临沂大学1-7答案正确(1 分)
1-8将一棵树转成二叉树，根结点没有左子树。
(1分)作者DS课程组单位临沂大学1-8答案正确(1 分)
1-9对（）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。
(2分)作者DS课程组单位浙江大学1-9答案正确(2 分)
1-10哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。
(2分)作者徐镜春单位浙江大学1-10答案正确(2 分)2-1树最适合于用来表示
(1分)作者DS课程组单位浙江大学2-1答案正确(1 分)
2-2在下述结论中，正确的是：
① 只有2个结点的树的度为1；
② 二叉树的度为2；
③ 二叉树的左右子树可任意交换；
④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。
(2分)作者陈越单位浙江大学2-2答案正确(2 分)
2-4二叉树一定是（）。
(2分)作者严冰单位浙大城市学院2-4答案正确(2 分)
2-5将二叉树B转换成树T后，B中结点的中序遍历次序就是T中结点的（）遍历次序。
(2分)作者严冰单位浙大城市学院2-5答案正确(2 分)
2-6一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。
(2分)作者严冰单位浙大城市学院2-6答案正确(2 分)
2-10若将一棵树 转化为对应的二叉树 ，则下列对 的遍历中，其遍历序列与 的后根遍历序列相同的是：
(2分)作者考研真题单位浙江大学2-10答案正确(2 分)
2-11对 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 的值是：
(3分)作者考研真题单位浙江大学2-11答案正确(3 分)
2-12以二叉链表作为二叉树的存储结构，在具有 个结点的二叉链表中（），空链域的个数为 __
(2分)作者魏宝刚单位浙江大学2-12答案正确(2 分)
2-13将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是：
父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系
(3分)作者DS课程组单位浙江大学2-13答案正确(3 分)
2-14设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为，和。则与森林F对应的二叉树根结点的右子树上的结点个数是：
(2分)作者DS课程组单位浙江大学2-14答案正确(2 分)
2-15设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
(2分)作者DS课程组单位临沂大学2-15答案正确(2 分)5-1下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。
typedef struct TreeNode *Tree;
struct TreeNode
{
int Key;
Tree Left;
Tree Right;
};
void Level_order ( Tree T )
{
Queue Q;
if ( !T ) return;
Q = CreateQueue( MaxElements );
Enqueue( T, Q );
while ( !IsEmpty( Q ) ){
T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
printf("%d ", T->Key);
if ( T->Left )
3分;
if ( 3分 )
3分;
}
}作者陈越单位浙江大学时间限制400 ms内存限制64 MB
5-3创建哈夫曼树。
#include<cstring>
#include<iostream>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
int i,min1=32767,min2=32767;
for(i=1;i<=len;i++)
{
if(HT[i].weight<min1&&HT[i].parent==0)
{
s2=s1;
min2=min1;
min1=HT[i].weight;
s1=i;
}
else if(HT[i].weight<min2&&HT[i].parent==0)
{ min2=HT[i].weight;
s2=i;
}
}
}
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
int m,s1,s2,i;
if(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=m;++i)
{ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }
for(i=1;i<=n;++i)
cin >> HT[i].weight;
for(i=n+1;i<=m;++i)
{
2分;
HT[s1].parent=2分;
HT[s2].parent=2分;
HT[i].lchild=2分;
HT[i].rchild=2分;
HT[i].weight=2分;
}
}
void print(HuffmanTree HT,int n)
{
for(int i=1;i<=2*n-1;i++)
cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
}
int main()
{
HuffmanTree HT;
int n;
cin >> n;
CreatHuffmanTree(HT,n);
print(HT,n);
return 0;
}输入样例：
第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n个整数(小于1000），表示每个节点表示的字符和权值。
5 1 5 2 7 10
输出样例：
输出2*n-1行，每行输出哈夫曼节点的权值、父节点编号、左右孩子节点编号。
1 6 0 0
5 7 0 0
2 6 0 0
7 8 0 0
10 9 0 0
3 7 1 3
8 8 6 2
15 9 4 7
25 0 5 8
作者王东单位贵州师范学院时间限制400 ms内存限制64 MB5-3答案正确(12 分)本题要求给定二叉树的高度。
函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};要求函数返回给定二叉树BT的高度值。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */int GetHeight( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0;
}/* 你的代码将被嵌在这里 */输出样例（对于图中给出的树）：
4
作者陈越单位浙江大学代码长度限制16 KB时间限制400 ms内存限制64 MBint GetHeight( BinTree BT ){
int a=0,b=0;
if(BT==NULL){
return 0;
}
a=GetHeight(BT->Left);
b=GetHeight(BT->Right);
if (a>b){
a++;
return a;
}
else{
b++;
return(b);
}
}
本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义：
void PreorderPrintLeaves( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */void PreorderPrintLeaves( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("Leaf nodes are:");
PreorderPrintLeaves(BT); printf("\n"); return 0;
}/* 你的代码将被嵌在这里 */输出样例（对于图中给出的树）：
Leaf nodes are: D E H I
作者陈越单位浙江大学代码长度限制16 KB时间限制400 ms内存限制64 MBvoid PreorderPrintLeaves( BinTree BT ){
if(BT!=NULL){
if(!BT->Left&&!BT->Right){
printf(" %c",BT->Data);
}
else{
PreorderPrintLeaves(BT->Left);
PreorderPrintLeaves(BT->Right);
}
}
}
存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。
具有10个叶结点的二叉树中，有9个度为2的结点。
某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。
某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。
二叉树可以用二叉链表存储，树无法用二叉链表存储。
将一棵树转成二叉树，根结点没有左子树。
对（）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。
哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。
树最适合于用来表示
在下述结论中，正确的是：
① 只有2个结点的树的度为1；
② 二叉树的度为2；
③ 二叉树的左右子树可任意交换；
④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。
二叉树一定是（）。
将二叉树B转换成树T后，B中结点的中序遍历次序就是T中结点的（）遍历次序。
一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。
若将一棵树 转化为对应的二叉树 ，则下列对 的遍历中，其遍历序列与 的后根遍历序列相同的是：
对 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 的值是：
以二叉链表作为二叉树的存储结构，在具有 个结点的二叉链表中（），空链域的个数为 __
将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是：
父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系
设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为，和。则与森林F对应的二叉树根结点的右子树上的结点个数是：
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。
typedef struct TreeNode *Tree;
struct TreeNode
{
int Key;
Tree Left;
Tree Right;
};
void Level_order ( Tree T )
{
Queue Q;
if ( !T ) return;
Q = CreateQueue( MaxElements );
Enqueue( T, Q );
while ( !IsEmpty( Q ) ){
T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
printf("%d ", T->Key);
if ( T->Left )
3分;
if ( 3分 )
3分;
}
}创建哈夫曼树。
#include<cstring>
#include<iostream>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
int i,min1=32767,min2=32767;
for(i=1;i<=len;i++)
{
if(HT[i].weight<min1&&HT[i].parent==0)
{
s2=s1;
min2=min1;
min1=HT[i].weight;
s1=i;
}
else if(HT[i].weight<min2&&HT[i].parent==0)
{ min2=HT[i].weight;
s2=i;
}
}
}
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
int m,s1,s2,i;
if(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=m;++i)
{ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }
for(i=1;i<=n;++i)
cin >> HT[i].weight;
for(i=n+1;i<=m;++i)
{
2分;
HT[s1].parent=2分;
HT[s2].parent=2分;
HT[i].lchild=2分;
HT[i].rchild=2分;
HT[i].weight=2分;
}
}
void print(HuffmanTree HT,int n)
{
for(int i=1;i<=2*n-1;i++)
cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
}
int main()
{
HuffmanTree HT;
int n;
cin >> n;
CreatHuffmanTree(HT,n);
print(HT,n);
return 0;
}输入样例：
第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n个整数(小于1000），表示每个节点表示的字符和权值。
5 1 5 2 7 10
输出样例：
输出2*n-1行，每行输出哈夫曼节点的权值、父节点编号、左右孩子节点编号。
1 6 0 0 5 7 0 0 2 6 0 0 7 8 0 0 10 9 0 0 3 7 1 3 8 8 6 2 15 9 4 7 25 0 5 8
本题要求给定二叉树的高度。
函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};要求函数返回给定二叉树BT的高度值。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */int GetHeight( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0;
}/* 你的代码将被嵌在这里 */输出样例（对于图中给出的树）：
4
int GetHeight( BinTree BT ){
int a=0,b=0;
if(BT==NULL){
return 0;
}
a=GetHeight(BT->Left);
b=GetHeight(BT->Right);
if (a>b){
a++;
return a;
}
else{
b++;
return(b);
}
}本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义：
void PreorderPrintLeaves( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */void PreorderPrintLeaves( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("Leaf nodes are:");
PreorderPrintLeaves(BT); printf("\n"); return 0;
}/* 你的代码将被嵌在这里 */输出样例（对于图中给出的树）：
Leaf nodes are: D E H I
void PreorderPrintLeaves( BinTree BT ){
if(BT!=NULL){
if(!BT->Left&&!BT->Right){
printf(" %c",BT->Data);
}
else{
PreorderPrintLeaves(BT->Left);
PreorderPrintLeaves(BT->Right);
}
}
}