公共基础知识重点内容.ppt
《公共基础知识重点内容.ppt》由会员分享,可在线阅读,更多相关《公共基础知识重点内容.ppt(79页珍藏版)》请在课桌文档上搜索。
1、计算机二级公共课辅导,计算机二级公共课辅导,考试方式:,1,公共基础知识的考试方式为笔试,加在Visula FoxPro数据库程序中,合为一张试卷。公共基础知占全卷的30分。2,公共基础知识有10道题和5道填空题。考试方式:3,笔试:90分钟,满分100分,其中含公共基础知识部分的30分。,选择题70分,35个,每小题2分。填空题 每空2分,15个空,共30分4,上机:90分钟,满分100分(1)基本操作(30分,包括4小题,分值依次 7分,7分,8分,8分)(2)简单应用(40分 包括2小4,每小题20分)(3)综合应用(30分 1小题),第一章 数据结构与算法,1.1算法(课本第1-2页)
2、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。,特征包括:(1)可行性;(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;(4)拥有足够的情报。,算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。指令系统:一个计算机系统能执行的所有指令的集合。基本运算和操作包括:算术运算、逻辑运算、关
3、系运算、数据传输。,算法的控制结构:顺序结构、选择结构、循环结构。算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。算法的时间复杂度和空间复杂度不相关。,数据结构研究的三个方面:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。,数据结构是指相互有关联的数据元素的集合。P11 数据的逻辑结构包含:(1)表示数据元素的信
4、息;(2)表示各数据元素之间的前后件关系。,数据的存储结构有顺序、链接、索引等。数据结构的表示方法:二元组 和图形表示法。P12 P13线性结构条件:P14(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。,线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。,非空线性表的结构特征:(1)且只有一个根结点a1,它无前件;(2)有且只有一个终端结点an,它无后件;(3)除根结点与终端结点外,其他所有结点
5、有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。,线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有元素的所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。顺序表的运算:插入、删除。(详见16页),1ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。,例:一个矢量第一个元素的存储地址是100,每个元素的长度为2,
6、则第5个元素的地址是108数据元素的存储位置均取决于第一个数据元素的存储位置,即:。ADR(ai)=ADR(a1)+(i-1)k 第5个元素的地址:ADR(a5)=100+(5-1)X2=108,14栈和队列 P19 P22,栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。,队列是指
7、允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满,设初始输入序列为1,2,3,4,5,利用一个栈产生输出序列,下列B序列是不可能通过栈产生的A)5,4,3,2,1 B)5,3,4,1,2C)4,3,2,1,5 D)3,4,5,2,1,由于栈的压入和退出只能在栈顶进行,所以要使出栈的第一个数是序列的最后一个数5,只能先把序
8、列所有元素都压入栈,但这时出栈序列只能是(A 5,4,3,2,1),所以(B 5,3,4,1,2)选项的出栈序列是错误的,应选(B。当初始序列压入一个时,就退出一个元素,这样就得到(A)选项的出栈序列1,2,3,4,5;先压入1,2,3,4四个元素,再退出所有元素,最后压入5,并退栈这时得到(C)选项的出栈序列4,3,2,1,5;压入1,2后对后面的元素3,4,5分别压入一个退出一个,这时便得到(D)选项的出栈序列3,4,5,2,1,5,4,3,2,1,4,3,2,1,5,3,2,1,4,5,15线性链表 P24,数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。结
9、点由两部分组成:(1)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向前一个或后一个结点。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。,链式存储方式即可用于表示线性结构,也可用于表示非线性结构。线性链表,HEAD称为头指针,HEAD=NULL(或0)称为空表,如果是两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。线性链表的基本运算:查找、插入、删除。,16树与二叉树 P31重难点,树是一种简单的非线性结构,所有元素之间具有明显的层次特性
10、。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。,在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。,二叉树的基本性质:P34(1)在二叉树的第k层上,最多有2k-1(k1)个结点;(2)深度为m的二叉树最多有2m-1个结点;(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;,(4)具有n个
11、结点的二叉树,其深度至少为log2n+1,其中log2n表示取log2n的整数部分;(5)具有n个结点的完全二叉树的深度为log2n+1;(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,.n给结点进行编号(k=1,2.n),有以下结论:,若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INT(k/2);若2kn,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);若2k+1n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上
12、有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。,二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。P38 二叉树的遍历:(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点。,17查找技术,顺序查找的使用情况:(1)线性表为无序表;(2)表采用链式存储结构。二分法查找只适用于顺序存储的有序表,对于长度
13、为n的有序线性表,最坏情况只需比较log2n次。,18排序技术,排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2;(2)快速排序法。插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;(2)希尔排序法,最坏情况需要O(n1.5)次比较。选择类排序法:(1)简单选择排序法,最坏情况需要n(n-1)/2次比较;(2)堆排序法,最坏情况需要O(nlog2n)次比较,第二章程序设计基础,21程序设计设计方法和风格 如何形成良好的程序设计风格 1、源程序文档化;2、数据说明的方法;3、语句的结构;4、输入和输出
14、。注释分序言性注释和功能性注释,语句结构清晰第一、效率第二。,22结构化程序设计,结构化程序设计方法的四条原则是:1.自顶向下;2.逐步求精;3.模块化;4.限制使用goto语句。结构化程序的基本结构和特点:(1)顺序结构:一种简单的程序设计,最基本、最常用的结构;(2)选择结构:又称分支结构,包括简单选择和多分支选择结构,可根据条件,判断应该选择哪一条分支来执行相应的语句序列;(3)重复结构:又称循环结构,可根据给定条件,判断是否需要重复执行某一相同程序段。,23面向对象的程序设计 面向对象的程序设计:以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。面向对象方法的优点
15、:对于长度为N的线性表,在最坏情况下,冒泡排序和快速排序需要比较的次数为N(N-1)/2对于长度为N的有序线性表,二分查找法只需要比较LOG2N次,而顺序查找需要比较N次。,(1)与人类习惯的思维方法一致;(2)稳定性好;(3)可重用性好;(4)易于开发大型软件产品;(5)可维护性好。,对象是面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息,操作描述了对象执行的功能,操作也称为方法或服务。,对象的基
16、本特点:(1)标识惟一性;(2)分类性;(3)多态性;(4)封装性;(5)模块独立性好。,类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象,对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括(1)接收消息的对象的名称;(2)消息标识符,也称消息名;(3)零个或多个参数。,继承是指能够直接获得已有的性质和特征,而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类,多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,第三章软件工程基础,31软件工程基本概念 计算机软件是包括程序、数据及相
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公共 基础知识 重点 内容

链接地址:https://www.desk33.com/p-267208.html