计算机二级基础知识精选文档.ppt

《计算机二级基础知识精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机二级基础知识精选文档.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计计算机二算机二算机二算机二级级基基基基础础知知知知识识本讲稿第一页，共五十二页目目 录录数据结构数据结构1软件工程软件工程2数据库基础数据库基础3本讲稿第二页，共五十二页线线 性性 表表v线性表线性表 线性表简称为表，是零个或多个元素的有穷序线性表简称为表，是零个或多个元素的有穷序列，通常可以表示成列，通常可以表示成k0，k1，kn-1（n=1）.顺序存储结构和链式存储结构顺序存储结构和链式存储结构本讲稿第三页，共五十二页线线 性性 表表v单链表与顺序表的比较：单链表与顺序表的比较：单链表的存储密度比顺序表低，它多占用了存储空间：单链表的存储密度比顺序表低，它多占用了存储空间：存储密度存储密

2、度=数据本身所占的存储量数据本身所占的存储量/整个数据结构所占的整个数据结构所占的存储量。存储量。在单链表里进行插入、删除运算比在顺序表中容易得多。在单链表里进行插入、删除运算比在顺序表中容易得多。对于顺序表，可随机访问任一元素，而在单链表中，需对于顺序表，可随机访问任一元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合成批地、顺序要顺着链逐个进行查找，因此单链表适合成批地、顺序地处理线性表中的元素时使用。地处理线性表中的元素时使用。本讲稿第四页，共五十二页v1.下列叙述中正确的是：下列叙述中正确的是：A.线性表的链式存储结构与顺序存储结构所需的存储线性表的链式存储结构与顺序存储结构所

3、需的存储空间是相同的空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构于顺序存储结构D.以上三种说法都不正确以上三种说法都不正确本讲稿第五页，共五十二页栈栈v定义：定义：栈是一种特殊的线性表，对于它所有的插入和删栈是一种特殊的线性表，对于它所有的插入和删除都限制在表的同一端进行。表中允许进行操作除都限制在表的同一端进行。表中允许进行操作的一端交栈顶，另一端叫栈底。没有元素的栈叫的一端交栈顶，另一端叫栈底。没有

4、元素的栈叫空栈。空栈。v特征：特征：先进后出。先进后出。本讲稿第六页，共五十二页队队 列列v定义：定义：队列是一种特殊的线性表，是一种只允许在表的队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的一端进行插入操作，而在另一端进行删除操作的线性表。允许删除的一端叫队列的头，允许插入线性表。允许删除的一端叫队列的头，允许插入的一端叫做队列的尾。没有元素的叫空队列。的一端叫做队列的尾。没有元素的叫空队列。v特征：特征：先进先出。先进先出。本讲稿第七页，共五十二页v2.下列叙述中正确的是下列叙述中正确的是A.栈是栈是“先进先出先进先出”的线性表的线性表B.队列是队列是

5、“先进后出先进后出”的线性表的线性表C.循环队列是非线性结构循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用有序线性表既可以采用顺序存储结构，也可以采用链式存储结构链式存储结构本讲稿第八页，共五十二页v3.下列叙述中正确的是下列叙述中正确的是A.在栈中，栈中元素随栈底指针与栈顶指针的变化而在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变在栈中，栈底指针不变，栈中元素随栈顶指针的变化而变化化而变化D.上

6、述三种说法都不对上述三种说法都不对本讲稿第九页，共五十二页树与树林树与树林v树树是包括是包括n（n0）个结点的有穷集合）个结点的有穷集合T，当，当T非空非空时满足：时满足：有且仅有一个特别标出的称作根的结点。有且仅有一个特别标出的称作根的结点。除根结点之外，其余结点分为除根结点之外，其余结点分为m0个不相交的非空集合个不相交的非空集合T1，T2，Tm，而这些集合中的每一个又都是树。，而这些集合中的每一个又都是树。树都称作这个根结点的子树。树都称作这个根结点的子树。本讲稿第十页，共五十二页树与树林树与树林v基本术语基本术语父结点、子结点、边父结点、子结点、边兄弟兄弟祖先、子孙祖先、子孙路径、路径

