公共基础知识

全国计算机二级考试公共基础知识第1页公共基础知识考试范围单选2*10=20分，填空2*5=10分，共30分数据构造与算法程序设计基础软件工程基础数据库设计基础第2页算法算法：解题方案精确而完整描述。5个特性：有穷性：算法执行有时间限制，不能无限制执行确定性：不能有二义性可行性:有输入：一种算法应有零个或多种输入。有输出：一定要有一种或多种输出。a=4/0第3页算法特性算法有穷性是指（）。（2023年4月）A）算法程序运行时间是有限B）算法程序所处理数据量是有限C）算法程序长度是有限D）算法只能被有限顾客使用A第4页算法复杂度p5算法时间复杂度：执行算法所需要计算工作量。算法时间复杂度是指（）。A）执行算法程序所需要时间B）算法程序长度C）算法执行过程中所需要基本运算次数D）算法程序中指令数C第5页算法空间复杂度算法空间复杂度：执行算法所需要内存空间。算法空间复杂度是指（）（2023年9月）A）算法在执行过程中所需要计算机存放空间B）算法所处理数据量C）算法程序中语句或指令条数D）算法在执行过程中所需要临时工作单元数A第6页1.2数据构造p7数据构造+算法=程序数据构造是指数据元素集合及数据元素之间关系集合。其逻辑构造有4种：（a）集合构造（b）线性构造（c）树型构造

（d）图状构造一对一一对多多对多非线性第7页数据构造存放概念：数据逻辑构造在计算机中存放表达分类：次序存放链式存放第8页线性表两种存放方式线性表次序存放：线性表中所有元素所占存放空间是连续线性表中各数据元素在存放空间中是按逻辑次序次序放12354地址：100101102第9页线性表两种存放方式15∧H…2线性表链式存放：逻辑上相邻两个数据元素存放位置上不一定相邻。注意：链式构造通过一种链连接到下一种元素次序存放和链式存放能够表达线性、非线性构造地址：100300300第10页次序存放和链式存放下列论述中正确是（）（2023年9月）A）次序存放构造存放一定是连续，链式存放构造存放空间不一定是连续B）次序存放构造只针对线性构造，链式存放构造只针对非线性构造C）次序存放构造能存放有序表，链式存放构造不能存放有序表D）链式存放构造比次序存放构造节省存放空间A第11页1.4线性表——栈和队列P19-20栈——先进后出表。栈顶top入栈出栈栈底bottom

进：a1,a2,a3a1a2a3出：a3,a2,a1操作受限制：只能从栈顶插入，只能从栈顶删除第12页栈1、一种栈初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈次序是（）。（2023年9月）A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA2、栈底至栈顶依次寄存元素A、B、C、D，在第五个元素E入栈前，栈中元素能够出栈，则出栈序列也许是()ABCEDB.DBCEAC.CDABED.DCBEA

BD第13页栈假设用一种长度为50数组(数组元素下标从0到49)作为栈存放空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，假如bottom=49，top=30(数组下标)，则栈中具有

个元素。（2023年3月）20…p…a03049bottomtop第14页队列21队列——先进先出入队出队队头标志front指向队头元素前一种；队尾标志rear指向最后一种元素。队头出，队尾进ABCfrontrearD012345队列长度=rear-front第15页54331092循环队列p22CBA…rear循环队列front队头标志front指向队头元素前一种；队尾标志rear指向最后一种元素。队头出，队尾进设某循环队列容量为50，头指针front=5（指向队头元素前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有个元素。（2023年4月）24第16页循环队列对于循环队列，下列论述中正确是()。（2023年9月）A）队头指针是固定不变B）队头指针一定大于队尾指针C）队头指针一定不大于队尾指针D）队头指针能够大于队尾指针，也能够不大于队尾指针D第17页二叉树P34结点度：结点所拥有孩子个数称为该结点度。叶结点：度为0结点称为叶结点，或者称为终端结点。分枝结点：度不为0结点称为分支结点，或者称为非终端结点。一棵树结点除叶结点外，其他都是分支结点。左孩子、右孩子、双亲、弟兄。祖先、子孙。结点层数（深度）ABCEDFIGH第1层第2层第3层第4层第18页二叉树性质34性质1一棵非空二叉树第k层上最多有个结点（i≥1）。性质2一棵深度为k二叉树中，最多具有个结点。2k﹣12k﹣1ABCEDFIHKGJLMNO第19页二叉树性质34性质3对于一棵非空二叉树，假如叶子结点数为n0，度数为2结点数为n2，则有：n0＝n2＋1。ABCEDFIGH证明：1、入枝：除了根结点，每个结点有一种入枝，假设有分支个数为m，总结点个数为n，n和m关系是：2、出支：度为2有2个出枝，度为1有1个出枝，度为0没有出枝，因此m=2*n2+n1m=n-1即m=n2+n1+n0-13、n2+n1+n0-1=2*n2+n1得n0=n2+1第20页二叉树特性例1：某二叉树有5个度为2结点以及3个度为1结点，则该二叉树中共有个结点。（2023年9月）【解析】：度为2：5个，度为1：3，度为0：6；一共5+3+6=14例2：深度为5满二叉树有个叶子结点（2023年4月）

