n个叶子节点的哈夫曼树 节点总数

一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。

（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。

（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。

（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。

（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。

下列选项中，（）就是不稳定的排序方法。

（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。

（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。

（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。

（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。

数据结构复习答案一、选择填空1.下面关于线性表的叙述中，错误的是哪一个？（）A）线性表采用顺序存储，必须占用一片连续的存储单元。

√B）线性表采用顺序存储，便于进行插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用链接存储，便于插入和删除操作。

2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

√A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表3.链表不具有的特点是（）。

A）插入、删除不需要移动元素√B）可随机访问任一元素C）不必事先估计存储空间D）所需空间与线性长度成正比4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A）O(0) B）O(1) √C）O(n) D）O(n2)5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。

A）O(i) B）O(1) √C）O(n) D）O(i-1)6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A）head==NULL B）head→next==NULL√C）head→next==head D）head!=NULL7.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

A）p->next=s;s->next=p->next; √B）s->next=p->next;p->next=s;C）p->next=s;p->next=s->next; D）p->next=s->next;p->next=s;8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。

√A）p->next=p->next->next B）p=p->nextC）p=p->next->next D）p->next=p9.( )又称为FIFO表；( )又称为FILO表。

数据结构练习第六章树一、选择题1.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-13.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A. 2m-1B. 2mC. 2m+1D. 4m4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A. BADCB. BCDAC. CDABD. CBDA5.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A. 9B. 10C. 11D. 126．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

A. 2k-1 B .2k C. 2k-1 D. 2k-17．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A. N0=N1+1 B. N=Nl+N2C. N=N2+1 D. N=2N1+l8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N=（）。

A. Nl +N2+……+Nm B. l+N2+2N3+3N4+……+(m-1)NmC. N2+2N3+3N4+……+(m-1)Nm D. 2Nl+3N2+……+(m+1)Nm9．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

A. 20B. 30C. 40D. 4510．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。

A. 3B. 4C. 5D. 612．深度为k的完全二叉树中最少有（）个结点。

Ch6树一、选择题：1.下列关于哈夫曼树的叙述，错误的是(C)。

A.哈夫曼树根结点的权值等于所有叶结点权值之和。

B.具有n个叶结点的哈夫曼树共有2n-1个结点。

C.哈夫曼树是一棵二叉树，因此它的结点的度可以为0, 1, 2。

D.哈夫曼树是带权路径长度最短的二叉树。

2.由3个结点可以构成多少棵不同形态的二叉树(C)。

A. 3B. 4C. 5D. 6(3.如果一棵二叉树结点的前序序列是A, B, C,后序序列是C, B, A,则该二叉树结点的中序序列是(D )。

A. A, B, CB. A, C, BC. B, C, AD.不能确定5.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说滔B )A.正确B.错误若结点有左子树，则令其Ichild指针指示其左孩子；若结点没有左子树，则令其Ichild指针指示其前驱;若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。

)6.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说/A )。

A.正确B.错误7.对一棵70个结点的完全二叉树，它有(A )个叶子结点。

A.35B.40C.30D.44⑥® © ©&13.设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树所包含的结点数至少为(B )。

A . 2h B . 2h-1 C . 2h+1 D . h+1＞与6房.山63个空点।引个结.辽8.设一棵二叉树中，度为1的结点数为9,则该二叉树的叶子结点的数目为(D )。

A . 10 B . 11C . 12D .不确定 n 0=n 2+19 .假定根结点的层次为0,含有15个结点的二叉树最小高度为(A )。

A . 3B . 4C . 5D . 6) 假定根结点的层次为1,含有15个结点的二叉树最小高度为410 .若一棵二叉树中，度为2的结点数为9,该二叉树的叶子结点的数目为(A )。

第 5 章树和二叉树1970-01-01第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

计算机学科专业基础综合数据结构-树与二叉树(二)(总分：100.00，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：44，分数：44.00)1.在下面关于树的相关概念的叙述中，正确的是______。

∙ A.只有一个结点的二叉树的度为1∙ B.二叉树的度一定为2∙ C.二叉树的左右子树可任意交换∙ D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树（分数：1.00）A.B.C.D. √解析：只有一个结点的二叉树的度为零。