7、长度路径、路径长度结点的层数结点的层数树的深度或高度树的深度或高度本讲稿第十一页，共五十二页树的周游树的周游v按深度方向周游按深度方向周游先根次序先根次序中根次序中根次序后根次序后根次序v按宽度方向周游按宽度方向周游本讲稿第十二页，共五十二页二叉树二叉树v二叉树二叉树可以定义为结点的有限集合，这个集合或可以定义为结点的有限集合，这个集合或者为空集，或者由一个根及两棵不相交的分别称者为空集，或者由一个根及两棵不相交的分别称作这个根的作这个根的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。本讲稿第十三页，共五十二页二叉树二叉树v二叉树不是树的特例二叉树不是树的特例v树和二叉树的主要差别：

8、树和二叉树的主要差别：二叉树中结点的子树要区分左子树和右子树二叉树中结点的子树要区分左子树和右子树即使在结点只有一棵子树的情况下也要明确指出该子树即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树是左子树还是右子树本讲稿第十四页，共五十二页满二叉树满二叉树v如果一棵深度为k的二叉树，当其结点数目为2k+1-1则称之为满二叉树。本讲稿第十五页，共五十二页完全二叉树完全二叉树v如果一个深度为如果一个深度为k的二叉树，其所有结点按层次编的二叉树，其所有结点按层次编号，其所有结点的编号都与相同深度的号，其所有结点的编号都与相同深度的满二叉树满二叉树的编号位置相同，则称之为完全二叉树的编

9、号位置相同，则称之为完全二叉树满二叉树一定是完全二叉树满二叉树一定是完全二叉树完全二叉树不一定是满二叉树完全二叉树不一定是满二叉树本讲稿第十六页，共五十二页二叉树的性质二叉树的性质v性质1 在非空二叉树的i层上至多有2i个结点（i0）v性质2 深度为k的二叉树中最多有2k+1-1个结点（k0）v性质3 对于任何一棵非空的二叉树，如果叶节点个数为n0，度为2的结点个数为n2，则有n0=n2+1v性质4 具有n个结点的完全二叉树的深度k为本讲稿第十七页，共五十二页v4.某二叉树有某二叉树有5个度为个度为2的结点，则该二叉树中的的结点，则该二叉树中的叶子结点数是叶子结点数是A.10B.8C.6D.4

10、本讲稿第十八页，共五十二页v5.支持子程序调用的数据结构是支持子程序调用的数据结构是A.栈栈B.树树C.队列队列D.二叉树二叉树本讲稿第十九页，共五十二页排排 序序v插入排序插入排序直接插入排序（简单插入排序）直接插入排序（简单插入排序）简单插入排序是最简单直观的排序方法。简单插入排序是最简单直观的排序方法。其基本方法是：把其基本方法是：把n n个待排序的元素看成为一个有序表和一个无个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含序表，开始时有序表中只包含一个元素，无序表中包含n-1n-1个元个元素，排序过程中每次从无序表中取出第一个元素，把它的依次与素，

11、排序过程中每次从无序表中取出第一个元素，把它的依次与有序表中的元素进行比较，将其插入到有序表的适当位置，使之有序表中的元素进行比较，将其插入到有序表的适当位置，使之成为新的有序表。成为新的有序表。在最坏的情况下，简单插入排序需要为次比较在最坏的情况下，简单插入排序需要为次比较n(n-1)/2n(n-1)/2。Shell排序排序 在最坏情况下，希尔排序所需要的比较次数为在最坏情况下，希尔排序所需要的比较次数为 。本讲稿第二十页，共五十二页排排 序序v选择排序法选择排序法简单选择排序法简单选择排序法简单选择排序的方法：从整个数据元素中选出最小的元素，将简单选择排序的方法：从整个数据元素中选出最小的

12、元素，将其交换到前面（应放的位置），对剩下的数据元素采用同样的其交换到前面（应放的位置），对剩下的数据元素采用同样的方法，直到没有可交换元素。方法，直到没有可交换元素。在最坏情况下，选择排序所需要的比较次数为在最坏情况下，选择排序所需要的比较次数为n(n-1)/2n(n-1)/2。堆排序堆排序堆排序法属于选择类的排序方法。堆排序法属于选择类的排序方法。在最坏情况下，堆排序所需要的比较次数为在最坏情况下，堆排序所需要的比较次数为 。本讲稿第二十一页，共五十二页排排 序序v交换排序法交换排序法冒泡排序冒泡排序冒泡排序法是一种最简单的交换类排序方法，通过相邻冒泡排序法是一种最简单的交换类排序方法，通

