第1章基本概念

-1-第1章基本概念1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。●数据：指能够被计算机识别、存储和加工处理的信息载体。●数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。●逻辑结构：指数据元素之间的逻辑关系。●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.●线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。-2-答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢?即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。1.3常用的存储表示方法有哪几种?答：常用的存储表示方法有四种:●顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。●链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。●索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。●散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。-3-2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.4为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。3.2链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3循环队列的优点是什么?如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。-4-3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。4.1简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。答：●空串是指不包含任何字符的串，它的长度为零。空白串是指包含一个或多个空格的串，空格也是字符。●串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。-5-6.2一棵度为2的有序树与一棵二叉树有何区别?答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。答：三个结点的树如下：只有两种形态○○/\|○○○|○三个结点的二叉树如下所示：有五种形态：(1)(2)(3)(4)(5)○○○○○/\//\\○○○○○○/\/\○○○○6.4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?解：设该树中的叶子数为n0个。该树中的总结点数为n个，则有：n=n0+n1+n2+…+nm(1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有-6-双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*nm(2)联立(1)(2)方程组可得：叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：(1)各层的结点数目是多少?(2)编号为i的结点的双亲结点(若存在)的编号是多少?(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?解：(1)层号为h的结点数目为kh-1(2)编号为i的结点的双亲结点的编号是：|_(i-2)/k_|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果.以下/表示整除。(3)编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1.6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。6.7在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针?解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;6.9试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。答：-7-(1)前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。(2)中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。(3)前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。(4)前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。6.15在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?答：分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。6.18高度为h的严格二叉树至少有多少个结点?至多有多少个结点?答：所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。6.21假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.(1)为这8个字母设计哈夫曼编码。(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?解：(1)哈夫曼编码根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000-8-(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.612.61/3=0.87=87%其平均码长是等长码的87%。所以平均压缩率为13%。7.1在图7.23所示的各无向图中：(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?答:(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图：(a)、(c)、(d)是连通图，(b)不是连通图，因为从1到2没有路径。