公共基础部分讲座

1公共基础第一部分：数据结构与算法（约占10分）（理解）·算法·数据结构·树与二叉树·查找技术·习题第二部分：程序设计基础（约占4分）（背）·程序设计设计方法与风格·结构化程序设计·面向对象的程序设计·习题第三部分：软件工程基础（约占8分）（背）·软件工程的基本概念·结构化分析方法·结构化设计方法·软件测试·程序的调试·习题第四部分：数据库设计基础（约占8分）（理解+背）·数据库系统的基本概念·数据模型2·关系代数·数据库的设计与管理·习题第一部分：数据结构与算法一、算法·概念：算法是指计算机在解题的过程中实施某种方法。（算法是一个操作序列，有限长度，目的是解决某类问题。）·基本特征：可行性、确定性、有穷性、拥有足够的情报（要有输入和输出）.·算法的要素：-对数据对象的运算和操作（算术运算，逻辑运算，关系运算，数据传输）-算法的控制结构（顺序，选择，循环）·算法的描述方法：流程图和N-S图，算法描述语言·算法的复杂度：评价一个算法的好坏。-时间复杂度（算法的运行次数）影响计算工作量的主要因素（运算的次数，问题的规模）以下哪些不能用来衡量时间复杂度：A、算法的程序长度B、算法所执行的语句条数C、算法程序执行的时间在同一问题规模下可以用以下两点衡量算法的时间复杂度：A、平均性态分析B、最坏情况复杂分析-空间复杂度（运行时所占用的空间（内存空间））一个算法所包含的空间复杂度：A、程序所占用的空间B、输入的初始数据所占用的空间C、算法执行中所的额外空间。Main(){Inti,sum;For(i=0;i100;i++){If(i%2==0){Sum+=i;}}Printf(“%d”,sum);}3习题练习：1、下列描述中正确的是A、算法就是程序B、算法强调利用技巧提高程序的执行效率C、设计算法只需要考虑结果的可靠性D、以上说法都不对2、下列叙述正确的是：A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度指算法中程序的执行条数C、算法的有穷性表示算法必须在执行有限的步骤后结束D、以上三种描述都不对3、下列叙述正确的是A、一个算法的空间复杂度大，其时间复杂度也大B、一个算法的空间复杂度大，其时间复杂度必小C、一个算法的时间复杂度大，其空间复杂度比小D、以上三种均不正确4、算法的空间复杂度是指：A、算法程序的变量数量B、算法程序的指令条数C、算法各个控制变量所占的额外空间D、算法执行过程中所需要的存储空间二、数据结构目的：提高数据处理的效率（一是提高数据的处理速度，二是尽量节省在处理过程中所占用的空间）基本概念：·数据：在计算机科学中所能输入到计算机中并被计算机程序所处理的符号总称·数据元素：数据的基本单位，在计算机程序中通常通过一个整体进行考虑·数据结构：是相互之间存在一种或者多种特定关系的数据元素的集和基本内容：4线性表：·线性表就是线性结构·线性表的顺序存储结构称为顺序表，在顺序表中，所有元素的存储空间是连续的，逻辑顺序是依次存放的。·线性表在最坏的情况下删除一个元素需要移动N-1次，插入一个元素最坏情况下也需要移动n次栈：·先进后出（LIFO,FILO）·注意：在顺序结构下，栈的插入与删除运算都不需要移动表中的其他元素；栈顶指针反映了栈中元素的变化·栈的存储结构与运算存储结构：数组运算：入栈，出栈，读栈顶元素·在顺序结构下读元素指：将栈顶元素读出来，但是不会删除（但是删除需要先将元素读出来，之后再删除）读栈顶元素需要注意：读栈顶元素不会删除元素，只是将栈顶元素赋予一个变量，当栈顶元素0为null时表示栈空队列：·先进先出（FIFO）·一般情况下，队列在顺序存储结构中通常以循环队列的方式进行操作，方法是将最后一个位置在出队列时加入到队头中去·循环队列的容量：当rearfront时，容量是rear-font;(队列未满)当rearfont时，容量是m+(rear-font);(队列已满，并且已经返回)·循环队列的运算1、入队操作，在rear+1;2、出队操作，在front+1线性表总结：·在插入和删除时需要移动元素·由于使用数组作为存储结构，所以空间不好扩展·不便于对存储空间的动态分配5故：对于大的线性数据结构和变动频繁的数据结构不适应使用线性存储结构链式结构线性表：·存储方式：由两部分组成，一部分用来存储元素值，另一部分用来存储后一个（前一个）元素的位置。·特点：存储数据元素之间的空间可以不连续；各节点之间的存储关系与元素的顺序可以不一致；可以用线性结构存储，也可以使用非线性结构存储·头指针；最后一个节点的指针为null，当头指针为null是表示该表为空表·单链表：只有next指针·双向链表：有pre指针和next指针·循环链表：·删除和插入时都不需要移动元素习题：1、不属于线性结构的是：A、队列B、线性表C、二叉树D、栈2、数据的存储结构是指A、存储在外存的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示3、下列关于栈描述错误的是：A、栈是先进后出的线性表B、栈只是顺序存储的C、栈具有记忆作用D、对栈的插入与删除不改变栈底指针4、下列对于线性链表的描述正确的是A、存储空间不一定是连续的，且各个元素的顺序是任意的B、存储空间不一定是连续的，且前一个元素一定存储在后一个元素的前面C、存储空间必须是连续的，且前一个元素一定存储在后一个元素的前面D、存储空间必须是连续的，且各个元素的顺序是任意的5、下列关于栈的描述正确的是：A、在栈中只能插入元素不能删除元素B、在栈中只能删除元素不能插入元素C、栈是特殊的线性表，只能在一端插入和删除元素D、栈是特殊的线性表，只能在一端插入元素，在另一端删除元素6、下列叙述正确的是：A、一种逻辑结构只能有一种存储结构B、数据的逻辑结构属于线性结构，数据的存储结构属于非线性结构C、一个逻辑结构可以有多种存储结构，且不同的存储结构不影响程序的效率D、一个逻辑结构可以有多种存储结构，且不同的存储结构会影响程序的效率7、按照后进先出的原则组织数据的是A、队列B、栈C、双向链表D、二叉树8、下列叙述正确的是A、线性链表是线性表的链式存储结构B、栈和队列是非线性存储结构C、双向链表是非线性存储结构D、只有根节点的二叉树是线性结构9、栈的运算特点是后进先出。元素a、b、c、d依次入栈，则不能得到的出栈序列是（）。A.abcdB.cabdC.dcbaD.bcda10、数据结构分为逻辑结构和存储结构，循环队列属于11、数据的逻辑结构在计算机空间的存放形式称为数据的612、按“先进后出”原则组织数据的是13、数据结构分为线性结构和非线性结构，带链队列属于三、树和二叉树：·树是非线性结构·基本概念结点：若干个指向子树的分支结点的度：某结点拥有子结点的个数树的度：树中所有结点度的最大值叶子结点：度为0结点分支结点：度不为0的结点结点的层次（深度）：根为第一层，根的结点为第二层，依次类推树的深度：树中结点的最大层次称为树的深度·二叉树：分支节点的度最多为2·二叉树的基本性质：1、在二叉树的第k层上，最多有2k-1个节点2、在深度为m的二叉树中，最多有2m-1个结点3、在任意一棵二叉树中，度为0的节点的总比度为2的节点多一个4、具有n个结点的二叉树，其深度至少为log2n+1·满二叉树和完全二叉树1、满二叉树：除了最后一层，每一层都有两个结点2、完全二叉树（左子树一直存在）·注意：二叉树的存储结构中，除了可以将满二叉树和完全二叉树按层次顺序结构存储之外，其余均只能使用链式存储。二叉树的遍历：前序遍历：根，左，右中序遍历：左，根，右后序遍历：左，右，根习题：71、在一棵二叉树上，第五层的结点最多有几个A、8B、16C、32D、152、某二叉树中度为2的结点有18个，度为0的结点有3、一棵二叉树第六层的结点最多有几个4、在深度为7的满二叉树中，叶子结点有个5、下图三种遍历的结果四、查找技术：顺序查找和二分查找二分查找：只有顺序存储的有序表才能使用二分查找运行效率：顺序查找：n,二分查找:log2n排序:习题：1、长度为n的线性表，在最坏的情况下，下列各排序法对应的比较次数中正确的是A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为(n(n-1))/22、对长度为n的线性表进行顺序查找，在最坏的情况下需要比较多少次A、log2nB、n/2C、nD、n+1FCEADGB83、数据结构中能够用二分法进行查找的是A、顺序存储结构的有序线性表B、线性链表C、二叉链表D、有序线性链表4、在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为A、63B、64C、6D、75、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）第二部分：程序设计基础（约占4分）（背）一、程序设计的方法和风格程序设计的风格强调简单和清晰，程序必须是可以理解的。1、设计的风格程序设计的根本目标是要降低程序的复杂性和提高程序的可读性·结构要清晰：程序编写要做到清晰第一，效率第二；要求程序是模块化结构的，每个模块内部都由顺序、选择、循环三个基本结构组成·模块化：个模块的功能尽量单一·设计程序时应遵循“简短朴实”的原则·不好的程序另可重写，也不要去修补2、语言应用的风格·选择合适的程序设计语言·对一些程序设计语言中的灵活大，不易理解的语句尽量少用3、程序文本的风格·程序的层次要分明，在各层之间应采用缩进规则·符号要规范，变量名的命名要遵循“常用从简，专用从繁”的原则·在程序中加必要的注释，注释分为序言性注释和功能性注释·在程序中要合理的使用分隔符4、输入与输出的风格·在需要输入数据时，应该给出必要的提示·要对输入的数据进行检验，以确认有效性·输入的步骤和操作要简单·要给输出加注释二、结构化程序设计结构化程序设计方法的四条原则：1、自顶向下；2、逐步求精；3、模块化；4、限制使用goto。·自顶向下：总体—细节；全局—局部·逐步求精：对复杂程序设计子目标过渡·模块化：总目标分成小目标，上层模块决定做什么，下层模块确定怎么做·限制使用goto语句·语句尽可能的清晰1、结构化程序的基本特点·以控制结构为单位，只有一个入口和一个出口，使各模块之间的接口尽可能简单·顺序结构、选择结构、循环结构2、结构程序设计的基本原则·使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑9·选用的控制结构只准许一个入口和一个出口·复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现·程序语句组成容易识别的块，每块只有一个入口和一个出口·严格控制goto语句程序设计并不等于编程。编程知识程序设计整个过程的一小步三、面向对象的程序设计传统结构化程序设计方法的核心是算法，面向对象的核心是对象1、基本概念·对象：具有属性和方法的实体·类：描述的是具有相似性质的一组对象。一个具体的对象称为类的实例·方法：允许作用于某个对象上的各种操作·消息：用来请求对象执行某一处理或者回答某些信息的要求·继承：类与类之间的关系·封装：是一种信息隐藏的技术，目的在于将对象的使用者和对象的设计者分开。用户只能见到对象封装界面上的信息，不必要知道实现的细节2、面向对象开发的优点：·与人类的习惯的思维方法一致；·稳定性好·可重用性好·易于开发大型软件产品·可维护性好四、考题练习1、下列选项不符合良好程序设计风格的是A、源程序要文档化B、数据说明的次序要规范化C、避免滥用goto语句D、模块设计要保证高耦合，高内聚2、下面描述中，符合结构化程序设计风格的是A、使用顺序、选择、循环三种基本控制结构表示程序的控制逻辑B、模块只有一个入口，可以有多个出口C、注重提高程序的执行效率D、不使用goto语句3、下列选项中不属于结构化程序设计方法的是A、自顶向下B、逐步求精C、模块化D、可复用4、下面概念中，不属于面向对象方法的是A、对象B、继承C、类D、过程调用5、在面向对象方法中，类的实例称为6、问题处理方案的正确而完整的描述称为7、在面向对象方法中，（）描述的是具有相似属性与操作的一组对象8、结构程序设计主要强调的是A、