13、过相邻数据元素的交换逐步将序列变成有序的。数据元素的交换逐步将序列变成有序的。在最坏情况下，冒泡排序所需要的比较次数为在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2n(n-1)/2。快速排序快速排序快速排序法属于交换类排序法。快速排序法属于交换类排序法。在最坏情况下，快速排序所需要的比较次数为在最坏情况下，快速排序所需要的比较次数为n(n-1)/2 n(n-1)/2。本讲稿第二十二页，共五十二页排排 序序v排序的最坏比较次数排序的最坏比较次数排序方式排序方式时间复杂度时间复杂度排序方式排序方式时间复杂度时间复杂度直接插入法直接插入法O(n2)堆排序堆排序Shell法法O（n1.5）冒

14、泡排序冒泡排序O(n2)简单选择法简单选择法O(n2)快速排序快速排序O(n2)本讲稿第二十三页，共五十二页v6.下列排序方法中，最坏情况下比较次数较少的下列排序方法中，最坏情况下比较次数较少的是：是：A.冒泡排序冒泡排序B.简单选择排序简单选择排序C.直接插入排序直接插入排序D.堆排序堆排序本讲稿第二十四页，共五十二页支撑软件支撑软件v支撑软件是支撑各种软件的开发与维护的软件，支撑软件是支撑各种软件的开发与维护的软件，又称为软件开发环境。它主要包括环境数据库、又称为软件开发环境。它主要包括环境数据库、各种接口软件和工具组。各种接口软件和工具组。本讲稿第二十五页，共五十二页v7.软件按功能可以

15、分为：应用软件、系统软件和软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的支撑软件（或工具软件）。下面属于应用软件的是：是：A.编译程序编译程序B.操作系统操作系统C.教务管理系统教务管理系统D.汇编程序汇编程序本讲稿第二十六页，共五十二页软件危机软件危机v软件危机是指在计算机软件的开发和维护过程中软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题。所遇到的一系列严重问题。v它包含两个方面的问题：它包含两个方面的问题：1.如何开发软件，以满足对软件日益增长的需求。如何开发软件，以满足对软件日益增长的需求。2.如何维护数量不断膨胀的已有软件。如何维

16、护数量不断膨胀的已有软件。本讲稿第二十七页，共五十二页软件危机软件危机v典型表现：典型表现：1.对软件开发成本和进度估计常常很不准确。对软件开发成本和进度估计常常很不准确。2.用户对用户对“已完成的已完成的”软件系统部不满意的现象经常发软件系统部不满意的现象经常发生。生。3.软件产品的质量往往靠不住。软件产品的质量往往靠不住。4.软件常常是不可维护的。软件常常是不可维护的。5.软件通常没有适当的文档资料。软件通常没有适当的文档资料。6.软件成本在计算机系统总成本中所占的比例逐年上升。软件成本在计算机系统总成本中所占的比例逐年上升。7.软件开发生产率提高的速度，远远跟不上计算机应用软件开发生产率

17、提高的速度，远远跟不上计算机应用迅速普及深入的趋势。迅速普及深入的趋势。本讲稿第二十八页，共五十二页v8.下面描述中，不属于软件危机表现的是：下面描述中，不属于软件危机表现的是：A.软件过程不规范软件过程不规范B.软件开发生产率低软件开发生产率低C.软件质量难以控制软件质量难以控制D.软件成本不断提高软件成本不断提高本讲稿第二十九页，共五十二页软件生命周期软件生命周期v软件生命周期有软件生命周期有软件定义软件定义、软件开发软件开发和和运行维护运行维护（也称软件维护）（也称软件维护）3个时期组成。其中，每个时期个时期组成。其中，每个时期又进一步划分成若干个阶段。又进一步划分成若干个阶段。本讲稿第

