下载文档原格式
数据结构（Java版）_郑州大学中国大学mooc课后章节答案期末考试题库2023年1.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列一定相同。
参考答案:错误2.在链队列中，即使不设置尾指针，也能进行入队操作。
参考答案:正确3.循环顺序队列和循环链队列都存在空间一处问题。
参考答案:错误4.直接选择排序的时间复杂度与关键字的初始排列无关。
参考答案:正确5.一个循环链表可以由给定的头指针或尾指针来唯一标识。
参考答案:正确6.所谓随机存取，就是通过首地址和元素的序号可以在O(1)的时间内找到指定的元素。
参考答案:正确7.快速排序在最坏情况下的时间复杂度是O(【图片】)。
参考答案:正确8.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）参考答案:正确9.在队列中存取数据元素的原则是（）。
参考答案:先进先出10.将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（）。
参考答案:142311.完全二叉树的存储结构通常采用顺序存储结构（）。
参考答案:正确12.在中序线索二叉树中，每一非空的线索均指向其祖先结点（）参考答案:正确13.二叉树中序线索化后，不存在空指针域（）参考答案:错误14.二叉树的层次遍历需要栈结构的支持。
参考答案:错误15.下列关于AOE网的叙述中，不正确的是（）参考答案:任何一个关键活动提前完成，那么整个工程将会提前完成16.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）参考答案:只有一个叶子结点17.引入二叉线索树的目的是（）参考答案:加快查找结点的前驱或后继的速度18.单源最短路径算法的时间复杂度为（）参考答案:O()19.对6个不同的数据元素进行直接插入排序，最多需要进行（）次关键字的比较。
参考答案:1520.完全二叉树中，若一个结点没有左孩子，则它必是树叶（）。
参考答案:正确21.已知循环队列存储在一维数组A[0【图片】n]中，且队列非空时front和rear分别指向队首元素和队尾元素。
一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。
本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。
虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。
【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。
6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。
6·4 线索二叉树1、线索二叉树的结点结构二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。
对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。
为了容易找到前驱和后继，有两种方法。
一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。
现将二叉树的结点结构重新定义如下：其中：ltag=0 时ltag=1 时lchild指向前驱；rtag=0 时rchild指向左子女；rtag=1 时rchild指向后继；以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，指向前驱和后继的指针叫线索，加上线索的二叉树叫线索二叉树，对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。
学习线索化时，有三点必须注意：一是何种“序”的线索化，是先序、中序还是后序；二是要“前驱”线索化、“后继”线索化还是“全”线索化（前驱后继都要）；三是只有空指针处才能加线索。
2、对二叉树进行中序线索化的算法bithptr *pre; /* 全程变量*/void INTHREAD(bithptr *p){if(p!=NULL){ INTHREAD(p->lchild); /* 左子树线索化*/if(p->lchild==NULL) { p->ltag=1;p->lchild=pre;}if(p->rchild==NULL) p->rtag=1;if(pre!=NULL && pre->rtag==1) pre->rchild=p;pre=p; /* 前驱指向当前结点*/INTHREAD(p->rchild); /* 右子树线索化*/}3、在线索二叉树上查找前驱和后继（1）中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。
若x是二叉树中序线索树中一个有左孩子的结点1二叉树中序线索树二叉树中序线索树（Threaded Binary Tree）是指用线索把二叉树的空缺指针打上标记，使其成为双链表，以便让二叉树具有更强的访问能力，同时节省存储空间。
2特点线索标识：对于空链接而言，我们给其添加一个特殊标记，来标识空链接，用来控制遍历时循环跳出。
数据结构：在线索树中，将每一个节点结构体特殊定义为线索化节点结构体，用tag标记左右孩子的指针是否为空，及其空时的处理方式。
3操作中序线索树的操作主要是遍历二叉树，即中序遍历和前序遍历。
中序遍历：中序遍历的核心在于只有当结点的左子树遍历完了才能继续遍历右子树，所以用线索树以后，其中序遍历可以沿所有指向前驱结点的线索一路返回根结点，即访问根结点之前访问它的前驱，然后从根结点出发，依次访问所有后继结点。
前序遍历：前序遍历的核心在于无论根节点在哪里，都要先访问它，然后访问左孩子，最后访问右孩子。
因此采用线索树以后，只要沿着指向父结点的线索一路回退根结点，即可访问所有的先序顺序访问。
4具体应用二叉树中序线索树和树结构在很多应用程序中都有广泛的应用，其中最常用的两个应用分别是树查询和语法分析。
树查询：用线索树具有快速查询的特性，可以大大提高查询的速度，尤其是在复杂的树结构中使用线索树，查询的速度会更快。
语法分析：用于自动处理语言，是对源代码中的符号进行分析的过程，以构建出一棵源程序的语法树节点，可以用线索树这种数据结构来实现快速的访问和查找。
5若x是二叉树中序线索树中一个有左孩子的结点若节点x具有左孩子，那么该节点x通过线索把左孩子结点加上标记，以便于后续遍历，当访问x时，可通过线索遍历该左节点，并与其他节点信息进行交互，而不必从根结点开始重复遍历。
同时，如果该节点x的右节点不是叶子结点，那么可以借助线索快速找到x的右节点，不需要通过先找到x的左节点才能找到右节点。
简述二叉树的五种形态二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。
根据节点的分布情况，二叉树可以分为五种形态，分别是满二叉树、完全二叉树、平衡二叉树、搜索二叉树和线索二叉树。
一、满二叉树满二叉树是指除了叶子节点外，每个节点都有两个子节点的二叉树。
也就是说，满二叉树的所有层都是满的，并且最后一层的叶子节点都靠左排列。
满二叉树的节点数可以通过公式计算得到，假设树的高度为h，则节点数为2^h - 1。
满二叉树的特点是结构简单，查找速度快。
在满二叉树中，任意两个节点的路径长度都相同。
二、完全二叉树完全二叉树是指除了最后一层之外，其他层都是满的，并且最后一层的叶子节点都靠左排列的二叉树。
完全二叉树的特点是节点数较少，结构相对简单。
完全二叉树通常用数组来表示，因为它的节点之间的关系可以通过数组的下标来表示。
在完全二叉树中，任意一个节点的左子节点的下标为2i，右子节点的下标为2i+1。
三、平衡二叉树平衡二叉树是指左右子树的高度差不超过1的二叉树。
平衡二叉树的特点是查找、插入和删除的时间复杂度都为O(logn)，其中n是节点的数量。
平衡二叉树的高度可以通过节点的平衡因子来计算，平衡因子定义为左子树的高度减去右子树的高度。
平衡因子的取值范围为-1、0和1，当平衡因子的绝对值大于1时，需要通过旋转操作来调整树的平衡性。
四、搜索二叉树搜索二叉树，也称为二叉搜索树或排序二叉树，是一种特殊的二叉树。
它的特点是对于树中的任意一个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。
搜索二叉树的中序遍历结果是一个递增的有序序列。
搜索二叉树的特点是可以快速地查找某个节点，时间复杂度为O(logn)，其中n是节点的数量。
但是，如果搜索二叉树不平衡，即左子树或右子树过深，则会导致查找的时间复杂度退化为O(n)。
五、线索二叉树线索二叉树是对二叉树进行了优化的数据结构，它通过添加指向前驱和后继节点的线索，使得遍历操作更加高效。
画出中序线索二叉树简单例题
假设有一个二叉树如下：
A
/ \
B C
/ \ / \
D E F G
根据中序遍历的顺序，节点的访问顺序应该为 D -> B -> E -> A -> F -> C -> G。
我们可以通过添加线索化标记，将每个节点的左右空指针改为指向其前驱和后继节点。
这样，递归遍历中序线索二叉树时不再需要通过递归调用访问左右子树，而可以直接跳转到前驱或后继节点。
线索化后的二叉树如下：
D
\
B
/ \
E A
\
F
/ \
G C
在中序线索二叉树中，对于每个节点，其指向前驱节点的指针称为"前驱线索"，指向后继节点
的指针称为"后继线索"。
这样，我们可以通过线索化标记快速找到任意节点的前驱和后继节点，而不需要遍历整棵树。
例如，节点 A 的后继节点为 F，前驱节点为空。
节点 C 的后继节点为尚未线索化的节点 G，
前驱节点为节点 A。
节点 D 的后继节点为节点 B，前驱节点为尚未线索化的节点 E。
通过线索化，我们可以利用中序线索二叉树实现快速查找任意节点的前驱和后继节点，而不需要进行递归遍历。
这样，我们可以在时间复杂度为O(1) 的情况下完成前驱和后继节点的查找，大大提高了效率。
总结起来，中序线索二叉树可以在原有二叉树的基础上添加线索化标记，从而实现快速查找任意节点的前驱和后继节点。
这一特性在某些需要频繁查找节点前驱和后继的应用场景中具有重要意义。
中序线索化二叉树数据结构.当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指针，所以从任一结点出发只能直接找到该结点的左、右孩子。
在一般情况下靠它无法直接找到该结点在某种遍历次序下的前驱和后继结点。
如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。
与此同时，我们可以证明：在n个结点的二叉链表中含有n+1个空指针。
因为含n个结点的二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有2n-(n-1)=n+1个空指针。
因此，可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。
这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
为了区分一个结点的指针是指向其孩子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。
这样，线索二叉树结点类型定义为：LchildLtagDataRtagRchild其中：1. Ltag=0时，表示Lchild指向该结点的左孩子；2. Ltag=1时，表示Lchild指向该结点的线性前驱结点；3. Rtag=0时，表示Rchild指向该结点的右孩子；4. Rtag=1时，表示Rchild指向该结点的线性后继结点；以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树；对二叉树以某种次序遍历将其变为线索二叉树的过程叫做线索化。
中序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索。
例如有如上图所示二叉树，则中序遍历的顺序是：O / J * I + H A G【参考程序】#include <stdio.h>#include <malloc.h>typedef enum{Link,Thread} PointerTag; /*指针标志*/typedef char DataType;typedef struct BiThreTree{ /*定义结点元素*/PointerTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild;}BiThreTree;BiThreTree *pre; /*全局变量，用于二叉树的线索化*/ BiThreTree *CreateTree() /*按前序输入建立二叉树*/{BiThreTree *T;DataType ch;scanf("%c",&ch);if(ch==’#’)T=NULL;else{T=(BiThreTree *)malloc(sizeof(BiThreTree));T->data=ch;T->LTag=Link; /*初始化时指针标志均为Link*/ T->RTag=Link;T->lchild=CreateTree();T->rchild=CreateTree();}return T;}void InThread(BiThreTree *T){BiThreTree *p;p=T;if(p){InThread(p->lchild);if(!p->lchild){ p->LTag=Thread;p->lchild=pre;}if(!pre->rchild){ pre->RTag=Thread;pre->rchild=p;}pre=p;InThread(p->rchild);}}BiThreTree *InOrderThrTree(BiThreTree *T) /*中序线索化二叉树*/ {BiThreTree *Thre; /*Thre为头结点的指针*/ Thre=(BiThreTree *)malloc(sizeof(BiThreTree));Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->RTag=Thread;pre->rchild=Thre;Thre->rchild=pre;return Thre;}void InThrTravel(BiThreTree *Thre) /*中序遍历二叉树*/{BiThreTree *p;p=Thre->lchild;while(p!=Thre) /*指针回指向头结点时结束*/ {while(p->LTag==Link)p=p->lchild;printf("%4c",p->data);while(p->RTag==Thread&&p->rchild!=Thre){p=p->rchild;printf("%4c",p->data);}p=p->rchild;}}void main(){BiThreTree *T,*Thre;printf(“PreOrder Create Binary Tree:\n”);T=CreateTree();Thre=InOrderThrTree(T);printf(“InOrder Traverse Binary Tree:\n”);InThrTravel(Thre);system("pause");}【调试举例】（1）建立二叉树时，按先序遍历方式输入：“ABD##EH##I##CF##G##”，其中“#”表示空指针。
（2）建立的二叉树为： AB CD E F GH I（3）程序输出为中序遍历线索化二叉树的结果：DBHEIAFCG已知A、B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中出现又在C表中出现的元素。
【实验步骤】1.试对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。
在实验报告中分析你的算法的时间复杂度。
2.A表中要删除的元素实际上就是在三个表中都存在的元素。
注意这三个线性表都是递增有序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。
3.改用单链表作为存储结构编写算法，请释放A表中无用的结点空间，并上机编程实现。
【算法思想】先从B和C中找出共有元素same，再从A中从当前位置开始，凡小于same的元素均保留，等于same的就跳过，大于same时就再找下一个same。
【顺序存储结构算法描述】void SqList_Delete(SqList&A, SqList B, SqList C){i=0;j=0;m=0;/*i指示A中元素原来的位置，m为移动后的位置*/while(i<A.length&&j<B.length&&k<C.length){if(B.elem[j]<C.elem[k]) j++;else if(B.elem[j]>C.elem[k])k++;else{same= B.elem[j];/*找到了相同元素same*/while(B.elem[j]==same)j++;while(C.elem[k])==same)k++;/*j,k后移到新的元素*/while(i<A.length&&A.elem[i]<same)A.elem[m++]=A.elem[i++];/*需要保留的元素移动到新位置*/while( i<A.length&&A.elem[i]==same)i++;}/*else*/}/*while*/while(i<A.length)A.elem[m++]=A.elem[i++];/*A的剩余元素重新存储*/A.length=m;}/*SqList_Delete*/【顺序存储结构参考程序】#include<stdio.h>main(){#define N 3/*宏定义,代表数组维数*/#define M 4#define T 5int i,j,k,r,m,same;/*定义变量分别指向数组a,b,c*/int a[N],b[M],c[T];printf(“please input numbers:\n”);for (i=0;i<N;i++) scanf("%d",&a[i]);for (j=0;j<M;j++) scanf("%d",&b[j]);for (k=0;k<T;k++) scanf("%d",&c[k]);i=0;j=0;m=0;k=0;/*分别赋值为0，即指向数组的第一元素*/ while(i<N&&j<M&&k<T){if(b[j]<c[k])j++;else if(b[j]>c[k]) k++;else{same=b[j];while(b[j]==same)j++;while(c[k]==same)k++;while(i<N&&a[i]<same)a[m++]=a[i++];while(i<N&&a[i]==same) i++;}}while(i<N)a[m++]=a[i++];printf("a[%d]={",m);/*输出删除元素后的数组a/*for (r=0;r<m-1;r++)printf("%d,",a[r]);printf("%d",a[m-1]);printf("}\n");return;}【程序调试】程序运行是屏幕显示：please input numbers: 此时输入三组测试数据，数据间用空格隔开：2 3 4回车3 4 5 6 回车4 5 6 7 8 回车程序输出结果：a[3]={2,3}，即删除了数组a中即在b和c中都出现的元素。
【单链表存储结构参考程序】# include <stdio.h># include <stdlib.h>Typedef struct LNode{int data;struct LNode *next;}Lnode,*LinkList;/*定义链表节点的结构*/void main ( ){/*功能：建立单链表A,B,C，并且删除A中均在B和C中出现的数据。
