数据结构教程李春葆课后答案

数据结构教程李春葆课后答案Tag内容描述：<p>1、第第 8 章章 图图 教材中练习题及参考答案 1. 图G是一个非连通图，共有28条边，则该图至少有多少个顶点？ 答：由于G是一个非连通图，在边数固定时，顶点数最少的情况是该图由两个连通分 量构成，且其中之一只含一个顶点（没有边），另一个为完全无向图。设该完全无向图的 顶点数为n， 其边数为n(n-1)/2，即n(n-1)/2=28，得n=8。所以，这样的非连通图至少有1+8=9 个顶点。 2. 有。</p><p>2、第第 5 章章 递归递归 教材中练习题及参考答案 1 有以下递归函数 void fun int n void fun int n if n 1 printf a d n n else printf b d n n fun n 1 printf c d n n 分析调用 fun 5 的输出结果 解 调用递归函数 fun 5 时 先递推到递归出口 然后求值 这里的递归出口语句是 printf a d。</p><p>3、第第 4 章章 串串 教材中练习题及参考答案 1. 串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。 答：从存储方面看，串中每个元素是单个字符，在设计串存储结构时可以每个存储单 元或者结点只存储一个字符。从运算方面看，串有连接、判串相等、求子串和子串替换等 基本运算，这是线性表的基本运算中所没有的。 2. 为什么模式匹配中，BF 算法是有回溯算法，而 KMP 算法是无回溯算法？ 答：。</p><p>4、第第 9 章章 查找查找 教材中练习题及参考答案 1. 设有5个数据do、for、if、repeat、while，它们排在一个有序表中，其查找概率分别 是p1=0.2，p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率分别为 q0=0.2，q1=0.15，q2=0.1，q3=0.03，q4=0.02，q5=0.01，该有序表如下： （1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。 （2）分别计算顺序查找的查找成功和不成功的平均查找长度。 （3）分别计算折半查找的查找成功和不成功的平均查找长度。 答： （1） 对该有序表分别采用顺序查找和折半查找时的判定。</p><p>5、第第 8 章章 图图 教材中练习题及参考答案 1. 图G是一个非连通图，共有28条边，则该图至少有多少个顶点？ 答：由于G是一个非连通图，在边数固定时，顶点数最少的情况是该图由两个连通分 量构成，且其中之一只含一个顶点（没有边），另一个为完全无向图。设该完全无向图的 顶点数为n， 其边数为n(n-1)/2，即n(n-1)/2=28，得n=8。所以，这样的非连通图至少有1+8=9 个顶点。 2. 有一个如图 8.2（a）所示的有向图，给出其所有的强连通分量。 答：图中顶点0、1、2构成一个环，这个环一定是某个强连通分量的一部分。再考察顶 点3、4，它们到这个。</p><p>6、第第 4 章章 串串 教材中练习题及参考答案 1. 串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。 答：从存储方面看，串中每个元素是单个字符，在设计串存储结构时可以每个存储单 元或者结点只存储一个。</p><p>7、第第 10 章章 内排序内排序 教材中练习题及参考答案 1. 直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时，时间 复杂度各是多少？ 答：含有n个元素的初始数据正序时，直接插入排序算法的时间复杂度为O(n)。 含有n个元素的初始数据反序时，直接插入排序算法的时间复杂度为O(n2)。 含有n个元素的初始数据全部相等时，直接插入排序算法的时间复杂度为O(n)。 2. 回答以下关于直。</p><p>8、第第 10 章章 内排序内排序 教材中练习题及参考答案 1. 直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时，时间 复杂度各是多少？ 答：含有n个元素的初始数据正序时，直接插入排序算法的时间复杂。</p><p>9、练习题2习题2 2 2 3 2 4 2 5和2 6 2 2设计一个算法 将x插入到一个有序 从小到大排序 的线性表 顺序存储结构 的适当位置上 并保持线性表的有序性 voidInsert SqList 2 3设计一个算法 将一个带头结点的数据域依次为a1 a2 an n 3 的单链表的所有结点逆置 即第一个结点的数据域变为an 最后一个结点的数据域为a1 voidReverse LinkList。</p><p>10、第第 1 章章 绪论绪论 教材中练习题及参考答案 1. 简述数据与数据元素的关系与区别。 答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数 据的基本单位，是数据的个体。数据元素与数据之。</p><p>11、第第 7 章章 树树和二叉树和二叉树 教材中练习题及参考答案 1. 有一棵树的括号表示为 A(B，C(E，F(G)，D)，回答下面的问题： （1）指出树的根结点。 （2）指出棵树的所有叶子结点。 （3）结点 C 的度是多少？ （4）这棵树的度为多少？ （5）这棵树的高度是多少？ （6）结点 C 的孩子结点是哪些？ （7）结点 C 的双亲结点是谁？ 答：该树对应的树形表示如图 7.2 所示。 （1）这棵树的根结点是 A。 （2）这棵树的叶子结点是 B、E、G、D。 （3）结点 C 的度是 2。 （4）这棵树的度为 3。 （5）这棵树的高度是 4。 （6）结点 C 的孩子结点是 E。</p>