数据结构(树与图部分)练习题

第七章图一、选择题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。

第7章树和森林树形结构是一类重要的非线性结构。

树形结构的特点是结点之间具有层次关系。

本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。

重点提示：●树的存储结构●树的遍历●树和森林与二叉树之间的转换7-1 重点难点指导7-1-1 相关术语1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。

要点：树是一种递归的数据结构。

2．结点的度：一个结点拥有的子树数称为该结点的度。

3．树的度：一棵树的度指该树中结点的最大度数。

如图7-1所示的树为3度树。

4．分支结点：度大于0的结点为分支结点或非终端结点。

如结点a、b、c、d。

5．叶子结点：度为0的结点为叶子结点或终端结点。

如e、f、g、h、i。

6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。

7．兄弟结点：具有同一父亲的结点为兄弟结点。

如b、c、d；e、f；h、i。

8．树的深度：树中结点的最大层数称为树的深度或高度。

9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。

10．森林：是m棵互不相交的树的集合。

7-1-2 树的存储结构1．双亲链表表示法以图7-1所示的树为例。

（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。

（2）存储示意图:-1 data:parent:（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。

下面的存储是不正确的：-1 data:parent:2．孩子链表表示法（1）存储思想：将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。

第六章树一．名词解释：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、树最适合用来表示（）。

A.元素之间无联系的数据B.元素之间具有层次关系的数据C.无序数据元素D.有序数据元素正确答案：B2、现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。

表示该遗传关系最适合的数据结构为（）。

A.线性表B.树C.数组D.图正确答案：B3、一棵节点个数为n、高度为h的m（m≥3）次树中，其分支数是（）。

A.n+hB.h-1C.n-1D.nh正确答案：C4、若一棵3次树中有2个度为3的节点，1个度为2的节点，2个度为1的节点，该树一共有（）个节点。

A.11B.5C.8D.10正确答案：A解析： A、对于该3次树，其中有n3=2，n2=1，n1=2，总分支数=总度数=n-1，总度数=1×n1+2×n2+3×n3=10，则n=总度数+1=11。

5、设树T的度为4，其中度为1、2、3、4的节点个数分别为4、2、1、1，则T中的叶子节点个数是（）。

A.6B.8C.7D.5正确答案：B解析： B、这里n1=4，n2=2，n3=1，n4=1，度之和=n-1=n1+2n2+3n3+4n4=15，所以n=16，则n0=n-n1-n2-n3-n4=16-8=8。

6、有一棵三次树，其中n3=2，n2=1，n0=6，则该树的节点个数为（）。

A.9B.12C.大于等于9的任意整数D.10正确答案：C解析： C、n=n0+n1+n2+n3=6+n1+1+2=9+n1。

7、假设每个节点值为单个字符，而一棵树的后根遍历序列为ABCDEFGHIJ，则其根节点值是（）。

A.JB.BC.以上都不对D.A正确答案：A8、一棵度为5、节点个数为n的树采用孩子链存储结构时，其中空指针域的个数是（）。

A.4nB.4n-1C.4n+1D.5n正确答案：C解析： C、总指针数=5n，非空总指针数=分支数=n-1，空指针域的个数=5n-(n-1)=4n+1。

9、有一棵三次树，其中n3=2，n2=2，n1=1，该树采用孩子兄弟链存储结构时，则总的指针域数为（）。

数据结构练习题习题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. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。

答案：升序排列的序列5. 栈的特点是_______进，_______出。

答案：后进，先出6. 图中两点间存在边则称它们为_______。

答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。

答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。

栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。

8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。

其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。

四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。

```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。

```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。

如果有不清楚的地方，欢迎随时向老师询问。

祝您考试顺利！。

一、填空题1. 一完全二叉树共有500个结点，则在该二叉树中有 个度为2的结点。

2. 设某二叉树的前序遍历序列为:ABCDEFGHI ，中序遍历序列为:BCAEDGHFI ，则该二叉树的后序遍历序列是 。

3. 对于一个稀疏图，在求该图对应的最小生成树时，Prim 算法和kruskal 算法哪一个算法效率更高 。

4. 对于一个n 个结点的满二叉树，假设该树有m 个树叶，深度为h ，则 h= 。

5. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 ，至多为 。

6. 一棵有n 个结点的满二叉树有_ _ 个叶子，该满二叉树的深度为_ __。

7. 设F 是由T1,T2,T3三棵树组成的森林,与F 对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B 的左子树中有__ _个结点。

8. 一颗含有101个结点的完全二叉树存储在数组A[1..101]中，若A[k]为叶子结点，则k 的最小值是 。

9. 一颗深度为h 的完全二叉树上的结点总数最小值为 ，最大值为 。

二、选择题1. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T 中的叶子数为（ ）。

A ．5B ．6C ．7D ．81. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（ ）。

A ．G 中有弧<Vi ，Vj>B ．G 中有一条从Vi 到Vj 的路径C ．G 中没有弧<Vi,Vj>D ．G 中有一条从Vj 到Vi 的路径 1. 若完全二叉树的结点总数为偶数，则度为1的结点有( )个。

A. 0B. 1C. 2D. 不确定1. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（ ）。

A ．CBEFDAB ． FEDCBAC ． CBEDFAD ．不定 1. 下述编码中哪一个不是前缀码（ ）。

习 题 六 树 和 二 叉 树6.1 单项选择题1. 如图8.7所示的4棵二叉树，_C ___不是完全二叉树。

