二级公共基础知识课件.ppt

二级公共基础知识，课程老师：黎利辉，课程时间： 2011年3月，一，关系面广，但难易度低，公共基础知识问题的特征和复习提案，计算机等级二级理论考试中有关公共知识部分的问题共15件，算法和数据结构，编程基础， 虽然涉及软件工程基础和数据库设计基础等四个学科，但从总体上来看，这次考试的考核内容难度较低，考试点也比较集中。 二、评价的重点是基本概念，基本方法和基本运算，计算机级二级理论考试的主题是基本概念，基本方法和基本运算，评价以概念和认识内容为主，理解性、应用内容极少。 三、评价的重点是数据结构和算法，以下是传统二级理论考试的大致统计：算法和数据结构： 50%程序设计基础： 12.5%软件设计基础： 18.75%数据库设计基础： 18.75%，1，算法的基本概念和常用要学习计算算法的时间复杂性，2、掌握数据结构的基本概念，理解数据的逻辑结构和存储结构，学习用图形表示数据结构，算法和数据结构：3、理解线性表的基本概念， 掌握线性表的顺序记忆结构和顺序记忆的线性表的基本运算，4，理解堆栈和队列的基本概念，5，理解线性链表的基本概念，在掌握线性链表的基本运算的同时，理解链表的基本概念和基本操作，6，树的概念， 特别是了解二叉树的基本概念和相关性质，掌握二叉树的记忆结构和扫描技术，7，掌握检索技术，利用顺序检索和二分检索，学习在数列中指定的数据进行检索，8，利用相关的排序技术，实现无序的数列排序操作。 1 .了解软件工程的基本概念；2 .了解软件工程的过程和软件生命周期，软件工程的目标和原则；3 利用结构化分析法了解软件工程中的需求分析方法，理解需求分析的方法和要完成的任务，4 .理解数据流图的使用方法，5、理解利用结构化设计方法进行软件设计的方法，理解软件设计的常用工具，6， 理解软件测试的目的和方法以及软件测试的标准，理解常用软件测试方法的差异及其各自的功能和特征7，理解程序调试的方法和原则。 1、理解编程方法和编程风格确立的要素，掌握编程的基本规则；2、理解结构化流程设计的基本原则，掌握结构化流程设计的基本结构和特征；编程基础：3、理解面向对象的编程方法数据库系统：1，理解数据库系统的基本概念，理解数据库系统的发展，2，理解数据模型的基本概念，理解E-R模型，层次模型，网格模型和关系模型，关系模型的数据结构，关系的操作和数据约束等3、了解关系模型的基本操作，掌握关系模型的基本运算和扩展运算，4、理解数据库的设计和管理，掌握数据库设计的几个阶段的方法和特征。 一、了解计算机的工作原理、工作原理，熟悉计算机内部执行功能的基本意义。 为了为理解程序奠定基础，特别是理解计算机是机器。 二、程序的定义、指令的集合。 (解释命令)用硬件控制系统自动实现某个功能。 用一系列代码实现。 三、程序如何运行，如何写程序，计算机本身只能识别二进制代码“0”、“1”。 编程最直接和最低水平的是机器语言。 为了解决机器语言难以理解、记忆困难等问题。 出现符号的语言。 为了使编程接近自然语言，高级语言登场。 c、PASCAL、FORTRAN等。为了协助高级语言编程，出现了开发工具，提高效率，减少工作量。 VB、VC、PB、Delphi、VFP等。 VFP不是一种编程语言。 无论用什么形式写代码，最终都要把代码翻译成机器语言。 这是编译器的工作。 语言不同，编译器也不同。 程序控制是逻辑控制。 因此，严密的逻辑思考是程序员必须的基本素质。 实现作为程序的功能。 有各种各样的方法。 具体如何使用取决于编程人员的个人想法. 因此，程序是脑力劳动的结晶，在某种意义上，程序设计也是艺术。 程序的特殊性决定了程序的复杂性，与实现功能的复杂性密切相关。 因此，为了规范复杂智能编程，使其科学化，出现了各种各样的编程方法。 结构化编程方法、面向对象编程方法等。 四、编程语言或工具、编程语言是指用于编写程序的语言。 人与计算机的交流是为了使计算机工作而使用语言，计算机也通过语言将结果传达给计算机的人“人与人的对话”。 人与计算机交流的语言不是普通人与人交流的语言，而是专业的语言编程语言。 程序设计语言是计算机系统软件的重要组成部分。 执行编程的语言很多，分为高级语言和低级语言。 差异在于接近自然语言程度的高级语言一般与具体的计算机硬件无关，是接近人类自然语言的语法习惯和数学表现形式。 用高级语言写的源程序不能直接用机器执行，通过程序的编译和解释的翻译可以用机器执行。 四、编程语言或工具(续)、一、算法(algorithm )、一、算法的基本概念、算法是解决特定问题步骤的准确完整描述，*算法不等于程序，不等于计算方法。 算法具有贫困性、确定性、可行性、输入和输出(具有足够的信息)等五个重要特性。 算法的基本特征是： (1)可行性。 针对实际问题设计的算法，执行起来会得到满意的结果。 (2)确定性。 每个命令的意义明确，没有二义性。 另外，在任何条件下，该算法只能得到唯一的执行路径，即，在相同输入的情况下获得相同的输出。 (3)具有贫困性。 算法必须在有限的时间内完成。 有两个意思。 一是算法中的操作步骤有限，二是所有步骤都可以在有限时间内完成。 (4)有充分的信息。 算法中的各种运算总是应用于单个运算对象，这些运算对象可能具有初始状态。 这是该算法执行的起点或依据。 因此，一个算法执行的结果总是与输入的初始数据相关，结果输出因输入而异。 如果输入不足或输入错误，则无法运行或运行算法. 一般而言，如果算法具有足够的信息，则此算法可能会在有效信息不足时无效。 2、算法的基本要素、数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输、算法的各操作间的执行顺序算法的工具，通常有常规流程图、N-S结构化流程图、算法描述语言等算法的控制结构：3，算法设计的基本方法，枚举法递归(以简洁的形式设计和描述算法)半递归技术回溯法，2，算法的复杂性(包括时间复杂性和空间复杂性)，1 )算法的时间复杂性是算法的实现(2)算法空间复杂度是执行该算法所需的存储器空间，包括算法占用的空间、输入的初始数据占用的空间和执行中需要的多馀的空间。3、例题表示算法的时间复杂性具有(C)A、执行算法所需的时间b、算法的长度c、执行算法所需的基本运算次数d、算法的指令数算法的基本特征具有可行性、确定性，【1】等充分的信息【答案】:贫困性算法的空间复杂性是指，(d )算法程序的长度b )算法程序中的指令数c )算法程序所占的存储空间d )执行过程中所需的存储空间，在计算机中，算法是指(b )。 问题解决方案的准确且完整的描述c )排序方法d )查询方法算法分析的目的是： (d )找出数据结构的合理性b )找出算法中输入输出的关系c )算法的易懂性和可靠性d )分析算法的效率，算法的工作量的大小【答案】:小时的复杂性和空间的复杂性，三，数据结构，一，数据结构的研究的主要内容，现在的计算机应用特征：一，处理的数据量大，有一定的关系2，其操作不仅仅是数值计算，更多的时候，需要组织、管理和检索它。 应用例1学籍文件管理，假设学籍文件管理系统中包含下表1-1所示的学生信息。 特征：每个学生的信息占一行，所有学生的信息按学号顺序排列，构成一张表的表中的各学生的信息根据学号的大小而有前后关系，这是我们所说的线性结构，对此的操作通常是插入某学生的信息，或删除某学生的信息，或删除某学生的信息。 另外，应用示例2输出n个对象的全序列输出n个对象的全序列可以以图1-1中所示的格式来描述。 图1-13个对象的全排列过程，特征：在求解过程中处理的数据间有层次关系，这是我们所说的树结构，对它的操作是树结构的构筑，最下位节点的内容的输出等。 使用例子3制定教育计划，需要考虑各科目的开设顺序。 有些课程需要领先课程，有些课程不需要，有些课程是其他课程的领先课程。 例如，计算机专业课的开设情况如下表：课程前后关系的图形形式：图1-2计算机专业课的开设前后关系，结论：数据结构主要研究以下三方面的问题：数据的逻辑结构：数据集合中各数据要素间固有的逻辑关系，包含：1)数据显示各数据要素之间的上下文数据的存储结构：处理数据时，各数据要素在计算机中的存储关系，数据的存储结构有顺序、链接、索引等。 对各种数据结构的运算* :数据的逻辑结构反映数据要素间的逻辑关系，数据的存储结构(也称为数据的物理结构)是将数据的逻辑结构存储在计算机的存储空间中的形式。 相同逻辑结构的数据可以采用不同的存储结构，但会影响数据处理的效率。 2、基本概念和术语、数据结构是研究数据组织、记忆和运算的一般方法学科。 示例：整数(1，2 )、实数(1.1，1.2 )字符串(Beijing )、图形和声音。 计算机管理图书问题：图书馆有各种各样的卡片：按书名、作者、分类。 如何把查阅书的信息保存到计算机上，调查时间短，必须考虑到节省空间。 最简单的方法之一是制作表，各书的信息在表中占了一行。 例如，数据元素在计算机上的表现，数据结构是研究数据组织、存储和运算的常用方法的学科。 如何在计算机上存储0、1、2、3、4、5、6、7、8、9这10个数字，能最快地达到你所需要的目的？ 目的不同，最佳的存储方法也不同。从大到小的阵列： 9，8，7，6，5，4，3，2，1，0输出偶数： 0，2，4，6，8，1，3，5，7，9，操作处理(插入、删除、修改、检索、排序)数据结构中的节点，数据元素(数据元素) 数据元素可能由几个数据项(DataItem )组成。 数据项目是数据的最小单位。 PS:数据元素是数据的基本单位，数据项属于数据元素！ 数据项是最小单位！ 数据元素也称为节点或记录。 数据结构有Group=(D，r )、有限个数据元素的集合、有限个节点间关系的集合、数据结构有Group=(D，r )、条件：1)，只有一个根节点2 )每一个节点前件最大，后件也最大。 不满足线性结构条件的数据结构。 线性结构：例如a、b、c、x、y、z、学生成绩单、线性表节点之间以线性关系连接起来：树结构、全校学生文件管理的组织方式、计算机程序管理系统也是典型的树结构。 h，g，f，e，c，d，b，a，树结构的节点间有分层的连接关系，d= 1，2 )，(1，3 )，(1，4 )，(2，3 )，(3，4 )，(2，4 ) ，d= 1，2，3 r= (1，2 )，(2) 3)，模式结构的节点间的连接是任意的，依次存储、存储地址、存储内容、要素n、要素I、要素2、要素1、Lo m，Lo (i-1)*m，m是对每个要素占有的存储单元数，依次存储结构具有两个基本特征： (1)要素占有(2)各数据元素在存储空间中按逻辑顺序存储，数据的存储结构按顺序存储，连锁存储、h、各节点由两部分构成：数据域和指针域。 数据字段包含元素本身的数据，而指针字段包含指针. 数据元素之间的逻辑联系用指针来表示。 数据的存储结构大于1、顺序存储结构占据的存储区域(每个节点由数据域和指针域构成)。 2 .逻辑上相邻的节点不需要在物理上相邻。 3 .灵活的插入删除(不需要移动节点，只更改节点内的指针)。连锁存储结构的特征：3、例题中，连锁表中没有的特征是，(b )存储空间b )不需要随机访问任意要素c )删除要素d所需的空间被插入到与线性表的长度成比例的数据结构中，与使用的计算机无关，数据的(c )存储结构b )物理结构c )逻辑非线性结构、顺序存储方法将逻辑上相邻的节点存储在物理位置【3】的存储单元中。 相邻数据处理的最小单位是，(c )数据b )数据要素c )数据项目d )以数据结构数据结构为计算机的学科，主要研究对数据的逻辑结构和各种数据结构的运算，并研究(a )数据的存储结构b )计算方法c )数据图d ) 逻辑存储线性表的逐次存储结构和线性表的连锁存储结构分别是(b )逐次访问的存储结构、逐次访问的存储结构b )随机访问的存储结构、逐次访问的存储结构c )随机访问的存储结构、随机访问的存储结构d )任意访问的存储结构、任意访问的存储结构由于数据结构中各数据元素之间的上下文关系的复杂性，一般将数据结构称为(C)A )动态结构和静态结构b )紧凑结构和非紧凑结构c )线性结构和非线性结构d )内部结构和外部结构数据结构，数据的逻辑结构和数据对【4】和数据的操作答案是物理结构(或存储结构)数据的基本单位是【5】。【答案】数据要素，3，例题解说，以下记述中错误的是，(b )数据的存储结构与数据处理的效率密切相关b )数据的存储结构与数据处理的效率无关