2022年数据结构基础 .pdf

1.几个最初等的基本概念？ 数据：是用于描述客观事物的数值或字符，它在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称。eg：整数，实数，字符串等都是数据。 数据元素：也称为结点，它是数据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项组成。 数据项：是数据的不可分割的最小单位；eg：学生记录就是一个数据元素，这个数据元素由学好、性别、姓名等数据项组成。 数据对象：数据对象是性质相同的数据元素的集合，是数据的一个子集。eg：大写字母就是一个数据对象，大写字母数据对象是集合A,B,.Z 。2.什么是数据结构？数据结构是研究什么的？ 数据结构的定义：数据结构是指相互之间存在某种关系的数据元素的集合。 数据结构的研究方向：数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三个方面的内容：对数据的运算和操作，即算法；数据的逻辑结构；算法的设计取决于数据的逻辑结构数据的物理存储结构；算法的实现取决于数据的物理存储结构3.数据结构的形式化定义数据结构是一个二元组，如数据结构DS=（ D， R）其中， D 是数据元素的有限集合，R 是定义在 D 上的关系的有限集合。eg：有如下数据，即一个矩阵：|26 3 1| |8127 4| |510911| 其对应的二元组表示为：B=（D，R）D=2 ，6，3，1，8，12，7，4，5，10，9，11 R=r1,r2 r1 表示行关系， r2 表示列关系它们各自定义如下：r1=, r2=, 4.数据结构的逻辑结构是什么？它有哪些分类？ 数据结构的逻辑结构：数据结构的逻辑结构描述的是数据元素之间的逻辑关系，它与数据的存储结构无关，同一逻辑结构可以对应多种存储结构 逻辑结构的分类：线性结构该结构中的结点之间存在一一对应关系，开始结点与结尾结点是唯一的，其余的结点都有且仅有一个前导与一个后继。eg：线性表非线性结构该结构中的结点之间存在一对多或者多对多的对应关系eg：树型结构、图型结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 5.数据结构的物理结构是什么？常见的数据存储方法有哪些？ 数据的物理结构：数据的物理结构也叫存储结构，是数据的逻辑结构在计算机中的表示（也叫映像） 。它包括数据元素的表示和数据关系的表示。当数据元素是由若干数据项组成时，对数据项的表示就称之为数据域。 数据的存储方法：数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储和非顺序存储。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构。顺序存储是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系； 非顺序存储是借助指针来表示数据元素之间的存储关系；指针是用来指示数据元素的存储地址的。 数据结构的四种存储方法：（1）顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。此种结构通常是借助数组类型来描述的。（2）链式存储方法该方法结点间的逻辑关系是由附加的指针字段表示的，并不要求逻辑上相邻的结点在物理位置上也相邻。此种结构通常是借助指针类型来描述的。（3）索引存储方法该方法在建立结点信息的同时，也建立了附加的索引表，索引表中的每一项称之为索引项，索引项的一般形式是：（关键字，地址） 。关键字标识唯一一个结点，地址作为指向结点的指针。此种结构可以提高数据查找的速度。（4）哈希存储方法即散列存储方法， 该方法根据结点的关键字通过哈希函数直接计算出该结点的存储地址。此种结构本质上是顺序存储的扩展。6.数据的运算与存储结构的关系？ 数据的运算：一个数据结构所包含的数据运算的种类和数目以及每个运算中的参数数目及类型， 都应该依据该数据结构的实际用途和需要来量身定做。它们只有在一定的数据结构上具体实现后才具有真实的意义。因此数据结构运算的实现和执行效率都与存储结构有关。7.什么是数据类型？ 数据类型：数据类型是一个值的集合以及定义在这个值集上的一组操作的总称。eg：c 语言中， int 是一种整型数据类型，其值集为某个区间上的整数（16 位机上为 -3276832767） ，而定义在这个值集上的操作有+、 -、* 、 等运算。8.什么是抽象数据类型（ADT ）？ 抽象数据类型 （ADT ） ：抽象数据类型是指一个数学模型以及定义在该数据模型上的一组操作。ADT 通常由用户自定义，ADT 由基本数据类型组成，并且包括一组相关的操作。其特征是使用与实现分离，可以实现封装和信息隐藏，即在ADT 设计时，可以把类型的声明与实现分离开来。9.什么是算法？算法有什么特性？ 算法：算法是指对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令都表示一个或多个操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 算法的特性：有穷性： 对于任意一组合法的输入值，在有穷时间内执行有穷步骤后一定可以结束。确定性： 对于每种情况下所应执行的操作，在算法中都要有明确的规定，使算法的执行者或阅读者能够明确该算法的含义及其是如何执行的，并且在任何条件下，算法都只有一条执行路径。可行性： 算法中的所有操作都必须在有限次数内完成，并且可以通过已经实现的基本操作进行运算。有输入：算法必须有输入量，没有输入的算法是不存在的。有输出：一个算法对信息加工后必须要产生一个结果。ps：算法与程序不同，程序可以不满足有穷性，eg：windows 操作系统在用户未操作之前将一直处于等待的循环中，直到出现新的用户操作为止。这个等待过程就是无穷的。由于一般的程序都不会出现这种情况，因此多数情况下对算法和程序并不严格区分。10.一个好的算法应该满足哪些要求？正确性：要求设计的算法能够正确的执行预先规定的功能和性能要求。可执行性：要求设计的算法能够方便的使用，此特性也称用户友好性。可读性：要求设计的算法应该易于理解，其逻辑必须是简单、清晰、有结构化的。健壮性： 要求设计的算法有很好的容错性，能提供异常处理，不会因一些异常情况而中断甚至崩溃。高效率与低存储：要求所设计的算法的执行时间越短越好，而该算法在执行过程中所需要占用的存储空间越小越好。11.什么是算法的时间复杂度？ 算法的时间复杂度：算法中的基本操作的循环次数是待解决问题规模n 的某个函数f（n） ，算法的时间量度记作：T（n）=O（f（n） ）它表示随着问题规模n 的增大，算法执行时间的增长率与f（n）的增长率相同。称之为算法的渐进时间复杂度，简称时间复杂度。特别的， 所说的时间复杂度通常是指最坏情况下的时间复杂度，即分析最坏情况估算算法执行时间的上界。影响程序运行时间的因素是多方面的，如机器的运行速度，编译程序产生的目标代码的质量，程序的输入等。我们把一个程序运行的时间定义为函数T（n） 。n 是该程序输入数据的规模，而不是某一个具体的输入，T（n）的单位是不确定的，一般将其看做在一台特定计算机上执行的指令条数。当讨论一个程序的运行时间T（ n）时，需要关注的不是T（n）的具体数值，而是它的增长率。我们称函数f（ n）为 T（n）增长率的上界，是指存在一个常数C 和整数 n。 ，当n=n。时， T（n）=C*g(n), 记为：T（n）= （ g（n） ） 。eg：设函数 T（n）=3*n3+2*n2, 证明： T（n）=O（n3） ，T（ n）=（n3） ；证明：采用数学归纳法证明取 n。=0，C=5，则，当n=0 时，有： 3*n3+2*n2=C*n3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 我们还可以证明函数3n 不是 O （2n） ,即 3nO （2n） 。 用反证法，假设 3n=O （2n） ，则存在常数C 和 n,当 n=n。时 ,3n=（3/2） n 可以大雨任意大的正数，因而这样的常数C 不存在。一个程序运行时间的增长率将最终决定该程序在计算机上能解决多大规模的问题。因此我们说一个运行时间为O（n2）的程序较之运行时间为O（n3）的程序有更好的时间复杂性。至于常数因子通常忽略不计。12.如何分析一个程序的时间复杂度？ 首先，针对程度基本成分S 的执行时间T（S）引入如下记号： T（x）为取变量或常量x 之值所消耗的时间，相当于汇编语言中取数并送给一个寄存器加载的这段时间。 T（.v）为取变量v 的地址之值所消耗的时间，凡是地址在编译阶段已经分配完的，其T（.v）=0。 T（=）为赋值操作所消耗的时间，相当于保存一个数所消耗的时间。 T（ ）执行运算操作 所消耗的时间。eg:T(+),T(-), 及 T(*) 和 T(/) 等。 T（call/return ）执行函数调用与函数返回所消耗的时间。 T（par）将参数par 传递给函数所消耗的时间。 其次，计算复合结构的增长率可用加法规则和乘法规则：设 T1(n)=O(f(n),T2(n)=O(g(n),则加法规则设 T1(n) 和 T2(n)是程序段P1 和 P2的运行时间， 则执行 P1 之后紧接着执行 P2 的运行时间T1(n)+T2(n) 是 O(maxf(n),g(n)。即：T1(n)+T2(n)=O(maxf(n),g(n) 乘法规则T1(n) T2(n)=O(f(n)g(n) 再次，一般来说，分析程序的时间复杂性是分块进行的：先求出程序中各语句、各模块的运行时间；再求整个程序的运行时间；13.怎样具体分析一个程序中的各种语句及模块的时间复杂度？表达式和赋值语句设表达式的语法格式：exp=常数 |变量 |F-name(e1,em)|(exp exp) 其中第三项为函数调用，F-name 是函数名， e1, ,em 是实在参数，用加法规则可计算时间如下：T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T( )+T(exp) T(F-name(e1,em)=T(call/return)+m*T(par)+T(F-body) eg:分析表达式c=a+b 的执行时间得：T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 对应于 c=a+b 的汇编程序为：loadainR1 loadbinR2 add R2toR1 load .cinR2/*取变量 c 的地址放入R2*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - store R1in R2 indirect/* 间接存数 */ 或者是loadainR1 add btoR2 store R1 inc/*此处可认为T(.c)=T(b)=0,*/ 由此例可见， 具体机器细节、 寄存器分配策略、编译与优化等，都给计算准确的执行时间带来极大困难，因此通常是对高级语言程序直接分析，不得已时才分析其对应的汇编程序。对高级语言的分析不必如汇编般细致，往往忽略许多复杂、次要的因素而注重分析时间的增长率。根据这种想法，每个赋值语句或读/写语句的运行时间通常取O(1)( 表示增长率是常数 )，但如果赋值语句右部表达式exp 中含有函数调用，那么则要考虑计算函数值所消耗的时间。语句序列一个语句序列s1. ,sk的运行时间由加法规则确定，为序列中消耗最多的语句的运行时间：T(s1. ,sk)=max(T(s1),T(sk) 条件语句T(if(B)s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 其中T(B) 是条件B 的测试时间；T(else)是条件语句内部的控制流动时间，通常取：T(B)+T(else)=O(1) 。根据上式显然有：T(if(B)s)=O(1)+T(s) switch 语句设 s 是如下语句switch(E) caseE1:s1; caseEk:sk; default :sm k 则 T(s)=T(E)+T(Ei)+maxT(s1), ,T(sk),T(sm) i=1 通常取： k T(E)+T(Ei)=O(1) i=1 for 语句循环次数已知时，循环语句的运行时间是n 次重复执行循环体所消耗的时间总和，n 为循环重复次数。每次重复所消耗的时间包括两部分：循环体本身的运行时间；计算循环参数、测试循环终止条件和跳回循环开头所消耗的时间。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - n T(for(i=1;i=n;i+)s)=(T(s)+T(i=1)+T(i=n)+T(i+)+T(for) i=1 其中 T(for) 代表跳回循环开头所消耗的时间，通常取：T(i=1)+T(i=n)+T(i+)+T(for)=O(1) n 具体计算时，一般应求级数T(s)之和，有时可以用乘法规i=1则，将常数因子忽略不计，可以认为上述时间是循环重复次数n 和 m 的乘积，其中m 是 n次执行循环体当中时间消耗最多的那一次运行时间。多层循环中， 要由内到外逐层分析。因此，当分析外层循环的运行时间时，内层循环应该是已知的；此时，我们把内层循环看成外层循环的虚幻体的一部分while 语句考虑循环次数未知的情形，应试图在循环体中找出与循环次数相关的变量，从而计算出循环次数，或循环的上/下限。设有语句while(B)s; 为分析方便，虚拟一个计数器i，使其成为：i=0;while(B)s;i+; 并认为i+的计算不消耗时间。设RT。表示某一次循环开始执行时的绝对时间，则可得关于循环的定时不变式如下：RT=RT。 +(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中T(while) 表示测试循环中指条件所消耗的时间，T(j) 表示跳回循环开头所消耗的时间。可以简化为：T(j)=T(while) ，因此，若i 已知，则：T(while(B)s)=RT-RT 。 =(i+1)T(B)+iT(s)+(2i+1)T(while) 循环的执行时间终究是有限的，除非它是死循环。常常可以找到循环重复次数的上/下限或每次重复执行循环体所消耗的时间的上/下界故令 I=i-min,i-max,iI，则：T(while(B)s)=(I+1)T(B)+I T(s)+(2I+1)T(while) 其中的去件运算定义为：a,b c,d=ac,bd eg1:设循环重复次数I=0,2,T(B)=3,5(毫秒 ),T(s)=7,9,T(while)=0,则：T(while(B)s)=1,3T(B)+0,2 T(s) =1 T(B)+0T(s),3 T(B)+2 T(s) =3,5,33,5+27,9 =3,33( 毫秒 ) eg2:设有正整数x。试计算 x 的近视值，精确到小数点后一位，并分析算法的时间复杂度。解：程序片段如下： a=0; while(a+1)*(a+1)=x) a+; while(a+0.1)*(a+0.1)=x) a=a+0.1; 语句计算结果的整数部分，虚设计数器i 的值与变量a 一致。该语句结束时有：i=a= x。若 x0,x-max, 则 I=0, x-max是紧凑的上 /下限。 x-max 可以取计算机的一个字能装名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 下的最大正整数。设：T(a=0)=1(即1,1) T(while)=1 T(a+1)2=x)=T(a+0.1)2=x)=4 T(a+)=T(a=a+0.1)=2 则语句的执行时间可计算如下：1+（I+1） 4+I 2+（2 I+1）=8 I+6 对语句，显然有iJ=0,9,故其执行时间为：（J+1） 4+J 2+（2J+1）=8 J+5 =0,9 8+5 =0，72+5 =5,77 整个程序片段的执行时间是I 8+6+5,77=I 8+11,83 它依赖于x-max 函数调用若程序中只有非递归调用，则从没有函数调用的子函数开始，计算所有这种子函数的运行时间。 若考虑到有函数调用的任一函数P，在 P 调用的全部子函数的运行时间都算完之后，即可开始计算P 的运行时间。若程序中有递归调用则令每个递归子函数对应于一个未知的时间开销函数T(n), 其中 n 是子函数的大小，之后列出关于T 的递归方程并求解。goto 语句仅当 goto 语句从一个循环跳到紧跟在该循环之后的一个程序段时，goto 语句的用法才是合理的。分析运行时间时，若 goto 语句在循环体内是有条件执行的，即当某条件完全形成后，才经 goto 语句跳出循环，把控制传到该循环彻底完成后才会执行的语句上，那么，若该条件没有完全形成，则不会跳出循环，即可认为由goto 语句引起的控制转移根本没有发生。eg：分析 “ 冒泡 ” 分类程序的运行时间。设 n 是一个常量，在主控制程序中已定义其可能达到最大值。voidBUBBLE(A) intAn; inti，j，temp；for(i=0;i=i+1;j-) if(Aj-1aj temp=Aj-1; Aj-1=Aj; Aj=temp; ; ; BUBBLE 的运行时间分析如下：语句的运行时间各为O(1) ，按加法规则，该组语句消耗的时间为：O(max(1,1,1)=O(1) 条件语句的运行时间为O(1) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 考虑循环语句。每次执行循环体耗时O(1),循环重复次数是n-i-1 ，故按乘法规则有：O(n-i-1)1)=O(n-i-1) 考虑外层循环。语句执行n-1 次；第 i 次执行循环体耗时O(n-i-1), 古按加法规则，整个程序的运行时间为：n-2 O（n-i-1） ）=O(n(n-1)/2)=O(n2) i=0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -