公共基础知识部分.ppt

《公共基础知识部分.ppt》由会员分享，可在线阅读，更多相关《公共基础知识部分.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、公共基础知识部分 一、数据结构与算法二、程序设计基础 三、软件工程基础 四、数据库设计基础一、数据结构与算法1、数据的存储结构是指（）A、存储在外存中的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示分析:数据的存储结构:数据的逻辑结构在计算机存储空间中的存放形式。也称为物理结构。数据的逻辑结构：反映数据元素之间关系的数据元素集合（数据对象）的表示。包括：元素的信息、数据元素之间的前后件关系。结构：集合、线性结构、树形结构、图形结构四种。一种逻辑结构的数据可以表示成多种存储结构：顺序、链顺序、链式、索引式、索引等。2、下列关于栈的描述中错误的是（）

2、A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入与删除操作中，不需要改变栈底指针分析：栈：特殊的线性表。限定只在一端进行插入与删除的线性表，这一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。3、对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-1)/2分析：冒泡排序和快速排序在最坏的情况下，需要比较 n(n-1)/2 次。4、对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）A、log2n B、n/2C

3、、n D、n+1分析：1、查找可分为：顺序查找和二分查找两种。2、对于长度为n的有序线性表，在最坏情况下，顺序查找需要比较n次，而二分查找只需要log2n次。5、下列对于线性链表的描述正确的是（）A、存储空间不一定连续，且各元素的存储顺序是任意的B、存储空间不一定连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的分析：1、线性链表：就是线性表的链式存储。存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。2、线性表的顺序存储：用一组地

4、址连续的存储单元依次一组地址连续的存储单元依次存储线性表存储线性表的数据元素。缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。6、某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。分析：1、二叉树的定义 二叉树只有一个根结点，每个结点最多只有两棵树（左子树、右子树）。2、二叉树的性质：性质1：在二叉树的第k层上至多有2k-1个结点（k=1）;性质2：深度为m的二叉树至多有2k-1个结点。性质3：对任意一棵二叉树，度为0的结点数总比度为2的 结点数多1。性质4：具有n个结点的完全二叉树深度至少为log2n+1。7、下列数据结构中，能用二分法进行查找的是（）A、顺序存

5、储的有序线性表B、线性链表C、二叉链表D、有序线性链表分析：二分查找只适用于顺序存储的有序表。8、下列关于栈的描述正确的是（）A、在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除D、栈是特殊的线性表，只能在一端插入元素，而字另一端删除元素9、下列叙述中正确的是（）A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率10、算法复杂度主要包括时间复杂度和

6、（）复杂度。分析:1、算法的复杂度主要包括时间复杂度和空间复杂度.2、算法的时间复杂度：指执行算法所需要的计算工作量；3、算法的空间复杂度：指执行这个算法所需要的内存空间；4、算法的时间复杂度与空间复杂度并不相关。5、一棵二叉树第六层(根结点为第一层)的结点数最多为（）个。6、数据结构分为逻辑结构和存储结构，循环队列属于（）结构。11、按照”后进先出”原则组织数据的数据结构是（）A、队列 B、栈C、双向链表 D、二叉树12、下列叙述中正确的是（）A、线性链表是线性表的链式存储结构B、栈与队列是非线性结构C、双向链表是非线性结构D、只有根结点的二叉树是线性结构分析：1、栈、队列和双向链表都是线性

7、结构，而二叉树是非线性结构。2、线性结构和非线性结构是从数据的逻辑结构角度而言，与该数据结构中有多少个元素没有关系，即使是空二叉树也是非线性结构的。13、对如下二叉树 进行后序遍历的结果为（）A、ABCDEF B、DBEAFCC、ABDECF D、DEBFCA分析：二叉树的遍历：就是按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。1.前序遍历（根-左-右）2.中序遍历（左-根-右）3.后序遍历（左-右-根）ABCDEF14、在深度为7的满二叉树中,叶子结点的个数为（）A、32 B、31 C、64 D、63分析：15、对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为（）

