当前位置：文档之家 › 数据结构(C语言版)第6章练习 清华大学出版社

数据结构(C语言版)第6章练习 清华大学出版社

  • 格式：doc
  • 大小：51.50 KB
  • 文档页数：3

1
第六章 数据结构作业
第六章 树
选择题
1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++
3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A．5 B．6 C．7 D．8
4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结
点个数是（ ）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定
6．具有10个叶结点的二叉树中有（ ）个度为2的结点，
A．8 B．9 C．10 D．ll
7．一棵完全二叉树上有1001个结点，其中叶子结点的个数为（ ）
A． 250 B． 500 C．254 D．505 E．以上答案都不对
8. 有n个叶子的哈夫曼树的结点总数为（ ）。
A．不确定 B．2n C．2n+1 D．2n-1
9. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A．logn+1 B．logn+1 C．logn D．logn-1
10．深度为h的满m叉树的第k层有（ ）个结点。(1=A．mk-1 B．mk-1 C．mh-1 D．mh-1
11．在一棵高度为k的满二叉树中，结点总数为（ ）
A．2k-1 B．2k C．2k-1 D．log2k+1
12．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左
右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
13．树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列 B. 中序序列 C. 后序序列
14．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
A．acbed B．decab C．deabc D．cedba
15．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树
的根是：
A、 E B、 F C、 G D、 H
16．n个结点的线索二叉树上含有的线索数为（ ）
A．2n B．n－l C．n＋l D．n
17．下述编码中哪一个不是前缀码（ ）。
A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）
18．从下列有关树的叙述中,选出5条正确的叙述 （ ）
A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B．当K≥1时高度为K的二叉树至多有2k-1个结点。
2

C．用树的前序周游和中序周游可以导出树的后序周游。
D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
E．将一棵树转换成二叉树后,根结点没有左子树。
F．一棵含有N个结点的完全二叉树,它的高度是LOG2N+1。
G．在二叉树中插入结点,该二叉树便不再是二叉树。
H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。
I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
J．用一维数组存储二叉树时,总是以前序周游存储结点。
判断题：
1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。
2. 二叉树只能用二叉链表表示。
3．在二叉树的第i层上至少有2i-1个结点(i>=1)
4．度为二的树就是二叉树。
5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。
填空题：
1．具有256个结点的完全二叉树的深度为______。
2．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶
子结点。
3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______
4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。
5．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3
则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。
6．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。

算法应用题
1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树
中有多少个叶子结点？
2、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？
（请给出具体的推理过程）
3、请采用顺序存储方式和链式存储方式，分别写出下图所示二叉树的存储结构。
A

B C
D E F
G H
4、求出上图所示二叉树的前序、中序和后序序列。
5、以二叉链表做存储结构，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。
6、设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）画出这棵二叉树的中序线索树
（3）画出这棵二叉树的后序线索树
7、假设一个二叉树的两种遍历如下：
前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA
3

画出这棵二叉树以及它的中序线索树；
8、给定一组权值3，27，7，8，14，23，6，12
（1）试画出用Huffman算法建造的Huffman树；
（2）求Huffman编码和平均编码长度（考虑概率）
9、将下列森林转化为二叉树。

10、求上述森林的前序和中序序列。
算法设计题：
1．设计算法，求前序线索树中结点P的后继
2．设计算法，求中序线索树中结点P的后继
3．用二叉链表表示的二叉树T，结点的值为整型，请设计算法，求T中结点值大于0的结点数，并作为算法
的返回值。

合集下载

C语言程序设计第3版,第6章函数程序设计

C语言程序设计第3版,第6章函数程序设计

C语言程序设计（第3版）张 磊编著 清华大学出版社
6.1 函数概述
C语言程序的特点：函数化结构 函数分类：系统函数、用户函数
系统函数：printf()、scanf()、sqrt()等 用户函数：在程序中编写的函数，又称自定义函数。 用户函数的特例：main()函数 如果在程序中经常需要某种处理，就可以编写一个函数，在需要 这种处理时，就调用该函数。 示例 计算a!+b!+c!
n) 简化形式：
函数类型 函数名（数据类型1,数据类型2,…,数据类型n） ⑵ 函数声明 函数声明是在主调函数的函数体说明部分描述被调函数原型。 ２．函数调用 函数调用是对已定义函数的具体应用。 一般形式： 函数名(实参表)
C语言程序设计（第3版）张 磊编著 清华大学出版社
6.3.3 函数调用
例6-6 调用p_star50()函数，连续输出20行*字符串，每行50个*字符。
printf("SUM=%ld\n",f(a)+f(b)+f(c)
}
long f(int n) /* 计算阶乘的函数 */
{
long t;
int i;
for(t=1,i=1;i<=n;i++)
t*=i;
return(t);
}
6.3 函数的定义及调用
6.3.1 函数的定义 6.3.2 函数值和return命令 6.3.3 函数调用
函数原型及 函数声明
void p_star(int n) {
****void p_star(int n); ****ifno*tr(kk;=1;k<=5;k++) 函数实参
int i; for(i=1;i<=n;i++)
清华大学出版社数据结构（C++版）（第2版）课后习题答案最全整理

清华大学出版社数据结构（C++版）（第2版）课后习题答案最全整理

清华大学出版社数据结构（C++版）（第2版）课后习题答案最全整理第1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

《数据结构》教程c语言版

《数据结构》教程c语言版

《数据结构》第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构--概念与基本类型 (6)1.1概述 (6)1.1.1数据结构应用对象 (6)1.1.2学习数据结构的基础 (7)1.1.2.1 C语言中的结构体 (7)1.1.2.2 C语言的指针在数据结构中的关联作用 (8)1.1.2.3 C语言的共用体(union)数据类型 (12)1.1.3数据结构定义 (15)1.2线性表 (17)1.2.1 顺序表 (18)1.2.2 链表 (20)1.2.2.1链表的基本结构及概念 (20)1.2.2.2单链表设计 (22)1.2.2.3单链表操作效率 (29)1.2.2.4双链表设计 (30)1.2.2.5链表深入学习 (32)1.2.2.6稀疏矩阵的三元组与十字链表 (36)1.2.3 堆栈 (41)1.2.3.1堆栈结构 (41)1.2.3.2基本操作 (42)1.2.3.3堆栈与递归 (44)1.2.3.4递归与分治算法 (45)1.2.3.5递归与递推 (49)1.2.3.6栈应用 (52)1.2.4 队列 (57)1.2.4.1队列结构 (57)1.2.3.2队列应用 (59)1.3非线性数据结构--树 (64)1.3.1 概念与术语 (64)1.3.1.1引入非线性数据结构的目的 (64)1.3.1.2树的定义与术语 (65)1.3.1.3树的内部节点与叶子节点存储结构问题 (66)1.3.2 二叉树 (66)1.3.2.1二叉树基本概念 (66)1.3.2.2完全二叉树的顺序存储结构 (68)1.3.2.3二叉树遍历 (69)1.3.2.4二叉树唯一性问题 (71)1.3.3 二叉排序树 (72)1.3.3.1基本概念 (72)1.3.3.2程序设计 (73)1.3.4 穿线二叉树 (79)1.3.4.1二叉树的中序线索化 (80)1.3.4.2中序遍历线索化的二叉树 (81)1.3.5 堆 (82)1.3.5.1建堆过程 (83)1.3.5.2在堆中插入节点 (85)1.3.6 哈夫曼树 (86)1.3.6.1最佳检索树 (86)1.3.6.2哈夫曼树结构与算法 (88)1.3.6.3 哈夫曼树应用 (90)1.3.6.4哈夫曼树程序设计 (92)1.3.7 空间数据结构----二叉树深入学习导读 (95)1.3.7.1k-d树概念 (96)1.3.7.2k-d树程序设计初步 (97)1.4非线性数据结构--图 (100)1.4.1图的基本概念 (100)1.4.2图形结构的物理存储方式 (103)1.4.2.1相邻矩阵 (103)1.4.2.2图的邻接表示 (104)1.4.2.3图的多重邻接表示 (106)1.4.3图形结构的遍历 (107)1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） (110)1.4.5有向图的最短路径 (113)1.4.5.1单源最短路径（single-source shortest paths） (113)1.4.5.2每对顶点间最短路经（all-pairs shortest paths） (116)1.4.6拓扑排序 (117)第二章检索 (123)2.1顺序检索 (123)2.2对半检索 (124)2.2.1 对半检索与二叉平衡树 (124)2.2.2对半检索思想在链式存储结构中的应用---跳跃表 (127)2.3分块检索 (133)2.4哈希检索 (134)2.4.1哈希函数 (135)2.4.2闭地址散列 (136)2.4.2.1线性探测法和基本聚集问题 (136)2.4.2.2删除操作造成检索链的中断问题 (138)2.4.2.3随机探测法 (139)2.4.2.4平方探测法 (140)2.4.2.5二次聚集问题与双散列探测方法 (141)2.4.3开地址散列 (142)2.4.4哈希表检索效率 (142)第三章排序 (145)3.1交换排序方法 (145)3.1.1直接插入排序 (145)3.1.2冒泡排序 (147)3.1.3 选择排序 (148)3.1.4 树型选择排序 (149)3.2S HELL排序 (150)3.3快速排序 (152)3.4堆排序 (154)3.5归并排序 (156)3.6数据结构小结 (159)3.6.1 数据结构的基本概念 (159)3.6.2 数据结构分类 (159)3.6.2.1数据结构中的指针问题 (160)3.6.2.2线性表的效率问题 (161)3.6.2.3二叉树 (161)3.6.3排序与检索 (161)3.7算法分析的基本概念 (162)3.7.1基本概念 (162)3.7.2上限分析 (164)3.7.3下限分析 (164)3.7.4空间代价与时间代价转换 (165)第6章高级数据结构内容--索引技术 (167)6.1基本概念 (167)6.2线性索引 (168)6.2.1 线性索引 (168)6.2.2 倒排表 (169)6.32-3树 (170)6.3.1 2-3树定义 (172)6.3.2 2-3树节点插入 (173)6.4B+树 (178)6.4.1 B+树定义 (178)6.4.2 B+树插入与删除 (180)6.4.3 B+树实验设计 (182)第一章数据结构--概念与基本类型1.1概述1.1.1数据结构应用对象计算机应用可以分为两大类，一类是科学计算和工业控制，另一类是商业数据处理。

第6章树和二叉树(5)-数据结构教程(Python语言描述)-李春葆-清华大学出版社

第6章树和二叉树(5)-数据结构教程(Python语言描述)-李春葆-清华大学出版社


pre
p
∧
pre
p
∧
(a) 将结点p的左空指针改为线索
(b) 将结点pre的右空指针改为线索
8/36
A
B
C
D
EF
G
中序序列： D G B A E C F
9/36
def _Thread(self,p): if p!=None:
self._Thread(p.lchild)
#对以p为根结点的二叉树进行中序线索化 #左子树线索化
self._Thread(self.b)
#中序遍历线索化二叉树
self.pre.rchild=self.root #最后处理,加入指向根结点的线索
self.pre.rtag=1
self.root.rchild=self.pre #根结点右线索化
7/36
采用中序遍历进行中序线索化 在整个算法中p总是指向当前访问的结点，pre指向其前驱结点。
#建立以root为头结点的中序线索二叉树
def ThInOrder(self):
#中序线索二叉树的中序遍历
6/36
def CreateThread(self):
#建立以root为头结点的中序线索二叉树
self.root=ThNode()
#创建头结点root
self.root.ltag=0
#头结点标志置初值
① 如果p结点的rchild指针为线索，则rchild所指为其后继结点。 ② 否则p结点的后继结点是其右孩子q的最左下结点post。
b
根结点
…
…… p
p …
… post
q
post结 … 点为q结
点的最右 下结点
11/36