数据结构课后习题解答

《数据结构课后习题解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章绪论一、基本问题问答：1、什么叫数据结构？如何理解“数据结构”？如何树立数据结构的学习体系？广义上的数据结构指的是：逻辑结构和物理结构。狭义上的数据结构专指逻辑结构，就是元素间的逻辑关系，主要类型有：集合型，线性结构，树型，图型！整个数据结构的课程就是围绕着以上儿种数据类型展开的，加上基于这些结构的某木操作:插入，删除，査找，取元素，取长度等等。另外，述有基于这些数据结构的鮫为复杂的算法:杳找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的部分，这一部分实际上主要在探讨算法，而不在是结构木身了。算法的概念将在片而提到。2、数据的物理结构和逻辑结构定义数据结构，当

2、计算机程序运行时，程序就按照定义给这些数据分配了空间。而数据定义,是在定义其逻辑结构。以链表为列，在实际定义时，一个个的结点，由于其指针域可以指向另一个结点，那么依靠这种指向关系，就可在逻辑上建立起一条链状结构！但是，在实际的程序执行时，是不会有这样的一条链的，而是通过在一个结点空间的某个空间内填入了下一个结点的地址！这样的每个有数据和地址的结点，才是其物理结构。3、算法的概念、分析,算法时间复杂度的含义及分析算法就是解决问题的方法或策略。一个算法好与坏的评价标准是：正确，可读，從壮，效率高，空间省！设计算法时，应该按照严教材上关于类C(或类P)语言的描述來作，格式为：statusfun_n

3、ame{〃算法说明for{....};//典型功能及复杂语句后加注释}//fun_name注意写好注释！不求多，但求粘！时间复杂度：分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复杂度考杏的是“某数量级”的概念，BP：T(n)=0(f(n))中,存在正的常数C和nO,使得当n>=nO时，0<=T(N)<=C*F(N)当空间复杂度为0(1)时，称算法为就地工作(原地工作)。算法时间复杂度的分析：时间复杂度的分析说到底是分析当系统规模增人时，系统所耗费时间的数量级。数量级的定义见上。简而言之，222,6nA2,"2是同-•数量级，因为山nT可推出其它两个(常数相乘)。此外，当时

4、间复杂度的公式中出现n的多项式时，应该以髙阶为准。因为此时影响总体变化规律的是高阶项的值。在分析时间复杂度时，应该以程序或算法中执行次数最多的语句为准，通常情况F是最内层循环的时间复杂芫，最内层语句的执行次数计算出來后，取最高的次数，然后去掉该项中的常数因子即可。空间复杂度的度量主要是看当系统规模n增大时，系统所占用的额外空间是否也在增大，按怎么的规律增大。如果没有增人，即额外空间始终是个常数，算法就是原地工作！4、算法设计规范1>在算法设计屮，第一个牵涉到的概念是：算法说明。它是写在过程或函数首部以下的注释内容。虽是注释内容，却是必不可少的。在测试屮也占有相当大的作用。此说明主要包括：算法

5、的功能，参数表中各参数的含义及输入输出定义;算法中引用了哪些全局变量或外部定义的变量，它们的作用，入口初值，以及应该满足哪些限制条件。女链表是否带头结点，表中元素是否有序，如果令序是递增还是递减等等！必要时，算法说明还可川来陈述算法思想，采川的存储结构等。递归算法的说明特別重要，读者应该力求将它写为算法的严格定义。儿个例子：2.29procedureDifferenceSqlist(VARa;Sqlist;b,c:Sqlist);｛删去增序顺序表中那些既在增序顺序表中B出现又在增序顺序表C中出现的元素｝2.33procedureSqlistlinkedlist(VARlc,Id,loinke

6、dList;llinkedList);｛将线性表II分割为3个循环链表lc,ld和Io,｝｛其中每个循环链表只含一类字符,分别为［7V..Z］、［O..9］和其它字符。｝2＞注释与断言在难懂的语句和关键的语句(段)Z后加以注释可以大大提高程序的可读性。注释要恰当，并非越多越好；此外，注释句的抽象程度应略高于语句(段)。断言是注释的一种特殊写法，它是一个逻辑谓词，陈述算法执行到此点时应满足的条件，即这种形式：当、、、时，、、。最重要的就是算法的入口断言与else分支断言。如果算法不含有参数佥性检测的代码段，书写入口断言是最低限度的要求。3＞输入、输出三种方式：a、通过专门的输入/出语句:rea

7、d,write,scant,printf等b、通过参数表中的参数传递c、通过全局及外部变量4＞错误处理三种处理方式：a＞error语句实现b、通过函数返回错误代码或错误状态值c^exit语句实现提倡使用第二种方式来实现错谋处理5＞语句的使用与算法结构避免使JUgoto语句，算法结构结构应该同层次对齐，卞一层向上一层缩进两格，并以适当的符号标识语句段的开始与结束：［］,｛｝6＞基本运算未明确要求的，不得直接川教