18、三十页，共五十二页v9.软件的生命周期是指：软件的生命周期是指：A.软件产品从提出、实现、使用维护到停止使用退役软件产品从提出、实现、使用维护到停止使用退役的过程的过程B.软件从需求分析、设计、实现到测试完成的过程软件从需求分析、设计、实现到测试完成的过程C.软件开发过程软件开发过程D.软件的运行维护过程软件的运行维护过程本讲稿第三十一页，共五十二页耦合性与内聚性耦合性与内聚性 v耦合性耦合性 耦合性是程序结构中各个模块之间相互关联的度量。它耦合性是程序结构中各个模块之间相互关联的度量。它取决于各个模块之间接口的复杂程度、调用模块的方式取决于各个模块之间接口的复杂程度、调用模块的方式以及哪些信

19、息通过接口。以及哪些信息通过接口。v内聚性内聚性 又称为块内联系，指模块的功能强度的度量，即一个模又称为块内联系，指模块的功能强度的度量，即一个模块内部各个元素彼此结合的紧密程度的度量。块内部各个元素彼此结合的紧密程度的度量。本讲稿第三十二页，共五十二页v10.耦合性和内聚性是对模块独立性度量的两个标耦合性和内聚性是对模块独立性度量的两个标准。下列叙述正确的是：准。下列叙述正确的是：A.提高耦合性降低内聚性有利于提高模块的独立性提高耦合性降低内聚性有利于提高模块的独立性B.降低耦合性提高内聚性有利于提高模块的独立性降低耦合性提高内聚性有利于提高模块的独立性C.耦合性是指一个模块内部各个元素间彼

20、此结合的紧耦合性是指一个模块内部各个元素间彼此结合的紧密程度密程度D.内聚性是指模块间互相连接的紧密程度内聚性是指模块间互相连接的紧密程度本讲稿第三十三页，共五十二页软件测试软件测试v软件测试的目的软件测试的目的测试是为了发现程序中的错误而执行程序的过程。测试是为了发现程序中的错误而执行程序的过程。好的测试方案是极可能发现迄今为止尚未发现的错误的好的测试方案是极可能发现迄今为止尚未发现的错误的测试方案。测试方案。成功的测试是发现了迄今为止尚未发现的错误的测试。成功的测试是发现了迄今为止尚未发现的错误的测试。本讲稿第三十四页，共五十二页v11.软件测试的目的是：软件测试的目的是：A.评估软件的可

21、靠性评估软件的可靠性B.发现并改正程序中的错误发现并改正程序中的错误C.改正程序中的错误改正程序中的错误D.发现程序中的错误发现程序中的错误本讲稿第三十五页，共五十二页v12.下面叙述中错误的是：下面叙述中错误的是：A.软件测试的目的是发现错误并改正错误软件测试的目的是发现错误并改正错误B.对被调试的程序进行对被调试的程序进行“错误定位错误定位”是程序调试的必是程序调试的必要步骤要步骤C.程序调试通常也成为程序调试通常也成为DebugD.软件测试应严格执行测试计划，排除测试的随意性软件测试应严格执行测试计划，排除测试的随意性本讲稿第三十六页，共五十二页白盒测试与黑盒测试白盒测试与黑盒测试v黑盒

22、测试黑盒测试 又称功能测试，它把程序看做一个黑盒子，完全不考虑又称功能测试，它把程序看做一个黑盒子，完全不考虑程序的内部结构和处理过程。即，程序的内部结构和处理过程。即，只检查程序的功能是只检查程序的功能是否按照功能说明书的规定正常运行。否按照功能说明书的规定正常运行。v白盒测试白盒测试 又称结构测试，它将程序看成一个透明的白盒子，又称结构测试，它将程序看成一个透明的白盒子，按照按照程序内部的逻辑测试程序，检测程序中的主要执行通路程序内部的逻辑测试程序，检测程序中的主要执行通路是否都能按预定的要求工作。是否都能按预定的要求工作。本讲稿第三十七页，共五十二页实体实体-联系图（联系图（E-R图）图

