计算机二级c语言基础知识重点
- 格式：doc
- 大小：38.50 KB
- 文档页数：5
百度文库 - 让每个人平等地提升自我
1 第1章 数据结构与算法
1．1．1算法的基本概念
所谓算法是指解方案的准确而完整的描述
1． 算法的基本特征 1)可行性 2)确定性 3)有穷性 4)拥有足够的情报 5)
2． 算法的基本要素 1)算法中对数据的运算的操作 ①算术运算 加、减、乘、除
②逻加运算③关系运算④数据传输 主要包括赋值、输入、输出操作
2）算法的控制结构
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成
描述算法的工具一般通常有传统流程图、N-S流程图、算法描述语言等
3． 算法设计的基本方法
1）列举法 2）归纳法 3）递推：从一个已知初始条件出发，逐次推出所要求的各中间结果和最后结果 4）递归：为了降低问题的复杂度，一般总是将问题逐层分解，最后归结为一些最简单的问题 ☆递归分为：直接递归和间接递归两种
直接递归：一个算法P调用P自已 。间接递归：一个算法P调用Q，Q又调用P
5）递半递推技术：所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓：“递推”，是指重复“减半”的过程。
6）回溯法：逐步探测解决问题的方法
1．1．2算法复杂度
算法的复杂度主包括时间复杂度和空间复杂度
☆ 时间复杂度：是指执行算法所需的计算工作量（即基本运算次数）
☆ 算法空间复杂度：执行这个算法所需要的内存空间
1． 2数据结构的基本概念
简单地说，数据结构是指相互有关联的数据元素的集合。
数据结构是指反映数据元素之间关系的数据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系
1． 数据的逻辑结构：反映数据元素之间逻辑关系的数据结构
☆ 逻辑结构有两个要素：一个是数据元素集合，通常记为D；二是D上的关系通常记为R
1． 5一年四季的数据结构可以表示成 B={D,R} D={春、夏、秋、冬}
R={（春、夏），（夏、秋），（秋、冬）}
2．数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）
1．2．2数据结构的图形表示
春 夏 秋 冬
☆在数据结构中,没有前件的结点称为根结点；没有后件的结构称终结点（也称为叶子结点）
1．3线性表及其顺序存储结构
1．3．1线性表的基本概念 父亲
儿子 女儿 百度文库 - 让每个人平等地提升自我
2 ☆线性表(Linear List)是最简单、最常用的一种数据结构
☆矩阵也一个线性表，只不过它是一个比较复杂的线性表。在矩阵中，既可以把每一行看成一个数据元素
习题1
一．选择题
1．算法的时间复杂度是指( )
A)执行算法程序所需的时间 B)算法程序的长度 C)算法执行过程中所需的基本运算次数
D)算法程序的指令的条数
2．算法的空间复杂是指( )
A)算法程序的长度B)算法程序的指令条数C)算法程序所占的存储空间D)算法执行过程中所需要的存储空间
3．下列叙述中正确的是( )
A)线性表是线性结构B)栈与队列是非线性结构C)线性表是非线性结构D)二叉树是线性结构
4．数据的存储结构是指( )
A) 数据所占的存储空间量B)数据的逻辑结构在计算机的表示
B) 数据在计算机中的顺序存储方式D)存储在外存中的数据
5．下列关系队列的叙述中正确的是( )
A)在队列中只能插入数据B)在队列中只能删除数据C)队列是先进先出的线性表D)队列是先进后出的线性表
6．下列关系栈的叙述中正确的是( )
A)在栈中只能插入数据B)在栈中只能删除数据C)栈是先进先出的线性表D)栈是先进后出的线性表
7．设有下列二叉树：
对此二叉树中序遍历的结果为( )A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA
8．在深度为5的满二叉树中，叶子结点的个数为( )
A)31 B)31 C)16 D)15
9．对长度为n的线性表进行顺序查找，在最坏的情况下需要的比较次数为( )
A) n+1 B)n C)(n+1)/2 D)n/2
10．设树T的度为4,其中度为1,2,3,4的结点的个数分别为4,2,1,1。则T中叶子结点数为( )
A) 8 B)7 C)6 D)5
二填空题
1．在长度为n的有序线性表中进行二分查找，需要的比较次数为 A
B C
D E F 百度文库 - 让每个人平等地提升自我
3 2．设一棵完全二叉树共有700 个结点，则在该二叉树中有 个叶结点
3．设一棵二叉树中遍历的结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历的结果为______________-
4．在最坏的情况下，冒泡法排序的时间复杂度为__________
5．在一个容量为15的循环队列中，若头指针front=6,尾指针rear=9,则该循环队列中共有____个元素
习题2
一．选择题
1．结构化程序设计主要强调的是( )
A)程序的规模 B)程序的易读性C)程序的执行效率D)程序的可移植性
2．对建立良好的程序设计风格，下面描述正确的是( )
A)程序简单、清晰、可读性好B)符号的命名只要符合语法C)充分考虑程序的执行效率
D)程序的注释可有可无
3．在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送( )
A)调用语句 B)命令 C)口令D)消息
4．信息隐蔽的概念与下述哪一种概念直接相关( )
A)软件结构定义B)模块独立性C)模块类型划分D)模块耦合度
5．下面对对象概念描述错误的是( )
A)任何对象都必须有继承性B)对象是属性和方法的封装体C)对象的通讯靠消息传递
D)操作是对象的动态属性
二．填空题
1．结构化程序设计的三种基本结构为顺序、选择和________
2．源程序文档化要求程序应加注释。注释一般分为序言性注释和___________
3．在面向对象方法中，信息隐蔽是通过对象的_________性来实现的。
4． 类是一个支持集成的抽象数据类型，而对象是类的______。
5． 在面向对象方法中，类之间共享属性的操作的机制称为_________。
习题3
一．选择题
1．在软件生命力周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是( ) A)根要设计B)详细设计C)可行性分析D)需求分析
2．下面属性软件工程3个要素的是( )A)工具B)过程C)方法D)环境
3．检查软件产品是否符合需求定义的过程称为( )
A)确认测试B)集成测试C)验证测试D)验收测试
4．数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是( )
A)控制流B)加工C)数据存储D)源和潭
5．下面不属于软件设计原则的是( )A)抽象B)模块化C)自底向上D)信息隐蔽
6．程序流程图(PFD)中箭头代表的是( )A)数据流B)控制流C)调用关系D)组成关系 百度文库 - 让每个人平等地提升自我
4 7．下列工具中为需求分析常用的工具是( )A)PAD B)PFD C)N-S D)DFD
8．在结构化方法中，软件功能分解属于下列开发中的阶段是( )
A)详细设计B)需求分析C)总体设计D)编程调试
9．软件调试的目的是( )A)发现错误B)改正错误C)改善软件的性能D)挖掘软件的潜能
10．软件需求分析阶段的工作，可以分四个方面：需求获取，需求分析，编写需求规格说明书，以及( ) A)阶段性报告B)需求评审C)总结D)都不正确
二、填空题
1．软件是程序、数据和_______的集合
2．Jackson方法是一种面向__________的结构化方法
3．软件工程研究的内容主要包括：__________技术和软件程序管理。
4．数据流图的类型有_________和事务型。
6．
7． 软件开发环境是全面支持软件开发全过程的_______集合。
习题4
一．选择题
1．在数据库管理技术发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段的是( )
A)数据库系统B)文件系统C)人工管理D)数据项管理
2．下述关于数据库系统的叙述中正确的是( )
A) 数据库系统减少了数据冗余B)数据库避免一切冗余
C)数据库系统中数据的一致性是指数据类型一致
D)数据库管理比文件系统管理更多的数据
3．数据库系统的核心是( ) A)数据库B)数据管理系统C)数据模型D)软件工具
4．用树形结构来表示实体之间联系的模型称为( )
A)关系模型B)层次模型C)网状模型D)数据模型
5．关系表中的每一行称为一个( )A)元组B)字段C)属性D)码
6．关系数据库管理系统能实现的专门关系运算包括( )
A)排序、索引、统计B)选择、投影、连接C)关联、更新、排序D)显示、打印、制表
7．在关系数据中，用来表示实体之间联系的是( )
A)树结构B)网结构C)线性表D)二维表
8．数据库设计包括两个方面的设计内容，它们是( )
A) 概念设计和逻辑设计B)模式设计和内模式设计
C)内模式设计和物理设计D)结构特性设计和行为特性设计
9．将E-R图转换到关系模式时，实体与联系都可以表示成( )A)属性B)关系C)键D)域
二．填空题
1．一个项目具有一个项目主管，一个项目主管可以管理多个项目，则实体“项目主管”与实体“项目”的联系属于________的联系。
