计算机二级VB()

1、二级公共基础知识二级公共基础知识计算机等级考试辅导分值分布数据的逻辑结构 什么是数据的逻辑结构？ 数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。（教材中的描述：结点与结点之间的相互关系） 数据的逻辑结构可分成2类 线性结构 非线性结构春春夏夏秋秋冬冬线性结构线性结构父亲父亲儿子儿子女儿女儿非线性结构非线性结构线性表的定义1. 数据元素之间是一对一的关系（即每个数据元素最多有一个直接前驱和一个直接后继）2. 非空线性表的特征： 只有一个根结点a1，无前驱； 有且只有一个终端结点an，无后继； 其它结点只有一个前驱和一个后续。 an a2 a1 数据结构的基本概念逻

2、辑结构为线性结构采用的存储结构为顺序结构线性表顺序表采用的存储结构为链式结构链表 链式存储结构线性表的链式存储结构数据域 指针域 什么是结点？结点由哪两部分组成？ 链式存储结构方式有那些特点？ 结点的储存不一定连续 各结点之间的存储顺序与数据元素的逻辑关系可以不一致 链式存储适合于线性结构也适合于非线性结构链表链表真题栈（考察重点，必须掌握） 栈是一种特殊的线性表，是限定在一端进行插入和删除的线性表，FILO。 栈顶和栈底 栈顶为可以进行插入和删除的一端 栈的操作 入栈插入 出栈删除 取栈顶元素a aaa入栈入栈出栈出栈栈顶栈顶n-1n21栈底栈底 2008.92008.9一个栈的初始状态为空

3、，现将元素一个栈的初始状态为空，现将元素1 1、2 2、3 3、4 4、A A、B B、C C、D D、E E依次入栈，然后再次出栈，则元素依次入栈，然后再次出栈，则元素出栈的顺序是出栈的顺序是_。A A）1234ABCDE1234ABCDEC C）ABCDE12345 DABCDE12345 D）54321EDCBA54321EDCBA 2009.32009.3支持子程序调用的数据结构是（支持子程序调用的数据结构是（ ）（A A）栈）栈 （B B）树）树 （C C）队列）队列 （D D）二叉树）二叉树B）EDCBA54321队列 队列是一种特殊的线性表，允许在一端进行插入操作，在另一端进行删

4、除操作，FIFO(LILO)。 队头和队尾 入队和出队出队出队 a1 a2 an 入队入队队头队头队尾队尾队列：可能出现假溢出现象队列：可能出现假溢出现象解决：采用循环队列（依然为顺序存储）解决：采用循环队列（依然为顺序存储）e55e44e33210元素个数元素个数(rear-front+maxsize)%maxsizemaxsize：队列的最大容量：队列的最大容量%：取余操作（：取余操作（Mod）循环队列及其运算真题数据结构的基本概念逻辑结构为非线性结构树、二叉树树二叉树（考察重点，必须掌握）abcdefg左支树左支树右支树右支树根结点根结点1231145891213671014151231

5二叉树满二叉树完全二叉树完全二叉树思考：完全二叉树有思考：完全二叉树有n个结点，问有多少个叶子结点？个结点，问有多少个叶子结点？深度是多少呢？深度是多少呢？满二叉树：每一层结点数达到最大满二叉树：每一层结点数达到最大完全叉树：除最后一层外，其余每一层结点数达到最完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点大，最后一层结点或满，或右边连续缺少若干结点二叉树性质423167891011121314155二叉树性质423167891011121314155真题二叉树的遍历ADBCD L RAD L RD L RBDCD L R先序

6、遍历序列：先序遍历序列：A B D C先序遍历:ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历:ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列： D B C A后序遍历:B真题真题程序设计基础程序设计基础第三章 软件工程 软件工程基本概念软件工程基本概念 软件工程的生命周期软件工程的生命周期考点1 软件 什么是软件？ 软件是包括程序、数据及相关文档的完整集合，软件是一种逻辑产品。 按功能分可分成哪3类？ 应用软件 系统软件 支撑软件（工具软件）考点考点2 2 软件工程的生命周期软件工程的生命周期 软