2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。

3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是B __。

A. t —＞left=NULLB. t —＞ltag=1C. t —＞ltag=1且t —＞left=NULLD. 以上都不对4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B __。

（A）（B）（C）（D）图8.7 4棵二叉树（A）（B）（C）图8.8 4棵二叉树A. 正确B. 错误5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。

A. 正确B. 错误6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。

A. 正确B. 错误7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。

A. 2hB. 2h-1C. 2h+1D. h+1 a8. 如图8.9所示二叉树的中序遍历序列___B_。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图8.9 一棵二叉树9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。

A. acbedB. decabC. deabcD. cedba10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。

A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。

BA．15 B．16 C．17 D．4712.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是D___ _。

数据结构习题72724数据结构习题及解析第6 章树和⼆叉树基础知识题6.1①已知⼀棵树边的集合为{ ,，}请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶⼦结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩⼦？（6）哪些是结点E的⼦孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？（10）以结点C为根的⼦树的深度是多少？6.2①⼀棵度为2的树与⼀棵⼆叉树有何区别？6.3①试分别画出具有3个结点的树和3个结点的⼆叉树的所有不同形态。

6.4③⼀棵深度为H的满k叉树有如下性质；第H层上的结点都是叶⼦结点，其余各层上每个结点都有k棵⾮空⼦树，如果按层次顺序从1开始对全部结点的编号，问：（1）各层的结点树⽬是多少？（2）编号为p的结点的⽗结点（若存在）的编号是多少？（3）编号为p的结点的第i 个⼉⼦结点（若存在）的编号是多少？（4）编号为p的结点有右兄弟的条件什么？其右兄弟的编号是多少？6.5②已知⼀棵树为k的树中有n1个度为1的结点，n2个度为2的结点,…n k个度为k 的结点,问该树中有多少个叶⼦结点?6.6③已知在⼀棵含有n个结点的树中,只有度为k的分⽀结点和度为0的叶⼦结点.试求该树含有的叶⼦结点的数⽬.6.7③⼀棵含有n个结点的k叉树，可能达到的最⼤深度和最⼩深度各为多少？6.8④证明：⼀棵满k叉树上的叶⼦结点数n0和⾮叶⼦结点数n1 之间满⾜以下关系：n0 =（k - 1）n1+ 16.9②试分别推导出含有n个结点和含有n0个叶⼦结点的完全三叉树的深度H。

6.10④对于那些所有⾮叶⼦结点均有⾮空左右⼦树的⼆叉树：（1）试问：有n个叶⼦结点的树中共有多少个结点？（2）试证明：∑2-（l i-1）=1 其中n 为叶⼦节点的个数，l i表⽰第i 个叶⼦节点所在的层次（设根结点所在层次为1）。

6.11③在⼆叉树的顺序存储结构中，实际上隐含这双亲的信息，因此可和三叉链表对应。

一、单选题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. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

第七章 图一、选择题1．图中有关路径的定义是（ ）。

【北方交通大学 2001 一、24 （2分）】A ．由顶点和相邻顶点序偶构成的边所形成的序列B ．由不同顶点所形成的序列C ．由不同边所形成的序列D ．上述定义都不是2．设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

【浙江大学 1999 四、4 (4分)】A ．n-1B ．nC ．n+1D ．nlogn ；4．要连通具有n 个顶点的有向图，至少需要（ ）条边。

【北京航空航天大学 2000 一、6(2分）】A ．n-lB ．nC ．n+lD ．2n5．n 个结点的完全有向图含有边的数目（ ）。

【中山大学 1998 二、9 （2分）】A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ）6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0B ．1C ．n-1D ．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A ．1/2B ．2C ．1D ．48．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。

【中山大学1999一、14】A ．5B ．6C ．8D ．99．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A ．逆拓扑有序B ．拓扑有序C ．无序的 【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。

数据结构练习（二）答案一、填空题：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. 请画出与下列二叉树对应的森林。

2.设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

3．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。

4. 假设树T是采用二叉链表结构储存的二叉树，编写函数，把树T的左右子树进行交换。

5. 二叉树结点数值采用顺序储存结构，如下表所示：e af dg c jhi b （1）画出二叉树表示；（2）写出前序、中序、后序遍历的结果；（3）写出结点值c的父结点及其左右孩子。

图1.请画出下图的邻接矩阵和邻接表。

2.设有无向图G，要求给出用普里姆算法和克鲁斯卡尔算法分别构造最小生成树。

3.对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；图64.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。

数据结构－树练习题一、选择题1、二叉树的深度为k，则二叉树最多有（ C ）个结点。

A. 2kB. 2k-1C. 2k-1D. 2k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。

A. R[2i-1]B. R[2i+1]C. R[2i]D. R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。

A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。

A. adbceB. decabC. debacD. abcde5、在一棵具有5层的满二叉树中结点总数为（ A ）。

A. 31B. 32C. 33D. 166、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。

A. 能B. 不能7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。

A. 3B. 2C. 4D. 58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。

A. 67B. 68C. 69D. 709、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。

A. 98B. 99C. 50D. 4810、表达式a*(b+c)-d的后缀表达式是（ B ）。

A. abcd+-B. abc+*d-C. abc*+d-D. -+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。

A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、树最适合用来表示（ C ）。

数据结构（树与图部分）练习题数据结构(树与图部分)练习题⼀、填空题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棵⼆叉树中，（）不是完全⼆叉树。

3.深度为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树中共有( )个结点。