东北大学计算机初试历年二叉树算法题目及解答

/*------------------------------------------2003数据结构部分-------------------------------------------*/ 二、已知f为单链表的表头指针，链表中存储的都是整型数据，试设计算法将此链表的结点按照递增次序进行就地排序。

void InsertSort_L(Linklist &La){//用直接插入排序使链表递增有序if(La->next){//链表不空p = La->next->next;La->next->next = Null;while(p != NULL){r = p->next; //暂存p的后继q = La;while(q->next && q->next->data < p->data)q = q->next; //查找插入位置p->next = q->next; //插入q->next = p;p = r;}//while}//if}三、给出中序线索二叉树的结点结构，试编写在不使用栈和递归的情况下先序编历中序线索二叉树的算法.void InTraveseThr(BitTree thrt){//遍历中序线索二叉树p = thrt->lchild; //p指二叉树根结点while (p!=thrt){while(p->Ltag == 0)p = p->lchild;printf(p->data);while(p->rtag == 1 && p->rchild != thrt){p = p->rchild;printf(p->data);}//whilep = p->rchild;}//while}//InTraversethr四、设关键字是一个由26个小写字母组成的字符串，哈希表的长度为26。

计算机专业基础综合（树与二叉树）-试卷2(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________ 解析：2.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。

（分数：2.00）A.10B.11C.9D.7 √解析：解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n 0，由此可以得出：n 0=1×4+2×1+3+4+1-(4+1+1+1)=14-7=7。

3.用下列元素序列(22，8，62，35，48)构造平衡二又树，当插入( )时，会出现不平衡的现象。

（分数：2.00）A.22B.35C.48 √D.6248后，首次出现不平衡子树，虚线框内即为最小不平衡子树。

4.下面的算法实现了将二叉树中每一个结点的左右子树互换。

addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。

typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p->rchild；p一>rChild=p一>lchild；( (1) )=q；if(p->lchild) ( (2) )： if(p->rchild)addQ(Q，p->rchild)： } }}（分数：2.00）A.p一>lchild，delQ(Q，p->lchild)B.p->rchild，delQ(Q，p->lchild)C.p一>lchild，addQ(Q，p->lchild) √D.p->rchild，addQ(Q，p->lchild)解析：5.已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。

[1996]设t为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。

