计算机公共基础(第三章)

计算机公共基础一、教学目标1. 使学生掌握计算机基础知识，包括计算机的发展史、计算机系统的组成、硬件和软件的基本概念。

2. 培养学生掌握基本的计算机操作技能，包括Windows操作系统的使用、文字处理软件Word、电子表格软件Excel的使用。

3. 培养学生具备基本的计算机应用能力，包括网络的使用、常用办公软件的使用、计算机安全与维护。

二、教学内容1. 第一章：计算机基础知识教学内容：计算机的发展史、计算机系统的组成、硬件和软件的基本概念。

2. 第二章：Windows操作系统教学内容：Windows操作系统的安装、界面及基本操作、文件管理、系统设置、常用附件的使用。

3. 第三章：文字处理软件Word教学内容：Word的基本操作、文档编辑与格式设置、表格制作、图文混排、文档打印。

4. 第四章：电子表格软件Excel教学内容：Excel的基本操作、数据录入与编辑、公式与函数的使用、数据分析与处理、图表制作。

5. 第五章：计算机网络基础教学内容：计算机网络的基本概念、Internet的使用、电子邮件的发送与接收、网络安全的注意事项。

三、教学方法1. 采用讲授法，讲解计算机基础知识，使学生掌握计算机的基本概念和原理。

2. 采用实践教学法，让学生亲自动手操作，熟练掌握Windows操作系统、Word 和Excel的使用技巧。

3. 采用案例教学法，通过实际案例分析，使学生学会计算机在实际工作中的应用。

四、教学资源1. 教材：《计算机公共基础》2. 课件：PowerPoint或其他演示软件制作的课件3. 实验设备：计算机、投影仪、白板等4. 网络资源：Internet、电子邮件客户端软件等五、教学评价1. 平时成绩：学生课堂表现、作业完成情况、实验报告等，占总评的30%。

2. 考试成绩：期末进行的理论知识考试和实际操作考试，占总评的70%。

3. 综合评价：结合平时成绩和考试成绩，全面评价学生的计算机公共基础知识和技能掌握情况。

全国计算机全国计算机二级公共基础知识二级公共基础知识二级公共基础知识((重点部分重点部分))第一章 数据结构基础1.1算法1.1.1 算法的基本概念算法是解题方案的准确而完整的描述算法是解题方案的准确而完整的描述，，它不等于程序它不等于程序，，也不等计算方法也不等计算方法。

算法的基本特征可行性(effectiveness) 确定性(definiteness) 有穷性(finiteness) 拥有足够的情报 算法的时间复杂度执行算法所需要的计算工作量 与下列因素有关：书写算法的程序设计语言 ,编译产生的机器语言，代码质量 机器执行指令的速度 ,问题的规模 问题的规模函数 算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n 的某个函数f(n)，记作记作：：T(n)=O(f(n)) 记号“O ”读作“大O ”。

表示随问题规模n 的增加，算法执行时间的增长率和f(n)相应增加。

常见算法复杂度常见算法复杂度：：O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶 O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶算法的空间复杂度算法执行过程中所需的最大存储空间 存储量包括以下三部分算法程序所占的空间 ,输入的初始数据所占的存储空间 ,算法执行过程中所要的额外空间1.2 数据结构的基本概念数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式 常用的存储结构：顺序, 链式, 索引一种数据结构可根据需要采用不同的存储结构。

采用不同的存储结构，其数据处理的效率是不同 线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。

常见的线性结构有：线性表、栈与队列、线性链表非线性结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。

