《计算机二级vb》由会员分享，可在线阅读，更多相关《计算机二级vb（49页珍藏版）》请在金锄头文库上搜索。
1、二级公共基础知识,计算机等级考试辅导,分值分布,算法与数据结构小结,数据的逻辑结构,什么是数据的逻辑结构？ 数据的逻辑结构是指数据元素之间的逻辑关系， 与数据的存储无关，是独立于计算机的。（教材中的描述：结点与结点之间的相互关系） 数据的逻辑结构可分成2类 线性结构 非线性结构,线性表的定义,1. 数据元素之间是一对一的关系（即每个数据元素最多有一个直接前驱和一个直接后继） 2. 非空线性表的特征： 只有一个根结点a1，无前驱； 有且只有一个终端结点an，无后继； 其它结点只有一个前驱和一个后续。,数据结构的基本概念,数据结构研究的内容 逻辑结构 存储结构 运算：插入、删除等,逻辑结构为线性结
2、构,采用的存储结构为顺序结构,线性表,顺序表,采用的存储结构为链式结构,链表,链式存储结构,线性表的链式存储结构,数据域,指针域,什么是结点？结点由哪两部分组成？ 链式存储结构方式有那些特点？ 结点的储存不一定连续 各结点之间的存储顺序与数据元素的逻辑关系可以不一致 链式存储适合于线性结构也适合于非线性结构,链表,真题,2005.4 下列对于线性链表的描述中正确的是_。 A) 存储空间不一定是连续，且各元素的存储顺序是任意的 B) 存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C) 存储空间必须连续，且前件元素一定存储在后件元素的前面 D) 存储空间必须连续，且各元素的存储顺序是任
3、意的,A,栈（考察重点，必须掌握）,栈是一种特殊的线性表，是限定在一端进行插入和删除的线性表，FILO。 栈顶和栈底 栈顶为可以进行插入和删除的一端 栈的操作 入栈插入 出栈删除 取栈顶元素,a,a,a,a,栈顶,n-1,n,2,1,栈底,2008.9一个栈的初始状态为空，现将元素1、2、3、4、A、B、C、D、E依次入栈，然后再次出栈，则元素出栈的顺序是_。 A）1234ABCDE C）ABCDE12345 D）54321EDCBA 2009.3支持子程序调用的数据结构是（ ） （A）栈 （B）树 （C）队列 （D）二叉树,B）EDCBA54321,队列,队列是一种特殊的线性表，允许在一端进
4、行插入操作，在另一端进行删除操作，FIFO(LILO)。 队头和队尾 入队和出队,队列：可能出现假溢出现象 解决：采用循环队列（依然为顺序存储）,rear,front,元素个数 (rear-front+maxsize)%maxsize,maxsize：队列的最大容量 %：取余操作（Mod）,循环队列及其运算,真题,2008.4设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有 个元素。,24,数据结构的基本概念,数据结构研究的内容 逻辑结构 存储结构 运算：排序、查询等,逻辑结构为非线性结构,树、二叉树,树,该树的
5、度为3,度为3,度为2,该树的深度为4,二叉树（考察重点，必须掌握）,二叉树的特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,左支树,右支树,根结点,满二叉树,完全二叉树,思考：完全二叉树有n个结点，问有多少个叶子结点？,深度是多少呢？,满二叉树：每一层结点数达到最大,完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点,二叉树性质,性质1：二叉树的第i层上至多有2 i-1（i 1）个结点，满二叉树的第k层上有2 k-1个结点； 性质2：深度为h的二叉树中至多含有2 h-1个结点，深度为h的满二
6、叉树共有2 h-1个结点； 性质3：若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1； 性质4：具有n个结点的完全二叉树，其深度为log2n+1，其中log2n表示取log2n的整数部分；,二叉树性质,性质5：完全二叉树按层序编号，某一结点编号为k，它若有左孩子，左孩子结点编号为2k；它若有右孩子，右孩子结点编号为2k+1。 推论：若完全二叉树有n个结点，那该二叉树有n-n/2个叶子结点，其中n/2表示对n/2取不大于n/2的最大整数。,真题,2007.4在深度为7的满二叉树中，度为2的结点个数为 。 2005.4某二叉树中度为2的结点有18个，则该二叉树中有
7、_ 个叶子结点。,19,63,二叉树的遍历,先序遍历(D L R): 中序遍历(L D R): 后序遍历(L R D):,D L R,先序遍历序列：A B D C,先序遍历:,L D R,中序遍历序列：B D A C,中序遍历:,L R D,后序遍历序列： D B C A,后序遍历:,真题,2006.9对下列二叉树进行中序遍历的结果是_。 A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG,A,真题,2006.4 对如下二叉树进行后序遍历的结果为_。 A ) ABCDEF B ) DBEAFC C ) ABDECF D ) DEBFCA,D,程序设计基础,第三章 软
8、件工程,软件工程基本概念 软件工程的生命周期,考点1 软件,什么是软件？ 软件是包括程序、数据及相关文档的完整集合，软件是一种逻辑产品。 软件=程序+文档 按功能分可分成哪3类？ 应用软件 系统软件 支撑软件（工具软件）,考点2 软件工程的生命周期,软件工程基本概念 软件工程的生命周期,可行性研究：可行性分析报告 需求分析：需求说明书 软件设计：设计规格说明书 软件测试：测试报告 运行与维护：维护报告,关系代数基础知识,并、差、交、除、广义笛卡尔积,选择、投影、连接、自然连接,比较运算、逻辑运算,关系代数,考点1 并运算,并：RS = t | tR tS 其中R和S具有相同个数的属性(即相同的
9、属性)，相应属性取自同一个域。 RS的结果仍然为n目关系，由属于R和属于S的所有元组组成。,考点2 差运算,差：R-S = t | tR tS 其中R和S具有相同个数的属性(即相同个数的属性)，相应属性取自同一个域； R-S的结果仍然为n目关系，由属于R而不属于S的所有元组组成。,考点3 交运算,交：RS = t | tR tS 其中R和S具有相同个数的属性(即相同个数的属性)，相应属性取自同一个域； RS的结果仍然为n目关系，由既属于R又属于S的所有元组组成。,考点5 广义笛卡尔积,笛卡尔积：RS = trts | trR tsS ,考点6 选择运算,映射(选择）： 在关系R中选择满足给定条
10、件的元组 其中F表示选择条件,关系Student,考点6 选择运算,关系Student,考点7 投影,投影 A(R)= tA | tR 从R中选择出若干个属性列组成新的关系，其中A表示R中的属性列。,关系Student,考点8 连接,连接运算从R和 S的广义笛卡尔积R|S中选取（R关系）在A属性组上的值与（S关系）在B属性组上值满足比较关系的元组。,连接,考点8 连接,考点9 自然连接,等值连接:在连接运算中，按照字段值对应相等为条件进行的连接操作称为等值连接。 自然连接是去掉重复属性的等值连接。,真题练习,2006.9设有如下三个关系表 A）T=RS B）T=RS C）T=RS D）T=R/
11、S 2007.4在下列关系运算中,不改变关系表中的属性但个数能减少元组个数的是 A)并 B)交 C)投影 D)笛卡儿乘积,C,B,2008.9有三个关系R、S和T如下： 由关系R和S通过运算得到关系T,则所使用的运算为_。 笛卡尔积 B. 交 C. 并 D. 自然连接,D,真题练习,2009.3有两个关系R，S如下： 由关系R通过运算得到关系S，则所使用的运算为（ ） A）选择 B）投影 C）插入 D）连接,B,真题练习,（3）2010.3有两个关系R和T如下： 则由关系R得到关系T的操作是( ) A)选择 B)投影 C)交 D)并,A,真题练习,2011.3有三个关系R、S和T如下： 则由关系R和S得到关系T的操作是（ ）。 A)自然连接 B)交 C)除 D)并,D,真题练习,
