二级C公共基础知识及练习题库.docx
《二级C公共基础知识及练习题库.docx》由会员分享，可在线阅读，更多相关《二级C公共基础知识及练习题库.docx（23页珍藏版）》请在冰点文库上搜索。
二级C公共基础知识及练习题库
二级C公共基础知识及例题
1．1数据结构与算法
1.1.1算法
1.算法的概念
（1）概念:
算法是指一系列解决问题的清晰指令.
（2）4个基本特征:
可行性、确定性、有穷性、拥有足够的情报。
（3）两种基本要素：
对数据对象的运算和操作、算法的控制结构（运算和操作时间顺序）
（4）设计的基本方法：
列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
2．算法的复杂度
（1）算法的时间复杂度：
执行算法所需要的计算工作量。
（2）算法的空间复杂度：
执行算法所需的内存空间。
1．1．2数据结构的基本概念
数据结构指相互有关联的的数据元素的集合，即数据的组织形式。
其中逻辑结构反映数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。
数据结构按各种元素之间的前后件的关系的复杂度可划分为：
（1）线性结构：
有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。
（2）非线性结构：
不满足线性结构的数据结构。
1．1．3线性表及其顺序存储结构
1．线性表的基本概念
线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。
2．线性表的顺序存储结构
●元素所占的存储空间必须连续。
●元素在存储空间的位置是按逻辑顺序存放的。
3．线性表的插入运算
在第i个元素之前插入一个新元素的步骤如下：
步骤一：
把原来第n个节点至第i个节点依次往后移一个元素位置。
步骤二：
把新节点放在第i个位置上。
步骤三：
修正线性表的节点个数。
4．线性表的删除运算
删除第i个位置的元素的步骤如下：
步骤一：
把第i个元素之后的不包括第i个元素的n-i个元素依次前移一个位置；
步骤二：
修正线性表的结点个数。
1．1．4栈和队列
1．栈及其基本运算
（1）基本概念：
栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端进行，也被称为“先进后出”表或“后进先出”表。
●栈顶：
允许插入与删除的一端。
●栈底：
栈顶的另一端。
（不允许插入与删除的一端）
●空栈：
栈中没有元素的栈。
（2）特点。
●栈顶元素是最后被插入和最早被删除的元素。
●栈底元素是最早被插入和最后被删除的元素。
●栈有记忆作用。
●在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。
●栈顶指针top动态反映了栈中元素的变化情况
（3）顺序存储和运算：
入栈运算、退栈运算和读栈顶运算。
2．队列及其基本运算
（1）基本概念：
队列是指允许在一端进行插入，在另一端进行删除的线性表，又称：
先进先出“的线性表。
●队尾：
允许插入的一端，用尾指针指向队尾元素。
●排头：
允许删除的一端，用头指针指向头元素的前一位置。
（2）循环队列及其运算：
入队运算与退队运算。
1．1．5树和二叉树
1．树的基本概念
树是简单的非线性结构，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1，T2，。
。
。
Tm，每个集合又是一棵树，称T1，T2，。
。
。
Tm，m为根结点的子树。
●父节点：
每一个节点只有一个前件，无前件的节点只有一个，称为树的根结点（简称树的根）。
●子节点：
每一个节点可以后多个后件，无后件的节点称为叶子节点。
●树的度：
所有节点最大的度。
●树的深度：
树的最大的层次。
2．二叉树及其基本性质
二叉树是一种非线性机构，是有限的节点的集合，该集合为空（空二叉树）或由一个根节点及两棵互不相交的左右二叉子树组成。
可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
●二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根结点；
●每个节点最多有两棵子树，称为左子树和右子树。
3．二叉树的存储结构
二叉树通常采用链式存储结构，存储节点由数据域和指针域（左指针域和右指针域）组成。
二叉树的链式存储结构也称二叉树的链表，对满二叉树和完全二叉树可按层次进行顺序存储。
4.二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中所有节点，主要指非空二叉树，对于空二叉树则结束返回。
二叉树的遍历包括前序遍历、中序遍历和后序遍历。
1．1．6查找技术
（1）顺序查找：
在线性表中查找指定的元素。
（2）二分查找：
线性表必是顺序存储结构，且必是有序表，反复查找直到成功或子表长度为0是结束。
1．1．7排序技术
（1）交换类排序法：
借助数据元素的“交换”进行排序，包括冒泡排序法和快速排序法。
（2）插入类排序法：
包括简单插入排序法和希尔排序法。
（3）选择类排序法：
包括简单选择排序法和堆排序法。
1．2程序基础
1．2．1程序设计方法与风格
（1）设计方法：
程序设计指设计、编制、调试程序的方法和过程，主要有结构化程序设计方法、软件工程方法和面向对象方法。
（2）设计风格：
良好的设计风格要注重源程序文档化、数据说明方法、语句的结构和输入输出。
1．2．2面向对象的程序设计
面向对象方法的本质是主张从客观世界固有的事物出发来构造系统，强调建立的系统能映射问题域。
●对象：
用来表示客观世界中任何实体，可以是任何有明确边界和意义的东西。
●类：
具有共同属性、共同方法的对象的集合。
●实例：
一个具体对象就是其对应分类的一个实例。
●消息：
实例间传递的信息，它统一了数据流和控制流。
●继承：
使用已有的类定义作为基础建立新类的定义技术。
●多态性：
指对象根据所接受的住息而作出动作，同样的信息被不同的对象接收时有不同的行动的现象。
面向对象程序设计特点：
与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。
1．3软件工程基础
1．3．1软件工程基本概念
1．软件的定义与特点
（1）定义：
软件是指与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档和数据。
（2）特点：
●是逻辑实体，有抽象性。
●生产没有明显的制作过程。
●运行使用期间不存在磨损、老化问题。
●开发、运行对计算机系统有依赖性，受计算机系统的限制，导致了软件移植问题。
●复杂性较高，成本昂贵。
●开发涉及诸多社会因素。
2．软件危机与软件工程
软件危机指在计算机软件的开发和维护中遇到的一系列严重问题。
软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序，包括软件开发技术和软件工程管理。
3．软件工程过程
把输入转化为输出的一组彼此相关的资源和活动。
4．软件生命周期
软件产品从提出、实现、使用维护到停止使用的过程。
5．软件工程的目标
在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适用性、可移植性、可追踪性和可互操作性且满足用户需求的产品。
6．软件工程的原则
软件工程的原则包括：
抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。
7．软件开发工具
从初期的单向工具向集成工具发展，软件开发的方法必须得到相应工具的支持。
8．软件开发环境
软件开发环境是全面支持软件开发过程的软件工具的集合。
计算机辅助软件工程（CASE）是当前最有特色的研究工作和发展方向。
1．3．2结构化分析方法
需求分析的任务是发现需求、求精、建模和定义需求的过程，可概括为：
需求获取、需求分析、编写需求规格说明书和需求评审。
常用的分析方法：
●结构化分析方法：
其实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程。
常用工具包括数据流图、数字字典（核心方法）、判断树和判断表。
●面向对象分析方法。
1．3．3结构化设计方法
1．软件设计的基本概念和方法
软件设计是一个把软件需求转换为软件表示的过程。
（1）基本原理：
抽象、模块化、信息隐蔽、模块独立性（试题标准：
耦合性和内聚性）。
（2）基本思想：
将软件设计成由相对独立、单一功能的模块组成的结构。
2.概要设计
（1）4个任务：
设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。
（2）面向数据流的设计方法：
数据流图的信息分为交换流和事物流，结构形式有交换型和事务型。
3．详细设计的工具
详细设计的工具包括：
●图形工具：
程序流程图、N—S图、PAD、HIPO。
●表格工具：
判定表。
●语言工具：
PDL（伪码）。
1．3．4软件测试
1．目的
为了发现错误而执行程序的过程。
2．准则
●所有测试应追溯到用户需求。
●严格执行测试计划，排除测试的随意性。
●充分注意测试中的群集现象。
●程序员应避免检查自己的程序。
●穷举测试不可能。
妥善保存设计计划、测试用例、出错统计和最终分析报告。
3．软件测试技术和方法
软件测试的方法按是否需要执行被测软件的角度，可分为表态测试和动态测试，按功能分为白盒测试和黑盒测试。
（1）白盒测试：
根据程序的内部逻辑设计测试用例，主要方法有逻辑覆盖测试、基本路径测试等。
（2）黑盒测试：
根据规格说明书的功能来设计测试用例，主要诊断方法有等价划分法、分界值分析法、错误推测法、因果图法等，主要用于软件确认测试。
1.3.5程序的调试
（1）任务：
诊断和改正程序中的错误。
（2）调试方法：
强行排错法、回溯法和原因排除法。
1．4数据库设计基础
1．4．1数据库系统的基本概念
（1）数据（Data）：
描述事物的符号记录。
（2）数据库（DataBase）：
长期存储在计算机内的、有组织的、可共享的数据集合。
（3）数据库管理系统的6个功能：
数据组织、数据操纵、数据维护、控制及保护和数据服务。
（4）数据库技术发展经历了3个阶段：
人工管理阶段——文件系统阶段——数据库系统阶段
（5）数据库系统的特点：
集成性、高共享性、低冗余性、数据独立性、数据统一管理与控制等。
（6）数据库系统的内部机构体系：
三级模式（概念模式、内模式、外模式）和二级映射（外模式/概念模式的映射、概念模式/内模式的映射）构成了数据库系统内部的抽象结构体系。
1．4．2数据模型
数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，描述的内容有数据结构、数据操作和数据约束。
有3个层次：
概念数据模型、逻辑数据模型和物理数据模型。
（1）E—R模型：
提供了表示实体、属性和联系的方法。
实体间联系有“一对一”、“一对多”和“多对多”；
（2）层次模型：
利用树形结构表示实体及其之间联系，其中节点是实体，树枝是联系，从上到下是一对多关系。
（3）网状模型：
用网状结构表示实体及其之间联系，是层次模型的扩展。
网络模型以及记录型为节点，反映现实中较为复杂的事物联系。
（4）关系模型：
采用二维表（由表框架和表的无组组成）来表示，可进行数据查询、增加、删除及修改操作。
关系模型允许定义“实体完整性”、“参照完整性”、和“用户定义的完整性”三种约束。
●键（码）：
二维表中唯一能标识元组的最小属性集。
●候选键（候选码）：
二维表中可能有的多个键。
●主键：
被选取的一个使用的键。
1．4．3关系代数
（1）传统的集合运算：
关系并运算、关系交运算、关系差运算和广义笛卡尔积。
（2）专门的关系运算：
选择、投影、连接。
1．1．4数据库设计与管理
1．数据库设计概述
●基本思想：
过程迭代和逐步求精。
●方法：
面向数据的方法和面向过程的方法。
●设计过程：
需求分析—概念设计—逻辑设计—物理设计—编码—测试—运行—进一步修改。
2．数据库设计的需求分析
需求收集和分析是数据库设计的第一阶段，常用结构化分析方法（自顶向下、逐层分解）和面向对象的方法，主要工作有绘制数据流程图、数据分析、功能分析、确定功能处理模块和数据间关系。
数据字典：
包括数据项、数据结构、数据流、数据存储和处理过程，是对系统中数据的详尽描述。
3．数据库的设计
（1）数据库概念设计：
分析数据间内在的语义关联，以建立数据的抽象模型。
（2）数据库的逻辑设计：
从E—R图向关系模型转换，逻辑模式规范化，关系视图设计可以根据用户需求随时创建。
（3）数据库的物理设计：
是数据在物理设备上的存储结构与存取方法，目的是对数据库内部物理结构作出调整并选择合理的存取路径，以提高速度和存储空间。
6．数据库管理
数据库管理包括数据库的建立、数据库的调整、数据库的重组、数据库的安全性与完整性控制、数据库故障恢复和数据库的监控。
1）下面叙述正确的是______。
（C）
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令（或语句）的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.以上三种描述都不对
（2）以下数据结构中不属于线性数据结构的是______。
（C）
A.队列B.线性表C.二叉树D栈
（3）在一棵二叉树上第5层的结点数最多是______。
（B）A.8B.16C.32D.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.349B.350C.255D.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.32B.31C.16D.15
（24）对建立良好的程序设计风格，下面描述正确的是______。
（A）
A.程序应简单、清晰、可读性好B.符号名的命名要符合语法
C.充分考虑程序的执行效率D.程序的注释可有可无
（25）下面对对象概念描述错误的是______。
（A）
A.任何对象都必须有继承性B.对象是属性和方法的封装体C.对象间的通讯靠消息传递D.操作是对象的动态性属性
（26）下面不属于软件工程的3个要素的是______。
（D）
A.工具B.过程C.方法D.环境
（27）程序流程图（PFD）中的箭头代表的是______。
（B）
A.数据流B.控制流C.调用关系D.组成关系
（28）在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。
其中数据独立性最高的阶段是______。
（A）
A.数据库系统B.文件系统C.人工管理D.数据项管理
（29）用树形结构来表示实体之间联系的模型称为______。
（B）
A.关系模型B.层次模型C.网状模型D.数据模型
（30）关系数据库管理系统能实现的专门关系运算包括______。
（B）
A.排序、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表
（31）算法一般都可以用哪几种控制结构组合而成______。
（D）
A.循环、分支、递归B.顺序、循环、嵌套C.循环、递归、选择D.顺序、选择、循环
（32）数据的存储结构是指______。
（B）
A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示
C.数据在计算机中的顺序存储方式D.存储在外存中的数据
（33）设有下列二叉树：
对此二叉树中序遍历的结果为______。
（B）
A.ABCDEFB.DBEAFCC.ABDECFD.DEBFCA
（34）在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送______。
（D）
D.消息A.调用语句B.命令C.口令
（35）检查软件产品是否符合需求定义的过程称为______。
（A）
A.确认测试B.集成测试C.验证测试D.验收测试
（36）下列工具中属于需求分析常用工具的是______。
（D）
A.PADB.PFDC.N-SD.DFD
（37）下面不属于软件设计原则的是______。
（C）
A.抽象B.模块化C.自底向上D.信息隐蔽
（38）索引属于______。
（B）
A.模式B.内模式C.外模式D.概念模式
（39）在关系数据库中，用来表示实体之间联系的是______。
（D）
A.树结构B.网结构C.线性表D.二维表
（40）将E-R图转换到关系模式时，实体与联系都可以表示成______。
（B）
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+1B.NC.（N+1）/2D.N/2
（45）信息隐蔽的概念与下述哪一种概念直接相关______。
（B）
A.软件结构定义B.模块独立性C.模块类型划分D.模拟耦合度
（46）面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。
（C）
A.模拟现实世界中不同事物之间的联系B.强调模拟现实世界中的算法而不强调概念
C.使用现实世界的概念抽象地思考问题从而自然地解决问题
D.鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考
（47）在结构化方法中，软件功能分解属于下列软件开发中的阶段是______。
（C）
A.详细设计B.需求分析C.总体设计D.编程调试
（48）软件调试的目的是______。
（B）
A.发现错误B.改正错误C.改善软件的性能D.挖掘软件的潜能
（49）按条件f对关系R进行选择，其关系代数表达式为______。
（C）
A.R|X|RB.R|X|RC.бf（R）D.∏f（R）
（50）数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是______。
（D）
A.自顶向下B.由底向上C.由内向外D.由整体到局部
（51）在计算机中，算法是指______。
（C）
A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法
（52）栈和队列的共同点是______。
（C）
A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点
（53）已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。
（A）
A.cedbaB.acbedC.decabD.deabc
（54）在下列几种排序方法中，要求内存量最大的是______。
（D）
A.插入排序B.选择排序C.快速排序D.归并排序
（55）在设计程序时，应采纳的原则之一是______。
（A）
A.程序结构应有助于读者理解B.不限制goto语句的使用C.减少或取消注解行D.程序越短越好
（56）下列不属于软件调试技术的是______。
（B）
A.强行排错法B.集成测试法C.回溯法D.原因排除法
（57）下列叙述中，不属于软件需求规格说明书的作用的是______。
（D）
A.便于用户、开发人员进行理解和交流
B.反映出用户问题的结构，可以作为软件开发工作的基础和依据
C.作为确认测试和验收的依据D.便于开发人员进行需求分析
（58）在数据流图（DFD）中，带有名字的箭头表示______。
（C）A.控制程序的执行顺序
B.模块之间的调用关系C.数据的流向D.程序的组成成分
（59）SQL语言又称为______。
（C）
A.结构化定义语言B.结构化控制语言C.结构化查询语言D.结构化操纵语言
（60）视图设计一般有3种设计次序，下列不属于视图设计的是______。
（B）
A.自顶向下B.由外向内C.由内向外D.自底向上
（61）
升级会员 