下载文档原格式
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编12(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.给定二叉树如下图所示。
设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是( )。
【2009年全国试题3(2分)（分数：2.00）A.LRNB.NRLC.RLND.KNL √解析：【2009 2.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是( )。
年全国试题5(2分)】（分数：2.00）A.39B.52C.11 1 √D.119解析：解析：本题问“完全二叉树的结点个数最多是多少”。
完全二叉树的叶子至多只能在最下面两层上。
本题告诉第6层有8个叶子，还会有24个分支结点，其在第7层最多有48个叶子，故选C。
若说第6层只有8个叶子，则应选A。
3.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u 和v可能具有的关系是( )。
【2009年全国试题6(2分)】I．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v 的父结点是兄弟关系（分数：2.00）A.只有ⅡB.I和Ⅱ√C.I和ⅢD.I、Ⅱ和Ⅲ解析：解析：I指的是二叉树中v是u的左子女的右子女，Ⅱ指的是二叉树中v是u的右子女的右子女。
若Ⅲ成立，则森林转换的二叉树中，u不可能是v的父结点的父结点。
故选B。
4.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。
【2010年全国试题3(2分)】（分数：2.00）√解析：5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是( )。
【2010年全国试题5(2分)】（分数：2.00）A.41B.82 √C.113D.122解析：解析：度为m的树中，叶子结点个数的求解公式是n i是度i的结点数。
第七章图一、选择题1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
一、基础知识题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个结点仅有一个孩子，则该二叉树的总结点数是多少。
3.2数据与结构练习题1.下列不属于简单数据类型的是（）A.浮点型B.整型C.列表D.布尔型2.根据下面数据结构图回答下列问题：（1）上图树结构中的根是。
（2）H，I，J是的子树。
（3）树结构的数据节点之间关系是。
（4）生活中的树结构的例子有。
3.图结构中数据之间的关系是（）A. 一对一B.多对多C. 一对多D. 多对一4.线性结构数据之间的关系是（）A. 一对一B.多对多C. 一对多D. 多对一5.队列属于（）A.线性结构B.树结构C.图结构D.以上均不是6.在线性数据结构中，当前元素的后一位元素被称为（）A. 首元素B.前趋元素C. 尾元素D. 后继元素7.全国航运图属于（）A.线性结构B.树结构C.图结构D.以上均不是8.在python中[]是用来创建（）A.集合B.列表C.元组D.字典9.在python中{}是用来创建（）A.集合B.列表C.元组D.字典10.由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构是（）A．图结构B．选择结构C．线性结构D．树结构11.下列不属于复合数据类型的是（）A.元组B.整型C.列表D.集合参考答案：第1题：C第2题：(1)A (2)D (3)一对多（4）行政区划、书的目录、磁盘文件的存储结构第3题：B第4题：A第5题：A第6题：D第7题：C第8题：B第9题：A第10题：C第11题：B。
数据结构练习（二）答案一、填空题：1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为（1）4，树的深度为（2）4 ，树中叶子结点的个数为（3）8。
2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间关系的表达式（4）n=2h-1,m=n+1-2h-1 n=2m-1 。
3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。
一棵深度为k的完全二叉树中最少有2k-1（6）个结点，最多有（7）2k-1个结点。
4．具有n个结点的二叉树，当它是一棵(8)完全二叉树时具有最小高度（9） log2n」+1，当它为一棵单支树时具有高度(10) n 。
5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。
6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。
7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。
8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。
9．已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。
10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。
11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。
度为k的树中第i层最多有___k i-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+k h-1____个结点。
一、单选题1、树最适合用来表示（）。
A.元素之间具有分支层次关系的数据B.有序数据元素C.元素之间无联系的数据D.无序数据元素正确答案：A2、在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是（）。
A.5B.4C.3D.2正确答案：B3、下列陈述中正确的是（）。
A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中每个结点最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点正确答案：C4、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为（）。
A.2h-1B.2h+1C.h+1D.2h正确答案：A解析： A、除根之外，每层只有两个结点，且互为兄弟。
5、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为（）。
A.2h-1B. 2h+1-1C. 2h-1-1D. 2h+1正确答案：A解析： A、构成完全二叉树。
6、具有n(n>0)个结点的完全二叉树的深度为（）。
A.⌊ log2(n)⌋ +1B.⌈log2(n)⌉C.⌊ log2(n)⌋D.⌈log2(n)+1⌉正确答案：A7、具有32个结点的完全二叉树有（）个叶子结点。
A.16B.14C.15D.17正确答案：A解析： A、对结点按层序编号，32号结点的双亲结点编号为16，则17至32号结点都为叶子，共16个。
8、一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有（）结点。
A.81B.78C.80D.79正确答案：A解析： A、完全二叉树的叶子结点只能在最下两层，要使结点最多，这棵二叉树深度为7，前6层结点数共为63，第6层有32个结点，其中叶子为23个，非叶子为9个，它们的度都为2，第7层只有18个结点，故整棵二叉树结点数为81.9、具有3个结点的二叉树有（）种。
A.6B.3C.5D.4正确答案：C10、若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为（）。
第六章树一．名词解释：1 树 2。
结点的度 3。
叶子 4。
分支点 5。
树的度6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树21 哈夫曼树二、填空题1、树（及一切树形结构）是一种“________”结构。
在树上，________结点没有直接前趋。
对树上任一结点X来说，X是它的任一子树的根结点惟一的________。
2、一棵树上的任何结点（不包括根本身）称为根的________。
若B是A的子孙，则称A是B的________3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。
4、二叉树第i(i>=1)层上至多有______个结点。
5、深度为k(k>=1)的二叉树至多有______个结点。
6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。
满二叉树也是______二叉树，但反之不然。
8、具有n个结点的完全二叉树的深度为______。
9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。
（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。
（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。
10.二叉树通常有______存储结构和______存储结构两类存储结构。
11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。
数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
数据结构(树与图部分)练习题一、填空题1.不考虑顺序的3个结点可构成种不同形态的树，种不同形态的二叉树。
2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为：。
3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。
4.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是；结点i的左孩子结点的编号是，结点i的右孩子结点的编号是。
5.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是______；结点i的左孩子结点编号是______，右孩子结点编号是______。
6.在有n个叶子结点的Huffman树中，总的结点数是：______。
7.图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限集合，E(G)是______的有限集合。
8.遍历图的基本方法有优先搜索和优先搜索两种方法。
9.图的遍历基本方法中是一个递归过程。
10.n个顶点的有向图最多有条弧；n个顶点的无向图最多有条边。
11.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是。
12.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。
二、单项选择题1.树型结构的特点是：任意一个结点：（）A、可以有多个直接前趋B、可以有多个直接后继C、至少有1个前趋D、只有一个后继2.如下图所示的4棵二叉树中，（）不是完全二叉树。
A B C D3.深度为5的二叉树至多有（）个结点。
A、16B、32C、31D、104.64个结点的完全二叉树的深度为：（）。
A、8B、7C、6D、55.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（）。
A、98B、99C、50D、486.在一个无向图中，所有顶点的度之和等于边数的（）倍。
A、1/2B、1C、2D、47.设有13个值，用它们组成一棵Huffman树，则该Huffman树中共有( )个结点。
A、13B、12C、26D、258.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为( )。
A、2,14B、2,15C、3,14D、3,159.若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x，它的双亲结点及左孩子结点的编号分别为( )。
A、2,11B、2,10C、3,9D、3,1010.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：A、48B、49C、50D、5111.无向图的邻接矩阵是一个( )。
A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵12.由64个结点构成的完全二叉树，其深度为：( )。
A、8B、7C、6D、513.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为( )。
A、2,14B、2,15C、3,14D、3,1514.图示二叉树的中序遍历序列是：（）A、abcdgefB、dfebagcC、dbaefcgD、defbagc15.图示二叉树的后序遍历序列是：（）A、ABCDEFGHB、BDAFEHGCC、DBFHGECAD、HGFEDCBA16.邻接表是图的一种（）。
A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构17.给定有向图如右图所示，则该图的一个强连通分量是：（）。
A、{A,B,C,F}B、{B,C,F}C、{B,C,D,F}D、{C,D,E,F}18.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A、将邻接矩阵的第i行删除B、将邻接矩阵的第i行元素全部置为0C、将邻接矩阵的第i列删除D、将邻接矩阵的第i列元素全部置为0三、判断题1.（）非线性数据结构可以顺序存储，也可以链接存储。
2.（）非线性数据结构只能用链接方式才能表示其中数据元素的相互关系。
3.（）完全二叉树一定是满二叉树。
4.（）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
5.（）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。
6.（）度为1的有序树与度为1的二叉树是等价的。
7.（）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。
8.（）已知一棵二叉树的先序序列和后序序列，就一定能构造出该二叉树。
9.（）在霍夫曼树中，权值最小的结点离根结点最近。
10.( )对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的每个顶点。
11.（）线性数据结构可以采用顺序存储结构或链式存储结构，而非线性数据结构只能采用链式存储结构。
12.（）二叉树中的叶子结点就是二叉树没有左、右子树的结点。
13.（）如果一棵树中某结点的度为1，则该结点仅有一棵子树。
14.（）在有向图中，若存在有向边<V1,V2>,则一定存在有向边<V2，V1>。
15.（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历后，并不一定能访问到该图的每个顶点。
16.（）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
四、简答题1.什么叫有序树？什么叫无序树？有序树和二叉树的差别是什么？2.什么叫完全二叉树？什么叫满二叉树？它们之间的关系是什么？3.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？五、综合题1.如图所示的两棵二叉树，分别给出它们的顺序存储结构。
第1棵树第2棵树2.已知一棵二叉树的中序、后序序列分别如下：中序：D C E F B H G A K J L I M后序：D F E C H G B K L J M I A要求：⑴画出该二叉树；⑵写出该二叉树的先序序列。
3.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。
先序：_ B _ F _ I C E H _ G中序：D _ K F I A _ E J C _后序：_ K _ F B H J _ G _ A4.将下图中的树转化为二叉树，并写出转换后的二叉树的后序遍历序列。
5.将下图所示的树转换成二叉树，并写出转换后二叉树的先序、中序、后序遍历结果。
6.将下列一棵二叉树进行前序遍历、中序遍历、后序遍历，并转化为树。
7.写出下面二叉树的先序、中序、后序遍历结果，并将它转换为树。
8. 分别写出下图所示二叉树的先序、中序和后序遍历序列。
9. 写出下图中的二叉树先序和后序遍历序列。
10. 输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴ 画出该二叉排序树；⑵ 画出删除结点302后的二叉排序树。
11. 按给出的一组权值{4，5，7，8，11}，建立一个霍夫曼树，并请计算出该树的带权路径长度WPL 。
12. 以{5,9,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。
13. 以{4,7,10,15,23}作为叶子结点的权值构造一棵Huffman 树，并求出其带权路径长度。
14. 以{5,6,7,8,9,10,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。
15. 以{10,12,16,21,30}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。
16. 如右所示的有向图，请给出它的： （1） 每个顶点的入度和出度；（2）邻接矩阵；（3）邻接表；（4）强连通分量。
17.已知一棵二叉树的中序和先序序列如下，求该二叉树的后序序列，并将它转换为树。
先序结果：A,B,E,F,C,D,G,H,I中序结果：E,F,B,C,G,H,I,D,A18.已知一棵二叉树的中序和后序遍历结果如下所示，求该二叉树的先序遍历序列。
中序结果：E,F,B,C,G,H,I,D,A后序结果：F,E,I,H,G,D,C,B,A19.请给出按自左向右的顺序依次将关键字为{30，5，20，23，9，27，6，14，45，22}的记录插入到一个初始时为空的二叉排序树后所建立的二叉排序树。
20.请将序列51，17，60，32，6，10，23，3，80，40，44，7排列为二叉排序树。
21.请将序列28，55，06，33，161，81，91，11，25，56，57，02排列为二叉排序树。
22.构造插入序列为{10，18，3，8，12，2，7，13}的二叉排序树，（要求过程）。
23.请给出下面的二叉树的先序、中序和后序遍历结果。
24.请给出下面的有向图的邻接矩阵、邻接表形式的存储结构，并计算出每个顶点的入度和出度。
25.已知某无向图的邻接表存储结构如下图所示，（1）请画出此无向图，（2）给出无向图的邻接矩阵表示。
