全国计算机等级考试二级C语言程序设计公共基础知识.docx
《全国计算机等级考试二级C语言程序设计公共基础知识.docx》由会员分享，可在线阅读，更多相关《全国计算机等级考试二级C语言程序设计公共基础知识.docx（45页珍藏版）》请在冰点文库上搜索。
全国计算机等级考试二级C语言程序设计公共基础知识
全国计算机等级考试二级C语言公共基础知识第一部分公共基础部分知识归纳
数据结构与算法
算法---是一组严谨地定义运算顺序的规则
算法的基本要素---一是对数据对象的运算和操作,二是算法的控制结构
算法设计基本方法---列举法、归纳法、递推、递归、减半递推
算法的复杂度---包括时间复杂度和空间复杂度
时间复杂度---执行算法所需的计算工作量
空间复杂度---执行算法所需的内存空间
数据结构---相互有关联的数据元素的集合。
如春、夏、秋、冬;18、11、35、23、16。
。
。
;父亲、儿子、女儿等都是数据元素。
前件---数据元素之间的关系,如父亲是儿子和女儿的前件
后件---如儿子是父亲的后件
结构---指数据元素之间的前后件关系
数据的逻辑结构—是指反映数据元素之间逻辑关系,而与它们在计算机中的存储位置无关
数据的存储结构（物理结构---数据的逻辑结构在计算机存储空间中的存放形式,数据元素在计算机存储空间的位置关系可能与逻辑关系不同。
根据数据结构中各数据元素之间前后件关系的复杂程度,可将数据结构分两类---线性结构与非线性结构
线性结构（线性表---满足下列两个条件（1有且只有一个根结点（2每一个结点最多有一个前件和后件。
则称该数据结构为线性结构,否则为非线性结构。
线性表是最简单、最常用的一种数据结构,其数据元素之间的相对位置是线性的,其存储方式为顺序存储的,如数组
栈---是限定在一端进行插入与删除的线性表,一端封闭,另一端开口,其操作原则是“先进后出”,栈的运算有入栈、退栈、读栈顶元素
队列---是指在一端进行插入（称为队尾而在另一端进行删除（称为队头的线性表,其操作规则是“先进先出”,其运算有入队和退队。
树---是一种简单的非线性结构,而且是层次结构,是倒立的大树,有根结点、父结点、子结点、叶子结点。
根结点在第一层,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度,树的最大层次称为树的深度。
二叉树---（1非空二叉树只有一个根结点（2每一个结点最多有两棵子树（左子树和右子树,其存储结构为链式。
二叉树性质---（1K层上最多有2（K-1个结点（2深度为m的二叉树最多有2m-1个结点
（3度为0的结点（叶子结点比度为2的结点多一个（4具有n个结点的二叉树,其深度至少为[Log2n]+1,其中[Log2n]表示对Log2n取整
满二叉树---除最后一层外,其余层的结点都有两个子结点
完全二叉树---除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点,叶子结点只可能在层次最大的两层上出现。
满二叉树是完全二叉树,而完全二叉树不是满二叉树。
完全二叉树有两个性质:
（1具有n个结点的完全二叉树的深度为[Log2n]+1（2
二叉树遍历---不重复地访问各个结点。
分为前序遍历（DLR-根左右、中序遍历（LDR-左根右和后序遍历（LRD-左右根
查找技术---顺序查找——对于长度为n的有序线性表,查找时需要比较n次二分法查找——对于长度为n的有序线性表,查找时需要比较log2n次
排序技术---假设线性表的长度为n,则冒泡排序和简单插入排序的比较次数（时间复杂度为n（n-1/2;希尔排序的比较次数为O（n1.5;简单选择排序的比较次数为n（n-1/2;堆排序的比较次数为O（nlog2n.
程序设计基础
结构化程序设计的三种结构---是顺序、选择和循环
对象---表示客观世界的任何实体
类---是具有共同属性和方法的对象的集合
实例---任何一个对象都是其对应类的实例
消息---一个实例和另一个实例之间传递的信息
继承---是指直接获得已有的性质和特征,而不必重复定义它们。
例如子类继承父类
结构化程序设计主要强调---程序的易读性
良好的程序设计风格是---程序应简单、清晰、可读性好
在面向对象方法中,一个对象请求另一个对象为其服务的方式是通过发送（消息来实现的
信息隐蔽的概念与（模块独立性概念直接相关
（任何对象都具有继承性这句话是错误的
注释分为（序言性注释和（功能性注释
在面向对象方法中,信息隐蔽是通过对象的（封装性来实现的
类是一个支持集成的抽象数据类型,而对象是类的（实例
在面向对象方法中,类之间共享属性和操作的机制称为（继承
第三章软件工程基础
软件生命周期---软件产品从提出、实现、使用维护到停止使用退役的过程。
分为软件定义、软件开发、软件运行维护三个阶段。
软件生命周期的主要活动阶段---可行性分析、需求分析、软件设计、软件实现、软件测试、运行和维护。
常见的需求分析方法---（1结构化分析方法---主要包括面向数据流的结构化分析方法SA;面向数据结构的Jackson方法JSD;面向数据结构的结构化数据系统开发方法DSSD。
（2面向对象的分析方法OOA
结构化分析方法工具
（1数据流图DFD,记住DFD图的几个符号:
（2数据字典DD
（3判定树
（4判定表
程序结构图（SC,N-S图,问题分析图（PAD
程序流程图（PFD的几个符号:
软件测试---黑盒测试:
功能测试
白盒测试:
内部结构测试,穷举路径测试
习题3
在软件生命周期中,能准确地判断软件系统必须做什么和必须具备哪些功能的阶段是（需求分析
软件工程的3个要素（工具,（过程,（方法
检查软件产品是否符合需求定义的过程称为（确认测试
软件设计原则是（抽象、（模块化、（信息隐蔽
需求分析常用的工具是（DFD
在结构化方法中,软件功能分解属于（总体设计阶段
软件测试的目的是（改正错误
软件需求分析阶段可分为四个方面（需求获取、（需求分析、（编写需求格式说明、（需求评审
软件是（程序、（数据、（文档的集合
Jakson方法是一中面向（数据流的结构化方法
软件工程研究的内容包括（软件开发技术、（软件工程管理
数据流图的类型有（交换型、（事务型
软件开发环境是全面支持软件开发全过程的（软件工具集合
第四章数据库设计基础（一
数据库---DB;数据库管理系统---DBMS;数据库管理员---DBA;数据库系统---DBS;数据库应用系统---DBAS
数据模型所描述的内容分三个部分（数据结构、（数据操作、（数据约束逻辑数据模型分（层次模型、（网状模型、（关系模型、（面向对象模型
E-R模型---实体关系模型,主要由实体、属性、联系组成,联系分:
1对1,1对多,多对多;
以二维表为基本结构所建立的模型称为关系模型,关系模型采用二维表来表示,简称表,由行和列组成,行称为元组或记录,列称为字段
主键---唯一标识一个记录的字段
外键---一个表的字段是其他表的主键
在数据管理技术的发展过程中,经历了人工管理阶段、文件系统阶段、数据库系统阶段,其中数据独立性最高的阶段是（数据库系统
数据库系统减少了（数据冗余;数据库系统的核心是（数据库管理系统用树型结构来表示实体间联系的模型称为（层次模型
关系表中的每一行称为（元组
关系数据库管理系统能实现的专门关系运算包括（选择、（投影、（连接在关系数据库中,用来表示实体之间联系的是（二维表
数据库设计包括两方面的设计内容（概念设计、（逻辑设计
将E-R图转换到关系模式时,实体与联系都可以表示成（关系
一个项目具有一个项目主管,一个项目主管可以管理多个项目,则实体“项目主管”与“项目”的联系属于（一对多
数据独立性分为逻辑独立性和物理独立性,当数据的存储结构改变时,其逻辑结构可以不变,因此,基于逻辑结构的应用程序不必修改,称为（逻辑独立性数据库系统中实现各种数据管理功能的核心软件称为（数据库管理系统DBMS关系模型的完整性规则是对关系的某种约束条件,包括实体完整性、（参照完整性和自定义完整性
数据库设计基础（二
4.1数据库系统的基本概念
数据:
实际上就是描述事物的符号记录。
数据的特点:
有一定的结构,有型与值之分,如整型、实型、字符型等。
而数据的值给出了符合定型的值,如整型值15。
数据库:
是数据的集合,具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序共享。
数据库存放数据是按数据所提供的数据模式存放的,具有集成与共享的特点。
数据库管理系统:
一种系统软件,负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等,是数据库的核心。
数据库管理系统功能:
（1数据模式定义:
即为数据库构建其数据框架;
（2数据存取的物理构建:
为数据模式的物理存取与构建提供有效的存取方法与手段;
（3数据操纵:
为用户使用数据库的数据提供方便,如查询、插入、修改、删除等以及简单的算术运算及统计;
（4数据的完整性、安生性定义与检查;
（5数据库的并发控制与故障恢复;
（6数据的服务:
如拷贝、转存、重组、性能监测、分析等。
为完成以上六个功能,数据库管理系统提供以下的数据语言:
（1数据定义语言:
负责数据的模式定义与数据的物理存取构建;
（2数据操纵语言:
负责数据的操纵,如查询与增、删、改等;
（3数据控制语言:
负责数据完整性、安全性的定义与检查以及并发控制、故
障恢复等。
数据语言按其使用方式具有两种结构形式:
交互式命令（又称自含型或自主型语言宿主型语言（一般可嵌入某些宿主语言中。
数据库管理员:
对数据库进行规划、设计、维护、监视等的专业管理人员。
数据库系统:
由数据库（数据、数据库管理系统（软件、数据库管理员（人员、硬件平台（硬件、软件平台（软件五个部分构成的运行实体。
数据库应用系统:
由数据库系统、应用软件及应用界面三者组成。
文件系统阶段:
提供了简单的数据共享与数据管理能力,但是它无法提供完整的、统一的、管理和数据共享的能力。
层次数据库与网状数据库系统阶段:
为统一与共享数据提供了有力支撑。
关系数据库系统阶段
数据库系统的基本特点:
数据的集成性、数据的高共享性与低冗余性、数据独立性（物理独立性与逻辑独立性、数据统一管理与控制。
数据库系统的三级模式:
（1概念模式:
数据库系统中全局数据逻辑结构的描述,全体用户公共数据视图;
（2外模式:
也称子模式与用户模式。
是用户的数据视图,也就是用户所见到的数据模式;
（3内模式:
又称物理模式,它给出了数据库物理存储结构与物理存取方法。
数据库系统的两级映射:
（1概念模式到内模式的映射;
（2外模式到概念模式的映射。
4.2数据模型
数据模型的概念:
是数据特征的抽象,从抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表与操作提供一个抽象的框架。
描述了数据结构、数据操作及数据约束。
E-R模型的基本概念
（1实体:
现实世界中的事物;
（2属性:
事物的特性;
（3联系:
现实世界中事物间的关系。
实体集的关系有一对一、一对多、多对多的联系。
E-R模型三个基本概念之间的联接关系:
实体是概念世界中的基本单位,属性有属性域,每个实体可取属性域内的值。
一个实体的所有属性值叫元组。
E-R模型的图示法:
（1实体集表示法;（2属性表法;（3联系表示法。
层次模型的基本结构是树形结构,具有以下特点:
（1每棵树有且仅有一个无双亲结点,称为根;
（2树中除根外所有结点有且仅有一个双亲。
从图论上看,网状模型是一个不加任何条件限制的无向图。
关系模型采用二维表来表示,简称表,由表框架及表的元组组成。
一个二维表就是一个关系。
在二维表中凡能唯一标识元组的最小属性称为键或码。
从所有侯选健中选取一个作为用户使用的键称主键。
表A中的某属性是某表B的键,则称该属性集为A的外键或外码。
关系中的数据约束:
（1实体完整性约束:
约束关系的主键中属性值不能为空值;
（2参照完全性约束:
是关系之间的基本约束;
（3用户定义的完整性约束:
它反映了具体应用中数据的语义要求。
4.3关系代数
关系数据库系统的特点之一是它建立在数据理论的基础之上,有很多数据理论可以表示关系模型的数据操作,其中最为著名的是关系代数与关系演算。
关系模型的基本运算:
（1插入（2删除（3修改（4查询（包括投影、选择、笛卡尔积运算4.4数据库设计与管理
数据库设计是数据应用的核心。
数据库设计的两种方法:
（1面向数据:
以信息需求为主,兼顾处理需求;
（2面向过程:
以处理需求为主,兼顾信息需求。
数据库的生命周期:
需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。
需求分析常用结构析方法和面向对象的方法。
结构化分析（简称SA方法用自顶向下、逐层分解的方式分析系统。
用数据流图表达数据和处理过程的关系。
对数据库设计来讲,数据字典是进行详细的数据收集和数据分析所获得的主要结果。
数据字典是各类数据描述的集合,包括5个部分:
数据项、数据结构、数据流（可以是数据项,也可以是数据结构、数据存储、处理过程。
数据库概念设计的目的是分析数据内在语义关系。
设计的方法有两种
（1集中式模式设计法（适用于小型或并不复杂的单位或部门;
（2视图集成设计法。
设计方法:
E-R模型与视图集成。
视图设计一般有三种设计次序:
自顶向下、由底向上、由内向外。
视图集成的几种冲突:
命名冲突、概念冲突、域冲突、约束冲突。
关系视图设计:
关系视图的设计又称外模式设计。
关系视图的主要作用:
（1提供数据逻辑独立性;
（2能适应用户对数据的不同需求;
（3有一定数据保密功能。
数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径,以提高数据库访问速度有效利用存储空间。
一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。
数据库管理的内容:
（1数据库的建立;
（2数据库的调整;
（3数据库的重组;
（4数据库安全性与完整性控制;
（5数据库的故障恢复;
（6数据库监控。
公共基础部分可以变化的题:
1一棵二叉树,第K层上最多有2（k-1个结点,深度为K的二叉树最多有2k-1个结点,如果是满二叉树呢?
例如:
在深度为5的满二叉树中,叶子结点的个数为（=2（5-1=16
2一棵二叉树共有70个叶子结点和80个度为1的结点,问这个二叉树的总结点
是多少?
答:
因为度为0的结点（叶子结点比度为2的结点多一个,所以度为2的结点数是69,所以总结点=70+69+80=219个
3一棵完全二叉树共有700个结点,则在该二叉树中有（350个叶子结点解答:
700/2=350
若把700改为675呢?
（=675/2=337.5进行四舍五入=338
4设树T的度为4,其中度为1,2,3,4的结点的个数分别为4,2,1,1。
则T中的叶子结点的个数为（8
解答:
n0=（t-1nt+（t-2n（t-1+...+1*n2+0*n1+1=3*1+2*1+1*2+0*4+1=8
5在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有多少个元素?
（3个
解答:
若头<尾,元素个数=尾-头
:
若头>尾,元素个数=15+（尾-头
7关于二叉树遍历问题:
有两个题型,一是给出二叉树,求三种遍历结果;二是给出两种遍历,求第三种遍历结果。
后者有点难度
三种遍历是:
前序（根左右、中序（左根右和后序（左右根
8关于查找和排序问题:
查找技术---顺序查找——对于长度为n的有序线性表,查找时需要比较n次二分法查找——对于长度为n的有序线性表,查找时需要比较log2n次
排序技术---假设线性表的长度为n,则冒泡排序和简单插入排序的比较次数（时间复杂度为n（n-1/2;希尔排序的比较次数为O（n1.5;简单选择排序的比较次数为n（n-1/2;堆排序的比较次数为O（nlog2n.
9关于出栈的问题:
记住是先进后出
例1:
栈底到顶依次存放A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈可能的序列是
ABCEDDCBEADBCEACDABE
例2:
如果进栈序列为e1,e2,e3,e4,则可能的出栈序列为:
e3,e1,e4,e2e2,e4,e3,e1e3,e4,e1,e2任意顺序
10关于E---R图
是实体属性和实体关系图,实体之间的关系有1:
11:
mm:
n
下面为大家提供一些习题
练习1
（1下面叙述正确的是______。
（C
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令（或语句的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.以上三种描述都不对
（2以下数据结构中不属于线性数据结构的是______。
（C
A.队列
B.线性表
C.二叉树
D.栈
（3在一棵二叉树上第5层的结点数最多是______。
（B
A.8
B.16
C.32
D.15
（4下面描述中,符合结构化程序设计风格的是______。
（A
A.使用顺序、选择和重复（循环三种基本控制结构表示程序的控制逻辑
B.模块只有一个入口,可以有多个出口
C.注重提高程序的执行效率
D.不使用goto语句
（5下面概念中,不属于面向对象方法的是______。
（D
A.对象
B.继承
C.类
D.过程调用
（6在结构化方法中,用数据流程图（DFD作为描述工具的软件开发阶段是______。
（B
A.可行性分析
B.需求分析
C.详细设计
D.程序编码
（7在软件开发中,下面任务不属于设计阶段的是______。
（D
A.数据结构设计
B.给出系统模块结构
C.定义模块算法
D.定义需求并建立系统模型
（8数据库系统的核心是______。
（B
A.数据模型
B.数据库管理系统
C.软件工具
D.数据库
（9下列叙述中正确的是______。
（C
A.数据库是一个独立的系统,不需要操作系统的支持
B.数据库设计是指设计数据库管理系统
C.数据库技术的根本目标是要解决数据共享的问题
D.数据库系统中,数据的物理结构必须与逻辑结构一致
（10下列模式中,能够给出数据库物理存储结构与物理存取方法的是______。
（A
A.内模式
B.外模式
C.概念模式
D.逻辑模式
（11算法的时间复杂度是指______。
（C
A.执行算法程序所需要的时间
B.算法程序的长度
C.算法执行过程中所需要的基本运算次数
D.算法程序中的指令条数
（12下列叙述中正确的是______。
（A
A.线性表是线性结构
B.栈与队列是非线性结构
C.线性链表是非线性结构
D.二叉树是线性结构
（13设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为______。
（B
A.349
B.350
C.255
D.351
（14结构化程序设计主要强调的是______。
（B
A.程序的规模
B.程序的易读性
C.程序的执行效率
D.程序的可移植性
（15在软件生命周期中,能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是______。
（D
A.概要设计
B.详细设计
C.可行性分析
D.需求分析
（16数据流图用于抽象描述一个软件的逻辑模型,数据流图由一些特定的图符构成。
下列图符名标识的图符不属于数据流图合法图符的是______。
（A
A.控制流
B.加工
C.数据存储
D.源和潭
（17软件需求分析阶段的工作,可以分为四个方面:
需求获取、需求分析、编写需求规格说明书以及______。
（B
A.阶段性报告
B.需求评审
C.总结
D.都不正确
（18下述关于数据库系统的叙述中正确的是______。
（A
A.数据库系统减少了数据冗余
B.数据库系统避免了一切冗余
C.数据库系统中数据的一致性是指数据类型的一致
D.数据库系统比文件系统能管理更多的数据
（19关系表中的每一横行称为一个______。
（A
A.元组
B.字段
C.属性
D.码
（20数据库设计包括两个方面的设计内容,它们是______。
（A
A.概念设计和逻辑设计
B.模式设计和内模式设计
C.内模式设计和物理设计
D.结构特性设计和行为特性设计
（21算法的空间复杂度是指______。
（D
A.算法程序的长度
B.算法程序中的指令条数
C.算法程序所占的存储空间
D.算法执行过程中所需要的存储空间
（22下列关于栈的叙述中正确的是______。
（D
A.在栈中只能插入数据
B.在栈中只能删除数据
C.栈是先进先出的线性表
D.栈是先进后出的线性表
（23在深度为5的满二叉树中,叶子结点的个数为______。
（C
A.32
B.31
C.16
D.15
（24对建立良好的程序设计风格,下面描述正确的是______。
（A
A.程序应简单、清晰、可读性好
B.符号名的命名要符合语法
C.充分考虑程序的执行效率
D.程序的注释可有可无
（25下面对对象概念描述错误的是______。
（A
A.任何对象都必须有继承性
B.对象是属性和方法的封装体
C.对象间的通讯靠消息传递
D.操作是对象的动态性属性
（41在下列选项中,哪个不是一个算法一般应该具有的基本特征______。
（C
A.确定性
B.可行性
C.无穷性
D.拥有足够的情报
（42希尔排序法属于哪一种类型的排序法______。
（B
A.交换类排序法
B.插入类排序法
C.选择类排序法
D.建堆排序法
（43下列关于队列的叙述中正确的是______。
（C
A.在队列中只能插入数据
B.在队列中只能删除数据
C.队列是先进先出的线性表
D.队列是先进后出的线性表
（44对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为______。
（B
A.N+1
B.N
C.（N+1/2
D.N/2
（45信息隐蔽的概念与下述哪一种概念直接相关______。
（B
A.软件结构定义
B.模块独立性
C.模块类型划分
D.模拟耦合度
（46面向对象的设计方法与传统的的面向过程的方法有本质不同,它的基本原理是______。
（C
A.模拟现实世界中不同事物之间的联系
B.强调模拟现实世界中的算法而不强调概念
C.使用现实世界的概念抽象地思考问题从而自然地解决问题
D.鼓励开发者在软件开发的绝大部分中都用实际领域
升级会员 