二叉树的度可以为0、1、2；二叉树的左右子树不能任意交换。

2.已知一算术表达式的中缀形式为A+B+C-D/E，后缀形式为ABC*+DE/-，其前缀形式为______。

∙ A.-A+B*C/DE∙ B.-A+B*CD/E∙ C.-+*ABC/DE∙ D.-+A*BC/DE（分数：1.00）A.B.C.D. √解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)-D/E，前缀表达式：-+A*BC/DE。

3.算术表达式a+b*(c+d/e)转为后缀表达式后为______。

∙ A.ab+cde/*∙ B.abcde/+*+∙ C.abcde/*++∙ D.abcde*/++（分数：1.00）A.B. √C.D.解析：根据表达式a+b*(c+d/e)可知其后缀表达式为abcde/+*+。

4.某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是______。

∙ A.JLKMNOI∙ B.LKNJOMI∙ C.LKJNOMI∙ D.LKNOJMI（分数：1.00）A.B.C. √D.解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。

[*] 由此图可以确认后序遍历的序列为LKJNOMI。

5.设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是______。

一、概念题（每空0.5分，共28分）1．树（及一切树形结构）是一种“________”结构。

在树上，________结点没有直接前趋。

对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2．由３个结点所构成的二叉树有种形态。

3．一棵深度为6的满二叉树有个分支结点和个叶子。

4．一棵具有２５７个结点的完全二叉树，它的深度为。

5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。

6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。

满二叉树也是______二叉树，但反之不然。

8．设一棵完全二叉树有700个结点，则共有个叶子结点。

9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。

11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。

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

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

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

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。

12.中序遍历的递归算法平均空间复杂度为。

13.二叉树通常有______存储结构和______存储结构两类存储结构。

14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

1、在一棵具有5层的满二叉树中结点总数为（A）。

A) 31 B）32C）33 D）16(2^n) - 1,N = 2k-1(N总结点数，k层数)2、串的逻辑结构与（A）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

P713、下列序列中，执行第一趟快速排序后得到的序列是（A）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]左大右小4、n个顶点的强连通图至少有（C）条边。

A）n B）n+1 C）n-1 D）n(n-1)单节点除外，so,-15、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A）。

A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p无限删除6、对下图V4的度为（C）。

A）1 B）2 C）3 D）4v1v2 v3v47、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）。

A）4 B）5C）6 D）7图1-7设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，度为3的个数n3树中结点总数n0+ n1 + n2 + n3，所有边的数量为0 * n0 + 1 * n1 + 2 * n2 + 3 * n3树中结点比边多1个，合并这两个式子就可以得到：n0 = 1 + n2 + 2 * n3 8、在数据结构中，从逻辑上可以把数据结构分为（C）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构数据的逻辑结构分两大类：线性结构和非线性结构数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法(hash存储)9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（B）。

试卷一一、简答题：（每小题3分，共15分）1.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？2.比较顺序表与单链表的优缺点。

3.请写出栈的链式存储结构的类型定义。

4.在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。

5.简述参数传递的主要方式及其特点。

二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。

( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi 到Vj的路径。

( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。

( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。

( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。

( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。

三、单项选择题：(每小题1分，共5分)1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:A) 顺序表B) 用头指针表示的单循环链表C) 用尾指针表示的单循环链表D) 单链表2．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X)C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y, R, X)3．下面是三个关于有向图运算的叙述：（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A) 只有（1）B) （1）和（2）C) 都正确D) 都不正确4．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为:A) 4 B) 5 C) 6 D) 75. 以下关于广义表的叙述中,正确的是：A) 广义表是由0个或多个单元素或子表构成的有限序列B) 广义表至少有一个元素是子表C) 广义表不能递归定义D) 广义表不能为空表四、填空题：(每小题2分,共 20分)1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对1≤k≤101, 若A[k]是非叶结点, 则k的最小值是: ，k的最大值是: 。