第一章数据结构和算法（习题)1.1算法一、选择1、下列叙述中正确的是（C )A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指执行算法程序中指令（或语句)的条数C、算法的有穷性是指算法必须能执行有限个步骤之后终止D、以上 3 种描述都不对2、下列叙述中正确的是（A ）A)、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据量D、以上 3 种说法都不对3、下列关于算法的时间复杂度陈述正确的是（C ）A、算法时间复杂度是指执行算法程序所需要的时间B、算法的时间复杂度是指算法程序的长度C、算法的时间复杂度是指算法程序执行过程中所需要的基本运算次数D、算法的时间复杂度是指算法程序中的指令条数4、算法的时间复杂度是指(C）A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数.5、算法的空间复杂度是指（ D ）A、算法程序的长度B、算法程序中的指令条数C、算法程序所占的存储空间D、算法执行过程中所需要的存储空间6、以下叙述正确的是（ D ）A、算法空间复杂度是指算法程序的长度B、算法的效率只与所处理数据的规模有关，而于数据的存储结构无关C、数据的逻辑结构与存储结构是一一对应的D、上述三种说法都不对.7、算法分析的目的是（ D ）A) 找出数据结构的合理性B)找出算法中输入和输出之间的关系C)分析算法的易懂性和可靠性D)分析算法的效率以求改进8、下列叙述中正确的是（ D ）________.A)一个算法的空间复杂度大，则其时间复杂度也必定大B)一个算法的空间复杂度大，则其时间复杂度必定小C)一个算法的时间复杂度大，则其空间可复杂度必定小9、在计算机中，算法是指（D ）A) 加工方法 B)用解题方案准确而完整的描述.C)排序方法D)查询方法10、在下列选项中，哪个不是一个算法一般应该具有的基本特征_C_____.A.确定性B.可行性C.无穷性D.拥有足够的情报11、下列叙述正确的是（ B ）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度和空间复杂度一定相关12、算法一般都可以用哪几种控制结构组合而成_D_____.A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环二、填空1、算法的复杂度主要包括_时间_复杂度和空间复杂度.2、算法执行过程中所需要的存储空间称为算法_空间复杂度_3、问题处理方案的正确而完整的描述称为为_算法_.4、算法基本特征是可行性，确定性，__有穷性___和拥有足够的情报.5、在算法正确的前提下，评价一个算法的两个标准是__时间复杂度和空间复杂度 .1.2数据结构一、选择1、以下数据结构中不属于线性数据结构的是（ C ）A、队列B、线性表C、二叉树D、栈2、数据的存储结构是指（ D ）A、存储在外存中的数据B、数据所占的存储空间C、数据在计算机中的顺序存储方式D、数据结构在计算机中的表示3、下列叙述中正确的是（ D ）A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构C、一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D、一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率.4、下列叙述中正确的是（ A ）A、线性链表是线性表的链式存储结构B、栈和队列是非线性结构C、双向链表是非线性结构D、只有一个根结点的二叉树是线性结构5、以下数据结构中不属于线性数据结构的是（ C ）A、队列B、线性表C、二叉树D、栈6、数据结构分为（ D ）A、表、队列、栈和树B、逻辑结构C、存储结构D、逻辑结构和存储结构7、数据结构是指反映数据元素之间关系的数据元素集合的表示，在下面的选项中，包含了数据结构信息的选项是（ B ）A、表示各数据元素之间的大小关系B、表示各数据元素之间的前后件关系C、表示各数据元素之间的相容关系D、表示各数据元素之间的排斥关系8、下面是对空的数据结构的描述，期中描述正确的是（ C ）A、一个空的数据结构只能是线性结构B、一个空的数据结构只能是非线性结构C、线性结构和非线性结构都可以是空的数据结构D、以上 3 个叙述都不对.9、数据结构中，与所使用的计算机无关的是数据的（ C ）A) 存储结构B)物理结构C)逻辑结构D)物理和存储结构10、数据结构作为计算机的一门学科，主要研究数据的逻辑结构，对各种数据结构进行的运算以及（ A）A)数据的存储结构B)计算方法C)数据映象D)逻辑存储11、下列叙述中正确的是____A__.A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构12、数据的存储结构是指___B___.A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据13、下列叙述中正确的是 (D)A) 数据的逻辑结构与存储结构必定是一一对应的B)由于计算机存储空间是向量式存储结构.因此，数据的存储结构必定是线性结构C)程序设计语言中的数组一般是顺序存储结构，因此,利用数组只能处理线性结构D)以上 3 种说法都不对二、填空1、数据的逻辑结构在计算机存储空间中的存放方式称为数据的_存储结构_.2、按照逻辑结构分类，数据结构分为线性结构和非线性结构.二叉树属于非线性__.3、数据逻辑结构有线性结构和__非线性___两大类.4、数据结构分为线性结构和非线性结构，带链的队列属于__线性结构1.3 顺序表和线性链表一、选择1、下列关于线性链表的描述正确的是（A )A、存储空间不一定连续，且各元素的存储顺序是任意的B、存储空间不一定是连续的，且前件元素一定存储在后件元素前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须是连续的，且各元素的存储顺序是任意的2、链表不具有得特点是（ B )A)不必事先估计存储空间B)可随机访问任意元素所需空间与线性表长度成正比C)插入删除元素不需要移动元素D)3、用链表表示线性表的优点是（ C )A)便于随机存储B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序和逻辑顺序相同4、线性表 L=(A1,A2,A3,……AI,…AN),下列说法正确的是（ D )A)每个元素都有一个直接前件和直接后件B)线性表至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小D)除了第一元素和最后一个元素，其余每个元素都有一个且只有一个直接前件和直接后件.5、在单链表中，增加头节点的目的是（ A )A)方便运算的实现B)使单练表至少有一个节点C)标识表节点中首节点的位置D)说明单练表是线性表达额链式存储实现.6、采用链接方式存储线性表的优点是C)A)便于随机读取B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序和逻辑顺序相同7、与单链表相比，双向链表的优点之一是（ D)A)插入，删除更加方便B)可以随机访问C)可以省略表头指针或表尾指针D)顺序访问相邻结点更加灵活.8、对线性表，应该采用链表表示的下列情况的是 (B)A)经常需要随机地读取数据 B)经常需要进行插入和删除操作C)表中元素的个数不变D)表中元素需要占据一片连续的存储空间9、线性表的顺序存储和线性表的链式存储分别是 (B)A)顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构10、循环链表的主要优点是 (B)A)不再需要头指针了. B)从表中任一结点出发都能访问整个链表C)在进行插入、删除运算时，能更好的保证链表不断开.D)已知某个结点位置之后，能够容易的找到它的直接前件.二、填空1、顺序存储方法是把逻辑上相邻的节点存储在物理位置___相邻_____的存储单元中.2、长度为 n 的顺序存储线性表中，当在任何位置上插入一个元素的概率相等时，插入一个元素所需要移动元素的平均个数为____ n/2_______.3、数据结构分为逻辑结构和存储结构，循环队列属于__存储______结构.1.4栈和队列一、选择1、下列关于栈叙述正确的是 (D)A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、对栈的插入和删除操作中，不需要改变栈底的指针2、下列关于栈的描述错误的是(B)A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入和删除操作中，不需要改变栈底指针.3、下列关于栈的描述正确的是(C)A 在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除元素D、栈是特殊的线性表，只能在一段插入元素，而在另一端删除元素4、按照先进后出原则组织数据的是（B)A、队列B、栈C、双向链表D、二叉树5、下列数据结构中，插入时不需要移动其他元素的是(C)A、有序线性表B、无序线性表C、栈和队列D、以上都不是6、设栈S 的初始状态为空，元素 a,b,c,d,e,f 依次通过栈S，若出栈的顺序是b,d,c,f,e,a 则栈的容量至少应该为 (A)A、3B、4C、5D、67、栈和队列的共同特点是(C)A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点8、一些重要的程序语言（如 c 语言和 pascal 语言)允许过程的递归调用.而实现递归中的存储分配方式通常用(A)A) 栈B)堆C)数组D)链表9、栈通常采用的两种存储结构是(A)A)顺序存储结构和链式存储结构B)散列方式和索引方式C)链表存储和数组D)线性存储和非线性存储10、栈底至栈顶依次存放元素 A、B、C、D,在第五个元素 E入栈之前，栈中元素可以出栈则出栈的序列可能是( B)A)ABCED B)DCBEA C)DBCEA D)CDABE11、下列关于队列的叙述中正确的是___C___.A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表12、如果进栈序列为 e1,e2,e3,e4则可能的出栈序列是 (B)A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意顺序二、填空1、在一个容量为15 的循环队列中，若头指针为front=6,尾指针rear=9,则该循环队列中共有___3____个元素.2、当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进入入队运算，这种情况称为___上溢________.1.5树和二叉树一、选择1、设树 T 的度为 4，其中度为 1，2，3，4 的结点个数分别为 4，2，1，1.则叶子结点数为()A、8B、7C、6D、52、树是结点的集合，它的根结点数目是（）A) 有且只有 1 个B)1 或多于 1 个C)0 或 1 D)至少 23、在一棵二叉树上第 5 层的结点数最多的是（）A、8B、16C、32D、154、一棵二叉树共有 70 个叶子结点与 80 个度为 1 的结点，则该二叉树中总的结点个数为A、221B、219C、231D、2295、具有 3 个结点的二叉树有（）A)2 种形态B) 4 种形态C)7 种形态D) 5 种形态6、下列关于二叉树的说法正确的是（）A)一棵二叉树中任何一个结点要么是叶子结点，要么恰有两个子树B)二叉树中的结点个数大于 0C)一棵二叉树中叶子结点的个数等于度为 2 的结点个数加 1D)二叉树中任何一个结点的左子树和右子树上的结点个数一定相等7、深度为 5 的二叉树至多有（）个结点.A)16 B)32 C)31 D)108、在深度为 7 的满二叉树中，叶子结点的个数为（）A、32B、31C、64D、639、在一棵深度为 K 的完全二叉树中，所含结点个数不少于( )A)2K B)2K+1 C)2K-1 D)2K-110、在一棵具有 35 个结点的完全二叉树中，该树的深度是（）A)5 B)6 C)7 D)811、设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为______. A. 349B. 350C. 255D. 351二、填空1、某二叉树中度为2的结点有18 个，则该二叉树中有_____19_个叶子结点.2、一棵二叉树第六层的结点数最多为____32__个3、设一棵完全二叉树共有 700 个结点，则二叉树中有____350__个叶子结点.4、在深度为 7 的满二叉树中，度为 2 的结点个数为______.答案 ACBBD CCCDB B 19 32 350 63 19 631.6二叉树遍历一、选择1、已知二叉树后序遍历序列是 DABEC,中序遍历是 DEBAC，则前序遍历是（）A) acbedB)decab C)deabc D)cedba2、已知一棵二叉树前序遍历和中序遍历分别为 ABDEGCFH和DBGEACHF，则二叉树的后序遍历为（）A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG3、若某二叉树的前序遍历访问顺序是 abdgcefh,中序 dgbaechf,则后序遍历为（）A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca4、设有下列二叉树,求后序遍历（）A) ZBTYCPXA B)ATBZXCYP C)ZBTACYXP D)ATBZXCPY5、对如图所示二叉树进行后序遍历的结果为（）A 、ABCDEFB 、DBEAFC C 、ABDECFD 、DEBFCA6、一棵二叉树的前序遍历序列是 ABDGCFK,中序序列是 DGBAFCK,则它的后序遍历是（) A)ACFKDBG B)GDBFKCA C)KCFAGDB D)ABCDFKG7、对下列二叉树,后序遍历A)DYBFAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ二、填空1、设二叉树的中序遍历为DBEAFC,前序为ABDECF ，则后序遍历为________________. 答案： DBDAD BB DEBFCA1.7查找与排序一、选择1、在下列数据结构中，能用二分法进行查找的是（ ）A 、顺序存储的有序线性表B 、线性链表C 、二叉链表D 、有序线性链表2、对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ ）A 、log2nB 、n/2C 、nD 、n+13、下列叙述中正确的是A 、线性链表是线性表的链式存储B 、栈和队列是非线性结构C 、双向链表是非线性结构D 、只有根结点的的二叉树是线性结构4、希尔排序法属于哪一种类型的排序法（ ）A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法5、对于长度为N 的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是（）A 、冒泡排序为n2B 、冒泡排序为 nC 、快速排序为 nD 、快速排序为 n(n-1)/2二、填空题1、对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为_______________.2、长度为 n 的有序线性表中进行二分法查找，需要的比较次数为___________.3、排序是计算机程序设计中的一个重要操作，常见的排序方法有插入排序，___________和选择排序等.4、冒泡排序与快速排序属于__________类的排序方法答案： ACABD 55 log2n 交换类交换第二章程序设计基础（习题)2.1程序设计规范及结构化程序设计一、选择1、下面描述中，符合结构化程序设计风格的是A、使用顺序，选择，循环三种基本控制结构表示程序的控制结构B、模块只有一个入口，可以有多个出口C、注意提高程序的执行效率D、不使用 GOTO 语句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)输入数据前要有提示信息二、填空1、结构化程序设计中的 3种基本逻辑结构为顺序、选择和________.2、源程序文档化要求程序应加注释.注释一般分为序言性注释和________、__________. 答案：ADDBA DAA 循环功能性注释2.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、操作是对象的动态属性（）6、下面叙述正确的是（）A、在面向对象的程序设计中，各个对象之间应具有相对独立，相互依赖性小B、在面向对象的程序设计中，各对象之间应具有密切的联系C、在面向对象的程序设计中，各个对象应都是公用的D、上述三种说法都不对.7、在面向对象方法中，实现信息屏蔽是通过对象的某一特性来实现的，这个特性是（）A、封装B、类C、对象D、继承8、在面向对象的程序设计中，能表示类之间相似性质的机制是（）A、继承B、封装C、分类D、虚函数机制9、以下不属于对象的基本特点的是（）A) 分类性B)多态性C)继承性D)封装性二、填空1、在面向对象方法中，类的实例称为________._______.2、在面向对象方法中，________.描述的是具有相似属性和操作的一组对象.3、在面向对象方法中，类之间共享属性和操作的机制称为________.4、在面向对象方法中，信息屏蔽是通过对象的________.性来实现的.5、类是一个支持集成的抽象数据类型，而对象是类的________.6、所谓数据封装就是将一组数据与这组数据有关的操作组合在一起，形成一个实体，这个实体也就是__________.7、类描述的是具有相似性质的________.8 、在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为________________.9、______.是一种信息屏蔽技术，目的在于将对象的使用者和对象的设计者分开答案：DACDA ABAC 对象类继承封装实例对象对象消息封装第三章软件工程基础（习题）3.1软件及软件特点一、选择1、下列描述中正确的是（）A、程序就是软件B、软件开发不受计算机系统限制C、软件既是逻辑实体，又是物理实体D、软件是程序、数据与相关文档的集合.二、填空1、软件是程序、数据和__________的集合答案：D 文档3.2软件危机及软件工程一、选择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)计算机的发展二、填空1、软件工程研究的内容包括：________技术和软件工程管理.答案：CDBCC 软件开发3.3软件生命周期及需求分析一、选择1、软件开发的结构化生命周期方法将软件生命周期划分成（）A)定义、开发、运行维护B)设计阶段、编程阶段、测试阶段C)总体设计、详细设计、编程调 D)需求分析、功能定义、系统设计2、在结构化方法中，在软件生命周期中用数据流图(DFD)作为描述工具的阶段是（）A、可行性分析B、需求分析C、详细设计D、程序编码3、在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是A、概要设计B、详细设计C、可行性分析D、需求分析4、下列工具中为需求分析常用工具的是（）A、PADB、PFDC、N-SD、DFD5、数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成，下列图符名标识的图符不属于数据流图合法图符的是（）A、控制流B、加工C、数据存储D、源和潭6、软件需求分析阶段的工作，可以分为四个方面：需求获取，需求分析、编写需求规格说明书，以及( )A、阶段性报告B、需求评审C、总结D、都不正确7、数据流图用于描述一个软件的逻辑模型，数据流图由一些特定的图符构成.下列图符名标识的图符属于数据流图合法图符的是（）A、控制流B、变量名C、数据存储D、注释8、需求分析阶段的任务是确定（）A) 软件开发方法B)软件开发工具C)软件开发费用D)软件系统功能9、在结构化分析方法中，数据字典的作用是（）A、存放所需处理的原始数据B、存放所有处理的结果C、存放所有的程序文件D、描述系统中所用到的全部数据和文件信息10、需求分析种开发人员要从用户那里了解（）A) 软件做什么B)用户使用界面C)输入的信息D)软件的规模11、数据流图用于抽象地描述一个软件的逻辑模型，数据流图由一些特定图符构成.下列图符名表示图符不属于数据流图合法图符的是（）A)控制流B)加工C)数据存储D)源和潭二、填空1、数据流图的类型有________.和事务型.2、软件生命周期中可分为多个阶段，一般定义为定义阶段、开发阶段和维护阶段.编码和测试属于________.阶段.可行性研究属于________.阶段.3、在结构化分析使用的数据流图（DFD)中，利用________.对其中的图形元素进行确切解释.4、在结构化设计方法中，数据流图表达了问题中的数据流与加工之间的关系，并且每一个_______对应一个处理模块.5、在结构化分析方法中，用于描述系统中所用到的全部数据和文件的文档称为_________.6、在结构化分析使用的数据流图中，利用什么对_______对其中的图形元素进行确切的解释.答案：ABDDA BCDDA A 变换型开发、定义数据字典加工数据字典数据字典3.4概要设计和详细设计1、在软件开发中，下列任务不属于设计阶段的是A、数据结构设计B、给出系统模型结构C、定义模块算法D、定义需求并建立系统模型2、下列选项中不属于软件生命周期开发阶段任务的是________.A)软件测试 B)概要设计 C)软件维护 D)详细设计3、在结构化分析方法中，软件功能分解属于下列软件开发中的阶段是（)A、详细设计B、需求分析C、总体设计D、编程调试4、在软件设计中，不属于过程设计工具的是（）A、PDL(过程设计语言)B、PAD图C、N-S 图D、DFD 图5、程序流程图(PFD)中的箭头代表的是（）A、数据流B、控制流C、调用关系D、组成关系6、在结构化设计方法生成的结构图（SC)中，带有箭头的连线表示（）A)模块之间的调用关系B)程序的组成成分C)控制程序的执行顺序D)数据流向7、软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指（）A)模块间的关系B)系统结构部件转化成软件过程描述C)软件层次结构D)软件开发过程8、下面不属于软件设计原则的是（）A、抽象B、模块化C、自底向上D、信息屏蔽9、为了使模块尽可能独立要求（）A、模块的内聚程度要尽量高，而各模块间的耦合程度要尽量强B、模块的内聚程度要尽量高而各模块间的耦合程度要尽量弱C、模块的内聚程度要尽量低，而各模块间的耦合程度要尽量弱。

国家计算机二级考试公共基础知识教材公共基础知识总结之第一章数据结构与算法 (1)公共基础知识总结之第二章程序设计基础 (4)公共基础知识总结之第三章软件工程基础 (5)公共基础知识总结之第四章数据库系统 (8)公共基础知识总结之第一章数据结构与算法第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

第一章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。

详细重点学习知识点：1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。

2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。

（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。

一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。

1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。

这表明使用绝对的时间单位衡量算法的效率是不合适的。

撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。