【解析】：满二叉树第5层上有25-1个结点。1416第21页二叉树35满二叉树完全二叉树ABCEDFIHKGJLMNOABCEDFIHGJ××第22页二叉树性质设完全二叉树共有n个结点，假如从根结点开始（根k=1），按层排序12354698710编号为k结点左孩子结点编号为2k，右孩子结点编号为2k+1;K父结点编号为INT(K/2);第23页二叉树遍历P186前序：根左右；中序：左根右；后序：左右根ABDEFZYCX前：ABDEXCFYZ中：DBXEAYFZC后：DXEBYZFCA第24页已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树后序遍历为（）A）GEDHFBCAB）DGEBHFCAC）ABCDEFGHD）ACBFEDHGB根左右第25页已知一棵二叉树后序遍历序列是dabec，中序遍历序列是debac，则它前序遍历序列是（）A．acbedB.decabC.deabcD.cedbaD第26页已知一棵二叉树中序遍历序列是DBEAFC，前序遍历序列是ABDECF，则它后序遍历序列是（）第27页1.7查找技术p39比较次数时间复杂度次序查找最坏nO(n)次序查找：从头到尾一种一种找，能够用于次序表或链表。

01234567109820332260533次序查找可用于有序、无序表，可用于次序存放和链式存放链表只能用次序查找第28页折半查找：有有序表(3,14,19,20,27,55,72,80,88,92)，查找723141920275572808892↑low=1↑High=10↑mid3141920275572808892↑low↑high↑mid3141920275572808892↑low↑high↑mid3141920275572808892↑low↑high↑mid12345678第29页1.8排序技术40交换类排序比较次数冒泡排序n(n-1)/2迅速排序log2n

插入类排序直接插入排序n(n-1)/2希尔排序n1.5选择类排序简单选择排序n(n-1)/2堆排序nlog2n下列排序办法中，最坏情况下比较次数最少是__________。（2023年9月二级C真题）冒泡排序

简单选择排序

直接插入排序

堆排序D第30页程序设计基础（记住基础概念）481、构造化程序设计标准：自顶向下，逐渐求精，模块化，限制使用goto语句。标准：清楚第一、效率第二3大基本构造：次序、选择、循环2、面向对象程序设计（略）第31页软件工程62软件、软件危机、软件工程定义软件生命周期：可行性研究、需求分析、软件设计、软件实现、软件测试、运行和维护软件工程标准：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完整性、可验证性构造化分析常用工具：数据流图（DFD）、数据字典(DD)等模块独立化：内聚性——模块内紧密程度耦合性——模块间紧密程度

高内聚，低耦合第32页软件测试86软件测试办法：静态测试和动态测试白盒测试——构造测试、逻辑驱动测试

办法——逻辑覆盖、基本途径测试等黑盒测试——功能测试、数据驱动测试

办法——等价划分法、边界值分析法、因果法等软件测试实行：单元测试、集成测试、确认测试、系统测试程序调试第33页数据库101数据——计算机中文字、图形、图像、声音等。e.g.一种学生数据学号姓名性别出生日期1001喜洋洋男1991.1.2数据库——数据集合。e.g.多种学生数据学号姓名性别出生日期1001喜洋洋男1991.1.11002美羊羊女1992.3.31003懒洋洋男1992.5.51004沸羊羊男1990.7.7放在计算机内存里第34页数据库应用系统（如：教学管理系统）2、数据库数据库管理系统（如：ACCESS）操作系统（如：WindowsXP）电脑硬件数据库系统存入数据（库）数据库系统关键第35页数据模型数据模型——E-R模型（实体——属性）课程教师参照书讲授编号姓名职称实体属性联系第36页数据模型实体间联系分类一对一联系(1:1)一对多联系(1:M)多对多联系(M:N)学生校长学校教师课程学生校长课程学生校长教师课程学生正校长一对一一对多多对多多对多第37页关系模型：二维表学号姓名学院年纪2023001202300220230032023004张浩然李一明王伟赵坚强CPCPEEEE18191820元组/统计属性第38页传统关系运算ABCa1b1c1a1b2c2a2b2c1RABCa1b2c2a1b3c2a2b2c1S(1)并运算：RUSABCa1b1c1a1b2c2a2b2c1a1b3c2(2)差运算：R-SR中有，S中没有ABCa1b1c1(3)差运算：R∩SABCa1b2c2a2b2c1第39页专门关系运算1、选择：从关系中找出满足给定条件元组。(选择运算是在二维表中选择满足指定条件行)2、投影：从关系模式中指定若干属性组成新关系。(在