《数据结构》习题一、单项选择题1．对矩阵进行压缩存储是为了（）A．节省存储空间 B．提高运算速度 C．便于运算 D．方便存储2．链式栈与顺序栈相比，一个比较明显的优点是（）A．插入操作更加方便 B．通常不会出现栈满的情况C．不会出现栈空的情况 D．删除操作更加方便3．设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（）A．3，4，1，2，5 B．1，2，3，4，5 C．2，3，4，1，5 D．5，4，3，2，14.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（）A．4,3,2,1,5,6 B．3,6,2,1,5,4 C．1,2,3,5,4,6 D．5,4,1,3,2,65．设输入序列为A，B，C，D。

借助一个栈可以得到的输出序列是（）A．A，C，D，B B．C，A，D，B C．D，C，A，B D．D，A，B，C6．将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（）A．34 B．35 C．36 D．无法确定7．已知完全二叉树有80个结点，则该二叉树有（）个度为1的结点。

A．0 B．1 C．2 D．不确定8．任何一个无向连通图的最小生成树（）A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在9．设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为（）A． O(n) B． O(n+e) C． O(n2) D． O(n3)10．用n个键值构造一棵二叉排序树，最低高度为（）A．n/2 B．n C．[㏒2n] D．[㏒2n]+111．如果以链表作为栈的存储结构，则执行出栈操作时（）A．必须判断栈是否满 B．必须判断栈是否空C．判断栈元素的类型 D．对栈不作任何判断12．设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）A．front=front+1 B．front=(front+1)%mC．rear=(rear+1)%m D．front=(front+1)%(m+1)13．线性表的长度是指（）A．顺序存储方式下数组所占用的元素个数 B．链表存储方式下的结点个数C．表中的元素个数 D．所能存储的最大的结点个数14．设有一个无向图G＝(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是（） A．G’为G的子图 B．G’为G的连通分量C．G’为G的极小连通子图且V’=V D．G’是G的一个无环子图15．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）A．一定都是同义词 B．一定都不是同义词C．都相同 D．不一定都是同义词16．在有序表A[20]中按二分查找方法查找A[13]依次比较的元素的下标是（）A．9，14，12，13 B．9，15，12，13C．9，14，11，12，13 D．10，15，12，1317．栈和队列都是（）A．顺序存储的线性表 B．链式存储的线性表C．限制的线性表 D．限制存储点的非线性结构18．向顺序栈中压入新元素时，应当（）A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行19．若树的先序序列和中序序列正好相同，则一定是一棵（）的二叉树。

数据结构C++考试题及答案数据结构试题⼀⼀、单项选择题（每⼩题3分，共30分）1、在有n 个叶⼦结点的哈夫曼树中，其结点总数为（）。

A、不确定B、2nC、2n+1D、2n-12、下列序列中，（）是执⾏第⼀趟快速排序得到的序列（排序的关键字类型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc]B、[cd，eb，ax，da]ff[ha，gc，bb]C、[gc，ax，eb，cd，bb]ff[da，ha]D、[ax，bb，cd，da]ff[eb，gc，ha]3、若线性表最常⽤的操作是存取第i 个元素及其前驱的值，则采⽤（）存储⽅式节省时间。

A、单链表B、双链表C、单循环链表D、顺序表4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。

A、堆排序B、冒泡排序C、直接选择排序D、快序排序5、某⼆叉树的先序序列和后序序列正好相反，则该⼆叉树⼀定是（）的⼆叉树。

A、空或只有⼀个结点B、⾼度等于其结点数C、任意结点⽆左孩⼦D、任意结点⽆右孩⼦6、下列排序算法中，某⼀趟结束后未必能选出⼀个元素放在其最终位置上的是（）。

A、堆排序B、冒泡排序C、直接选择排序D、快序排序7、快速排序算法在最好情况下的时间复杂度为（）。

A、O(n)B、O(n 2 )C、O(nlogn)D、O(logn)8、已知数据表A中每个元素距其最终位置不远，则采⽤（）排序算法最省时间。

A、堆排序B、插⼊排序C、直接选择排序D、快序排序9、带权有向图G⽤邻接矩阵A存储，则顶点i的⼊度为A中（）。

A、第i⾏⾮∞的元素之和B、第i列⾮∞的元素之和C、第i⾏⾮∞且⾮0的元素之和D、第i列⾮∞且⾮0的元素之和10、在有n个结点且为完全⼆叉树的⼆叉排序树中查找⼀个键值，其平均⽐较次数的数量级为（）。

A、O(n)B、O(n 2 )C、O(nlogn)D、O(logn)⼆、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每⼩题１分，共10分）1.对任意⼀个图，从它的某个顶点出发进⾏⼀次深度优先或⼴度优先搜索遍历可访问该图的每个顶点。

20226月数据结构习题1、一棵二叉树没有单分支结点，有6个叶结点，则该树总共有____11____个结点。

2、数据结构的实质就是研究数据的、以及定义在逻辑结构上所进行的一组5、一个图的_________表示法是唯一的，而___________表示法是不唯一的。

6、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有个叶子结点。

7、G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是。

8、结构中的数据元素存在多对多的关系称为_____图状（网状）___结构。

9、按照二叉树的递归定义，对二叉树遍历的常用算法有先序；中序；后序三种。

10、在具有n个单元的循环队列中，队满时共有__________个元素。

11、3个结点可构成棵不同形态的树。

12、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为14、根据数据元素间关系的不同特性，通常可分为集合、线性、树形、图状四类基本结构。

15、数据结构中的数据元素存在一对多的关系称为__树形_____结构。

16、要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。

则比较的次数和算法的时间复杂度分别为__n-1和O(n)__17、顺序存储的栈中，在作进栈运算时,应先判别栈是否,在进行出栈运算时应先判别栈是否。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为。

18、在带头结点的循环链表h中，判断表空的条件是19、具有n个顶点的有向完全图的弧数为_________。

20、数据的存储结构被分为_________和_________。

21、设有一顺序栈S，元素1,2,3,4,5,6依次进栈，如果6个元素出栈的顺序是2,3,4,6,5,1,则栈的容量至少应该是________。

22、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

第6章树和二叉树一、选择题（每小题1分，共10分）1.以下数据结构中，（ A ）是非线性数据结构。

A.树B.线性表C.队列D.栈2.在一棵二叉树中第五层上的结点数最多为（ B ）。

A.8B.15C.16D.323. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。

A. CBEFDAB. FEDCBAC. CBEDFAD. 不定4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。

A.9B.11C.15D.不确定5.给定二叉树如图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ）。

A. LRNB. NRLC. RLND. RNL6.在下列存储形式中，哪一个不是树的存储形式？（ D ）A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储表示法7.有n个叶子的哈夫曼树的结点总数为（D ）。

A．不确定B．2n C．2n+1 D．2n-18.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ）A.2iB.2i+1C.2i-1D.i+19. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。

A.23B.37C.44D.4610.一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）。

A. +1B. log2n+1C.D. log2n-111.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。

A.36B.60C.48D.5312.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。

A. 24B. 71C. 48D. 5313.具有35个结点的完全二叉树的深度为( B )。

数据结构试卷试1一、解释下列术语（每小题4分，共20分）1. 头指针2. 二叉排序树的定义3. 头结点4. 数据的逻辑结构5. 排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素A.n-iB. n-i+1C. n-i-1D.i2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列A.1,2,3,4B.2,3,4,1C. 4,3,2,1D.3,4, 1,23. 对二叉排序进行( )遍历可以得到结点的排序序列A.前序B.中序C. 后序D.按层次4．有64个结点的完全二叉树的深度为（）。

A 8B 7C 6D 55．折半查找法的时间复杂度是( )A.(n2)B.O(n)C. O(n㏒n)D. O(㏒n)6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。

A 1140B 1145C 1120D 11257. 有n个叶子结点的哈夫曼树的结点总数为（）。

A 不确定B 2nC 2n+1D 2n-18. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（）。

A acbedB decabC deabcD cedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。

A (r-f+m)mod mB r-f+1C r-f-1D r-f10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。

A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子 D任一结点无右孩子三，判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。

计算机专业基础综合（树与二叉树）-试卷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个结点，那么二叉树的树形有( )种。

