计算机二级公共基础知识.docx
- 文档编号:12060310
- 上传时间:2023-06-04
- 格式:DOCX
- 页数:48
- 大小:46.77KB
计算机二级公共基础知识.docx
《计算机二级公共基础知识.docx》由会员分享,可在线阅读,更多相关《计算机二级公共基础知识.docx(48页珍藏版)》请在冰点文库上搜索。
计算机二级公共基础知识
三、程序怎样执行、如何编写程序
v计算机本身仅能识别二进制代码“0”、“1”。
v编程最直接、最低级的就是机器语言。
v为解决机器语言难理解、记忆等问题。
出现符号语言。
v为使编程接近自然语言,出现高级语言。
如C、PASCAL、FORTRAN等。
v为配合高级语言编程,出现了开发工具,提高效率、减轻劳动量。
如VB、VC、PB、Delphi、VFP等。
因此VFP不是编程语言。
v不管什么形式编写代码,最终都应将代码翻译成机器语言,这就是编译程序的工作。
不同的语言有不同的编译器。
v程序控制是一种逻辑控制。
因此,严谨的逻辑思维是一个程序员必备的基本素质。
v用程序实现某一功能。
有许多方法。
具体用哪种完全取决于程序员个人的思维方式。
因此,程序是脑力劳动的结晶,从某种意义上,编程又是一门艺术。
v程序的特殊性决定了程序的复杂性,且与实现功能的复杂性密切相关成正比。
因此为使复杂的、智力的编程工作规范化、科学化,便出现了各种编程设计方法。
如结构化编程方法、面向对象的程序设计方法等。
v不管用什么方法编程,不管编程者智力程度如何,不管采用什么样的编程语言和方法,程序最终完成的功能稳定、可靠、实用、易维护和安全等是程序的最终目标,也是程序员的追求。
v程序设计是一个复杂艰巨的过程。
编写代码仅是程序设计的一部分。
必须先有思想,再有方法,然后才是编写代码,且要经过许多反复,不可急功近利。
v四、程序设计语言或工具
v程序设计语言指的是用来编写程序的语言。
v人与计算机交流要使用语言,以便让计算机工作,计算机也通过语言把结果告诉用计算机的人——“人机对话”。
v人与计算机交流的语言非平常人与人之间交流的语言,是专门的语言——程序设计语言。
v程序设计语言是计算机系统软件的重要组成部分。
v执行程序设计的语言有很多,可分高级语言和低级语言,区别在于接近自然语言的程度
v高级语言一般与具体的计算机硬件无关,比较接近人类自然语言的语法习惯及数学表达形式。
v用高级语言编写的源程序不能被机器直接执行,需通过编译成解释程序的翻译才可被机器执行(机器语言)。
一、算法(algorithm)
1、算法的基本概念
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
它是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
算法具有有穷性、确定性、可行性、输入和输出(拥有足够的情报)等5个重要特性。
2、算法的基本要素
v对数据对象的运算和操作:
算术运算、逻辑运算、关系运算、数据传输
v算法的控制结构:
Ø算法中各操作之间的执行顺序;
Ø描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等;
Ø一个算法一般可以用顺序、选择、循环三种基本结构组合而成。
3、算法设计的基本方法
v列举法
v归纳法
v递推
v递归(以简洁的形式设计和描述算法)
v减半递推技术
v回溯法
二、算法的复杂度
1、时间复杂度
v依据算法编制的程序在计算机上运行时所消耗的时间来度量。
通常有事后统计法和事前分析估算法。
v一个算法是由控制结构(顺序、分支和循环)和原操作构成的,算法时间取决于两者的综合效果。
v算法中基本操作重复执行次数n和算法执行时间同步增长,称作算法的时间复杂度。
2、空间复杂度
v一般是指执行这个算法所需要的内存空间。
v一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间。
v一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅
助空间。
3、例题讲解
v算法的时间复杂度是指(C)
A、执行算法程序所需要的时间B、算法程序的长度
C、算法执行过程中所需要的基本运算次数
D、算法程序中的指令条数
v算法的基本特征是可行性、确定性、【1】和拥有足够的情报。
【答案】:
有穷性
v算法的空间复杂度是指(D)
A)算法程序的长度B)算法程序中的指令条数
C)算法程序所占的存储空间
D)执行过程中所需要的存储空间
v在计算机中,算法是指(B)
A)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法
v算法分析的目的是(D)
A)找出数据结构的合理性
B)找出算法中输入和输出之间的关系
C)分析算法的易懂性和可靠性
D)分析算法的效率以求改进
v算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。
【答案】:
时间复杂度和空间复杂度
三、数据结构(DataStructure)
1、数据结构研究的主要内容
v当今计算机应用的特点:
1、所处理的数据量大且具有一定的关系;
2、对其操作不再是单纯的数值计算,而更多地是需要对其进行组织、管理和检索。
对数据的讨论不单单是数据本身,还要包括数据与数据之间的关系。
数据结构的主要研究问题:
2、基本概念和术语
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
v数据元素(DataElement)
数据元素是数据的基本单位,即数据集合中的个体。
有时一个数据元素可由若干数据项(DataItem)组成。
数据项是数据的最小单位。
数据元素亦称节点或记录。
数据结构可描述为Group=(D,R)
●例1:
一年四季的数据结构可表示成
B=(D,R)
D={春,夏,秋,冬}
R={(春,夏),(夏,秋),(秋,冬)}
●例2:
家庭成员数据结构可表示成
B=(D,R)
D={父亲,儿子,女儿}
R={(父亲,儿子),(父亲,女儿)}
3、例题讲解
v数据处理的最小单位是(C)
A)数据B)数据元素C)数据项D)数据结构
v数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(A)
A)数据的存储结构B)计算方法
C)数据映象D)逻辑存储
v数据结构包括数据的逻辑结构、数据的【4】以及对数据的操作运算。
【答案】物理结构(或存储结构)
线性结构与非线性结构:
v线性结构:
有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。
如:
一年四季,26个英文字母
v非线性结构:
线性以外的数据结构。
如:
反映家庭成员间辈分关系的数据结构
4、线性表(LinearList)
v线性表:
具有线性结构的有限序列。
数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的。
v线性表的定义:
线性表是n个元素的有限序列,它们之间的关系可以排成一个线性序列:
a1,a2,……,ai,……,an
其中n称作表的长度,当n=0时,称作空表。
v线性表的特点:
1、线性表中所有元素的性质相同。
2、除第一个和最后一个数据元素之外,其它数据元素有且仅有一个前驱和一个后继。
第一个数据元素无前驱,最后一个数据元素无后继。
3、数据元素在表中的位置只取决于它自身的序号。
v在线性表上常用的运算有:
初始化、求长度、取元素、修改、前插、删除、检索、排序
v线性表的顺序存储结构及其插入与删除操作
v特点:
1、线性表中数据元素类型一致,只有数据域,存储空间利用率高。
2、所有元素所占的存储空间是连续的。
3、各数据元素在存储空间中是按逻辑顺序依次存放的
(a)做插入、删除时需移动大量元素。
(b)空间估计不明时,按最大空间分配。
Ø线性表的顺序存储结构——可用C语言中的一维数组来描述.intV[M];
其中:
V是数组的名字,M是数组大小,假设数组中的元素是整型类型
第i个元素的ai存储地址:
Loc(ai)=Loc(a1)+(i-1)*m
v删除算法的分析
Ø在进行删除操作时,若假定删除每个元素的可能性均等则平均移动元素的个数为:
Ø分析结论
顺序存储结构表示的线性表,在做插入或删除操作时,平
均需要移动大约一半的数据元素。
当线性表的数据元素量较大,并且经常要对其做插入或删除操作时,这一点需要值得考虑。
❑线性表的例题讲解
v顺序存储方法是把逻辑上相邻的结点存储在物理位置【1】的存储单元中。
【答案】相邻
v长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为【2】。
【答案】n/2
v线性表L=(a1,a2,a3,…ai,…an),下列说法正确的是(D)
A)每个元素都有一个直接前件和直接后件
B)线性表中至少要有一个元素
C)表中诸元素的排列顺序必须是由小到大或由大到小
D)除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件
v数据结构中,与所使用的计算机无关的是数据的(C)
A)存储结构B)物理结构
C)逻辑结构D)物理和存储结构
※下列叙述中,错误的是(B)
A)数据的存储结构与数据处理的效率密切相关
B)数据的存储结构与数据处理的效率无关
C)数据的存储结构在计算机中所占的空间不一定是连续的
D)一种数据的逻辑结构可以有多种存储结构
※数据的存储结构是指(B)
A)数据所占的存储空间
B)数据的逻辑结构在计算机中的表示
C)数据在计算机中的顺序存储方式
D)存储在外存中的数据
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分成(C)
A)动态结构和静态结构
B)紧凑结构和非紧凑结构
C)线性结构和非线性结构
D)内部结构和外部结构
※数据的逻辑结构有线性结构和【2】两大类。
非线性结构
※当线性表采用顺序存储结构实现存储时,其主要特点是【1】。
【答案】逻辑结构中相邻的结点在存储结构中仍相邻。
5、堆栈和队列
❑堆栈和队列的定义
栈和队列是两种特殊的线性表,它们是运算时要受到某些限制的线性表,故也称为限定性的数据结构。
v堆栈的定义
堆栈:
限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。
设栈s=(a1,a2,…ai,…,an),
其中a1是栈底元素,an是栈顶元素。
栈顶(top):
允许插入和删除的一端;约定top始终指向新数据元素将存放的位置。
栈底(bottom):
不允许插入和删除的一端。
v队列的定义
队列:
一种特殊的线性结构,限定只能在表的一端进行插入,在表的另一端进行删除的线性表。
此种结构称为先进先出(FIFO)表。
v队列的主要运算
(1)设置一个空队列;
(2)插入一个新的队尾元素,称为进队;
(3)删除队头元素,称为出队;
(4)读取队头元素;
❑堆栈和队列的例题讲解
v栈和队列的共同特点是(C)
A)都是先进先出
B)都是先进后出
C)只允许在端点处插入和删除元素
D)没有共同点
v如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(B)
A)e3,e1,e4,e2B)e4,e3,e2,e1
C)e3,e4,e1,e2D)任意顺序
v一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。
而实现递归调用中的存储分配通常用(A)
A)栈B)堆C)数组D)链表
v栈底至栈顶依次存放元素A、B、C、D,在第五个元素E
入栈前,栈中元素可以出栈,则出栈序列可能是(B)
A)ABCEDB)DCBEA
C)DBCEAD)CDABE
v栈通常采用的两种存储结构是(A)
A)顺序存储结构和链表存储结构
B)散列方式和索引方式
C)链表存储结构和数组
D)线性存储结构和非线性存储结构
v栈和队列通常采用的存储结构是【1】。
【答案】链式存储和顺序存储
v下列数据结构中,按先进后出原则组织数据的是(B)
A)线性链表B)栈C)循环链表D)顺序表
v当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。
这种情况称为【2】。
答案:
上溢
v由两个栈共享一个存储空间的好处是(B)
A)减少存取时间,降低下溢发生的机率
B)节省存储空间,降低上溢发生的机率
C)减少存取时间,降低上溢发生的机率
D)节省存储空间,降低下溢发生的机率
v下列关于栈的叙述中正确的是(D)
A)在栈中只能插入数据B)在栈中只能删除数据
C)栈是先进先出的线性表D)栈是后进先出的线性表
v下列关于队列的叙述中正确的是(C)
A)在队列中只能插入数据B)在队列中只能删除数据
C)队列是先进先出的线性表D)队列是后进先出的线性表
顺序存储结构常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
v顺序存储结构的三个缺点:
1.作插入或删除操作时,需移动大量元数。
2.长度变化较大时,需按最大空间分配。
3.表的容量难以扩充。
6、线性链表
v线性链表的基本概念:
线性表的链式存储结构称为线性链表。
为了适应线性表的链式存储结构,计算机存储空间被划分为一个一个小块,每
一小块占若干字节,通常称这些小块为存储结点。
将存储空间中的每一个存储结点分为两部:
v一部分称为数据域,用于存储数据元素的值;
v另一部分称为指针域,用于存放下一个数据元素的存储序号(即存储结点的地址),也就是指向后件结点.
v链接存储结构特点:
1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活(不必移动节点,只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
指向线性表中第一个结点的指针HEAD称为头指针。
当HEAD=NULL(或0)时称为空表。
对于线性链表,可以从头指针开始,沿着各个结点的指针扫描到链表中的所有结点。
v线性链表的基本运算:
线性链表的运算主要有以下几个:
①在线性链表中包含指定元素的结点之前插入一个新元素。
②在线性链表中删除包含指定元素的结点。
③将两个线性链表按要求合并成一个线性链表。
Ø线性链表的插入运算:
线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。
为了要在线性链表中插入一个新元素,首先要给该元素分配一个新结点,然后将存放新元素值的结点链接到线性链表中指定的
位置。
Ø线性链表的删除运算:
Ø循环链表:
循环链表的结构与前面所讨论的线性链表相比,具有以下两个特点:
①循环链表的头指针指向表头结点。
②在循环链表中,所有结点的指针构成了一个环状链。
在实际应用中,循环链表与线性单链表相比主要有以下两个方面的优点:
①在循环链表中,只要指出表中任何一个结点的位置,就可以从它出发访问到表中其他所有的结点。
②由于在循环链表中设置了一个表头结点,因此,在任何情况下,循环链表中至少有一个结点存在,从而使空表与非空表的运算统一。
❑线性链表的例题讲解
v链表不具有的特点是(B)
A)不必事先估计存储空间B)可随机访问任一元素
C)插入删除不需要移动元素D)所需空间与线性表长度成正比
v数据结构分为逻辑结构与存储结构,线性链表属于【1】。
【答案】存储结构
v线性表的顺序存储结构和线性表的链式存储结构分别是(B)
A)顺序存取的存储结构、顺序存取的存储结构
B)随机存取的存储结构、顺序存取的存储结构
C)随机存取的存储结构、随机存取的存储结构
D)任意存取的存储结构、任意存取的存储结构
7、树与二叉树:
v树的基本概念:
前面我们讨论的线性表,栈、队列和数组等都是线性结构。
而树是一种非线性数据结构,它的每一个结点,都可以有不止一个直接后继,除根外的所有结点,都有且只有一个直接前趋。
这些数据结点按分支关系组织起来,清晰地反映了数据元素之间的层次关系。
v二叉树(BinaryTree):
因为树的每个结点的度不同,存储困难,使对树的处理算法很复杂。
所以引出二叉树的讨论。
二叉树(binarytree)是一种很有用的非线性结构。
二叉树具有以下两个特点:
(1)非空二叉树只有一个根结点;
(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
Ø二叉树的性质:
性质1:
在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
例子1:
某二叉树中度为2的结点有18个,则该二叉树中有19个叶子结点。
性质2:
二叉树的第i层上至多有2i-1(i1)个结点
性质3:
深度为h的二叉树中至多含有2h-1个结点
v满二叉树与完全二叉树
满二叉树是指除最后一层外,每一层上的所有结点都有两个子结点。
完全二叉树是指这样的二叉树:
除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
注意:
满二叉树是完全二叉树,完全二叉树不一定是满二叉树。
v满二叉树的特点:
每一层上都含有最大结点数。
v完全二叉树的特点:
除最后一层外,每一层都取最大结点数,最后一层结点都集中在该层最左边的若干位置
v规律总结:
对于完全二叉树而言
Ø如果它的结点个数为偶数,则该二叉树中:
叶子结点的个数=非叶子结点的个数
Ø如果它的结点个数为奇数,则该二叉树中:
叶子结点的个数=非叶子结点的个数+1
(即叶子结点数比非叶子结点数多一个)
v例题讲解
1、设一棵完全二叉树共有700个结点,则在该二叉树中有350个叶子结点。
2、在深度为5的满二叉树中,叶子结点的个数为(C)
A)32B)31C)16D)15
v二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
二叉树的遍历可以分为三种:
前序遍历、中序遍历、后序遍历。
设访问根结点记作V;遍历根的左子树记作L;遍历根的右子树记作R;
前序:
VLR(即根左右)中序:
LVR(即左根右)
后序:
LRV(即左右根)
v例题讲解
1、设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为:
DEBFCA
2、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为(B)
A)GEDHFBCAB)DGEBHFCA
C)ABCDEFGHD)ACBFEDHG
v具有3个结点的二叉树有(D)
A)2种形态B)4种形态
C)7种形态D)5种形态
8、查找和排序:
v查找——又称为检索
查找算法的评价主要考虑算法的时间复杂性,既可以采用数量级的形式表示,也可以采用平均检索(查找)长度,即在查找成功情况下的平均比较次数来表示。
查找可分为顺序查找和二分法查找两种。
(a)顺序查找:
顺序查找又称线性查找。
它是一种最简单、最基本的查找方法。
基本思想是:
从表中第一条记录开始,逐个进行记录的关键字和给定值的比较。
若某个记录的关键字和给定值相等,则查找成功;否则,若直至最后一个记录,其关键字和给定值都不相等,则表明表中没有所查记录,查找不成功。
(b)二分查找:
二分查找又称折半查找。
作为二分查找对象的表必须是顺序存储的有序表,即各记录的次序是按其关键字的大小顺序(以下假定按从小到大的顺序)排列的表。
二分查找的具体做法是:
先取表中间位置的记录关键字与给定值比较。
若相等,则查找成功;否则,若给定值比该记录的关键字小,则给定值必在表的前半部分。
在这前半部分中再取中间位置记录的关键字进行比较,就又可以排除这部分的一半。
依次反复进行,直到找到给定值或找完全表而找不到为止。
对于n较大时,查找长度可以近似地表示为
v排序(sort)
排序是将一组杂乱无章的数据按一定的规律顺次排列起来。
通常数据对象有多个属性域,即由多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。
该域称为关键字(key)。
排序的时间开销是衡量算法好坏的最重要的标志。
对于长度为n的有序线性表,查找时最坏情况只需比较n次。
(a)交换类排序:
Ø冒泡排序法:
需要比较的次数为n(n-1)/2
Ø快速排序法:
是对冒泡排序的改进,是目前内部排序中速度最快的一种。
(b)插入类排序:
插入类排序的基本方法是:
每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
Ø简单插入排序法:
最坏情况需要n(n-1)/2次比较;
Ø希尔排序法:
最坏情况需要O(n)次比较。
(c)选择类排序:
选择类排序的思想是:
每一趟(例如,第i趟,i=0,1,…,n−2)在后面n−i个待排序对象中选出关键字最小(升序,若为降序,选出最大关键字)的对象,作为有序对象序列的第i个对象。
待到第n−2趟作完,待排序对象只剩下1个,不用再
选了,结束排序。
Ø简单选择排序法,最坏情况需要n(n-1)/2次比较;
Ø堆排序法,最坏情况需要O(nlog2n)次比较。
(一)程序设计方法与风格
v如何形成良好的程序设计风格:
1、源程序内部文档化;
Ø选择标识符的名字
Ø注释(序言性和功能性注释)
Ø程序的视觉组织
2、数据说明
Ø显式地说明一切变量
Ø数据说明的次序应该规范化
Ø便于查找变量(按顺序排列)
Ø对复杂数据结构应注释说明
3、语句的结构
Ø每条语句简单明了
Ø尽量不用或少用GOTO语句
Ø尽量只采用3种基本控制结构编程
4、输入和输出
Ø对所有输入数据进行校验和合理性检查
Ø输入输出格式保持一致
Ø设计良好的输出报表
输入方式应力求简单,尽量避免给用户带来不必要的麻烦;交互式输入数据时应有必要的提示信息;程序应对输入数据的合法性进行检查;若用户输入某些数据后可能产生严重后果,应给用户输出必要的提示并要求用户确认;应根据系统的特点和用户的习惯设计出令用户满意的输入方式。
输出数据的格式应清晰,美观;输出数据时要加上必要的提示信息。
(二)结构化程序设计
结构化程序设计的主要思想是功能分解并逐步求精。
当一些任务十分复杂不易描述时,可以将它拆分为一系列较小的功能部件,直到这些子任务小到易于理解和实现的程度。
结构化程序的特点:
程序结构仅由顺序、选择和循环3种结构复合而成。
(三)面向对象的程序设计方法
面向对象的程序设计(Object-OrientedProgramming,OOP)是一种把面向对象的思想应用于软件开发过程中,指导开发活动的系统方法,简称OO方法,它是建立在对象概念(对象、类和继承)基
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 二级 公共 基础知识