公共基础讲义第一部分

《公共基础讲义第一部分》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公共基础目录第一章：数据结构与算法（约占10分）算法数据结构树与二叉树查找技术习题一第二章：程序设计基础（约占4分）程序设计方法和风格结构化程序设计面向对象程序设计习题二第三章：软件工程基础（约占8分）无忧学校等级视频www.xuelixia-wuyouschool.cn软件工程几本概念结构化分析方法结构化设计方法软件测试程序的调试习题三第四章：数据库设计基础（约占8分）数据库系统的基本概念数据模型关系代数数据库设计与管理习题四第一章数据结构与算法（约占10分）1.1算法求1~100自己之间所有整数之和（s=1+

2、2+3+…100）main(){intk,s;k=1;s=0;while(k<=100)---条件表达式{s+k;---循环体语句k++;}printf(“%s=%d”,s);}1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述，也就是一种解决问题的方法*：算法不等于程序，它是优先程序的。2、算法的基本特征（1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得

3、出相同的输出。（3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。（4）拥有足够的情报。一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3.算法的基本要素:第一要素

4、：对数据对象的运算和操作1.算数运算+-*/2.逻辑运算NOTANDOR3．关系运算><>=<=<>4.数据传输第二要素：算法控制结构（决定了算法的执行顺序）顺序选择循环4.算法设计的基本方法1.列举法（列举所有解决方案）根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。2.归纳法（特殊—＞一般）适合于列举量为无限的情况通过列举少量的特殊情况，经过分析，最后找出一般的关系。3递推法（已知->未知）从已知的初始条件出发，逐次推出要求的各中间结果和最后结果）4递归法（逐层分解）

5、将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题………5减半递推法（对问题分而治之）“减半”是指将问题的规模减半，而问题的性质不变。所谓“递推”是指重复“减半”的过程6回溯法复杂应用，找出一个解决问题的线索，然后沿着这个线索逐步多次“探、试”5算法复杂度（一个算法所要付出的代价）主要包括时间复杂度和空间复杂度。（1）概念：时间杂度是指执行算法所需要的计算工作量含义：执行算法的过程中所需基本运算的执行次数来度量。（2）算法空间复杂度是指执行这个算法所需要的内存空间。下面的方

6、法不是用来度量算法的时间复杂度：1）算法程序的长度或算法程序中语句（指令）的条数2）算法程序所执行的语句条数3）算法程序执行的具体时间1.2数据结构的基本概念数据：所有能输入到计算机中并被计算机处理的符号的总称数据元素：数据的基本单位，在计算机程序中被作为一个整体进行考虑的符号的总称数据结构：数据结构是指相互有关联的数据元素的集合。2、数据结构的内容（1）数据的逻辑结构：数据元素之间所固有的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。（2）数据的存储结构（也称为物理结构）：在对数据进行处

7、理时，各数据元素在计算机中的存储关系数据的存储结构有顺序、链接等。1）顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。2）链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，

8、但影响数据处理效率。逻辑结构与物理结构的关系：a.一种逻辑结构可以用不同的物理结构来实现b.逻辑结构决定了算法的设计无忧学校等级视频www.xuelixia-wuyouschool.cnc.物理结构决定了算法的实现（3）对各种数据结构进行的运算。3、数据结构的图形表示表示数据结构有两种方法：二元关系表和图形例：一年四季的数据结构用图形可以表示成：一个数据结构除了用二元关系