8、。16、设一棵完全二叉树共有839个结点，则在该二叉树中有_个叶子结点。17、下列叙述中正确的是_。A、一个算法的空间复杂度大，则其时间复杂度也必定大B、一个算法的空间复杂度大，则其时间复杂度必定小C、一个算法的时间复杂度大，则其空间可复杂度必定小D、上述三种说法都不对18、在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A、63B、64C、6D、719、对下列二叉树 进行中序遍历的结果是_。A、ACBDFEG B、ACBDFGEC、ABDCGEF D、FCADBEG20、按“先进后出”原则组织数据的数据结构是 _。21、数据结构分为线性结构和非线性结构，带链的队列属

9、于_。22、下列叙述中正确的是（）A、算法的效率只与问题的规模有关，而与数据的存储结构无关B、算法的时间复杂度是指执行算法所需要的计算工作量C、数据的逻辑结构与存储结构是一一对应的D、算法的时间复杂度与空间复杂度一定相关23、下列对队列的叙述中正确的是（）A、队列属于非线性表B、队列按“先进后出”原则组织数据C、队列在队尾删除数据D、队列按“先进先出”原则组织数据分析：队列：是一种操作受限的线性表。他只允许在线性表的一端进行插入操作，另一端进行删除操作。其中，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有“先进先出”的特点。24、对下列二叉树：进行前序遍历的结果是（）A、DYBEAF

10、CZX B、YDEBFZXCAC、ABDYECFXZ D、ABCDEFXYZABCDEFXYZ25、某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（）。26、在深度为7的满二叉树中，度为2的结点个数为（）。27、下列叙述中正确的是（）A、数据的逻辑结构与存储结构必定是一一对应的B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C、程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D、以上三种说法都不对28、冒泡排序在最坏情况下的比较次数是（）A、n(n+1)/2 B、nlog2nC、n(n-1)/2 D、n/229、一棵二叉树中共有70个

11、叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）A、219 B、221C、229 D、23130、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_存储结构。31、对下列二叉树进行中序遍历的结果是_。FCEADGBHP二、程序设计基础二、程序设计基础1、在面向对象方法中，类的实例称为（）2、在面向对象方法中，（）描述的是具有相似属性与操作的一组对象。3、下面关于类、对象、属性和方法的叙述中，错误的是（）A、类是对一类相似对象的描述，这些对象具有相同种类的属性和方法B、属性用于描述对象的状态，方法用于表示对象的行为C、基于同一个类产生的两个对

12、象可以分别设置自己的属性值D、通过执行不同对象的同名方法，其结果必然是相同的4、下列选项中不属于结构化程序设计方法的是（）A)自顶向下 B)逐步求精c)模块化 D)可复用分析：1、结构化程序设计方法的主要原则：自顶向下，逐步求精，模块化，限制使用goto语句。2、可复用性：是软件工程追求的目标之一，是提高软件产品效率的最主要的方法。5、下面选项中不属于面向对象程序设计特征下面选项中不属于面向对象程序设计特征的是的是_.A继承性继承性B多态性多态性 C类比性类比性 D封装性封装性6、在面向对象方法中，实现信息隐蔽是依靠（）A对象的继承B对象的多态C对象的封装D对象的分类7、下列叙述中，不符合良好

13、程序设计风格要求的是（）A程序的效率第一，清晰第二B程序的可读性好C程序中要有必要的注释D输入数据前要有提示信息三、软件工程基础1、下列对于软件测试的描述中正确的是（）A、软件测试的目的是证明程序是否正确B、软件测试的目的是使程序运行结果正确C、软件测试的目的是尽可能多地发现程序中的错误D、软件测试的目的是使程序符合结构化原则分析：软件测试的目的：尽可能多地发现软件产品中的错误和缺陷。软件测试一般不由开发人员测试自己的程序。测试发现错误后，可以立即进行调试并改正错误，经调试改错后还应进行测试。2、为了使模块尽可能独立，要求（）A、模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强B、模块的内

14、聚程度要尽量高，且各模块间的耦合程度要尽量弱C、模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱D、模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强分析：耦合：两个或两个以上模块之间关联的紧密程度。内聚：衡量一个模块内部各个元素彼此结合的紧密程度。耦合性和内聚性是模块独立的两个定性标准。耦合与内聚是相互关联的。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块的内聚性，有利于提高模块的独立性。3、下列描述中正确的是（）A、程序就是软件B、软件开发不受计算机系统的限制C、软件既是逻辑实体，又是物理实体D、软件是程序、数据与相关文档的集合分析：1、软件：是计算

15、机系统中与硬件相互依赖的另一部分，包括程序、数据和相关文档的完整集合；2、程序：是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。3、数据：是使程序能正常操纵信息的数据结构。4、文档：是与程序的开发、维护和使用有关的图文资料。4、诊断和改正程序中错误的工作通常称为 _。分析：程序调试：指在发生程序错误的情况下，确定出错的位置并纠正错误，其中关键是要确定出错的位置。程序调试主要在开发阶段。5、下列叙述中正确的是（）A、程序设计就是编制程序B、程序的测试必须由程序员自己去完成C、程序经调试改错后还应进行再测试D、程序经调试改错后不必进行再测试6、下列描述中正确的是（

16、）A、软件工程只是解决软件项目的管理问题B、软件工程主要解决软件产品的生产率问题C、软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D、软件工程只是解决软件开发中的技术问题分析：软件工程是用工程、科学和数学的原则与方法研制、维护计算机软件的有关技术及管理方法，由于软件开发中面临着纷繁复杂的问题，所以强调用工程化的原则去处理。7、在软件设计中，不属于过程设计工具的是（）A、PDL(过程设计语言)B、PAD图C、N-S图D、DFD图分析：DFD(数据流图)是常用的结构化分析工具；PDL、PAD、N-S是常见的过程设计工具，其中PAD、N-S属于图形工具，PDL属于语言工具。8、下列叙述中

17、正确的是（）A、软件交付使用后还需要再进行维护B、软件工具交付使用就不需要再进行维护C、软件交付使用后其生命周期就结束D、软件维护是指修复程序中被破坏的指令9、两个或两个以上模块之间关联的紧密程度称为A、耦合度 B、内聚度C、复杂度 D、数据传输特性10、下列叙述中正确的是（）A、软件测试应该由程序开发者来完成B、程序经调试后一般不需要再测试C、软件维护只包括对程序代码的维护D、以上三种说法都不对11、程序测试分为静态分析和动态测试。其中 _是指不执行程序,而只是对程序文本进行检查,通过阅读和讨论,分析和发现程序中的错误。分析：1、软件测试的方法：静态测试和动态测试。2、静态分析(静态测试)：

18、无须执行被测代码，而是借助专用的软件测试工具评审软件文档或程序，度量程序静态复杂度，检查软件是否符合编程标准，借以发现编写的程序的不足之处，减少错误出现的概率。3、动态测试：使被测代码在相对真实环境下运行，从多角度观察程序运行时能体现的功能、逻辑、行为、结构等的行为，以发现其中的错误现象。12、下列选项不符合良好程序设计风格的是_。A、源程序要文档化B、数据说明的次序要规范化C、避免滥用 goto 语句D、模块设主地要保证高耦合、高内聚13、从工程管理角度，软件设计一般分为两步完成，它们是_。A、概要设计与详细设计B、数据设计与接口设计C、软件结构设计与数据设计D、过程设计与数据设计分析：1、

19、从工程管理角度来看，软件设计一般分为两步：概要设计和详细设计。2、从技术观点来看，软件设计包括结构设计、数据设计、接口设计、过程设计四个步骤。14、下列选项中不属于软件生命周期开发阶段任务的是_。A、软件测试B、概要设计C、软件维护D、详细设计分析：1、通常把软件产品从提出、实现、使用、维护到停止使用退役的过程称为软件生命周期。2、软件生命周期分为3个时期共8个阶段：软件定义期：包括问题定义、可行性研究和需求分析三个阶段；软件开发期：包括概要设计、详细设计、实现和测试四个阶段；运行维护期：运行维护阶段。15、下列软件系统结构图 的宽度为_。分析：宽度：整体控制跨度，即各层中所含的模块数的最大值

20、。16、_的任务是诊断和改正程序中的错误。17、在结构化程序设计中，模块划分的原则是_。A）各模块应包括尽量多的功能。B）各模块的规模应尽量大。C）各模块之间的联系应尽量紧密。D）模块内具有高内聚度，模块间具有低耦合度。18、下列叙述中正确的是_.A）软件测试的主要目的是发现程序中的错误。B）软件测试的主要目的是确定程序中错误的位置。C）为了提高软件测试的效率，最好由程序员自己来完成软件测试的工作。D）软件测试是证明软件没有错误。19、软件测试分为白盒和黑盒测试。等价类划分法属于_测试。分析：1、软件动态测试分为：白盒测试和黑盒测试。2、白盒测试：在程序内部进行，主要用于完成软件内部操作的验证

21、。白盒测试的基本原则是：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一个分支至少执行一次；验证所有内部数据结构的有效性。主要白盒测试的方法有逻辑覆盖方法和基本基路径测试方法。3、黑盒测试：根据程序规格说明所规定的功能来设计测试用例，它不考虑程序的内部结构和处理过程。常用的黑盒测试方法有：等价类划分法、边界分析法、错误猜测法与因果图等等。20、软件生命周期可以分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属于_阶段。21、在结构化分析使用的数据流图(DFD)中，利用_对其中的图形元素进行确切解释。分析：数据字典(DD)：用来定义数据流图中的各个成分的具体含义。

22、数据字典的任务是对于数据流图中出现的所有被命名的图形元素在数据字典中作为一个词条加以定义，使得每一个图形元素的名字都有一个确切的定义。22、软件是指_.）程序）程序和文档）算法加数据结构）程序、数据与相关文档的完整集合23、软件调试的目的是_.A）发现错误B）改正错误C）改善软件的性能D）验证软件的正确性24、下列叙述中正确的是_.A）程序执行的效率与数据的存储结构密切相关。B）程序执行的效率只取决于程序的控制结构。C）程序执行的效率只取决与所处理的数据量。D）以上三种说法都不对。25、软件需求规格说明书应具有完整性、无歧义性、可验证性、可修改性等特性，其中最重要的是_.26、在两种基本测试方

23、法中,_测试的原则之一是保证所测模块中每一个独立路径至少要执行一次。27、在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块(桩模块)。其中_的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。四、数据库设计基础1、数据库（DB）、数据库系统（DBS）、数据库管理系统（DBMS）三者之间的关系是_.分析：数据库系统(DBS)：由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台五个部分构成的,DBMS是核心。2、数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为_.分析：物理

24、独立性:指数据的存储结构与逻辑结构之间的转换,即当数据的存储结构改变时,数据的逻辑结构不变,从而使得应用程序不必改变.逻辑独立性:指数据的总体逻辑结构与局部逻辑结构之间的转换,即当数据的总体逻辑结构改变时,可以保持局部逻辑结构不变,因而基于局部逻辑结构的应用程序也可以不必改变.3、用二维表格结构来表示实体及实体之间联系的数据模型称为_.4、用树型结构表示实体之间联系的模型是_.5、数据库设计的根本目标是要解决_问题。6、在关系数据库中，把数据表示成二维表，每一个二维表称为_.7、对于关系的描述，正确的是（）A、同一个关系中允许有完全相同的元组B、同一个关系中元组必须按关键字升序存放C、在一个关

25、系中必须将关键字作为该关系的第一个属性D、同一个关系中不能出现相同的属性名8、专门的关系运算不包括下列中的（）A、联接运算 B、选择运算C、投影运算 D、交运算分析：专门的关系运算：选择、投影和联接。传统的集合运算：并、交和差。9、从关系模式中指定若干个属性组成新的关系的运算称为（）A、联接 B、投影 C、选择 D、排序10、关系运算中的选择运算是（）A、从关系中找出满足给定条件的元组的操作B、从关系中选择若干个属性组成新的关系的 操作C、从关系中选择满足给定条件的属性的操作D、A和B都对11、设有部门和职员两个实体，每个职员只能属于一个部门，一个部门可以有多名职员，则部门与职员之间的联是_.

26、12、如果一个班只能有一个班长，而且一个班长不能同时担任其他班的班长，班级和班长两个实体之间的关系属于_.13、“商品”和“顾客”两个实体集之间的联系一般是_.14、在奥运会游泳比赛中，一个游泳运动员可以参加多项比赛，一个游泳比赛项目可以有 多个运动员参加，游泳运动员与游泳比赛项目两个实体之间的联系是_.15、数据库系统与文件系统的最主要区别是（）A、数据库系统复杂，而文件系统简单B、文件系统不能解决数据冗余和数据独立性问题，而数据库系统可以解决C、文件系统只能管理程序文件，而数据库系统能够管理各种类型的文件D、文件系统管理的数据量较少，而数据库系统可以管理庞大的数据量16、数据独立性是数据库

27、技术的重要特点之一。所谓数据独立性是指（）A、数据与程序独立存放B、不同的数据被存放在不同的文件中C、不同的数据只能被对应的应用程序所使用D、以上三种说法都不对分析：数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。17、在E-R图中,用来表示实体的图形是（）A)矩形 B)椭圆形 C)菱形 D)三角形分析：在E-R图中，实体用矩形表示；属性用椭圆形表示；联系用菱形表示；18、在数据库系统中，用户所见的数据模式为_。A）概念模式B）外模式C）内模式D）物理模式分析：外模式也称为子模式或用户模式，也就是用户所见到的数据模式；概念模式也称为模式；内模式也称为存储模

28、式，是数据在数据库内部的表示方式；内模式和模式只能有一个，而外模式可以有多个。19、数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和_。A）编码设计B）测试阶段C）运行阶段D）物理设计20、设有如下三个关系表下列操作中正确的是_。A）T=R SB）T=RSC）T=RSD）T=R/S21、在下列关系运算中，不改变关系表中的在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是属性个数但能减少元组个数的是_.A并并 B交交 C投影投影 D笛卡儿乘积笛卡儿乘积22、下列叙述中错误的是下列叙述中错误的是_.A在数据库系统中，数据的物理结构必须与在数据库系统中，数据的物理结构必须与逻辑结构

29、一致逻辑结构一致B数据库技术的根本目标是要解决数据的共数据库技术的根本目标是要解决数据的共享问题享问题C数据库设计是指在已有数据库管理系统的数据库设计是指在已有数据库管理系统的基础上建立数据库基础上建立数据库D数据库系统需要操作系统的支持数据库系统需要操作系统的支持23、下列叙述中正确的是（）A数据库系统是一个独立的系统，不需要操作系统的支持B数据库技术的根本目标是要解决数据的共享问题C数据库管理系统就是数据库系统D以上三种说法都不对24、下列叙述中正确的是（）A为了建立一个关系，首先要构造数据的逻辑关系B表示关系的二维表中各元组的每一个分量还可以分成若干数据项C一个关系的属性名表称为关系模式D一个关系可以包括多个二维表25、下列关于关系运算的叙述正确的是（）A、投影、选择、联接是从二维表的行的方向来进行运算B、并、交、差是从二维表的列的方向来进行运算C、投影、选择、联接是从二维表的列的方向来进行运算D、以上三种说法都不对