下载文档原格式
习题51.填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。
答案：129（2）3个结点可构成（___________）棵不同形态的二叉树。
答案：5（3）设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）个叶子。
答案：31（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。
高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。
答案：2 n-1 1 n 1 n-1（5）深度为k的二叉树，至多有（___________）个结点。
答案：2k-1（6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。
答案：2n-1（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。
答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT （X）的编号为（）。
答案：24（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。
答案：384（11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。
答案：68（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。
答案：128（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。
答案：ABCDEF（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。
数据结构第五章习题1.名词解释（1）串（2）广义表2.判断题〔以下各题，正确的请在前面的括号内打√，错误的打×〕〔〕〔1〕串中不可以包含空白字符。
〔〕〔2〕两个串相等必有串长度相同。
〔〕〔3〕两个串相等那么各位置上的字符不一定对应相同。
〔〕〔4〕串的长度不能为零。
〔〕〔5〕子串是主串中字符构成的有限序列。
〔〕〔6〕串是一种特殊的线性表。
〔〕〔7〕空格串是由一个或多个空格字符组成的串，其长度为1。
〔〕〔8〕广义表最大子表的深度为广义表的深度。
〔〕〔9〕广义表不能递归定义。
〔〕〔10〕广义表的组成元素可以是不同形式的元素。
3.填空题（1）串中字符的个数称为串的____________。
（2）不含有任何字符的串称为____________，它的长度是____________。
（3）串的___________就是把串所包含的字符序列，依次存入连续的存储单元中去。
（4）串的链式存储结构是将存储区域分成一系列大小相同的节点，每个节点有两个域：____________域和____________域。
其中____________域用于存储数据，____________域用于存储下一个节点的指针。
（5）子串的定位操作通常称为串的____________。
（6）串的两种最根本的存储方式是____________和____________。
（7）广义表((a), ((b), c), (((d))))的表头是____________，表尾是____________。
（8）广义表的表尾总是一个____________。
4.选择题（1）串是一种特殊的线性表，其特殊性表达在〔〕。
A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以任意（2）串的长度是〔〕。
A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数且大于零D．串中所含字符的个数（3）空串与空格串〔〕。
A．相同B．不相同C．可能相同D．无法确定（4）求字符串T在字符串S中首次出现的位置的操作为〔〕。
05 图【单选题】1. 设无向图G 中有五个顶点，各顶点的度分别为2、4、3、1、2，则G 中边数为（C ）。
Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定2. 含n 个顶点的无向完全图有（D ）条边；含n 个顶点的有向图最多有（C ）条弧；含n 个顶点的有向强连通图最多有（C ）条弧；含n 个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n 个顶点，则要接通全部顶点至少需（G ）条边。
A 、n 2B 、n(n+1)C 、n(n-1)D 、n(n-1)/2E 、n+1F 、nG 、n-13. 对下图从顶点a 出发进行深度优先遍历，则（A ）是可能得到的遍历序列。
A 、acfgdebB 、abcdefgC 、acdgbefD 、abefgcd对下图从顶点a 出发进行广度优先遍历，则（D ）是不可能得到的遍历序列。
A 、abcdefgB 、acdbfgeC 、abdcegfD 、adcbgef4. 设图G 的邻接矩阵A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010101010，则G 中共有（C ）个顶点；若G 为有向图，则G 中共有（D ）条弧；若G 为无向图，则G 中共有（B ）条边。
A 、1B 、2C 、3D 、4E 、5F 、9G 、以上答案都不对5. 含n 个顶点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A 、0B 、1C 、n-1D 、n6. 用邻接表存储图所用的空间大小（A ）。
A 、与图的顶点数和边数都有关B 、只与图的边数有关C 、只与图的顶点数有关D 、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B ）个表结点。
A 、n 2B 、n(n-1)C 、n(n+1)D 、n(n-1)/28. 无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。
第5章：数组和广义表 1. 了解数组的定义；填空题：1、假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 。
2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。
2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址；填空题：1、已知A 的起始存储位置（基地址）为1000，若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。
(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。
答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1，c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950选择题：（ A ）1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。
（无第0行第0列元素）A ．16902B ．16904C ．14454D ．答案A, B, C 均不对 答：此题（57列×60行＋31行）×2字节＋10000=16902( B )2、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：A ．i(i-1)/2+j-1B ．i(i-1)/2+jC ．i(i+1)/2+j-1D ．i(i+1)/2+j3、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。
( ×)2、二叉树的左右子树可任意交换。
（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。
（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。
（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。
( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
（×）8、度为2的树就是二叉树。
（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。
A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。
A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。
该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。
①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。
A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。
A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。
2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。
数据结构-第5章--数组练习题第5章数组一、选择题3.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(A)。
A.BA+141B.BA+180C.BA+222D.BA+2254.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（A）。
A.808B.818C.1010D.10205.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。
1195A.1175B.1180C.1205D.12107.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
供选择的答案：A.198B.195C.1972+64某3=19410.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（iA.i某(i-1)/2+jB.j某(j-1)/2+iC.i某(i+1)/2+jD.j某(j+1)/2+i11.设A是n某n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(C)。
A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（AB）。
朱战立数据结构第五版答案第一章：引论1.1 数据结构的概念数据结构是指数据对象中元素之间的关系和相互操作的一种集合体。
数据结构的设计和实现对于解决实际问题非常重要。
1.2 抽象数据类型（ADT）抽象数据类型是指一个数学模型以及该模型上的一组操作。
通过使用抽象数据类型，我们可以将数据对象的表示和对数据对象的操作封装在一起，从而实现了数据的抽象。
1.3 算法的基本概念算法是解题方案的准确而完整的描述，它是实现特定功能的有限指令序列。
算法的设计和分析是数据结构和算法课程的核心内容。
第二章：算法分析2.1 算法效率的度量算法的效率可以从时间复杂度和空间复杂度两个方面来度量。
时间复杂度是指算法执行所需要的时间；空间复杂度是指算法执行所需要的额外空间。
2.2 最坏情况和平均情况在算法分析中，我们通常关注算法在最坏情况下的表现，这是因为最坏情况下的性能是算法的上界，可以保证算法在任何情况下都能满足要求。
2.3 算法设计的要求算法设计的要求包括正确性、可读性、健壮性和高效性。
一个好的算法应当能够解决问题、易于理解、能够处理各种输入，并且在合理的时间内完成。
第三章：线性表3.1 线性表的定义线性表是具有相同数据类型的n个数据元素的有限序列。
线性表可以为空表，也可以包含一个或多个数据元素。
3.2 线性表的顺序表示线性表的顺序表示是指使用一组地址连续的存储单元依次存储线性表的元素。
顺序表示的优点是随机访问速度快，但插入和删除操作的效率较低。
3.3 线性表的链式表示线性表的链式表示是指使用一组任意存储单元来存储线性表的元素，通过指针将这些存储单元链接在一起。
链式表示的优点是插入和删除操作的效率较高，但访问元素的速度较慢。
3.4 线性表的应用线性表是最常用的数据结构之一，它在实际问题中有广泛的应用。
例如，线性表可以用来实现栈、队列、串等数据结构。
第四章：栈和队列4.1 栈栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。
数据结构习题(5)学号________ 姓名_______ 课堂号(___________)1.选择题1)对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22)下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3)折半查找的时间复杂性为（D）A. O（n2）B. O（n）C. O（nlog(n)）D. O（log(n)）4)概率不同的有序表，最适合的查找算法是（ C ）A．顺序查找B．折半查找C．静态树表查找 D．索引顺序表查找5)平均查找长度最短的查找方法是____C________。
A．折半查找 B.顺序查找 C.哈希查找 4.其他6)折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
若查找表中元素58，则它将依次与表中A比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，507)当采用分快查找时，数据的组织方式为 ( B )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同8)分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D. (100，80， 60， 90， 120，130，110)9)设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。
数据结构第五章数组和广义表(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。
A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。
A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。
从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。
(1)存放A至少需要( )个字节。
(2)A的第8列和第5行共占( )个字节。
(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。
供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。
A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。
A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。
A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。
计算机学科专业基础综合数据结构-5一、综合应用题(总题数：10，分数：100.00)一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。
如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1).各层的结点个数是多少?（分数：4.00）__________________________________________________________________________________________可以参照二叉树的性质，将其扩展到m叉树。
因为第1层有1个结点，第2层有m个结点，第3层有m 2个结点……一般地，第i层有m i-1个结点(1≤i≤h)。
(2).编号为i的结点的父结点(若存在)的编号是多少?（分数：4.00）__________________________________________________________________________________________在m叉树的情形，结点i的第1个子女编号为j=(i-1)×m+2。
反过来，结点i的双亲的编号是，根结点没有双亲，所以以上计算式要求i＞1。
如果考虑对于i=1也适用(根的双亲设为0)，可将上式改为。
(3).编号为i的结点的第k个子女结点(若存在)的编号是多少?（分数：4.00）__________________________________________________________________________________________因为结点i的第1个子女编号为(i-1)×m+2，若设该结点子女的序号为k=1，2，…，m，则第k个子女结点的编号为(i-1)×m+k+1(1≤k≤m)。
(4).编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?（分数：4.00）__________________________________________________________________________________________当结点i不是其双亲的第m个子女时才有右兄弟。