int swithLRChild(BiTree *t){ BiTree *stack[100] = {0};int stack_length = 0;if (NULL == t){return 0;}stack[stack_length++] = t;while (stack_length > 0){//pop stackBiTree *node = stack[stack_length - 1];stack_length -= 1;BiTree *temp = node->lchild;node->lchild = node->rchild; node->rchild = temp;if (NULL != node->rchild){ stack[stack_length++] = node->rchild;}if (NULL != node->lchild){stack[stack_length++] = node->lchild;}}return 1;}[1998]一棵高度为K且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t中，试设计删除树中序号为i且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树（不一定是完全二叉树）的算法。

//存数据的位置是从1的索引开始的，避免需要访问索引为0的空间，避免需要频繁的索引转换void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i){//因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了int del_node_index = 2*i;if (2*del_node_index + 1 >= *last_index){//左孩子只存在左子树sorted_bitree[i] = sorted_bitree[del_node_index];while (del_node_index*2 <= *last_index){//后面的位置都往上移动sorted_bitree[del_node_index] = sorted_bitree[2*del_node_index];del_node_index *= 2;}sorted_bitree[del_node_index] = -1;printf("last_index:%d\n", *last_index);}else{//移动到左孩子的右孩子del_node_index = del_node_index*2 + 1;while (2*del_node_index <= *last_index){del_node_index *= 2;}//因为叶子节点，所以不需要移动printf("r:%d rp:%d\n", sorted_bitree[i], sorted_bitree[del_node_index]);sorted_bitree[0] = sorted_bitree[del_node_index];sorted_bitree[del_node_index] = -1;}}[2002]对以二叉链表存储的非空二叉树，从右向左依次释放所有叶子结点，释放的同时，把结点值存放到一个向量中。

二叉树的遍历题目及答案1. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。

因而二叉树的遍历次序有六种。

最常用的是三种：前序法（即按N L R次序），后序法（即按L R N 次序）和中序法（也称对称序法，即按L N R次序）。

这三种方法相互之间有关联。

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。

解：法1：先由已知条件画图，再后序遍历得到结果；法2：不画图也能快速得出后序序列，只要找到根的位置特征。

由前序先确定root，由中序先确定左子树。

例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。

如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。

如法对B的左右子树同样处理，则问题得解。

2.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。

然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。

将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

3、当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是A. BDEAGFHCB. EBDGACFHC. HGFEDCBAD. HFGDEABC答案：B4. 已知一棵二叉树的前序遍历为ABDECF，中序遍历为DBEAFC，则对该树进行后序遍历得到的序列为______。

A．DEBAFCB．DEFBCAC．DEBCFAD．DEBFCA[解析] 由二叉树前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。

二叉树算法题
题目一：二叉树的深度
给定一个二叉树，找出其最大深度。

示例：
输入：
# 定义二叉树节点
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 创建二叉树
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
输出：
4
解释：二叉树的深度为4，分别是 [3], [9, 20], [15, 7] 和 []。

提示：递归深度优先搜索 (DFS) 是一个有效的解决方案。

对于每个节点，我们可以递归地计算其左子树和右子树的深度，然后返回最大的深度。

为了避免重复计算，我们可以使用一个队列来存储已访问的节点。

在计算深度的过程中，我们需要跟踪当前的深度。

当我们到达一个节点的深度时，我们就可以从队列中删除它，因为我们不需要再次计算它。

为了避免进入无限循环，我们需要在算法中使用一个变量来记录访问过的节点数量，如果超过了树中的节点数量，我们可以提前返回结果。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编10(总分68, 做题时间90分钟)1. 单项选择题1.先序序列为a，b，c，d的不同二叉树的个数是( )。

【2015年全国试题2(2分)】SSS_SINGLE_SELA 13B 14C 15D 16分值: 2答案:C解析：先序序列为1，2，3，…，n的不同的二叉树的数目是1／(n+1)((2n)!／(n!*n!))。

2.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是( )。

【201 5年全国试题3(2分)】SSS_SINGLE_SELA 24，10，5和24，10，7B 24，10，5和24，12，7C 24，10，10和24，14，11D 24，10，5和24，14，6分值: 2答案:D解析：A的错误在于若路径上有两个10，叶子5应和另一个权值5组成左右子女，7和3组成左右子女，显然不符合哈夫曼的构造规则(应该3和5组成左右子女构造双亲结点)；若路径上只有一个10，5和7并非其左右子女。

B的错误在于双亲10和双亲12不可能构造双亲24。

C的错误是路径上不可能有相同权值10的结点。

D是正确的，双亲10的另一个子女是5，双亲14的另一个子女是8，而双亲10和双亲14恰是双亲24的左右子女。

3.树是一种逻辑关系，表示数据元素之间存在的关系为( )。

【北京交通大学2007(2分)】SSS_SINGLE_SELA 集合关系B 一对一关系C 一对多关系D 多对多关系分值: 2答案:C4.下列判断，( )是正确的。

【华南理工大学2005一、1(2分)】SSS_SINGLE_SELA 二叉树就是度为2的树B 二叉树中不存在度大于2的结点C 二叉树是有序树D 二叉树的每个结点的度都为2分值: 2答案:B解析：二叉树与树是两个不同的概念。

相同点是二者都是树形结构，不同点有三：一是二叉树的度至多是2，树无此限制；二是二叉树的子树有左右子树之分，只有一棵子树时，也必须区分是左子树还是右子树，树不必这样；三是二叉树允许为空，树不准为空，但是多数教科书认为树可以为空，否则空二叉树无法转换成空树，本题第一问有二义性。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编4(总分：74.00，做题时间：90分钟)一、综合题(总题数：35，分数：74.00)1.(1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。

【东北大学1999六(4分)】【东南大学2000一、4(6分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右子树”，后序遍历顺序是“左子树一右子树一根”，根据以上原则，本题解答如下：1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。

3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。

4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。

(2)由中序序列DBEAFIHCG和后序序列DEBHIFGCA)解析：2.分别给出满足下列条件的二叉树。

(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。

【四川大学2004】【烟台大学2007四、2(8分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：空二叉树满足题目要求，若二叉树非空，则(1)前序和中序遍历结果相同的二叉树是任一结点无左子女； (2)前序和中序遍历结果不相同而是相反的二叉树是任一结点无右子女； (3)中序和后序遍历结果相同的二叉树是任一结点无右子女； (4)前序和后序遍历结果相同的二叉树是只有根结点。

东北大学智慧树知到“计算机科学与技术”《数据结构Ⅱ》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为A.左子树的叶子结点B.左子树的分支结点C.右子树的叶子结点D.右子树的分支结点2.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是()。

A.分块查找B.顺序查找C.二分查找D.散列查找3.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是()。

A.head (tail (LS))B.tail (head (LS))C.head (tail (head (tail (LS))))D.head (tail (tail (head (LS))))4.在待排关键字序列基本有序的前提下，效率最高的排序方法是()。

A.直接插入排序B.快速排序C.直接选择排序D.归并排序5.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，(a1n,a2n,…,ann)),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是A.tail (head (tail (L)))B.head (tail (head (L)))C.head (head (tail (L)))D.head (head(head(L)))6.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。

若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为()。

A.21B.23C.41D.627.判断两个串大小的基本准则是()。

A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小8.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.49.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。