23、）v方框表示数据对象，圆角矩形表示数据对象的属方框表示数据对象，圆角矩形表示数据对象的属性，菱形表示性，菱形表示“联系联系”。v联系：一对一、一对多、多对多联系：一对一、一对多、多对多 本讲稿第三十八页，共五十二页v13.一个工作人员可以使用多台计算机，而一台计一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员与实体计算机可被多个人使用，则实体工作人员与实体计算机之间的联系是：算机之间的联系是：A.一对一一对一B.一对多一对多C.多对多多对多D.多对一多对一本讲稿第三十九页，共五十二页数据模型数据模型v层次型层次型 v网状型网状型 v关系型关系型二维表二维表 v它们之间

24、的它们之间的划分原则划分原则是是数据之间的联系方式数据之间的联系方式。本讲稿第四十页，共五十二页v14.将将E-R图转换为关系模式时，实体和联系都可图转换为关系模式时，实体和联系都可以表示为：以表示为：A.属性属性B.键键C.关系关系D.域域本讲稿第四十一页，共五十二页v15.层次型、网状型和关系型数据库划分原则是：层次型、网状型和关系型数据库划分原则是：A.记录长度记录长度B.文件的大小文件的大小C.联系的复杂程度联系的复杂程度D.数据之间的联系方式数据之间的联系方式本讲稿第四十二页，共五十二页数据库三级模式数据库三级模式v模式模式 模式又称为概念模式或逻辑模式，对应于概念级。它是模式又称为

25、概念模式或逻辑模式，对应于概念级。它是由数据库设计者综合所有用户的数据，按照统一的观点由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共视图（全局视构和特征的总体描述，是所有用户的公共视图（全局视图）。体现、反映数据库的图）。体现、反映数据库的整体观整体观。本讲稿第四十三页，共五十二页数据库三级模式数据库三级模式v外模式外模式 外模式又称子模式，对应于用户级。它是某个或某几个外模式又称子模式，对应于用户级。它是某个或某几个用户所看到的数据库的数据试图，是与某一应用有

26、关的用户所看到的数据库的数据试图，是与某一应用有关的数据的逻辑表示。它反映数据库的数据的逻辑表示。它反映数据库的用户观用户观。v内模式内模式内模式又称存储模式，对应于物理级，它是数据库的内模式又称存储模式，对应于物理级，它是数据库的存存储观储观。本讲稿第四十四页，共五十二页v16.数据库设计中反映用户对数据要求的模式是：数据库设计中反映用户对数据要求的模式是：A.内模式内模式B.概念模式概念模式C.外模式外模式D.设计模式设计模式本讲稿第四十五页，共五十二页关系运算关系运算v专门的关系运算专门的关系运算选择选择投影投影本讲稿第四十六页，共五十二页关系运算关系运算连接连接 R：S：等值连接等值连

27、接自然连接自然连接 R:S:除除连接运算连接运算本讲稿第四十七页，共五十二页v17.有两个关系有两个关系R，S如下：如下：R S 由关系由关系R通过运算得到关系通过运算得到关系S,则所使用的运算为：则所使用的运算为：A.选择选择B.投影投影C.插入插入D.连接连接ABC a32b01c21ABa3b0c2本讲稿第四十八页，共五十二页v18.有两个关系有两个关系R，S，T如下：如下：R S T 由关系由关系R和和S通过运算得到关系通过运算得到关系T,则所使用的运算为：则所使用的运算为：A.自然连接自然连接B.交交C.投影投影D.并并ABC a12b21c31ADc4ABCDc314本讲稿第四十九页，共五十二页v19.数据库应用系统中的核心问题是：数据库应用系统中的核心问题是：A.数据库设计数据库设计B.数据库系统设计数据库系统设计C.数据库维护数据库维护D.数据库管理员培训数据库管理员培训本讲稿第五十页，共五十二页v20.面向对象方法中，继承是指：面向对象方法中，继承是指：A.一组对象所具有的相似性质一组对象所具有的相似性质B.一个对象具有另一个对象的性质一个对象具有另一个对象的性质C.各对象之间的共同性质各对象之间的共同性质D.类之间共享属性和操作机制类之间共享属性和操作机制本讲稿第五十一页，共五十二页计算机基础谢谢!本讲稿第五十二页，共五十二页