7、件工程基本概念软件工程基本概念 软件工程的生命周期软件工程的生命周期可行性研究：可行性分析报告可行性研究：可行性分析报告需求分析：需求说明书需求分析：需求说明书软件设计：设计规格说明书软件设计：设计规格说明书软件测试：测试报告软件测试：测试报告运行与维护：维护报告运行与维护：维护报告数据库的基本概念数据库的基本概念数据的独立性 数据库系统数据库管理系统DBMS 数据 数据库 数据库的基础知识数据库的基础知识关系模型 ERER模型、层次模型、网状模型概念模型、逻辑模型、物理模型基本概念(定义、要素、分类)关系代数基础知识关系代数基础知识并、差、交、除、广义笛卡尔积 选择、投影、连接 比较运算、逻

8、辑运算数据库设计方法数据库设计方法及步骤及步骤方法步骤(需求分析、概念结构分析、逻辑结构分析、物理结构分析、数据库运行和维护) 关系代数基础知识关系代数基础知识选择、投影、连接、自然连接选择、投影、连接、自然连接比较运算、逻辑运算比较运算、逻辑运算关系代数考点1 并运算 并并：RS = t | tR tS 其中其中R和和S具有具有相同个数的属性相同个数的属性(即相同的属性即相同的属性)，相应属性取自同一个域。相应属性取自同一个域。 RS的结果仍然为的结果仍然为n目关系，目关系，由属于由属于R和属于和属于S的的所有元组组成所有元组组成。考点2 差运算 差：R-S = t | tR tS 其中其中

9、R和和S具有具有相同个数的属性相同个数的属性(即相同个数的属性即相同个数的属性)，相，相应属性取自同一个域；应属性取自同一个域； R-S的结果仍然为的结果仍然为n目关系，由目关系，由属于属于R而不属于而不属于S的所有的所有元组组成。元组组成。考点3 交运算 交：RS = t | tR tS 其中其中R和和S具有具有相同个数的属性相同个数的属性(即相同个数的属性即相同个数的属性)，相应属性取自同一个域；相应属性取自同一个域； RS的结果仍然为的结果仍然为n目关系，目关系，由由既属于既属于R又属于又属于S的的所有元组组成。所有元组组成。考点5 广义笛卡尔积 笛卡尔积：笛卡尔积：RS = trts

10、| trR tsS 考点6 选择运算映射(选择选择）：在关关系R中选择满选择满足给给定条条件的元组组其中F表示选择条件1)(|)(TFRttRF)(StudentISSdept)(5StudentIS或关系关系StudentStudent 考点考点6 选择运算选择运算)(20StudentSageISSdept)(2045StudentIS或关系关系Student考点7 投影 投影 A(R)= tA | tR 从从R中选择出若干个属性列组成新的关系，其中中选择出若干个属性列组成新的关系，其中A表示表示R中的属性列。中的属性列。)()(5,2,StudentStudentSdeptSname考点

11、8 连接 连接运算从R和 S的广义笛卡尔积R|S中选取（R关系）在A属性组上的值与（S关系）在B属性组上值满足比较关系的元组。|BtAtStRtttSRsrsrsrBA连接连接连接连接CER|S考点8 连接考点9 自然连接 等值连接:在连接运算中，按照字段值对应相等为条件进行的连接操作称为等值连接。 自然连接是去掉重复属性的等值连接。 A AB BC CE Ea1a1b1b15 53 3a1a1b2b26 67 7a2a2b3b38 81010a2a2b3b38 82 2真题练习 2006.9设有如下三个关系表 A）T=RS B）T=RS C）T=RS D）T=R/S 2007.4在下列关系运算中,不改变关系表中的属性但个数能减少元组个数的是 A)并B)交C)投影D)笛卡儿乘积RSTABCABCm13m13nn132008.9有三个关系R、S和T如下：由关系R和S通过运算得到关系T,则所使用的运算为_。A.笛卡尔积B. 交C. 并D. 自然连接真题练习2009.3有