C语言公共基础知识

公共基础知识一.数据结构1算法的基本特征：可行性、确定性、有穷性、拥有足够的情报2算法的基本要素：①对数据对象的运算和操作（+-*/）②算法的控制结构，及运算或操作间的顺序3数据结构的内容：数据元素的信息、数据的前后关系4数据的存储方式：顺序存储结构、链式存储结构*5线形结构的满足条件：①有且只有一个根结点②每一个结点最多有一个前件，也最多有一个后件（及一个挨着一个）（非线性结构没有以上条件，如树形结构）*6数据结构的类型：线性结构、树形结构、网状结构、元素7线性表的顺序存储结构:①线性表中所有元素所占的存储空间是连续的②线性表中各元素在存储空间中是按逻辑顺序依次存放的8线性表包括顺序线性表和线性链表二.栈、队列和树1栈的定义:它是一种特殊的线性表．．．，他所有的插入与删除都限定在表的同一端进行。在栈中，一端是封闭的，另一端是开口，允许插入和删除元素。允许插入的一端称为栈顶，另一端称为栈底，当栈中没有元素的时候称为空栈。*2栈的特点：后进先出、先进后出3栈的基本运算有三种：入栈、退栈和读栈顶元素4队列的定义：只允许一端进行插入，而另一端只进行删除的线性表。允许删除的一端称为队头，允许插入的一端称为队尾*5队列的特点：先进先出，后进后出6循环队列的运算：入队运算、退队运算*7树是一种简单的非线性．．．结构*8树的各部分的相关术语根结点：没有前件的结点（只有一个）父结点：只有一个前件的结点子结点：有多个后件的结点叶子结点：没有后件的结点度：在数结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度深度：即一个树结构拥有的层数子树：在树中，以某个结点为根构成的树称为该结点的子树9空二叉树没有结点，非空二叉树有且只有一个根结点10二叉树的最大度数为2*11满二叉树：除了最后一层外，其它各层的结点都有两个字结点（即第n层有2的n-1方个结点）*12完全二叉树：除了最后一层外，其它各层的结点数均达到最大值，最后一层缺少若干结点*13二叉树的性质①二叉树的第n层，最多有（2的n-1次方）各结点②深度为n的二叉树中，最多有（2的n次方-1）个结点③对任何一颗二叉树，叶子结点总比度为2的结点多一个，即叶子结点数为n+1（n表示度为2的个数）④具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示去log2n的整数部分⑤一个二叉树的结点数等于n+2*m（n表示度为1的个数，m表示度为2的个数）*14二叉树的遍历可分为3种：前序遍历，中序遍历，后序遍历（见下方说明）即二叉树的遍历结果为ABDHEICFJG15线性表不管是顺序存储，还是链式存储的结构，都只能用顺序查找*16排序方法有：冒泡排序、简单插入排序、简单选择排序、快速排序、堆排序（在最坏情况使用堆排序效率最快）三．程序设计*1结构化程序设计方法的原则：自顶向下、逐步求精、模块化、限制使用goto语句2程序结构包含有：顺序结构、选择结构、重复结构*3面向对象包括对象、类和实例、消息、继承、多态性4对象的基本特点：标识唯一性、分类性、多态性、封装性、模块独立性好5消息传递是对象间通信的手段，一个对象通过向另一ABCDEFHIJG对象发送信息来求其服务6继承是指能够直接获得已有的性质和特征，而不必重复地定义它们7对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性四.软件工程基础1计算机软件包括了：程序、数据、文档2软件的特点①软件是一种逻辑实体，具有抽象性②软件没有明显的制作周期③对硬件和环境具有依赖性④软件在使用期间不存在磨损、老化问题⑤软件复杂性高，成本昂贵⑥软件开发涉及诸多的社会问题*3软件的分类：①系统软件（egC语言）②应用软件（egWord/QQ）③支撑软件（开发和维护软件产品的工具软件）4软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性5软件的周期包括：软件定义期、软件开发期、运行维护期*6需求分析工作：需求获取、需求分析、编写需求规格书和需求评审7需求分析方法：结构化分析方法、面向对象的分析方法*8结构化分析方法的常用工具：数据流图、数据字典、判定表、判定树9软件需求规格说明书是确保软件质量的有力措施，是软件开发过程中的重要文档之一*10软件设计基本的原则：①模块化（划分数目不宜太多或太少）②抽象（有概gai括性）③信息隐蔽性④模块独立性（要求内聚性高、耦合性低）11软件概要设计的基本任务：①设计软件系统结构②数据结构及数据库设计③编写概要设计文档12结构图有4种模块类型：协调模块、传入模块、变换模块、传出模块*13过程设计工具：程序流程图（PFD）、N-S图、PAD图、PDL*14软件测试有许多种方法，根据软件是否需要被执行，可分为静态测试和动态测试（上机测试），按照功能划分，可分为白盒测试（各模块测试）和黑盒测试（举例测试）15白盒测试包括：逻辑覆盖测试（模块测试），基本路经测试16黑盒测试地方法有：等价类划分法、边界值分析法、错误推测法*17软件测试的实施的4个步骤：单元测试、集成测试、确认测试（验收测试）和系统测试*18软件调试方法：强行排错法、回溯法、原因排除法五.数据库设计基础1数据库是指长期存储在计算机内的、有组织的、可共享的数据集合，它具有两大特点即“集成”和“共享”2数据库管理系统的功能：①数据模式定义②数据存取的物理构建③数据操纵④数据完整性、安全性的定义与检查⑤数据库的并发控制与故障恢复⑥数据的服务*3数据管理技术的发展经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段*4数据库系统的基本特点：①数据集成性②数据的共享相高，赘余性低③数据独立性高④数据统一管理与控制5数据库系统的三级模式．．结构：概念nian模式（ASCll码）外模式（显示给用户看）、内模式（物理模式，如电信号）6数据模型．．的三要素：数据结构、数据操作和数据约束7数据模型的类型：①概念数据模型②逻辑数据模型③物理数据模型*8实体间联系的类型：一对一、一对多、多对多*9几何图形表示E-R模型中的三个概念：①实体集表示法（矩形）②属性表示法（椭圆）③联系表示法（棱leng形）*10关系模型的完整性约束：①实体完整性约束②参照完整性约束③用户定义的完整性约束*11关系代数的基本运算：①投影运算（pai[A](R)）A为R的属性列②选择运算6F（R）F表示选择条件③笛卡尔积R*S*12关系代数的扩充运算：交、连接、除13数据库管理工作：①数据库的建立②数据库的调整③数据库的重组④数据库安全性与完整性控制⑤数据库的故障恢复⑥数据库监控常见考点算法的空间复杂度是指算法执行过程中所需要的存储空间软件工程的3个要素是：工具、过程、方法软件开发离不开系统环境资源支持，其中必要的测试数据属于辅助资源结构化程序设计主要强调的是：程序的易读性关系模型较之格式化模型（网状模型、层次模型）有以下优点：数据结构比较简单、具有很高的数据独立性、可以直接处理多对多的联系、以及有坚实的理论基础算法的复杂度有时间复杂度和空间复杂度。算法的时间复杂度是指执行算法需要的工作量，可以用执行算法过程所需基本运算的执行次数来度量；算法的空间复杂度是指算法执行过程中所需要的存储空间软件工程研究内容主要包括：软件开发技术和软件工程管理数据库保护分为：安全性控制、完整性控制、开发性控制性和数据的恢复算法的有穷性是指：算法程序的运行时间是有限的需求分析阶段的任务是确定软件系统功能程序流程图中带有箭头的线段表示的是控制流数据流程图中带有箭头的线段表示数据流模块之间的耦合包括：内容、公共、外部、控制、标记、数据、非直接耦合软件需求规则说明书具有以下几个方面的作用：①便于用户、开发人员进行交流和理解②反映出用户问题的结构，可作为软件开发的基础和依据③作为确认测试和验收的依据数据库设计包括数据库概念设计和数据库逻辑设计两大方面数据库设计过程3个步骤是：概念设计、逻辑设计、物理设计关系表中，每一行成为一个元组，对应表中的一条记录；每一列成为一个属性，对应表中的一个字段数据库设计可分为以下几个阶段：需求分析阶段、概念设计阶段、物理设计阶段、逻辑设计阶段、实施阶段及数据库运行和维护阶段确认测试的任务是验收软件的功能和性能，以及其他特征是否满足需求；集成测试的主要目的是发现与接口有关的错误顺序存储结构在数据的插入和删除操作上的效率比链式存储结构的要低线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构、顺序存取的存储结构树的根结点数目是0（空树）或1数据库是一个数据集合数据库系统包括数据库和数据库管理系统数据模型数据库设计的核心软件生命周期中花费费用最多的阶段是软件维护为了提高测试的效率，应该集中对付那些错误群集的程序程序设计的主导风格是：清晰第一、效率第二数据处理的最小单位是数据项；若干的数据项组成数据元素数据库系统的核心是数据库管理系统软件定义期间包括可行性研究和需求分析两个阶段软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护和预防性维护软件测试的重要特征有：测试的挑剔性、完全测试的不可能性及测试的经济性软件测试过程按4个步骤进行，即：单元测试、集成测试、确认测试和系统测试数据处理是指将数据转换为信息的过程数据的物理独立性是指数据的物理结构的改变，不会影响数据库的逻辑结构数据模型包括：层次模型、网状模型和关系模型数据库保护可分为：安全性控制、完整性控制、并发性控制和数据的恢复软件开发模型包括瀑布模型、快速原型发模型和螺旋模型关系R和S，若R-(R-S)，则其中R-S表示属于R但不属于S，R-(R-S)表示数据库技术的根本目标是要解决数据的共享问题二叉树的遍历前序遍历ABDHEICFJG中序遍历HDBEIAJFCG后序遍历HDIEBJFGCA在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑设计阶段常见的排序方法有插入排序、交换排序、选择排序软件测试有许多种方法，根据软件是否需要被执行，可分为静态测试（无须被执行）和动态测试（上机测试），按照功能划分可分为白盒测试（各模块测试）和黑盒测试（举例测试）数据流程图（DFD）可以用于需求分析阶段软件按功能可以分为：应用软件（教务管理软件）系统软件（编译程序、操作系统、汇编程序）支持软件（介于两者之间，协助用户开发软件的工具软件）几何图形表示E-R模型中的三个概念：①实体集表示法（矩形）②属性表示法（椭圆）ABCDEFHIJG③联系表示法（棱leng形）程序流程图中棱形框包括逻辑判断错题集#defineF(x,y)xy?y:xMain(){intx,y,z;x=5;y=10;z=10*F(x+y,x*y);printf(“%d\n”,z);}输出结果为：此题容易错解为：z=10*(x+yx*y?x*y:x+y)=10*50=500;正确的解法是：z=10*x+yx*y?x*y:x+y=5+10=15Main(){inta[10]={1,2,3},*p;p=a;Printf(“%d\n”,p);Printf(“%d\n”,p+5);}假设第一个Printf语句输出的是204，则第二个Printf语句输出的结果是：分析：解此道题首先要明白第一个Printf语句输出是a的首地址，又因为a[10]定义是int,则数组中每一个元素占两个字节，则p+5移动了10字节，所以第二语句输出的值是214Main(){intx=1,y=5;For(;x=10;x++){If（y2）break;Elsey-=5;}Printf(“%d”,x);}输出结果为：分析：此题的易错点在执行语句break后，x是否需要+1，其实语句break在跳出循环后，并没有+1，所以答案为1Main(){intx=5,y=2;Printf(“%d”,++x+y,++y-x);}输出结果为：分析：解此道题要明白%d对应哪个数，并且它们的运算顺序是怎样的；%d对应的数是++x+y，而它们的运算顺序是：先运算++y-x，再运算++x+y，所以结果为9.如果将输出语句改为Prin