n个叶子节点的哈夫曼树节点总数【主题】n个叶子节点的哈夫曼树节点总数【引言】在计算机科学中，哈夫曼树是一种用来编码和解码的数据结构。

它通过将出现频率较高的字符编码为较短的比特串，从而提高了编码效率。

然而，在构建哈夫曼树时，我们是否能够确定节点的总数呢？【探索节点总数的多种情况】1. 当只有一个叶子节点时，哈夫曼树的节点总数为1。

这是最简单的情况，哈夫曼树只包含一个节点，即该叶子节点。

2. 当有两个叶子节点时，哈夫曼树的节点总数为3。

我们可以通过构建一个根节点，并将两个叶子节点连接到根节点下来实现。

3. 当有三个叶子节点时，哈夫曼树的节点总数为5。

我们可以将两个权值较小的叶子节点连接到一个新的中间节点上，再将剩余的叶子节点连接到这个中间节点下。

4. 更一般地，当有n个叶子节点时，哈夫曼树的节点总数可以用下面的式子表示：2n-1。

【深入理解节点总数的推导】为了更深入地理解节点总数的推导过程，让我们从最简单的情况开始推导：当只有一个叶子节点时，节点总数为1；当有两个叶子节点时，节点总数为3，正好是两个叶子节点的数量加上一个根节点；当有三个叶子节点时，需要连接两个权值最小的叶子节点，同时将剩余的叶子节点连接到这个新的中间节点上，形成一个具有3个节点的子树。

节点总数为3+3=6。

同理，当有n个叶子节点时，需要连接两个权值最小的叶子节点，同时将剩余的叶子节点连接到这个新的中间节点上，形成一个具有n个节点的子树。

节点总数为n-1+n=2n-1。

【个人观点和理解】节点总数的推导过程虽然看似简单，但却蕴含了深刻的数学原理和数据结构的应用。

哈夫曼树作为一种高效的编码和解码数据结构，其节点的总数对于算法的时间复杂度和空间复杂度有着直接的影响。

通过了解节点总数的规律，我们可以更好地理解和使用哈夫曼树。

总结回顾：我们通过探索多种情况和推导过程，深入地理解了n个叶子节点的哈夫曼树的节点总数。

从最简单的情况开始，我们逐步推导出节点总数的通用表达式2n-1。

数据结构题⽬和答案思考题⼀、填空题：（20分，每空1分）1、数据的基本单位是数据元素，最⼩单位是s数据项。

2、x=91; n=100;while(n>0){if (x>100){ x=x-10; n=n-1;}else x=x+1;}上述算法中语句x=x+1的执⾏次数T(n)= O(N^3) 。

3、已知⼆维数组A[21][11]采⽤⾏序为主⽅式存储，每个元素占4个存储单元，并且A[0][0]的存储地址为1016，则A[10][5]的存储地址是。

4、在进出规则上，队列的特点是，堆栈的特点是。

5、深度为5（根层次为1）的⼆叉树最多有个结点；第4层最多有个结点。

6、在长度为n的顺序表（即顺序存储结构的线性表）中插⼊⼀个元素，需要平均移动个元素。

7、在⽆向图中, 若对于任意⼀对顶点v i和v j, 都存在, 则称此图是连通图。

8、设有⼀个10阶的对称矩阵A，采⽤压缩存储⽅式，以⾏为主存储，a00为第⼀个元素，其存储地址为1，每个元素占1个地址空间，则a75的地址为。

9、线性表的两种常⽤存储结构有存储结构和存储结构。

10、当增量d为1时，该趟希尔排序与排序基本⼀致。

11、数据结构是研究数据的，和算法。

12、常⽤图的存储结构有：邻接矩阵，邻接表，⼗字链表，邻接多重表；13、顺序表的插⼊算法int Insert(elemtype List[],int *num,int i, elemtype x){int j;if(i<0| | i>*num+1){printf(“\n i值不合法!”);return 0;}for (j=*num;j>=i;j--); /*数据元素依次后移*/ List[ i]=x; (*num)++;return 1;}1在单链表中设置头结点的作⽤是___ 简化操作_____________________________________。

2顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻。